题解 | #欢迎加入河南大学ACM！#

个人感觉难度划分：A/CBDEFG/JHIK

题解按照题目顺序

B题

需要判断两个字符串是否存在，同时存在或者同时不存在时输出NO，遍历一遍字符串，找到'A'时检验是否是两个之一，最后判断即可。注意：有些人使用substr来判断，也是可以的，但是注意substr第二个参数是字符串长度，而不是终止位置。

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    string a1 = "Association_for_Computing_Machinery";
    string a2 = "Air_Combat_Maneuvering";
    bool t1 = 0, t2 = 0;
    int n = s.size();
    auto check = [&](string s, string k, int i) -> bool
    {
        int len = k.size();
        for (int j = 0; j < len; j++){
            if (s[i + j] != k[j]){
                return 0;
            }
        }
        return 1;
    };
    for (int i = 0; i < n; i++){
        if (s[i] == 'A'){
            if (!t1){
                t1 = check(s, a1, i);
            }
            if (!t2){
                t2 = check(s, a2, i);
            }
        }
    }
    if (t1 && t2 || t1 == 0 && t2 == 0){
        cout << "NO\n";
    }else{
        cout << "YES\n";
    }
    return 0;
}

C题需要判断是否超出int范围，注意题目中|x|< $10^{18}$ 故可以使用long long 存下，判断是否超过INT_MAX即可.注意：x为负数时，最小可到-INT_MAX-1,不能取绝对值直接判

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 MAX = INT_MAX;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 t;
    cin >> t;
    if(t < 0 && abs(t) > MAX + 1 || t > MAX){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
    return 0;
}

D题

由于"henu"并不存在相等的子字符串，所以不可能存在范围相交的"henu"，故枚举即可

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n - 3; i++){
        if (s[i] == 'h' && s[i + 1] == 'e' && s[i + 2] == 'n' && s[i + 3] == 'u'){
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

E题

开一个二维数组f[i][j]代表第i个盒子和第j个颜色，模拟即可

#include <bits/stdc++.h>
using namespace std;
int f[101][101];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    while (q--){
        int op;
        cin >> op;
        if (op == 1){
            int x, y, col;
            cin >> x >> y >> col;
            if (f[x][col] == 0){
                continue;
            }else{
                f[x][col]--;
                f[y][col]++;
            }
        }else if (op == 2){
            int x, col;
            cin >> x >> col;
            f[x][col]++;
        }else{
            int x, col;
            cin >> x >> col;
            cout << f[x][col] << "\n";
        }
    }
    return 0;
}

F题

可以通过将时间全部转化为秒来计算，由于调时间时，到24:00:00会重新变成00:00:00，故不能直接计算判断。
即 $(s-p)+(24*60*60)*n=tk$ 有解，由于n>=t时，已经循环了，故枚举n $\in$ [0,t)即可通过
对于输入问题，可以使用很多方式解决：scanf(),由于限制每一位都是两位，也可以substr
同时也可以使用char来解决':'问题,题解使用更C++的方式写输入

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MOD = 24 * 60 * 60;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 p = 0, s = 0, t = 0;
    auto read = [&]() -> i64
    {
        i64 a, b, c;
        char x, y;
        cin >> a >> x >> b >> y >> c;
        return a * 60 * 60 + b * 60 + c;
    };
    p = read(), s = read(), t = read();
    i64 k = s - p;
    for (i64 i = 0; i < t; i++){
        if (k > 0 && k % t == 0){
            cout << k / t << '\n';
            return 0;
        }
        k += MOD;
    }
    cout << -1 << '\n';
    return 0;
}

G题

本题由于数据量并不是很大，实际上关闭同步流后,按照题意模拟暴力也可以能过此题。
讲一下非暴力如何过，由于一个数异或两次相同的数，结果不变。
对于先修改最后查询的题，可以使用前缀和和差分优化。

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n, q1, q2;
    cin >> n >> q1 >> q2;
    vector<i64> f(n + 1), sum(n + 2);
    for (int i = 1; i <= n;i++){
        cin >> f[i];
    }
    while (q1--){
        i64 l, r, x;
        cin >> l >> r >> x;
        sum[l] ^= x;
        sum[r + 1] ^= x;
    }
    for (int i = 1; i <= n;i++){
        sum[i] ^= sum[i - 1];
        f[i] ^= (sum[i] ^ f[i - 1]);
    }
    while (q2--){
        i64 l, r;
        cin >> l >> r;
        cout << (f[r] ^ f[l - 1]) << '\n';
    }
    return 0;
}

H题

本题数据量较大，如果使用暴力复杂度为 $O(T*(nm)^2)$ ,只能过66.67%,需要考虑优化。
看本题希望能自己画图,辅助理解,语文不行,只能尽量描述了
注意到本题只有'1'才能产生贡献,可以将行和列分开看,其中列比较简单,无论如何移动,在本次不加入'1'时,列产生的答案数量不变
若加入的是'1'则会将后面的数往后移动,仅当上一行该位置的数也是'1'时,才会重复
故只需要记录m个位置是否出现过即可,使用map来记录,t时刻列产生map.size()个贡献
对于行,我没有想到非常巧妙的方式能算,于是我使用三个数组来模拟,f[i]表示当前行添加第i个数时会产生的贡献,pref[i]是当前行添加第i个数字时,上一行剩下的数字产生的贡献,如果pref[i]=1,尽管目前行没有添加'1',f[i]仍然为1,对于运算过后的行,每一行都会固定经过这些数字,可以将运算过的行数值放入sum中.
故每个时刻产生的贡献为map.size()+sum;

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n,m;
    string s;
    cin>>n>>m>>s;
    s=" "+s;
    unordered_map<int, bool> col;
    vector<int> f(m+1),pref(m+1),sum(m+1);
    for(int i=1;i<=n;i++){
        bool ism=false;//判断该行是否添加过'1'
        int k=0;//记录该行有几个'1',方便记录pref
        for(int j=1;j<=m;j++){
            f[j]=0;
            if(s[(i-1)*m+j] =='1'){
                k++;
                col[j]=1;
                ism=true;
            }
            if(ism || pref[j]){//若已经添加过1,或者上一行剩下的数字有1
                f[j]=1;
            }
            sum[j]+=f[j];
            cout<<sum[j]+col.size()<<" ";
            pref[j]=0;
        }
        for(int j=1;j<=m;j++){//模拟pref
            if(s[(i-1)*m+j]=='1'){
                k--;
            }
            if(k){
                pref[j]=1;
            }
        }
    }
    cout<<"\n";
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

