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

这篇具有很好参考价值的文章主要介绍了第五届传智杯-初赛【B组-题解】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

A题

题目背景

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

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

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

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

输入格式

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

输出格式

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

输入输出样例

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

 题解:

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

传智杯真题,传智杯,算法,c++,开发语言,传智杯

参考代码 

版本 1:

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int main(){
    int a, b;
    cin >> a >> b;
    cout << fixed << setprecision(0) << copysignl(a, b) + 1e-9 << endl;
    return 0;
}

版本 2:

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int main(){
    i64 a, b; cin >> a >> b;
    cout << (b < 0 ? -llabs(a) : llabs(a));
    return 0;
}

版本3:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin >> a >> b;
    if (b>0 && a==INT_MIN)
        cout << 2147483648ll << endl;
    else
    {
        a=abs(a);
        if (b<0)
            a*=-1;
        cout << a << endl;
    }
    return 0;
}

版本4:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong(), b = scanner.nextLong();
        System.out.println((Math.abs(a) * (b > 0 ? 1 : -1)));
    }
}

B题:

题目背景

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

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

传智杯真题,传智杯,算法,c++,开发语言,传智杯传智杯真题,传智杯,算法,c++,开发语言,传智杯

初始时齿轮的状态如上。

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

把第一个齿轮拨动一个单位长度,变为如上图所示。传智杯真题,传智杯,算法,c++,开发语言,传智杯 

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 题解:

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

传智杯真题,传智杯,算法,c++,开发语言,传智杯

参考代码 

 版本 1:

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 2e5 + 3;
int A[MAXN], B[MAXN];
int main(){
    int n = qread(), m = qread(), l = max(n, m);
    dn(n, 1, i) A[i] = qread();
    dn(m, 1, i) B[i] = qread();
    up(1, l, i) A[i] += B[i], A[i + 1] += A[i] / (i + 1), A[i] %= i + 1;
    if(A[l + 1]) ++ l;
    dn(l, 1, i) printf("%d%c", A[i], " \n"[i == 1]);
    return 0;
}

版本2:

#include <bits/stdc++.h>
using namespace std;
int a[200050],b[200050];
int main()
{
    auto read=([&]{
        int x;cin >> x;
        return x;
    });
    int n=read(),m=read();
    int len=max(n,m)+1;
    generate_n(a+1,n,read);
    generate_n(b+1,m,read);
    reverse(a+1,a+n+1);
    reverse(b+1,b+m+1);
    for (int i=1;i<=len;i++)
    {
        a[i]+=b[i];
        a[i+1]+=(a[i]/(i+1));
        a[i]%=(i+1);
    }
    while (a[len]==0 && len>1)
        len--;
    reverse(a+1,a+len+1);
    for (int i=1;i<=len;i++)
        cout << a[i] << " ";
    return 0;
}

版本3:

import java.util.Scanner;

public class Main {

    public static int[] a = new int[200005];
    public static int[] b = new int[200005];
    public static int[] c = new int[200005];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int maxLength = Math.max(n, m);
        for (int i = (maxLength - n) + 1; i <= maxLength; ++i)
            a[i] = scanner.nextInt();
        for (int i = (maxLength - m) + 1; i <= maxLength; ++i)
            b[i] = scanner.nextInt();
        for (int i = maxLength, cnt = 2; i > 0; --i, ++cnt) {
            c[i] += a[i] + b[i];
            if (c[i] >= cnt) {
                c[i] -= cnt;
                c[i - 1] += 1;
            }
        }
        if (c[0] > 0) {
            System.out.printf("%d ", c[0]);
        }
        for (int i = 1; i <= maxLength; ++i) {
            System.out.printf("%d ", c[i]);
        }
        System.out.println();
    }
}

D题:

题目背景

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

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

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 题解:

传智杯真题,传智杯,算法,c++,开发语言,传智杯

参考代码 

版本1:

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 1e5 + 3;
int A[MAXN], ans = INF;
int main(){
    int n = qread(), m = qread();
    up(1, n, i) A[i] = qread();
    sort(A + 1, A + 1 + n);
    int j = 1;
    up(1, min(n, m + 1), i){
        j = max(i, j);
        while((i - 1) + (n - j) + min(i - 1, n - j) > m) ++ j;
        ans = min(ans, A[j] - A[i]);
    }
    printf("%d\n", ans);
    return 0;
}

