本文共 2180 字，大约阅读时间需要 7 分钟。

A - Number of Multiples

水题

B - An Odd Problem

水题

C - XYZ Triplets

水题，注意数组不要开小了

D - Anything Goes to Zero

这道题思路很妙：

首先计算出字符串中所有 1 的数量 cnt，然后分三种情况：

代码实现

#include 
   
    
using namespace std;
typedef long long ll;
ll power(ll a, ll b, ll mod) {
    return b ? power(a * a % mod, b / 2, mod) * (b % 2 ? a : 1) % mod : 1;
}
ll cal(ll n) {
    ll cnt = 1;
    while (n) {
        n = n % __builtin_popcount(n);
        cnt++;
    }
    return cnt;
}
int main() {
    ll n, cnt = 0, ans1 = 0, ans2 = 0, ans;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') cnt++;
    }
    if (cnt > 1) {
        for (ll i = 0; i < n; i++) {
            if (s[i] == '1') {
                ans1 = (ans1 + power(2, n - i - 1, cnt - 1)) % (cnt - 1);
                ans2 = (ans2 + power(2, n - i - 1, cnt + 1)) % (cnt + 1);
            }
        }
        for (ll i = 0; i < n; i++) {
            if (s[i] == '0') {
                ans = (ans2 + power(2, n - i - 1, cnt + 1)) % (cnt + 1);
                cout << cal(ans) << endl;
            } else {
                ans = (ans1 + ((cnt - 1) - power(2, n - i - 1, cnt - 1) % (cnt - 1)) % (cnt - 1)) % (cnt - 1);
                cout << cal(ans) << endl;
            }
        }
    } else if (cnt == 1) {
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') {
                ans2 = (ans2 + power(2, n - i - 1, cnt + 1)) % (cnt + 1);
            }
        }
        for (ll i = 0; i < n; i++) {
            if (s[i] == '0') {
                ans = (ans2 + power(2, n - i - 1, cnt + 1)) % (cnt + 1);
                cout << cal(ans) << endl;
            } else {
                cout << 0 << endl;
            }
        }
    } else {
        for (int i = 0; i < n; i++) {
            cout << 1 << endl;
        }
    }
    return 0;
}
   

解释

通过这种方法，可以高效地解决字符串变换问题，并确保结果正确。

转载地址：http://aaykz.baihongyu.com/