2025寒假专场12

· · 题解

增一减一

每次操作都会加一减一, 所有n个数的总和不会变, 而且n个数最后各自的差值不会大于1, 设最后的n个数是由x和x+1组成的; 那我们就可以直接让sum/n, 得出的数就是x; 接下来就要看会有多少个x+1, 那就是sum \mod n, 需要让sum对n取余就可以得到最终序列中x+1的个数; 最后我们就可以把n个数从大到小排序, 前sum \mod n个数需要变化为x+1, 剩下的数需要变化为x; 最后把变化的次数除2就是最终答案;

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+10;
int n, m, idx;
int f[N];
signed main(){
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        cin >> f[i];
        sum += f[i];
    }
    sort(f + 1, f + 1 + n, greater<>());
    int x = sum / n;
    int y = sum % n;
    for(int i = 1; i <= n; i++){
        if(i <= y) idx += abs(f[i] - (x + 1));
        else idx += abs(f[i] - x);
    }
    cout << idx / 2;
    return 0;
}

绘制颜色

开一个数组c, c[i]表示下一个颜色为i的字符要替换为c[i]; 我们把每个颜色中最靠前的字符的下标存一下, 最后更新他们即可; 这样就可以线性地更新完所有字符;

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10;
int n, m;
int f[N], la[N];
char c[N];
int main(){
    cin >> n >> m;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) cin >> f[i];
    for (int i = 0; i < n; i++) {
        if (!c[f[i]]) { // 记录第一轮 
            c[f[i]] = s[i];
            la[f[i]] = i;
        }
        else {
            char x = c[f[i]];
            c[f[i]] = s[i];
            s[i] = x;
        }
    }
    for (int i = 1; i <= m; i++) // 更新最前面的位置 
        s[la[i]] = c[i];

    cout << s;
    return 0;
}

字母操作

本题的处理难点在于由于数据范围较大, 我们不能每次输入都接着操作, 只能是读取所有操作之后最后进行处理; 因为每次更改大小写都是全部更改, 所以我们只看最后一个更改大小写的操作的位置last即可; 当t=1时, 我们可以记录这次操作是第几个操作, 当t=1的操作顺序在last之后就不需要改变大小写了;

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int sp;
int nu[N];
signed main(){
    string s;
    cin >> n >> s;
    s = ' ' + s;
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        char c;
        cin >> a >> b >> c;
        if (a == 1) {
            s[b] = c;
            nu[b] = i;
        }
        else if (a == 2) {
            sp = 1;
            idx = i;
        }
        else {
            sp = 2;
            idx = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (nu[i] > idx) continue;
        else {
            if (sp == 1 && isupper(s[i])) s[i] += 32;
            if (sp == 2 && islower(s[i])) s[i] -= 32;
        }
    }
    for (int i = 1; i <= n; i++) cout << s[i];
    return 0;
}

魔幻的饼干

考虑模拟; 那么我们要遍历所有字母, 并且操作完之后还要重复上述过程, 大致相当于O(n^3)的复杂度, 要考虑优化;

当我们删除一行时, 可能会由此出现新的满足条件的列, 所以最外层的n我们是很难优化的, 只能取考虑优化遍历; 我们遍历无非就是想看看这一行/列是否是由同一种字母组成, 那我们可以开一个数组st[i][j], 表示第i行中字母j的数量, 如果该字母的数量等于第i行的长度, 那么就说明是由同一种字母组成, 这样我们就可以把O(n^2)变成O(26n);

和st[i][j]相对应的fst[i][j]表示第i列中字母j的数量; rs[i]表示当前第i行的长度为多少, cs[i]表示当前第i列的长度为多少;

首先我们先遍历行i, 如果有满足条件的字母j, 那么就可以让st[i][j]清零, 注意: 当我们把一行的字母j删除后, 那么每一列中字母j的数量都会减一, 并且所有的列的长度也会减一, 但是我们要在遍历完所有列之后才能更新, 如果遍历列之前更新, 那么一些原本满足条件的列可能就会变得不满足了, 所有我们可以先把该字母存起来; 为了增加效率我们还可以对第i行打个标记, 意思是这一行以及被删除了, 可以不用遍历了, 也方便后期找答案; 对于列也是一样的操作; 遍历完行和列后我们就可以开始更新了, 更新每一行/列中某个字母的数量, 更新行和列的长度; 最后我们遍历所有位置, 如果某个位置的行和列都没有被标记, 说明该位置的字母没有被删除, 计数即可;

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
char g[N][N];
int st[N][N], fst[N][N];
int rs[N], cs[N];
bool ro[N], co[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            st[i][g[i][j] - 'a']++; // 统计行的字母 
            fst[j][g[i][j] - 'a']++;// 统计列的字母 
        }
    }
    for (int i = 1; i <= n; i++) rs[i] = m;//第i行长度 
    for (int j = 1; j <= m; j++) cs[j] = n;//第j列长度 
    while (1) {
        vector<int> rv, cv;
        bool qu = false;
        for (int i = 1; i <= n; i++) {
            if (ro[i]) continue;
            for (int j = 0; j < 26; j++) {
                if (st[i][j] == rs[i] && st[i][j] >= 2) {
                    qu = true;
                    ro[i] = true;
                    st[i][j] = 0;
                    rv.push_back(j);
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            if (co[i]) continue;
            for (int j = 0;  j < 26; j++) {
                if (fst[i][j] == cs[i] && fst[i][j] >= 2) {
                    qu = true;
                    co[i] = true;
                    fst[i][j] = 0;
                    cv.push_back(j);
                }
            }
        }
        for (int x : rv) {
            for (int i = 1; i <= m; i++) {
                fst[i][x]--;
                cs[i]--;
            }
        }
        for (int x : cv) {
            for (int i = 1; i <= n; i++) {
                st[i][x]--;
                rs[i]--;
            }
        }
        if (!qu) {
            break;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!ro[i] && !co[j]) {
                res++;
            }

        }
    }
    cout << res;
    return 0;
}
/*
4 3
aab
aaa
abc
cbd
*/

竞选

01背包：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f3f3f3f3f;
const int N = 110, M = 1e5 + 10;
int A[N], B[N], C[N];
int dp[M];
signed main(){
    int n;
    cin>>n;
    int sum = 0;
    for(int i = 1; i <= n; i++) 
        cin >> A[i] >> B[i] >> C[i], sum += C[i];

    //01背包-->dp[i]表示赢得i个席位需要转移的最少人数
    memset(dp,127,sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = sum; j >= C[i]; j--){
            if(A[i] > B[i]) dp[j] = min(dp[j - C[i]], dp[j]);
            else dp[j] = min(dp[j - C[i]] + (A[i] + B[i] + 1) / 2 - A[i], dp[j]);
        }
    }
    int ans = INF;
    for(int i = (sum + 1) / 2; i <= sum; i++)
        ans = min(ans, dp[i]);
    cout << ans;
    return 0;
}