版本2:

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    public static int[] a = new int[100005];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        for (int i = 1; i <= n; ++i)
            a[i] = scanner.nextInt();
        Arrays.sort(a, 1, n + 1);
        int j = 1, ans = Integer.MAX_VALUE;
        for (int i = 1; i <= Math.min(n, m + 1); ++i) {
            j = Math.max(j, i);
            while((i - 1) + (n - j) + Math.min(i - 1, n - j) > m) 
                ++j;
            ans = Math.min(ans, a[j] - a[i]);
        }
        System.out.println(ans);
    }
}

E题:

题目背景

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

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

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 题解

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 参考代码

版本1:

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
i64 qread(){
    i64 w=1,c,ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
i64 val(i64 p){return 2 * p * p - p;}
int main(){
    up(1, qread(), TTT){
        i64 k = qread(), p = 0;
        dn(30, 0, i){
            if(val(p | 1 << i) < k) p |= 1 << i;
        }
        int i = p + 1, w = i - 1;
        i64 l = val(p) + 1, ll = l + w;
        i64 r = val(i),     rr = r - w;
        if(l  <= k && k <  ll) printf("%lld\n", k - l     ); else 
        if(ll <= k && k <= rr) printf("%lld\n", w - k + ll); else 
            printf("%lld\n", k - r);
    }
    return 0;
}

版本2:

#include <iostream>
using namespace std;
int main()
{
    int q;
    cin >> q;
    while (q--)
    {
        long long k,l=1,r=2e9,ans=0;
        cin >> k;
        while (l<=r)
        {
            long long mid=(l+r)/2;
            if ((long long)mid*mid*2-mid>=k)
            {
                r=mid-1;
                ans=mid;
            }
            else
                l=mid+1;
        }
        ans--;
        long long len=ans*ans*2-ans;
        k-=len+1;
        if (k<=ans)
            cout << k << endl;
        else if (k<=3*ans)
            cout << 2*ans-k << endl;
        else
            cout << -4*ans+k << endl;

    }
    return 0;
}

版本3:

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static long val(long p) {
        return p * 2 * p - p;
    }

    public static class Scanner {
        public BufferedReader in;
        public StringTokenizer tok;
        public String next() { hasNext(); return tok.nextToken(); }
        public String nextLine() { try { return in.readLine(); } catch (Exception e) { return null; } }
        public long nextLong() { return Long.parseLong(next()); }
        public int nextInt() { return Integer.parseInt(next()); }
        public PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        public boolean hasNext() {
            while (tok == null || !tok.hasMoreTokens()) try { tok = new StringTokenizer(in.readLine()); } catch (Exception e) { return false; }
            return true;
        }
        public Scanner(InputStream inputStream) { in = new BufferedReader(new InputStreamReader(inputStream)); }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
        while (q-- > 0) {
            long k = scanner.nextLong(), p = 0;
            for (int i = 30; i >= 0; --i) {
                if (val(p | 1 << i) < k)
                    p |= 1 << i;
            }
            long i = p + 1, w = i - 1;
            long l = val(p) + 1, ll = l + w;
            long r = val(i), rr = r - w;
            if (l <= k && k < ll)
                System.out.println(k - l);
            else if (ll <= k && k <= rr)
                System.out.println(w - k + ll);
            else
                System.out.println(k - r);
        }
    }
}

G题

题目背景

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

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

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

