A.ICPC Time

显然答案为 。

时间复杂度 。

void solve(){
    print((read()+5)%24);
}

B.倍数

如果数字里有 或者 ，那么把 或者 放到末尾即可。

时间复杂度 。

void solve(){
    string s;cin>>s;
    ll f = 0;
    for(auto v:s){
        f|=(v=='5');
        f|=(v=='0');
    }
    cout<<(f?"YES\n":"NO\n");
}

C.邻合

考虑 。

令 为不选择第 个数字前 个数字可以保留的最大个数， 为选择第 个数字前 个数字可以保留的最大个数。

则有

时间复杂度 。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    vector<PLL> dp(n+1);
    for(ll i=1;i<=n;i++){
        dp[i].fi = max(dp[i-1].fi, dp[i-1].se);
        if(a[i]>1){
            dp[i].se = dp[i-1].fi + 1;
            if(i>1&&__gcd(a[i], a[i-1])>1){
                dp[i].se = max(dp[i].se,dp[i-1].se+1);
            }
        }
    }
    print(n-max(dp[n].fi, dp[n].se));   
}

D.对和

令 。

则有

设有 个奇数，奇数的 之和为 ；有 个偶数，偶数的 之和为 。则

• 奇数与奇数之间的贡献为 。（后一项为奇数和奇数加起来额外产生的 ）

• 偶数与偶数之间的贡献为 。

• 奇数与偶数之间的贡献为 。

时间复杂度 。

void solve(){
    ll n = read();
    vector<ll> odd, even;
    ll ans=0, sum1=0, sum2=0;
    for(ll i=1;i<=n;i++){
        ll t = read();
        if(t&1) odd.pb(t),sum1+=t/2;
        else even.pb(t),sum2+=t/2;
    }
    ll n1 = odd.size(), n2 = even.size();
    ans += (n1-1) * sum1 + n1 * (n1-1)/2;
    ans += (n2-1) * sum2;
    ans += n1*sum2 + n2*sum1;
    print(ans);
}

E.镜像

由于 ，因此我们只需要在 的范围内 BFS 即可。

时间复杂度

void solve(){
    ll a = read(), b = read(), k = read();
    vector<ll> dis(1e6+1, INF);
    queue<PLL> q;
    q.push({0,a});
    dis[a] = 0;
    while(!q.empty()){
        auto [d,t] = q.front();
        q.pop();
        if(t%10){
            ll tt=0,ttt=t;
            while(ttt){
                tt=(tt*10+ttt%10);
                ttt/=10;
            }
            if(dis[tt]>d+1){
                dis[tt]=d+1;
                q.push({d+1,tt});
            }
        }
        if(t+k<=1e6){
            if(dis[t+k]>d+1){
                dis[t+k]=d+1;
                q.push({d+1,t+k});
            }
        }
    }
    print(dis[b]<INF?dis[b]:-1);
}

F.差异

设 为 ，即所有字符串第 个字符 的数量之和。

则

对于第 个位置：

• 如果原来为 ，则原来不同的数目为 ，变为 后 的数量减一，不同的数目为 ，因此
• 如果原来为 ，则原来不同的数目为 ，变为 后 的数量加一，不同的数目为 ，因此

我们希望最小化不同的数量，即找到一个子数组 使得 最小，即最小子数组和。（经典贪心）

答案为 。

时间复杂度 。

void solve(){
    ll n, m;cin>>n>>m;
    vector<string> s(n);
    vector<ll> cnt(m);
    for(ll i=0;i<n;i++){
        cin>>s[i];
        for(ll j=0;j<m;j++){
            cnt[j] += (s[i][j] == '1');
        }
    }
    for(ll i=0;i<n;i++){
        ll pre = 0;
        for(ll j=0;j<m;j++){
            if(s[i][j] == '1') pre += n-cnt[j];
            else pre += cnt[j];
        }
        vector<ll> d(m);
        for(ll j=0;j<m;j++){
            if(s[i][j] == '1') d[j] = cnt[j]-1 - (n-cnt[j]);
            else d[j] = (n-1-cnt[j]) - cnt[j];
        }
        ll mi = 0, cur = 0;
        for(ll j=0;j<m;j++){
            cur = min(d[j], cur+d[j]);
            mi = min(mi, cur);
        }
        cout<<pre+mi<<'\n';
    }
}