参考代码放在最后面。

思路

A.ICPC Time

直接模拟即可

B.倍数

满足的数字一定符合个位数为 或者 ，于是在原串中找即可。

C.邻质

一种特殊情况：当 时，该数字一定要被修改。

否则，若 则贪心把 改成 即可。

一个技巧：在 std::gcd 中 。

时间复杂度为 。

D.对和

考虑把原式拆分成

提取 项，容易得到：

考虑提取出所有独立项，化简为：

后半段可以等价为 ，其中 内条件成立时值为 ，否则为 。

此时后半段只与 的值有关，记 为 的数量，我们可以将上述等式化成：

时间复杂度 。

E.镜像

考虑 BFS，我们只需遍历到 以内所有数即可，时间复杂度为 ，可能会卡常，需要注意一下，尽量开 bool 数组。

vector<bool> 开 的大小也可以过，最慢的点跑了 毫秒。

F.差异

由于每一列的元素具有独立性，即修改任意第 号元素，不会对其他位置的答案产生影响，所以可以考虑每列单独考虑，即预处理每列 1 的数量，方便后续计算。

对于每个串而言，翻转第 个字符的收益为 ，不翻转的收益为 ，我们可以使用有限状态动态规划做到 ，即记录状态区间前、内部以及后面三种状态。

时间复杂度为 。

代码

A.ICPC Time

void solve(){
    int x;
    cin >> x;
    cout << (x + 5) % 24;
}

B.倍数

void solve(){
    string s;
    cin >> s;
    for (int ch : s){
        if (ch == '0' || ch == '5'){
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

C.邻质

void solve(){
    int n;
    cin >> n;
    vector<int> a(n+2);
    int ans = 0;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++){
        if (gcd(a[i],a[i-1]) == 1) {
            ans++,a[i] = 0;
        }
    }
    cout << ans << "\n";
}

D.对和

void solve(){
    int n;
    cin >> n;
    vector<i64> a(n+2);
    for (int i = 1;i <= n;i++) cin >> a[i];
    i64 ans = 0,c1 = 0;
    for (int i = 1;i <= n;i++){
        ans += (n-1) * (a[i] / 2);
        if (a[i] & 1) c1++;
    }
    ans += c1 * (c1 - 1) / 2;
    cout << ans << "\n";
}

E.镜像

constexpr int N = 1e7+7;
vector<bool> vis(N);
vector<int> cls;

void solve(){
    int a,b,k;
    cin >> a >> b >> k;
    auto rev = [](int x)->int {
        string s = to_string(x);
        reverse(s.begin(),s.end());
        return stoi(s);
    };
    queue<p32> q;
    auto add = [&](int x)->void {
        if (vis[x]) return;
        vis[x] = 1;
        cls.push_back(x);
    };
    q.push({a,0});
    add(a);
    bool tag = 0;
    while(q.size()){
        auto [x,step] = q.front();
        q.pop();
        if (x == b){
            cout << step << "\n";
            tag = 1;
            break;
        }
        if (x + k <= b * 10 && !vis[x+k]) {
            q.push({x+k,step+1});
            add(x+k);
        }
        if (x % 10){
            int nxt = rev(x);
            if (!vis[nxt]) {
                q.push({nxt,step+1});
                add(nxt);
            }
        }
    }
    if (!tag) cout << -1 << "\n";
    for (const int &x : cls){
        vis[x] = 0;
    }
    cls.clear();
}

F.差异

void solve(){
    int n,m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0;i < n;i++) cin >> s[i];
    vector<int> cnt(m);
    for (int i = 0;i < n;i++){
        for (int j = 0;j < m;j++){
            cnt[j] += s[i][j] == '1';
        }
    }
    using t32 = std::array<int,3>;
    constexpr int inf = 1e9;
    for (int i = 0;i < n;i++){
        vector<t32> dp(m+1,{inf,inf,inf});
        dp[0][0] = 0;
        for (int j = 0;j < m;j++){
            int c;
            if (s[i][j] == '1') c = n-cnt[j];
            else c = cnt[j];
            dp[j+1][0] = dp[j][0] + c;
            dp[j+1][1] = min(dp[j][0],dp[j][1]) + n-c-1;
            dp[j+1][2] = min({dp[j][0],dp[j][1],dp[j][2]}) + c;
        }
        cout << min({dp[m][2],dp[m][1],dp[m][0]}) << "\n";
    }
}

模板

主程序

#include<bits/stdc++.h>
#if __has_include("tool/local.hpp")
#include "tool/local.hpp"
#include "grader.hpp"
#else
#define Testcases(T) while(T--) solve();
    #ifndef ONLINE_JUDGE
    #define listen(...) freopen("data.in","r",stdin),freopen("data.out","w",stdout);
    #else
    #define listen(...)
    #endif
#endif
using namespace std;
// Base type
using ll = long long;
using ld = long double;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using p32 = std::array<int,2>;
using p64 = std::array<i64,2>;

// mt19937_64 rnd(time(0));

void solve(){
    int x;
    cin >> x;
    cout << (x + 5) % 24;
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr),std::cout.tie(nullptr);
    listen(_TIMER,_FILE,_CHECKER);
    int T = 1;
    // std::cin >> T;
    Testcases(T);
    return 0;
}

The End