题解

1.0 ABC359 A-F + CF1593 A-F 部分题解

2026-03-10
0
0
29分钟

A题：

简单计数，直接写就行；

#include<bits/stdc++.h>

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int n; std::cin >> n;
    int ans = 0;

    while(n--){
        std::string s; std::cin >> s;

        if(s == "Takahashi") ans++;
    }

    std::cout << ans;
    return 0;
}

B题：

简单计数，判断好枚举边界后枚举所有间隔一个的一组人即可；

C题：

需要将横放的砖压缩为一格，压缩完成后任意移动都会收费，累加即可；

#include<bits/stdc++.h>

using i64 = long long;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    i64 sx, sy, tx, ty; std::cin >> sx >> sy >> tx >> ty;

    i64 sX = ((sx + sy) % 2 == 0) ? sx : sx - 1;
    i64 sY = sy;

    i64 tX = ((tx + ty) % 2 == 0) ? tx : tx - 1;
    i64 tY = ty;

    i64 dx = std::abs(sX - tX);
    i64 dy = std::abs(sY - tY);

    i64 ans = 0;
    if (dx <= dy) {
        ans = dy;
    } else {
        ans = dy + (dx - dy) / 2;
    }

    std::cout << ans << "\n";
    return 0;
}

D题：

有点难，我觉得比e难；

本题使用状压dp，遍历每一个状态的字符串判断好条件后计数；

记状态为 i，则转移方程为：

f_{new\_i} = \sum\limits_i f_i

判断？处所有的情况，代码如下：

#include<bits/stdc++.h>

using i64 = long long;

const int M = 998244353;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k; std::cin >> n >> k;

    std::string s; std::cin >> s;

    int Ki = k - 1;
    int lenK = (1 << Ki);

    std::function<bool(int, int)> check = [&](int mark, int k) ->bool {
        for(int i = 0;i <= k / 2;i++){
            int l = (mark >> k - 1 - i) & 1;
            int r = (mark >> i) & 1;
            
            if(l != r) return false;
        }

        return true;
    };

    std::vector<i64> f(lenK, 0);

    for(int mask = 0;mask < lenK;mask++){
        bool isM = 1;

        for(int i = 0;i < Ki;i++){
            if(s[i] == '?') continue;

            int bit = (mask >> (Ki - 1 - i)) & 1;
            int checkB = (s[i] == 'B'? 1 : 0);

            if(bit != checkB){
                isM = false;
                break;
            }
        }

        if(isM) f[mask] = 1;
    }

    for(int i = Ki;i < n;i++){
        std::vector<i64> Nf(lenK, 0);

        for(int mask = 0;mask < lenK; mask++){
            if(f[mask] == 0) continue;

            for(int c = 0;c <= 1;c++){
                if(s[i] != '?' && (s[i] == 'B'? 1 : 0) != c) continue;
            

                int M_mask = (mask << 1) | c;

                if(!check(M_mask, k)){
                    int nw_mask = (M_mask) & (lenK - 1);
                    Nf[nw_mask] = (Nf[nw_mask] + f[mask]) % M;
                }
            }
        }

        f = Nf;
    }

    i64 ans = 0;
    for(int mask = 0;mask < lenK;mask++){
        ans = (ans + f[mask]) % M;
    }

    std::cout << ans << '\n';
    return 0;
}

E题：

本题略难，考察单调栈；

先观察题干，发现当左边的挡板低于右边的时候，灌入的水会先填满高挡板左边的所有位置，因此思考需要对右边的较大值来计算需要灌满的数量；假设右边挡板的位置（可管辖的区间）为 r，高度为 h，左边高度大于等于右侧挡板的挡板位置为 l;则计算式为：

sum = (l - r) * h

发现需要两个挡板的位置，且要判断高度，所以可以用一个单调递减的单调栈来存储左侧较大的挡板高度和位置；当右侧的挡板低于栈顶的挡板时，入栈，加水没过新入栈挡板的高度即可；当右侧挡板高于栈顶，则弹出栈并计算总水量；

#include<bits/stdc++.h>

using i64 = long long;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int n; std::cin >> n;

    std::vector<i64> a;

    std::stack<std::pair<i64, i64>> sta;

    i64 now = 0;
    for(int i = 0;i < n;i++){
        int x; std::cin >> x;

        i64 len = 1;

        while(!sta.empty() && sta.top().first <= x){
            now -= sta.top().first * sta.top().second;//得减去没过较低挡板用的水量防止重复计算

            len += sta.top().second;
            sta.pop();
        }

        sta.push({x, len});
        now += x * len;
        a.push_back(now + 1);
    }

    for(const i64 & i : a) std::cout << i << '\n';
    return 0;
}

G题：

计算题，计算另两个人中较大的人与自己的差值即可；

#include<bits/stdc++.h>

using i64 = long long;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t; std::cin >> t;

    while(t--){
        int a, b, c; std::cin >> a >> b >> c;

        int ma = std::max(a, b);
        ma = std::max(ma, c);

        i64 A = std::max(0, std::max(b, c) + 1 - a);
        i64 B = std::max(0, std::max(a, c) + 1 - b);
        i64 C = std::max(0, std::max(a, b) + 1 - c);

        std::cout << A << ' ' << B << ' ' << C << '\n';
    } 

    return 0;
}

H题：

规律题；

发现能被25整除的数最后二位都是00，25，50，75，以此判断即可；

#include<bits/stdc++.h>

using i64 = long long;

