abc 290 D

这道题最重要的结论是
在约瑟夫环中，如果 n 和 d 是互质的，那么不会撞到一起
但如果 g = gcd(n, d) != 1，那么会在 n / g 次后撞在一起，

约瑟夫环问题，能得出一个结论，如果 n 和 d 是互质的，那么就不会碰到
否则，n 和 d 分别可以写成 a * g 和 b * g
在第 a 个数会碰到，如果碰到的话，就会往后延一个
总共会后延 g 次，由此可以得到公式
ans = d * (k - 1) % n + (k - 1) / a;

abc 289 D

简单 DP
两种写法，效率上无差异

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, x;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }
    cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i ++) {
        cin >> b[i];
    }
    cin >> x;

    vector<int> dp(x + 1, 0);
    for (auto i : b) {
        dp[i] = -1;
    }
    dp[0] = 1;

    /*  1
    for (int i = 0; i <= x; i ++) {
        if (dp[i] != 1) continue;
        for (auto j : a) {
            if (i + j <= x && dp[i + j] == 0) dp[i + j] = 1;
        }
    }
    */

    /*  2
    for (int i = 1; i <= x; i ++) {
        if (dp[i] == -1) continue;
        for (auto j : a) {
            if (i - j >= 0 && dp[i - j] == 1) {
                dp[i] = 1;
            }
        }
    }
    */

    cout << (dp[x] == 1 ? "Yes\n" : "No\n");

    return 0;
}

abc 288 D

一眼看上去是差分
可以将 i 分入 i % k 组，对于每个 i 来说，能影响它的值的只有同一个组内之前的差分值
也就是说，每次操作都会使同组的上一个位置差分值变为 0，而自己则增加 前面的那个值
所以是前缀和的操作，只要一个区间同组的值之和为 0，则最后可以变为满足题目要求的区间