• 第五届传智杯-初赛【B组-题解】

    A题

    题目背景

    在宇宙射线的轰击下，莲子电脑里的一些她自己预定义的函数被损坏了。

    对于一名理科生来说，各种软件在学习和研究中是非常重要的。为了尽快恢复她电脑上的软件的正常使用，她需要尽快地重新编写这么一些函数。

    你只需输出fun(a,b) 的值。

    输入格式

    • 共一行两个整数 a,b。

    输出格式

    • 共一行一个整数 fun(a,b) 的值。

    输入输出样例

     

     题解：

    签到题：首先用if 语句判断 b 的符号，然后加在 a 的绝对值上即可。

    参考代码 

    版本 1：

    1. #include
    2. #define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
    3. #define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
    4. using namespace std;
    5. typedef long long i64;
    6. const int INF = 2147483647;
    7. int main(){
    8.     int a, b;
    9.     cin >> a >> b;
    10.     cout << fixed << setprecision(0) << copysignl(a, b) + 1e-9 << endl;
    11.     return 0;
    12. }

    版本 2：

    1. #include
    2. #define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
    3. #define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
    4. using namespace std;
    5. typedef long long i64;
    6. const int INF = 2147483647;
    7. int main(){
    8.     i64 a, b; cin >> a >> b;
    9.     cout << (b < 0 ? -llabs(a) : llabs(a));
    10.     return 0;
    11. }

    版本3：

    1. #include 
    2. using namespace std;
    3. int main()
    4. {
    5.     int a,b;
    6.     cin >> a >> b;
    7.     if (b>0 && a==INT_MIN)
    8.         cout << 2147483648ll << endl;
    9.     else
    10.     {
    11.         a=abs(a);
    12.         if (b<0)
    13.             a*=-1;
    14.         cout << a << endl;
    15.     }
    16.     return 0;
    17. }

    版本4：

    1. import java.util.Scanner;
    2.  
    3. public class Main {
    4.     public static void main(String[] args) {
    5.         Scanner scanner = new Scanner(System.in);
    6.         long a = scanner.nextLong(), b = scanner.nextLong();
    7.         System.out.println((Math.abs(a) * (b > 0 ? 1 : -1)));
    8.     }
    9. }

    B题：

    题目背景

    【题目背景和题目描述的两个题面是完全等价的，您可以选择阅读其中一部分。】

    专攻超统一物理学的莲子，对机械结构的运动颇有了解。如下图所示，是一个三进制加法计算器的（超简化）示意图。

    初始时齿轮的状态如上。

     

    把第一个齿轮拨动一个单位长度，变为如上图所示。 

     

     题解：

    模拟题。按照题目要求输入整数 a,b，模拟这个奇怪的进位规则即可。

    参考代码 

     版本 1：

    1. #include
    2. #define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
    3. #define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
    4. using namespace std;
    5. typedef long long i64;
    6. const int INF = 2147483647;
    7. int qread(){
    8.     int w=1,c,ret;
    9.     while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    10.     while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    11.     return ret * w;
    12. }
    13. const int MAXN = 2e5 + 3;
    14. int A[MAXN], B[MAXN];
    15. int main(){
    16.     int n = qread(), m = qread(), l = max(n, m);
    17.     dn(n, 1, i) A[i] = qread();
    18.     dn(m, 1, i) B[i] = qread();
    19.     up(1, l, i) A[i] += B[i], A[i + 1] += A[i] / (i + 1), A[i] %= i + 1;
    20.     if(A[l + 1]) ++ l;
    21.     dn(l, 1, i) printf("%d%c", A[i], " \n"[i == 1]);
    22.     return 0;
    23. }

    版本2：

    1. #include 
    2. using namespace std;
    3. int a[200050],b[200050];
    4. int main()
    5. {
    6.     auto read=([&]{
    7.         int x;cin >> x;
    8.         return x;
    9.     });
    10.     int n=read(),m=read();
    11.     int len=max(n,m)+1;
    12.     generate_n(a+1,n,read);
    13.     generate_n(b+1,m,read);
    14.     reverse(a+1,a+n+1);
    15.     reverse(b+1,b+m+1);
    16.     for (int i=1;i<=len;i++)
    17.     {
    18.         a[i]+=b[i];
    19.         a[i+1]+=(a[i]/(i+1));
    20.         a[i]%=(i+1);
    21.     }
    22.     while (a[len]==0 && len>1)
    23.         len--;
    24.     reverse(a+1,a+len+1);
    25.     for (int i=1;i<=len;i++)
    26.         cout << a[i] << " ";
    27.     return 0;
    28. }

    版本3：

    1. import java.util.Scanner;
    2.  
    3. public class Main {
    4.  
    5.     public static int[] a = new int[200005];
    6.     public static int[] b = new int[200005];
    7.     public static int[] c = new int[200005];
    8.  
    9.     public static void main(String[] args) {
    10.         Scanner scanner = new Scanner(System.in);
    11.         int n = scanner.nextInt(), m = scanner.nextInt();
    12.         int maxLength = Math.max(n, m);
    13.         for (int i = (maxLength - n) + 1; i <= maxLength; ++i)
    14.             a[i] = scanner.nextInt();
    15.         for (int i = (maxLength - m) + 1; i <= maxLength; ++i)
    16.             b[i] = scanner.nextInt();
    17.         for (int i = maxLength, cnt = 2; i > 0; --i, ++cnt) {
    18.             c[i] += a[i] + b[i];
    19.             if (c[i] >= cnt) {
    20.                 c[i] -= cnt;
    21.                 c[i - 1] += 1;
    22.             }
    23.         }
    24.         if (c[0] > 0) {
    25.             System.out.printf("%d ", c[0]);
    26.         }
    27.         for (int i = 1; i <= maxLength; ++i) {
    28.             System.out.printf("%d ", c[i]);
    29.         }
    30.         System.out.println();
    31.     }
    32. }

    D题：

    题目背景

    莲子正在研究分子的运动。

    每个分子都有一个速度，约定正方向为正，负方向为负。分子的数量极多，速度又并不一致，看上去杂乱无章。于是莲子希望调整部分分子的速度，使得最终分子们看上去整齐。

     题解：

    参考代码 

    版本1：

    1. #include
    2. #define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
    3. #define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
    4. using namespace std;
    5. typedef long long i64;
    6. const int INF = 2147483647;
    7. int qread(){
    8.     int w=1,c,ret;
    9.     while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    10.     while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    11.     return ret * w;
    12. }
    13. const int MAXN = 1e5 + 3;
    14. int A[MAXN], ans = INF;
    15. int main(){
    16.     int n = qread(), m = qread();
    17.     up(1, n, i) A[i] = qread();
    18.     sort(A + 1, A + 1 + n);
    19.     int j = 1;
    20.     up(1, min(n, m + 1), i){
    21.         j = max(i, j);
    22.         while((i - 1) + (n - j) + min(i - 1, n - j) > m) ++ j;
    23.         ans = min(ans, A[j] - A[i]);
    24.     }
    25.     printf("%d\n", ans);
    26.     return 0;
    27. }

    版本2：

    1. import java.util.Scanner;
    2. import java.util.Arrays;
    3.  
    4. public class Main {
    5.  
    6.     public static int[] a = new int[100005];
    7.  
    8.     public static void main(String[] args) {
    9.         Scanner scanner = new Scanner(System.in);
    10.         int n = scanner.nextInt(), m = scanner.nextInt();
    11.         for (int i = 1; i <= n; ++i)
    12.             a[i] = scanner.nextInt();
    13.         Arrays.sort(a, 1, n + 1);
    14.         int j = 1, ans = Integer.MAX_VALUE;
    15.         for (int i = 1; i <= Math.min(n, m + 1); ++i) {
    16.             j = Math.max(j, i);
    17.             while((i - 1) + (n - j) + Math.min(i - 1, n - j) > m) 
    18.                 ++j;
    19.             ans = Math.min(ans, a[j] - a[i]);
    20.         }
    21.         System.out.println(ans);
    22.     }
    23. }

    E题：

    题目背景

    梅莉这个学期选修了经济学。但是主修心理学的她实在不擅长经济领域的分析，为此她时常抱怨自己学不会，想退课。

    但是如果现在退掉的话这学期的学分就不够啦，因此她根据“梦中”的经历，“胡诌”了一个简单到不现实的市场模型，并依据这个模型编起了 essay。为了方便地编出图表，她需要写一个程序来查询每个时刻的市场贸易差。

     题解

     参考代码

    版本1：

    1. #include
    2. #define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
    3. #define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
    4. using namespace std;
    5. typedef long long i64;
    6. const int INF = 2147483647;
    7. i64 qread(){
    8.     i64 w=1,c,ret;
    9.     while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    10.     while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    11.     return ret * w;
    12. }
    13. i64 val(i64 p){return 2 * p * p - p;}
    14. int main(){
    15.     up(1, qread(), TTT){
    16.         i64 k = qread(), p = 0;
    17.         dn(30, 0, i){
    18.             if(val(p | 1 << i) < k) p |= 1 << i;
    19.         }
    20.         int i = p + 1, w = i - 1;
    21.         i64 l = val(p) + 1, ll = l + w;
    22.         i64 r = val(i),     rr = r - w;
    23.         if(l  <= k && k <  ll) printf("%lld\n", k - l     ); else 
    24.         if(ll <= k && k <= rr) printf("%lld\n", w - k + ll); else 
    25.             printf("%lld\n", k - r);
    26.     }
    27.     return 0;
    28. }

    版本2：

    1. #include 
    2. using namespace std;
    3. int main()
    4. {
    5.     int q;
    6.     cin >> q;
    7.     while (q--)
    8.     {
    9.         long long k,l=1,r=2e9,ans=0;
    10.         cin >> k;
    11.         while (l<=r)
    12.         {
    13.             long long mid=(l+r)/2;
    14.             if ((long long)mid*mid*2-mid>=k)
    15.             {
    16.                 r=mid-1;
    17.                 ans=mid;
    18.             }
    19.             else
    20.                 l=mid+1;
    21.         }
    22.         ans--;
    23.         long long len=ans*ans*2-ans;
    24.         k-=len+1;
    25.         if (k<=ans)
    26.             cout << k << endl;
    27.         else if (k<=3*ans)
    28.             cout << 2*ans-k << endl;
    29.         else
    30.             cout << -4*ans+k << endl;
    31.  
    32.     }
    33.     return 0;
    34. }

    版本3：

    1. import java.io.*;
    2. import java.util.StringTokenizer;
    3.  
    4. public class Main {
    5.  
    6.     public static long val(long p) {
    7.         return p * 2 * p - p;
    8.     }
    9.  
    10.     public static class Scanner {
    11.         public BufferedReader in;
    12.         public StringTokenizer tok;
    13.         public String next() { hasNext(); return tok.nextToken(); }
    14.         public String nextLine() { try { return in.readLine(); } catch (Exception e) { return null; } }
    15.         public long nextLong() { return Long.parseLong(next()); }
    16.         public int nextInt() { return Integer.parseInt(next()); }
    17.         public PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    18.         public boolean hasNext() {
    19.             while (tok == null || !tok.hasMoreTokens()) try { tok = new StringTokenizer(in.readLine()); } catch (Exception e) { return false; }
    20.             return true;
    21.         }
    22.         public Scanner(InputStream inputStream) { in = new BufferedReader(new InputStreamReader(inputStream)); }
    23.     }
    24.  
    25.     public static void main(String[] args) {
    26.         Scanner scanner = new Scanner(System.in);
    27.         int q = scanner.nextInt();
    28.         while (q-- > 0) {
    29.             long k = scanner.nextLong(), p = 0;
    30.             for (int i = 30; i >= 0; --i) {
    31.                 if (val(p | 1 << i) < k)
    32.                     p |= 1 << i;
    33.             }
    34.             long i = p + 1, w = i - 1;
    35.             long l = val(p) + 1, ll = l + w;
    36.             long r = val(i), rr = r - w;
    37.             if (l <= k && k < ll)
    38.                 System.out.println(k - l);
    39.             else if (ll <= k && k <= rr)
    40.                 System.out.println(w - k + ll);
    41.             else
    42.                 System.out.println(k - r);
    43.         }
    44.     }
    45. }

    G题

    题目背景

    梅莉买到了一张特殊的带有花纹的纸。整张纸的图案可以视为，由一个较小的图案，沿着横向与纵向无限循环而成。同时，这个基本图案部分透明，部分不透明。

    于是，如果将这张纸覆盖在书本上，那么一些字可以被看见，另一些字看不见。

    莲子突发奇想：假使她制作一张很大很大的数表，将花纹纸覆盖在上面，那么就会有很多数字被遮挡。那些没有被遮挡的数字的和是多少呢？

    题目描述

     

     

     

     

     题解：

     参考代码：

    1. #include
    2. #define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
    3. #define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
    4. using namespace std;
    5. typedef long long i64;
    6. const int INF = 2147483647;
    7. int n, m, r, c, q;
    8. int qread(){
    9.     int w=1,c,ret;
    10.     while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    11.     while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    12.     return ret * w;
    13. }
    14. const int MAXN = 2e3 + 3;
    15. const int MAXM =  50 + 3;
    16. const int MOD  = 998244353;
    17. int A[MAXN][MAXN], S[MAXN][MAXN]; bool B[MAXN][MAXN];
    18. int calc(int a1, int b1, int a2, int b2){
    19.     int ret = S[a2][b2];
    20.     if(a1 > r) ret = (ret - S[a1 - r][b2] + MOD) % MOD;
    21.     if(b1 > c) ret = (ret - S[a2][b1 - c] + MOD) % MOD;
    22.     if(a1 > r && b1 > c) ret = (ret + S[a1 - r][b1 - c]) % MOD;
    23.     return ret;
    24. }
    25. int main(){
    26.     n = qread(), m = qread();
    27.     up(1, n, i) up(1, m, j) A[i][j] = qread();
    28.     r = qread(), c = qread();
    29.     up(1, r, i) up(1, c, j) B[i][j] = qread();
    30.     up(1, n, i) up(1, m, j){
    31.         S[i][j] = A[i][j];
    32.         if(i > r) S[i][j] = (S[i][j] + S[i - r][j]) % MOD;
    33.         if(j > c) S[i][j] = (S[i][j] + S[i][j - c]) % MOD;
    34.         if(i > r && j > c)
    35.             S[i][j] = (S[i][j] - S[i - r][j - c] + MOD) % MOD;
    36.     }
    37.     q = qread();
    38.     up(1, q, i){
    39.         int _x1 = qread(), _y1 = qread();
    40.         int _x2 = qread(), _y2 = qread();
    41.         int ans = 0;
    42.         up(1, min(r, _x2 - _x1 + 1), a)
    43.             up(1, min(c, _y2 - _y1 + 1), b) if(B[a][b] == 0){
    44.                 int a1 = _x1 + a - 1, a2 = a1 + (_x2 - a1) / r * r;
    45.                 int b1 = _y1 + b - 1, b2 = b1 + (_y2 - b1) / c * c;
    46.                 ans = (ans + calc(a1, b1, a2, b2)) % MOD;
    47.         }
    48.         printf("%d\n", ans);
    49.     }
    50.  
    51.     return 0;
    52. }

     H题

    题目背景

    莲子设计了一个三维立体空间软件。这个软件可以模拟真实的物理引擎，包括实体方块和水流方块。然而，同时计算大量水流会对软件造成不小的负荷。

    于是，莲子希望找到这样一种算法，快速计算这些水流模拟后的结果。

     

     

     

     

     

     

     题解：

    搜索题。

    注意一个重要性质：水流之间可视为互不干扰的。虽然确实有强度更大的水流可以覆盖强度更小的水流这样的设定，但容易发现强度更大的水流，可以流到的空间，包含了强度更小的水流。

    （感性理解一下）

     参考代码

    代码1：

    1. #include
    2. #define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
    3. #define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
    4. using namespace std;
    5. typedef long long i64;
    6. const int INF =2147483647;
    7. struct Pos2{
    8.     int x, y;
    9.     Pos2(int _x = 0, int _y = 0):x(_x), y(_y){}
    10.     const bool operator < (const Pos2 &t) const {
    11.         if(x != t.x) return x < t.x;
    12.         return y < t.y;
    13.     }
    14.     const bool operator > (const Pos2 &t) const {
    15.         if(x != t.x) return x > t.x;
    16.         return y > t.y;
    17.     }
    18.     const bool operator ==(const Pos2 &t) const {
    19.         return x == t.x && y == t.y;
    20.     }
    21. };
    22. struct Pos3{
    23.     int x, y, z;
    24.     Pos3(int _x = 0, int _y = 0, int _z = 0):
    25.         x(_x), y(_y), z(_z){}
    26.     const bool operator < (const Pos3 &t) const {
    27.         if(x != t.x) return x < t.x;
    28.         if(y != t.y) return y < t.y;
    29.         return z < t.z;
    30.     }
    31.     const bool operator > (const Pos3 &t) const {
    32.         if(x != t.x) return x > t.x;
    33.         if(y != t.y) return y > t.y;
    34.         return z > t.z;
    35.     }
    36.     const bool operator ==(const Pos3 &t) const {
    37.         return x == t.x && y == t.y && z == t.z;
    38.     }
    39. };
    40. const int BASE = 13331;
    41. struct Hash{
    42.     unsigned operator ()(const Pos2 t) const{
    43.         return t.x * BASE + t.y;
    44.     }
    45.     unsigned operator ()(const Pos3 t) const{
    46.         return (t.x * BASE + t.y) * BASE + t.z;
    47.     }
    48. };
    49. unordered_mapbool, Hash> B;   // 存 (x, y, z) 是否有方块
    50. unordered_mapbool, Hash> V;   // 存 (x, y, h + 1) 有没有使用过
    51. unordered_mapint , Hash> D;   // 存 (x, y) 的最短路程
    52. unordered_mapbool, Hash> W;   // 存 (x, y, h + 1) 位置有没有水方块
    53. unordered_mapint , Hash> K;   // 存 (x, y, h + 1) 位置水方块的强度
    54. const int DIR[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    55. const int MAXN = 2e5 + 3;
    56. int n, p, X[MAXN], Y[MAXN], Z[MAXN], I[MAXN];
    57. int qread(){
    58.     int w = 1, c, ret;
    59.     while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    60.     while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    61.     return ret * w;
    62. }
    63. bool cmp(int a, int b){ return Z[a] > Z[b]; }
    64. int _x0, _y0;
    65. int main(){
    66.     n = qread(), p = qread(), _x0 = qread(), _y0 = qread();
    67.     W[Pos2(_x0, _y0)] = true;
    68.     up(1, n, i){
    69.         X[i] = qread(), Y[i] = qread(), Z[i] = qread(), I[i] = i;
    70.         B[Pos3(X[i], Y[i], Z[i])] = true;
    71.     }
    72.     sort(I + 1, I + 1 + n, cmp);
    73.     up(1, n, i){
    74.         int h = Z[I[i]], j;
    75.         queue  P, Q;
    76.         for(j = i;j <= n && Z[I[j]] == h;++ j){
    77.             int o = I[j], x = X[o], y = Y[o];
    78.             Pos2 u(x, y);
    79.             if(W.count(u))
    80.                 P.push(u), K[u] = p, W.erase(u);
    81.             up(0, 3, k){
    82.                 int nx = x + DIR[k][0];
    83.                 int ny = y + DIR[k][1];
    84.                 Pos2 v(nx, ny);
    85.                 if(!V.count(v) && !B.count(Pos3(nx, ny, h))
    86.                     && !B.count(Pos3(nx, ny, h + 1)))
    87.                     V[v] = true, D[v] = 0, Q.push(v);
    88.             }
    89.         }
    90.         while(!Q.empty()){
    91.             Pos2 u = Q.front(); Q.pop(); int x = u.x, y = u.y;
    92.             up(0, 3, k){
    93.                 int nx = x + DIR[k][0];
    94.                 int ny = y + DIR[k][1];
    95.                 Pos2 v(nx, ny);
    96.                 if(!D.count(v) && B.count(Pos3(nx, ny, h))
    97.                     && !B.count(Pos3(nx, ny, h + 1)))
    98.                     D[v] = D[u] + 1, Q.push(v);
    99.             }
    100.         }
    101.         while(!P.empty()){
    102.             Pos2 u = P.front(); P.pop(); int x = u.x, y = u.y;
    103.             int d = D[u], s = K[u];
    104.             if(!B.count(Pos3{x, y, h})){
    105.                 W[u] = true; continue;
    106.             }
    107.             if(s == 1) continue;
    108.             up(0, 3, k){
    109.                 int nx = x + DIR[k][0];
    110.                 int ny = y + DIR[k][1];
    111.                 Pos2 v(nx, ny);
    112.                 if( D[v] == d - 1)
    113.                 if(!K.count(v) && !B.count(Pos3(nx, ny, h + 1)))
    114.                     K[v] = s - 1, P.push(v);
    115.             }
    116.         }
    117.         i = j - 1, D.clear(), K.clear(), V.clear();
    118.     }
    119.     printf("%u\n", W.size());
    120.     return 0;
    121. }

    代码2：

    1. import java.io.*;
    2. import java.util.*;
    3.  
    4. public class Main {
    5.     public static class Vec2d {
    6.         public int x, y;
    7.  
    8.         public Vec2d(int x, int y) {
    9.             this.x = x;
    10.             this.y = y;
    11.         }
    12.  
    13.         @Override
    14.         public int hashCode() {
    15.             return Arrays.hashCode(new int[] {x, y});
    16.         }
    17.  
    18.         public boolean equals(Vec2d vec2d) {
    19.             return this.x == vec2d.x && this.y == vec2d.y;
    20.         }
    21.         @Override
    22.         public boolean equals(Object vec2d) {
    23.             if (!(vec2d instanceof Vec2d))
    24.                 return false;
    25.             return this.x == ((Vec2d) vec2d).x && this.y == ((Vec2d) vec2d).y;
    26.         }
    27.     }
    28.  
    29.     public static class Vec3d {
    30.         public int x, y, z;
    31.  
    32.         public Vec3d(int x, int y, int z) {
    33.             this.x = x;
    34.             this.y = y;
    35.             this.z = z;
    36.         }
    37.         @Override
    38.         public int hashCode() {
    39.             return Arrays.hashCode(new int[] {x, y, z});
    40.         }
    41.         public boolean equals(Vec3d vec2d) {
    42.             return this.x == vec2d.x && this.y == vec2d.y && this.z == vec2d.z;
    43.         }
    44.         @Override
    45.         public boolean equals(Object vec2d) {
    46.             if (!(vec2d instanceof Vec3d))
    47.                 return false;
    48.             return this.x == ((Vec3d) vec2d).x && this.y == ((Vec3d) vec2d).y && this.z == ((Vec3d) vec2d).z;
    49.         }
    50.     }
    51.  
    52.     public static class Scanner {
    53.         public BufferedReader in;
    54.         public StringTokenizer tok;
    55.  
    56.         public String next() {
    57.             hasNext();
    58.             return tok.nextToken();
    59.         }
    60.  
    61.         public String nextLine() {
    62.             try {
    63.                 return in.readLine();
    64.             } catch (Exception e) {
    65.                 return null;
    66.             }
    67.         }
    68.  
    69.         public long nextLong() {
    70.             return Long.parseLong(next());
    71.         }
    72.  
    73.         public int nextInt() {
    74.             return Integer.parseInt(next());
    75.         }
    76.  
    77.         public PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    78.  
    79.         public boolean hasNext() {
    80.             while (tok == null || !tok.hasMoreTokens()) try {
    81.                 tok = new StringTokenizer(in.readLine());
    82.             } catch (Exception e) {
    83.                 return false;
    84.             }
    85.             return true;
    86.         }
    87.  
    88.         public Scanner(InputStream inputStream) {
    89.             in = new BufferedReader(new InputStreamReader(inputStream));
    90.         }
    91.     }
    92.  
    93.     public static Map isblock = new HashMap<>();
    94.     public static Map isused = new HashMap<>();
    95.     public static Map dist = new HashMap<>();
    96.     public static Map iswater = new HashMap<>();
    97.     public static Map strwater = new HashMap<>();
    98.  
    99.     public static final int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    100.  
    101.     public static int n, k, _x0, _y0;
    102.     public static int[] x = new int[100050], y = new int[100050], z = new int[100050];
    103.     public static List var_id = new ArrayList<>();
    104.  
    105.     public static void main(String[] args) {
    106.         Scanner scanner = new Scanner(System.in);
    107.         n = scanner.nextInt();
    108.         k = scanner.nextInt();
    109.         _x0 = scanner.nextInt();
    110.         _y0 = scanner.nextInt();
    111.         iswater.put(new Vec2d(_x0, _y0), true);
    112.         for (int i = 1; i <= n; i++) {
    113.             x[i] = scanner.nextInt();
    114.             y[i] = scanner.nextInt();
    115.             z[i] = scanner.nextInt();
    116.             isblock.put(new Vec3d(x[i], y[i], z[i]), true);
    117.             var_id.add(i);
    118.         }
    119.         var_id.sort((x, y) -> z[y] - z[x]);
    120.         List id = new ArrayList<>();
    121.         id.add(0);
    122.         for (int i = 0; i < n; ++i)
    123.             id.add(var_id.get(i));
    124.         for (int i = 0; i < 5; ++i)
    125.             id.add(0);
    126.         for (int i = 1; i <= n; i++) {
    127.             int height = z[id.get(i)];
    128.             Queue p = new LinkedList<>(), q = new LinkedList<>();
    129.             // spread at the same height
    130.             for (int nid = id.get(i); i <= n && z[nid] == height; ) {
    131.                 int nx = x[nid], ny = y[nid];
    132.                 Vec2d u = new Vec2d(nx, ny);
    133.                 if (iswater.getOrDefault(u, false)) {
    134.                     iswater.put(u, false);
    135.                     p.add(u);
    136.                     strwater.put(u, k);
    137.                 }
    138.                 for (int j = 0; j < 4; j++) {
    139.                     int nx1 = nx + dx[j], ny1 = ny + dy[j];
    140.                     Vec2d v = new Vec2d(nx1, ny1);
    141.                     Vec3d v1 = new Vec3d(nx1, ny1, height);
    142.                     Vec3d v2 = new Vec3d(nx1, ny1, height + 1);
    143.                     if (!isused.getOrDefault(v, false) && !isblock.getOrDefault(v1, false) && !isblock.getOrDefault(v2, false)) {
    144.                         isused.put(v, true);
    145.                         dist.put(v, 0);
    146.                         q.add(v);
    147.                     }
    148.                 }
    149.                 i++;
    150.                 nid = id.get(i);
    151.             }
    152.             i--;
    153.             // spread water in Q
    154.             while (!q.isEmpty()) {
    155.                 Vec2d var1 = q.element();
    156.                 q.remove();
    157.                 int x = var1.x, y = var1.y;
    158.                 Vec2d u = new Vec2d(x, y);
    159.                 for (int j = 0; j < 4; j++) {
    160.                     int nx = x + dx[j], ny = y + dy[j];
    161.                     Vec2d v = new Vec2d(nx, ny);
    162.                     Vec3d v1 = new Vec3d(nx, ny, height);
    163.                     Vec3d v2 = new Vec3d(nx, ny, height + 1);
    164.                     if (dist.getOrDefault(v, 0) == 0 && isblock.getOrDefault(v1, false) && !isblock.getOrDefault(v2, false)) {
    165.                         dist.put(v, dist.get(u) + 1);
    166.                         q.add(v);
    167.                     }
    168.                 }
    169.             }
    170.             //spread water in P
    171.             while (!p.isEmpty()) {
    172.                 Vec2d var1 = p.element();
    173.                 p.remove();
    174.                 int x = var1.x, y = var1.y;
    175.                 Vec2d u = new Vec2d(x, y);
    176.                 Vec3d u1 = new Vec3d(x, y, height);
    177.                 int d = dist.getOrDefault(u, 0), s = strwater.getOrDefault(u, 0);
    178.                 if (!isblock.getOrDefault(u1, false)) {
    179.                     iswater.put(u, true);
    180.                     continue;
    181.                 }
    182.                 if (s == 1)
    183.                     continue;
    184.                 for (int j = 0; j < 4; j++) {
    185.                     int nx = x + dx[j], ny = y + dy[j];
    186.                     Vec2d v = new Vec2d(nx, ny);
    187.                     Vec3d v1 = new Vec3d(nx, ny, height + 1);
    188.                     if (dist.getOrDefault(v, 0) == d - 1 && strwater.getOrDefault(v, 0) == 0 && !isblock.getOrDefault(v1, false)) {
    189.                         strwater.put(v, s - 1);
    190.                         p.add(v);
    191.                     }
    192.                 }
    193.             }
    194.             isused.clear();
    195.             dist.clear();
    196.             strwater.clear();
    197.         }
    198.         int cnt = 0;
    199.         for (boolean i : iswater.values()) {
    200.             cnt += i ? 1 : 0;
    201.         }
    202.         System.out.println(cnt);
    203.     }
    204. }

    💖 喜欢我的文章，记得点赞👍+评论💬+收藏⭐️+关注😙の，你的反馈就是我不断更新的动力！

  • 相关阅读:
    面了个腾讯拿38K跳槽出来的，见识到了真正的测试天花板
    vue+axios+el-progress(elementUI组件)实现下载进度条实时监听（小白简洁版）
    C++day1
    SpringMVC（4）——数据封装与异常处理
    Java-Lambda表达式基本理解及使用
    欧盟反垄断法的改变：对跨境电商的冲击和机遇
    day-44 代码随想录算法训练营（19） 动态规划 part 06
    人工智能领域的机器学习方法给我们的带来了哪些好处？
    ueditor百度富文本编辑器粘贴后html丢失class和style样式
    微服务框架 SpringCloud微服务架构 20 RestClient 操作索引库 20.4 创建索引库
  • 原文地址：https://blog.csdn.net/weixin_51563198/article/details/128058132