竞赛讨论区 > 2021牛客OI赛前集训营-普及组题解(第三场)

2021牛客OI赛前集训营-普及组题解(第三场)

头像
鸡尾酒QAQ
发布于 2021-10-10 07:51:32 APP内打开
赞 1 | 收藏 0 | 回复1 | 浏览418

普及组题解

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])); 
}

1条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