普及组题解

T1 反码

使用字符串进行读入，按照题意模拟即可

T2 异或

我们发现在循环移位的时候，结果的改变只与个别位置有关。例如数组长度为 3，则刚开始时数组的价值为 ^ + ^ ，向右循环一次之后变为 ^ + ^ ，其中只少了一个 ^ 的值，多了一个 ^ 的值，其余部分是不变的。（对于更长的数组也可以用类似的方法进行推演）

得到此结论之后，我们只需要关注在循环移动的同时，哪一对异或值消失了，哪一对异或值增加了，就可以得到答案。

#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], num[maxn];
int main(){
    int n, q, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int last = n - 1, now = n - 1;
    long long ans = 0;
    for(int i = 0; i < n; i++){
        num[i] = a[i] ^ a[(i+1)%n];
        if(i != n - 1)    ans += num[i];
    }
    cout << ans << " ";
    while(m--){
        cin >> q;
        now = ((now - q) % n + n) % n;
        ans = ans + num[last] - num[now];
        last = now;
        cout << ans << " ";
    }

}

T3 最大公约数

从大到小枚举答案，假设 gcd 为 k，则说明 [l,r] 的区间之内至少要有 2 个 k 的倍数，这样才可以凑出两个数字 gcd 为 k。

对于区间内是否有 2 个 k 的倍数，我们可以用前缀和作差的方式算出——即 1~r 之间 k 的倍数有 r/k 个，1~(l-1) 之间 k 的倍数有 r/(l-1) 个，作差即可得到 [l,r] 中 k 的倍数的数量

#include 
using namespace std;
int main(){
    int i = 1e7, l, r;
    for(cin >> l >> r; (r / i - (l - 1) / i) < 2; i--);
    cout << i << endl;
}

T4 波浪

定义 dp[i][0/1][0/1] 为扫描到数组的 i 位置，且此位置比上一位置小/大，此位置改动/没改动过所需要的最小改动次数。

只记录大小关系是不行的，因为有可能通过改变而修改了这个数字和前一个数字的大小关系。只记录是否改变过也不行，因为不知道上一个数字和之前的大小关系，就无法确定这个数字应该改得更大还是更小。

知道状态之后，我们进行分类讨论：例如本身这个数字就比上一个大，比上一个小，和上一个数字相等。

讨论这三种不同的情况即可得到答案。

#include 
using namespace std;
const int maxn = 1e5 + 5;
int dp[maxn][2][2], a[maxn];
// 0 small 1 big
// 0 change 1 notchange
int main(){
    int n, q;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    dp[1][1][1] = dp[0][0][1] = 0;
    if(a[2] > a[1]){
        dp[2][1][0] = dp[2][0][1] = dp[2][0][0] = 1;
        dp[2][1][1] = 0;
    }else if(a[2] < a[1]){
        dp[2][1][1] = dp[2][0][0] = dp[2][1][0] = 1;
        dp[2][0][1] = 0;
    }else{
        dp[2][0][0] = dp[2][1][0] = dp[2][0][1] = dp[2][1][1] = 1;
    }
    for(int i = 3; i <= n; i++){
        if(a[i] > a[i-1]){
            dp[i][1][1] = min(dp[i-1][0][0], dp[i-1][0][1]);
            dp[i][0][0] = min(dp[i-1][1][0], dp[i-1][1][1]) + 1;
            dp[i][0][1] = dp[i-1][1][0];
            dp[i][1][0] = dp[i][1][1] + 1;
        }else if(a[i] < a[i-1]){
            dp[i][0][1] = min(dp[i-1][1][0], dp[i-1][1][1]);
            dp[i][1][0] = min(dp[i-1][0][0], dp[i-1][0][1]) + 1;
            dp[i][1][1] = dp[i-1][0][0];
            dp[i][0][0] = dp[i][0][1] + 1;
        }else{
            dp[i][1][1] = dp[i-1][0][0];
            dp[i][0][1] = dp[i-1][1][0];
            dp[i][0][0] = min(dp[i-1][1][0], dp[i-1][1][1]) + 1;
            dp[i][1][0] = min(dp[i-1][0][0], dp[i-1][0][1]) + 1;
        }
//        cout << i << " " << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][1][0] << " " << dp[i][1][1] << endl;
    }
    cout << min(min(dp[n][0][1], dp[n][0][0]), min(dp[n][1][0], dp[n][1][1])); 
}