题解

2.1 ABC231 A-F + CF1986 A-F 部分题解

2026-03-10
0
2
33分钟

A题：

没有难度，小数除法直接写即可；

#include<bits/stdc++.h>

using i64 = long long;

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

    std::cout << (long double)x / 100.0;
    
    return 0;
}

B题

注意到输入为字符串，用哈希表存储票数同时维护最大值即可；

#include<bits/stdc++.h>

using i64 = long long;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n; std::cin >> n;
    std::map<std::string, int> cnt;

    int maxC = 0;
    while(n--){
        std::string s; std::cin >> s;
        cnt[s]++;

        maxC = std::max(maxC, cnt[s]);
    }

    for(const auto& i : cnt){
        if(i.second == maxC){
            std::cout << i.first;
            return 0;
        }
    }

    
    return 0;
}

C题：

发现要求的是大于x的人数，想到lower_bound可以直接找到大于x的元素的指针，转为索引计算即可；

#include<bits/stdc++.h>

using i64 = long long;

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

    std::vector<i64> higth(n, 0);
    for(i64& i : higth) std::cin >> i;

    std::sort(higth.begin(), higth.end());//注意排序，lower只能用于有序的容器
    while(q--){
        i64 x; std::cin >> x;

        int it = std::lower_bound(higth.begin(), higth.end(), x) - higth.begin();
        std::cout << n - it << '\n';
    }

    
    return 0;
}

D题：

略有难度，考察部分有dsu；

考虑到对于编号 a,\ b;两者相邻等效于连边，故可以转化问题为：对于一点，与其他点连边，最后形成一条链；发现只要一点的度 deg > 2 时，就会违反题目条件；
考虑可能出现首尾相连的情况(即出现环)，所以要判断是否成环，考虑用并查集(dsu)；

#include<bits/stdc++.h>

using i64 = long long;

struct dsu{
    std::vector<i64> parten;

    dsu(int n) : parten(n + 2, 0){
        std::iota(parten.begin(), parten.end(), 0);
    }

    i64 find(i64 x){
        if(parten[x] == x) return x;

        return parten[x] = find(parten[x]);
    }

    bool united(int x, int y){
        int rootx = find(x);
        int rooty = find(y);

        if(rootx != rooty){
            parten[rootx] = rooty;
            return 1;
        }

        return 0;
    }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m; std::cin >> n >> m;
    std::map<int, int> deg;
    dsu ma(n);

    int ans = 1;
    for(int i = 0;i < m;i++){
        int x, y; std::cin >> x >> y;

        deg[x]++;
        deg[y]++;

        if(deg[x] > 2 || deg[y] > 2) ans = 0;

        if(!ma.united(x, y)) ans = 0;
    }
    
    std::cout << (ans? "Yes" : "No");
    return 0;
}

E题：

略有难度，考察记忆化搜索；

对于一个价值 X 的商品要买下有两种操作：

用有的硬币凑够 X 买下；
用大于 X 的硬币买下后，由店员找钱；

两种操作在任意 X 都会成立，所以考虑线性规划或者记忆化搜索；

题目中提出所有的A_i < A_{i + 1} 后者是前者的倍数，所以正向递推中会有过多的状态不会被取到，为降低复杂度使用记忆化搜索；

用哈希表来记录状态

std::map<std::pair<int, i64>, i64> check

从 X 向买下这件物品开始搜索，代码如下；

#include<bits/stdc++.h>

using i64 = long long;

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

    std::vector<i64> corn(n, 0);
    for(i64& i : corn) std::cin >> i;

    std::map<std::pair<int, i64>, i64> check;

    std::function<i64(int, i64)> solve = [&](int i, i64 X) ->i64 {
        if(i == 0){
            return X;
        }

        if(check.count({i, X})){
            return check[{i, X}];
        }

        i64 cnt = X / corn[i];
        i64 re = X % corn[i];//统计面值为corn[i]的硬币要多少个

        if(re == 0){
            return check[{i, X}] = cnt;
        }

        i64 res1 = cnt + solve(i - 1, re);//情况1
        i64 res2 = cnt + solve(i - 1, corn[i] - re) + 1;//情况2，要找的钱变成新的物品价值

        return check[{i, X}] = std::min(res1, res2);
    };

    std::cout<< solve(n - 1, x);

    return 0;
}

F题：

比较难，考察树状数组和离散化；

观察题目，题目要求选两个礼物 i,\ j,要求 A_i \le A_j 且 B_i \ge B_j ;所以考虑偏序，将嫉妒值 a先排序后在查找有多少满足 B_i \ge B_j的礼物数量后统计即可；

观察到 a,\ b \le 1e9；所以用数组直接统计会爆空间，我们只关心两个 b 的相对大小，所以考虑离散化；

    std::sort(b.begin(), b.end());
    b.erase(std::unique(b.begin(), b.end()), b.end());//先排序后去重

    std::function<int(int)> getIndex = [&](int val){
        return std::lower_bound(b.begin(), b.end(), val) - b.begin() + 1;
    };//查询输入的b在所有的b中第几大；

同时要考虑，对于 a相同的礼物， b应当降序排序；这样在用树状数组统计 b较小的礼物时可以统计上 a相同 b较大的礼物(因为要 b较大的礼物，所以算后缀)；

    std::sort(p.begin(), p.end(), [](std::pair<int, int> x, std::pair<int, int> y){
        if(x.first != y.first) return x.first < y.first;
        return y.second < x.second;
    });

用树状数组统计，每次要进行更新；最后的代码如下：

#include<bits/stdc++.h>

using i64  = long long;