题目描述

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯 传智杯真题,传智杯,算法,c++,开发语言,传智杯

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯 传智杯真题,传智杯,算法,c++,开发语言,传智杯

 题解:

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 参考代码:

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int n, m, r, c, q;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 2e3 + 3;
const int MAXM =  50 + 3;
const int MOD  = 998244353;
int A[MAXN][MAXN], S[MAXN][MAXN]; bool B[MAXN][MAXN];
int calc(int a1, int b1, int a2, int b2){
    int ret = S[a2][b2];
    if(a1 > r) ret = (ret - S[a1 - r][b2] + MOD) % MOD;
    if(b1 > c) ret = (ret - S[a2][b1 - c] + MOD) % MOD;
    if(a1 > r && b1 > c) ret = (ret + S[a1 - r][b1 - c]) % MOD;
    return ret;
}
int main(){
    n = qread(), m = qread();
    up(1, n, i) up(1, m, j) A[i][j] = qread();
    r = qread(), c = qread();
    up(1, r, i) up(1, c, j) B[i][j] = qread();
    up(1, n, i) up(1, m, j){
        S[i][j] = A[i][j];
        if(i > r) S[i][j] = (S[i][j] + S[i - r][j]) % MOD;
        if(j > c) S[i][j] = (S[i][j] + S[i][j - c]) % MOD;
        if(i > r && j > c)
            S[i][j] = (S[i][j] - S[i - r][j - c] + MOD) % MOD;
    }
    q = qread();
    up(1, q, i){
        int _x1 = qread(), _y1 = qread();
        int _x2 = qread(), _y2 = qread();
        int ans = 0;
        up(1, min(r, _x2 - _x1 + 1), a)
            up(1, min(c, _y2 - _y1 + 1), b) if(B[a][b] == 0){
                int a1 = _x1 + a - 1, a2 = a1 + (_x2 - a1) / r * r;
                int b1 = _y1 + b - 1, b2 = b1 + (_y2 - b1) / c * c;
                ans = (ans + calc(a1, b1, a2, b2)) % MOD;
        }
        printf("%d\n", ans);
    }

    return 0;
}

 H题

题目背景

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

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

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯传智杯真题,传智杯,算法,c++,开发语言,传智杯 

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

 传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

传智杯真题,传智杯,算法,c++,开发语言,传智杯

 题解:

搜索题。

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

(感性理解一下)

传智杯真题,传智杯,算法,c++,开发语言,传智杯传智杯真题,传智杯,算法,c++,开发语言,传智杯

 参考代码