void solve(){
    std::string n; std::cin >> n;

    i64 ans = 100000;
    for(int i = n.size() - 1;i >= 1;i--){
        char now = n[i];

        if(now == '0'){
            for(int j = i - 1;j >= 0;j--){
                if(n[j] == '0' || n[j] == '5'){
                    ans = std::min(ans, (i64)(n.size() - j - 2));

                    break;
                }
            }
        }

        if(now == '5'){
            for(int j = i - 1;j >= 0;j--){
                if(n[j] == '2' || n[j] == '7'){
                    ans = std::min(ans, (i64)(n.size() - j - 2));

                    break;
                }
            }
        }
    }

    std::cout << ans << '\n';
}

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t; std::cin >> t;

    while(t--) solve();

    return 0;
}

I题：

贪心；

优先让后面的老鼠先进洞即可，证明可以自己下来看看；

#include<bits/stdc++.h>

using i64 = long long;

void solve(){
    int n, k; std::cin >> n >> k;

    std::vector<int> a(k, 0);
    for(int& i : a) std::cin >> i;

    std::sort(a.begin(), a.end());

    i64 ans = 0, sum = 0;
    for(int i = k - 1;i >= 0;i--){
        int now = a[i];

        if(sum < a[i]){
            sum += n - a[i];
            ans++;
        }else break;
    }

    std::cout << ans << '\n';
}

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t; std::cin >> t;

    while(t--) solve();

    return 0;
}

J题：

略有难度，考察数论；

所有的 a_i来说减去任意 k使得各数相等，则记 mi = \min\limits_i(a_i)，有：

k =\gcd\limits_i (a_i- mi)

直接计算即可；

#include<bits/stdc++.h>

using i64 = long long;

void solve(){
    int n; std::cin >> n;

    std::vector<int> a(n, 0);

    i64 mx = -100000000, mi = 10000000;
    for(int & i : a){
        std::cin >> i;

        mx = std::max(mx, (i64)i);
        mi = std::min(mi, (i64)i);
    }

    if(mx == mi){
        std::cout << -1 << '\n';
        return ;
    }

    i64 ans = 0;
    for(int i = 0;i < n;i++){
        ans = std::gcd(ans, a[i] - mi);
    }

    std::cout << ans << '\n';
}

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t; std::cin >> t;

    while(t--) solve();

    return 0;
}

K题：

D1的复杂版本，略有难度；

在D1的结论下，要求满足要求的数变成了一半；没有常规思路，但发现数据量较小，考虑枚举每个 a_i的因数，判断后计数即可；

#include<bits/stdc++.h>

using i64 = long long;

void solve(){
    int n; std::cin >> n;

    std::vector<int> a(n, 0);

    std::map<int, int> cnt;
    int mcnt = 0;
    for(int & i : a){
        std::cin >> i;
        cnt[i]++;
        mcnt = std::max(mcnt, cnt[i]);
    }

    if(mcnt >= n / 2){
        std::cout << -1 << '\n';
        return ;
    }

    i64 mk = 0;
    std::function<bool(int)> check = [&](int k) ->bool {
        if(k <= mk) return 0;

        std::vector<int> p(n, 0);
        for(int i = 0;i < n;i++) p[i] = (a[i] % k + k) % k;

        std::sort(p.begin(), p.end());

        int len = 1, mlen = 0;
        for(int i = 1;i < n;i++){
            if(p[i] == p[i - 1]) len++;
            else{
                mlen = std::max(mlen, len);
                len = 1;
            }
        }
        mlen = std::max(len, mlen);

        if(mlen >= n / 2) return 1;
        return 0;
    };

    for(int i = 0;i < n;i++){
        for(int j = i + 1;j < n;j++){
            int d = std::abs(a[i] - a[j]);

            for(int x = 1;x * x <= d;x++){
                if(d % x == 0){
                    if(check(x)){
                        mk = std::max(mk, (i64)x);
                    }

                    if(check(d / x)){
                        mk = std::max(mk, (i64)d / x);
                    }
                }
            }
        }
    }

    std::cout << mk << '\n';
}

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t; std::cin >> t;

    while(t--) solve();

    return 0;
}

L题：

难度较低；

本题要求每次操作删去叶子节点，如果每次操作遍历树复杂度会超；考虑子叶节点度为1，则每次操作更新相邻点的度后记录下次操作因删除点即可；

#include<bits/stdc++.h>

using i64 = long long;

void solve(){
    int n, k; std::cin >> n >> k;

    std::vector<std::vector<int>> ma(n + 2);
    std::vector<int> dgree(n + 3, 0);
    for(int i = 0;i < n - 1;i++){
        int u, v; std::cin >> u >> v;

        ma[u].push_back(v);
        ma[v].push_back(u);

        dgree[u]++;
        dgree[v]++;
    }

    if(n == 1){
        if(k >= 1) std::cout << "0\n";
        else std::cout << "1\n";

        return ;
    }

    std::queue<int> End;

    for(int i = 1;i <= n + 2;i++){
        if(dgree[i] == 1) End.push(i);
    }

    int dn = n;
    while(!End.empty() && k > 0){
        int nn = End.size();
        dn -= nn;

        for(int i = 0;i < nn;i++){
            int now = End.front();
            End.pop();

            for(int last : ma[now]){
                dgree[last]--;

                if(dgree[last] == 1) End.push(last);
            }
        }

        k--;
    }

    std::cout << dn << '\n';
}

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t; std::cin >> t;

    while(t--) solve();

    return 0;//2
}

如果觉得文章对你有用，请随意赞赏

1.0 ABC359 A-F + CF1593 A-F 部分题解

A题：

B题：

C题：

D题：

E题：

G题：

H题：

I题：

J题：

K题：

L题：

评论