int tree[2000005];//树状数组

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

    int n; std::cin >> n;

    std::vector<std::pair<int, int>> p(n, {0, 0});
    std::vector<int> b;
    for(auto& i : p) std::cin >> i.first;
    for(auto& i : p){
        std::cin >> i.second;
        b.push_back(i.second);
    }

    std::sort(b.begin(), b.end());
    b.erase(std::unique(b.begin(), b.end()), b.end());

    std::function<int(int)> getIndex = [&](int val){
        return std::lower_bound(b.begin(), b.end(), val) - b.begin() + 1;
    };
    
    std::function<void(int, int)> update = [&](int x, int val){
        for(;x <= n;x += (x & -x)) tree[x] += val;
    };//更新树状数组

    std::function<i64(int x)> query = [&](int x) ->i64 {
        i64 sum = 0;
        for(;x > 0;x -= (x & -x)) sum += tree[x];
        return sum;
    };//查询小于val的b个数
    
    std::sort(p.begin(), p.end(), [](std::pair<int, int> x, std::pair<int, int> y){
        if(x.first != y.first) return x.first < y.first;
        return y.second < x.second;
    });

    i64 ans = 0;
    int mInd = b.size();

    for(int i = 0;i < n;){
        int j = i;

        while(j < n && p[i] == p[j]){
            j++;
        }//相同的礼物一次统计

        int cnt = j - i;
        int index = getIndex(p[i].second);

        update(index, cnt);

        i64 indj = query(n) - query(index - 1);
        
        i = j;
        ans += indj * cnt;
    }

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

G题：

简单题目，对于三个输入找出最大最小值求差即可；

#include<bits/stdc++.h>

using i64 = long long;

void solve(){
    int x, y, z; std::cin >> x >> y >> z;

    int mm = std::max(std::max(x, y), z);
    int mi = std::min(std::min(x, y), z);

    std::cout << mm - mi << '\n';
}

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

    while(t--) solve();

    return 0;
}

H题：

略有难度；

观察题面，发现 N,\ \ M的大小较小，可能会想到找出每一个满足条件的点，模拟 -1 过程，这样做会爆时间；

再次观察，发现每个合法的点操作后的最大大小为四周点的最大值，所以只要找出最大值后操作一次即可；又题目中操作的点始终有偏向左上角的趋势，所以直接遍历一遍即可；

#include<bits/stdc++.h>

using i64 = long long;

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

    std::vector<std::vector<i64>> ma(n, std::vector<i64> (m, 0));
    for(auto& i : ma){
        for(auto& j : i) std::cin >> j;
    }

    int dx[4] = {0, 0, 1, -1},
        dy[4] = {1, -1, 0, 0};

    bool isFinial = 0;

    auto check = [&](){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                i64 now = ma[i][j], mm = 0;

                bool isThis = 1;
                for(int k = 0;k < 4;k++){
                    int px = i + dx[k],
                        py = j + dy[k];

                    if(px < 0 || px >= n || py < 0 || py >= m) continue;

                    mm = std::max(mm, ma[px][py]);
                    if(ma[px][py] >= now) isThis = 0;
                }

                if(isThis){
                    ma[i][j] = mm;
                }

                if(i == n - 1 && j == m - 1) isFinial = 1;
            }
        }
    };

    check();

    for(const auto& i : ma){
        for(const auto& j : i) std::cout << j << ' ';

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

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

    while(t--) solve();

    return 0;
}

I题：

略有难度；

题目要求得出最小字典序的答案，贪心考虑将交换操作中字典序较小的放在前面的位置；

考虑到会有重复的交换下标，假设有 K个，前 K-1 个大字典序的填满，故不在考虑；

用 set 存储交换下标，同时对字符串 C中的字符排序；由小到大一次取出即可；

#include<bits/stdc++.h>

using i64 = long long;

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

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

    std::set<int> index;
    for(int i = 0;i < m;i++){
        int x; std::cin >> x;
        x--;

        index.insert(x);
    }

    std::string c; std::cin >> c;
    std::sort(c.begin(), c.end());

    int x = 0;
    for(const auto& i : index){
        s[i] = c[x];
        x++;
    }

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

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

    while(t--) solve();

    return 0;
}

J题：

分析透后没有多少难度；

题干要求对一数字组成的字符串中插入 n-2的符号( +或 *)，考虑已下性质：

对于正整数 a,\ \ \ b\ \ (a,\ b \ \ne 1) 一定存在 a+b\le a*b;
任意数×1不增加， ×0 等于 0；

那么对于所有的数，不等于1， 0的加起来，遇到1用乘法，遇到0答案就是零；

注意的是在n大的情况下会有一个两位数，所以遍历这个两位数求最小答案即可；

#include<bits/stdc++.h>

using i64 = long long;

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

    if(n == 2) std::cout << (s[0] - '0') * 10 + s[1] - '0' << '\n';
    else if(n == 1) std::cout << s[0] - '0' << '\n';
    else{
        i64 mians = 1000000000;

        for(int i = 0;i < n - 1;i++){
            int two_bit = (s[i] - '0') * 10 + s[i + 1] - '0';

            std::vector<int> num;
            for(int j = 0;j < n;j++){
                if(i == j){
                    num.push_back(two_bit);
                    j++;
                }else num.push_back(s[j] - '0');
            }

            for(const int& i : num){
                if(i == 0){
                    mians = 0;
                    break;
                }
            }

            i64 sum = 0;
            for(const int& i : num){
                if(i > 1){
                    sum += i;
                }
            }

            if(sum == 0){
                sum = 1;
            }

            mians = std::min(mians, sum);
        }

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

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

    while(t--) solve();

    return 0;
}

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

2.1 ABC231 A-F + CF1986 A-F 部分题解

A题：

B题

C题：

D题：

E题：

F题：

G题：

H题：

I题：

J题：

评论