代码1:

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
struct Pos2{
    int x, y;
    Pos2(int _x = 0, int _y = 0):x(_x), y(_y){}
    const bool operator < (const Pos2 &t) const {
        if(x != t.x) return x < t.x;
        return y < t.y;
    }
    const bool operator > (const Pos2 &t) const {
        if(x != t.x) return x > t.x;
        return y > t.y;
    }
    const bool operator ==(const Pos2 &t) const {
        return x == t.x && y == t.y;
    }
};
struct Pos3{
    int x, y, z;
    Pos3(int _x = 0, int _y = 0, int _z = 0):
        x(_x), y(_y), z(_z){}
    const bool operator < (const Pos3 &t) const {
        if(x != t.x) return x < t.x;
        if(y != t.y) return y < t.y;
        return z < t.z;
    }
    const bool operator > (const Pos3 &t) const {
        if(x != t.x) return x > t.x;
        if(y != t.y) return y > t.y;
        return z > t.z;
    }
    const bool operator ==(const Pos3 &t) const {
        return x == t.x && y == t.y && z == t.z;
    }
};
const int BASE = 13331;
struct Hash{
    unsigned operator ()(const Pos2 t) const{
        return t.x * BASE + t.y;
    }
    unsigned operator ()(const Pos3 t) const{
        return (t.x * BASE + t.y) * BASE + t.z;
    }
};
unordered_map<Pos3, bool, Hash> B;   // 存 (x, y, z) 是否有方块
unordered_map<Pos2, bool, Hash> V;   // 存 (x, y, h + 1) 有没有使用过
unordered_map<Pos2, int , Hash> D;   // 存 (x, y) 的最短路程
unordered_map<Pos2, bool, Hash> W;   // 存 (x, y, h + 1) 位置有没有水方块
unordered_map<Pos2, int , Hash> K;   // 存 (x, y, h + 1) 位置水方块的强度
const int DIR[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int MAXN = 2e5 + 3;
int n, p, X[MAXN], Y[MAXN], Z[MAXN], I[MAXN];
int qread(){
    int w = 1, c, ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
bool cmp(int a, int b){ return Z[a] > Z[b]; }
int _x0, _y0;
int main(){
    n = qread(), p = qread(), _x0 = qread(), _y0 = qread();
    W[Pos2(_x0, _y0)] = true;
    up(1, n, i){
        X[i] = qread(), Y[i] = qread(), Z[i] = qread(), I[i] = i;
        B[Pos3(X[i], Y[i], Z[i])] = true;
    }
    sort(I + 1, I + 1 + n, cmp);
    up(1, n, i){
        int h = Z[I[i]], j;
        queue <Pos2> P, Q;
        for(j = i;j <= n && Z[I[j]] == h;++ j){
            int o = I[j], x = X[o], y = Y[o];
            Pos2 u(x, y);
            if(W.count(u))
                P.push(u), K[u] = p, W.erase(u);
            up(0, 3, k){
                int nx = x + DIR[k][0];
                int ny = y + DIR[k][1];
                Pos2 v(nx, ny);
                if(!V.count(v) && !B.count(Pos3(nx, ny, h))
                    && !B.count(Pos3(nx, ny, h + 1)))
                    V[v] = true, D[v] = 0, Q.push(v);
            }
        }
        while(!Q.empty()){
            Pos2 u = Q.front(); Q.pop(); int x = u.x, y = u.y;
            up(0, 3, k){
                int nx = x + DIR[k][0];
                int ny = y + DIR[k][1];
                Pos2 v(nx, ny);
                if(!D.count(v) && B.count(Pos3(nx, ny, h))
                    && !B.count(Pos3(nx, ny, h + 1)))
                    D[v] = D[u] + 1, Q.push(v);
            }
        }
        while(!P.empty()){
            Pos2 u = P.front(); P.pop(); int x = u.x, y = u.y;
            int d = D[u], s = K[u];
            if(!B.count(Pos3{x, y, h})){
                W[u] = true; continue;
            }
            if(s == 1) continue;
            up(0, 3, k){
                int nx = x + DIR[k][0];
                int ny = y + DIR[k][1];
                Pos2 v(nx, ny);
                if( D[v] == d - 1)
                if(!K.count(v) && !B.count(Pos3(nx, ny, h + 1)))
                    K[v] = s - 1, P.push(v);
            }
        }
        i = j - 1, D.clear(), K.clear(), V.clear();
    }
    printf("%u\n", W.size());
    return 0;
}

代码2:文章来源地址https://www.toymoban.com/news/detail-754535.html

import java.io.*;
import java.util.*;

public class Main {
    public static class Vec2d {
        public int x, y;

        public Vec2d(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(new int[] {x, y});
        }

        public boolean equals(Vec2d vec2d) {
            return this.x == vec2d.x && this.y == vec2d.y;
        }
        @Override
        public boolean equals(Object vec2d) {
            if (!(vec2d instanceof Vec2d))
                return false;
            return this.x == ((Vec2d) vec2d).x && this.y == ((Vec2d) vec2d).y;
        }
    }

    public static class Vec3d {
        public int x, y, z;

        public Vec3d(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
        @Override
        public int hashCode() {
            return Arrays.hashCode(new int[] {x, y, z});
        }
        public boolean equals(Vec3d vec2d) {
            return this.x == vec2d.x && this.y == vec2d.y && this.z == vec2d.z;
        }
        @Override
        public boolean equals(Object vec2d) {
            if (!(vec2d instanceof Vec3d))
                return false;
            return this.x == ((Vec3d) vec2d).x && this.y == ((Vec3d) vec2d).y && this.z == ((Vec3d) vec2d).z;
        }
    }

    public static class Scanner {
        public BufferedReader in;
        public StringTokenizer tok;

        public String next() {
            hasNext();
            return tok.nextToken();
        }

        public String nextLine() {
            try {
                return in.readLine();
            } catch (Exception e) {
                return null;
            }
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        public boolean hasNext() {
            while (tok == null || !tok.hasMoreTokens()) try {
                tok = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                return false;
            }
            return true;
        }

        public Scanner(InputStream inputStream) {
            in = new BufferedReader(new InputStreamReader(inputStream));
        }
    }

    public static Map<Vec3d, Boolean> isblock = new HashMap<>();
    public static Map<Vec2d, Boolean> isused = new HashMap<>();
    public static Map<Vec2d, Integer> dist = new HashMap<>();
    public static Map<Vec2d, Boolean> iswater = new HashMap<>();
    public static Map<Vec2d, Integer> strwater = new HashMap<>();

    public static final int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

    public static int n, k, _x0, _y0;
    public static int[] x = new int[100050], y = new int[100050], z = new int[100050];
    public static List<Integer> var_id = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        _x0 = scanner.nextInt();
        _y0 = scanner.nextInt();
        iswater.put(new Vec2d(_x0, _y0), true);
        for (int i = 1; i <= n; i++) {
            x[i] = scanner.nextInt();
            y[i] = scanner.nextInt();
            z[i] = scanner.nextInt();
            isblock.put(new Vec3d(x[i], y[i], z[i]), true);
            var_id.add(i);
        }
        var_id.sort((x, y) -> z[y] - z[x]);
        List<Integer> id = new ArrayList<>();
        id.add(0);
        for (int i = 0; i < n; ++i)
            id.add(var_id.get(i));
        for (int i = 0; i < 5; ++i)
            id.add(0);
        for (int i = 1; i <= n; i++) {
            int height = z[id.get(i)];
            Queue<Vec2d> p = new LinkedList<>(), q = new LinkedList<>();
            // spread at the same height
            for (int nid = id.get(i); i <= n && z[nid] == height; ) {
                int nx = x[nid], ny = y[nid];
                Vec2d u = new Vec2d(nx, ny);
                if (iswater.getOrDefault(u, false)) {
                    iswater.put(u, false);
                    p.add(u);
                    strwater.put(u, k);
                }
                for (int j = 0; j < 4; j++) {
                    int nx1 = nx + dx[j], ny1 = ny + dy[j];
                    Vec2d v = new Vec2d(nx1, ny1);
                    Vec3d v1 = new Vec3d(nx1, ny1, height);
                    Vec3d v2 = new Vec3d(nx1, ny1, height + 1);
                    if (!isused.getOrDefault(v, false) && !isblock.getOrDefault(v1, false) && !isblock.getOrDefault(v2, false)) {
                        isused.put(v, true);
                        dist.put(v, 0);
                        q.add(v);
                    }
                }
                i++;
                nid = id.get(i);
            }
            i--;
            // spread water in Q
            while (!q.isEmpty()) {
                Vec2d var1 = q.element();
                q.remove();
                int x = var1.x, y = var1.y;
                Vec2d u = new Vec2d(x, y);
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j], ny = y + dy[j];
                    Vec2d v = new Vec2d(nx, ny);
                    Vec3d v1 = new Vec3d(nx, ny, height);
                    Vec3d v2 = new Vec3d(nx, ny, height + 1);
                    if (dist.getOrDefault(v, 0) == 0 && isblock.getOrDefault(v1, false) && !isblock.getOrDefault(v2, false)) {
                        dist.put(v, dist.get(u) + 1);
                        q.add(v);
                    }
                }
            }
            //spread water in P
            while (!p.isEmpty()) {
                Vec2d var1 = p.element();
                p.remove();
                int x = var1.x, y = var1.y;
                Vec2d u = new Vec2d(x, y);
                Vec3d u1 = new Vec3d(x, y, height);
                int d = dist.getOrDefault(u, 0), s = strwater.getOrDefault(u, 0);
                if (!isblock.getOrDefault(u1, false)) {
                    iswater.put(u, true);
                    continue;
                }
                if (s == 1)
                    continue;
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j], ny = y + dy[j];
                    Vec2d v = new Vec2d(nx, ny);
                    Vec3d v1 = new Vec3d(nx, ny, height + 1);
                    if (dist.getOrDefault(v, 0) == d - 1 && strwater.getOrDefault(v, 0) == 0 && !isblock.getOrDefault(v1, false)) {
                        strwater.put(v, s - 1);
                        p.add(v);
                    }
                }
            }
            isused.clear();
            dist.clear();
            strwater.clear();
        }
        int cnt = 0;
        for (boolean i : iswater.values()) {
            cnt += i ? 1 : 0;
        }
        System.out.println(cnt);
    }
}

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