I题

需要划分成k个区间，使区间和非递减，本题使用dp[i][j]解决，其意义代表第i个元素结尾的第j个区间
注意：由于需要递增，我们更希望讨论第x区间时，第x-1区间的总和越小越好，故需要初始化为inf。
讨论区间和时，使用前缀和优化求和

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(){
    i64 n, k;
    cin>>n>>k;
    vector<i64> f(n + 1);
    for (int i = 1; i <= n;i++){
        cin >> f[i];
        f[i] += f[i - 1];
    }
    vector<vector<i64>> dp(n + 1, vector<i64>(k + 1,LLONG_MAX));
    dp[0][0] = -LLONG_MAX;
    for (int i = 1; i <= n;i++){//第i个元素
        for (int j = 1;j<=i;j++){//区间的第一个元素
            for (int l = 1; l <= k;l++){//第k个区间
                if(f[i]-f[j-1]>=dp[j-1][l-1]){
                    dp[i][l] = min(dp[i][l], f[i] - f[j - 1]);
                }
            }
        }
    }
    if(dp[n][k]!=LLONG_MAX){
        cout << "Yes\n";
    }else{
        cout << "No\n";
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

J题

此题没有看上去这么难，由于(1,1)和(n,m)不能重复来回移动，所以剩下 $n*m-2$ 个格子，类似于华容道，剩下的格子中最少需要两个空格子(通过移动可以到右下角）就能稳定到右下角，故可以看作有一个 $n*m-4$ 的背包存卡牌，由于需要(n,m)从上往下排列好，所以需要以递减的方式移动到(n,m)，我是使用大根堆来模拟的，也可以标好号排序来模拟。
注意：本题若已经超过了n*m-4个，不能直接终止，因为数据并没有输入完，会导致后面数据错位，所以要么提前输入完模拟，要么等运行完再输出

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(){
    i64 n, m, k;
    cin >> n >> m >> k;
    i64 stg = n * m - 4;
    priority_queue<i64> que;
    i64 pt = k;
    bool ans = true;
    for (int i = 0; i < k; i++){
        while (!que.empty() && que.top() == pt){
            pt--;
            que.pop();
        }
        i64 x;
        cin >> x;
        if (x == pt){
            pt--;
        }else{
            que.push(x);
        }
        if (que.size() > stg){
            ans = false;
        }
    }
    if(ans){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

K题

首先题目给出了我能杀等级 $<=$ x的史莱姆，所以 $a_i$ 数值其实并不重要，对于我来讲只有能自己解决的i个史莱姆和只能靠天雷解决的j个史莱姆
一开始，我思考是否有概率的通项公式解，但是很难找到，于是想到使用动态规划dp[i][j]表示还剩i我能解决，j个只能靠天雷解决的状态
但是动态规划比较难写,于是使用记忆化搜索来解决，对于某个状态，dfs(i,j)剩下i个我自己可以杀的史莱姆，j个只能靠天雷杀的史莱姆，对于我来讲，我只能将其变成dfs(i-1,j),然后天雷可以造成两种状态dfs(i-1,j-1)或者dfs(i-2,j);其中前一种的概率是p1= $\frac{j}{i+j-1}$ 后一种概率是p2= $\frac{i-1}{i+j-1}$ ,故转移为 $dfs(i,j)=p1*dfs(i-1,j-1)+p2*dfs(i-2,j)\$ 对于概率使用逆元即可，题目也给出了方法。
数据较大，需要开long long，并且需要注意爆long long
tips:可以去做周赛80的G题，方法与本题类似，可以巩固一下

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
const i64 MOD = 998244353;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n, x;
    cin >> n >> x;
    i64 l = 0, r = 0;
    for (int i = 0; i < n; i++){
        i64 k;
        cin >> k;
        if (k <= x){
            l++;
        }
        else{
            r++;
        }
    }
    vector<vector<i64>> f(l + 1, vector<i64>(r + 1));
    vector<vector<bool>> vis(l + 1, vector<bool>(r + 1));
    i64 t = n / 2 + n % 2;
    if (l < t){
        cout << 0 << "\n";
        return 0;
    }
    auto ksm = [&](i64 a, i64 b) -> i64{
        i64 res = 1;
        a %= MOD;
        while (b){
            if (b & 1){
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    };
    function<i64(i64, i64)> dfs = [&](i64 i, i64 j) -> i64
    {
        if (i < 0){
            return 0;
        }
        if (j == 0){
            return 1;
        }
        if (vis[i][j]){
            return f[i][j];
        }
        if (i == 0){
            return 0;
        }
        i64 pt = ksm(i - 1 + j, MOD - 2);
        f[i][j] = (dfs(i - 2, j) * (i - 1) % MOD * pt % MOD + dfs(i - 1, j - 1) * j % MOD * pt % MOD) % MOD;
        vis[i][j] = 1;
        return f[i][j] % MOD;
    };
    cout << dfs(l, r) % MOD << "\n";
    return 0;
}