到了这里,关于第五届传智杯-初赛【B组-题解】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第五届湖北省大学生程序设计竞赛(HBCPC 2023)vp赛后补题

    思路: 数位dp,如果我们暴力的计算的状态的话,显然就是记录每个数字出现几次。但是显然这样难以发挥数位dp的记忆化功效,因为只有出现次数相同,你是什么数字,实际是无所谓的。所以我们尝试记录每个出现次数有多少个数字 尝试打表发现,结果只有1477种 所以,对

    2024年02月07日
    浏览(44)
  • 通付盾受邀出席区块链技术和应用峰会暨第五届中国区块链开发大赛成果发布会及颁奖仪式

    由江苏省工业和信息化厅、中国电子技术标准化研究院联合举办的“标准引领、创新驱动”第五届中国区块链开发大赛成果发布会在苏州隆重召开。 通付盾受邀参与此次盛会, 【基于区块链的“数信云”安全应用与服务平台】获得“江苏省区块链产业发展试点示范项目”荣

    2024年02月16日
    浏览(54)
  • 洛谷 P8836 [传智杯 #3 决赛] 打牌

    洛谷题目链接 记录上一个出牌的人的出牌数量,和出牌种类,用桶来记录每个人每种牌的数量,枚举每一种种类,如果当前牌的数量大于上一次的出牌数量,则判断其种类,如果种类小于上一次出牌的种类,则需要比上次多出一张牌,否则就跟上一次出牌数量一样多,如果当

    2024年01月16日
    浏览(19)
  • 2020 CSP - J初赛 题解

    快要CSP了,最近疯狂刷题中… 终于 抽出时间 乘爸妈不在 写了一篇题解 如需做题,请到以下网站自行练习。 本博客只提供讲解。 洛谷有题 初赛真题 - 信奥赛题库 题号 1~5: A A D C C 6~10: B A A A A 11~15: A D C A A 16~20: 对 错 对 错 A 21~25: D 错 错 对 D 26~30: B D 错 对 错 31~35:

    2024年02月11日
    浏览(40)
  • 第十五届蓝桥杯 模拟赛第二期java组题解

    一、 问题描述 小蓝要在屏幕上放置一行文字,每个字的宽度相同。 小蓝发现,如果每个字的宽为 36 像素,一行正好放下 30 个字,字符之间和前后都没 有任何空隙。 请问,如果每个字宽为 10 像素,字符之间不包含空隙,一行可以放下多少个字? 答案提交 这是一道结果填空

    2024年02月03日
    浏览(48)
  • 【Java】2021 RoboCom 机器人开发者大赛-高职组(初赛)题解

    机器人小白要来 RoboCom 参赛了,在赛场中遇到人要打个招呼。请你帮它设置好打招呼的这句话:“ni ye lai can jia RoboCom a?”。 输入格式: 本题没有输入。 输出格式: 在一行中输出 ni ye lai can jia RoboCom a? 。 输入样例: 输出样例: Solution: 人脸识别是基于人的脸部特征信息进

    2024年02月12日
    浏览(36)
  • 2022 CSP-J1 CSP-S1 初赛 第1轮 真题讲评 真题解析

    CSP-J/S 2022初赛讲评 CSP-J/S 2022初赛讲评_哔哩哔哩_bilibili CSP-J2022 初赛第一轮解析 选择题 CSP-J2022 初赛第一轮解析 选择题_哔哩哔哩_bilibili 2022csp j初赛解析-单项选择题 2022csp j初赛解析-单项选择题_哔哩哔哩_bilibili CSP-J2022 初赛第一轮 解析 阅读程序1 CSP-J2022 初赛第一轮 解析 阅读

    2024年02月12日
    浏览(38)
  • 【蓝桥杯Web】第十五届蓝桥杯(Web 应用开发)模拟赛 2 期 | 全部题解

    感觉蓝桥杯的模拟赛一次比一次难了😑 制作不易,代码都是纯手敲,觉得有帮助的伙伴们记得点个赞评论一下,谢谢大家支持😍 话不多说直接上答案 目录 1、想不相等 2、三行情书 3、电影院在线订票 4、老虎机 5、星际通讯 6、蓝桥杯排位赛 7、拼出一个未来 8、超能英雄联

    2024年02月05日
    浏览(49)
  • 【蓝桥杯选拔赛真题59】python小写字母 第十五届青少年组蓝桥杯python 选拔赛比赛真题解析

    目录 python小写字母 一、题目要求 1、编程实现 2、输入输出

    2024年01月24日
    浏览(42)
  • 全国大学生信息安全竞赛初赛writeup(历年CISCN真题与解析)

    收录了大佬们参加全国大学生信息安全竞赛初赛的writeup和真题环境,方便学习,排名不分先后,谨参考完整度和CSDN站内优先原则。 在此,对大佬们的分享表示由衷的敬意和诚挚的感谢! 第十二、十三届全国大学生信息安全竞赛——创新实践能力赛原题 如果遇到打不开的链

    2024年02月06日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包