【RS十周年】比赛题解

hxydz · 2025-08-28 11:47:32 · 算法·理论

Successful person

优先用大盒：先看 n 能否被 5 整除，若能，用 5 颗装盒子数最少，结果为 n / 5。
混合装尝试：若不能被 5 整除，看余数能否被 3 整除，能则用 5 颗装和 3 颗装组合。
逐步减 3 尝试：若上述都不满足，不断从 n 中减 3，每减一次检查剩余数量能否被 5 整除，能则计算总盒数。
若整个过程都没找到方案，输出 wwyytsn!，否则输出最少盒子数。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int result = -1;
    if (n % 5 == 0) {
        result = n / 5;
    } else if ((n % 5) % 3 == 0) {
        result = n / 5 + (n % 5) / 3;
    } else {
        int temp = n;
        while (temp >= 3) {
            temp -= 3;
            if (temp % 5 == 0) {
                result = temp / 5 + (n - temp) / 3;
                break;
            }
        }
    }
    if (result == -1) {
        cout << "wwyytsn!";
    } else {
        cout << result;
    }
    return 0;
}

迷魂阵

（本来有个更难的小模拟的，但是后面题有点爆了，所以这题想着节省一点时间的）

每个棋子走到对面需要 n - 1 步数，所以至少需要 2n(n - 1) 步。如果某一列的黑子和白子同时向他们的正方向移动，那么会相撞。不妨让黑子在原来的列，白子进行交错。考虑第 i 列的白子最后走到了第 p_i 列，那么m多出来步数为

由于 p_i ≠ i，该和式存在下界⌈\frac{1}{x}⌉可以对相邻的两列 p_i = i + 1，p_(i+1) = i,当 n 是偶数时这样直 接可以取到下界，而 n 是奇数时，只需要前三列 p_1 = 3, p_2 = 1, p_3 = 2 即可，刚好满足下界。

代码1

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long ans = n * (2 * n - 1);
    if (n & 1) cout << ans + 1 << endl;
    else cout << ans << endl;
    return 0;
}

代码2

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n;
int main() {
    cin >> n;
    cout << 2 * n * (n - 1) + n + (n % 2);
    return 0;
}

地心历险

算法一

注意到图是三部图，如果令 s_i ≡ col_i(mod 3) 就复合条件了。图的性质不太好，先研究树的情况。
对于一个非根节点，显然可以通过父亲边调整权值。设 m = (cool_{root} - s_{root}) mod 3 ，那么如果我们可以找到包含根的一个奇环，我们不断在上面 -m, +m ，与根相连的两条边都是 -m ，这样相当于 + m mod 3。而其他点都不变，也就满足了条件。于是当这个图不是二分图时，找一个奇环上的点做根 即可。
接下来考虑二分图的情况，重新给图染色（只用 01）。不妨令根的颜色为 0，这样只有当最后算出情况 是 1 的时候才会出错。可我们发现 2 这种点权还没用，这时我们不妨选两条边给其加 1，容易发现这时 并没有什么问题。可以选择度数大于 2 的点当根。

算法二

上述算法中直接构造只有根可能出错，故当根不合法时，重新随机选择根和 dfs 生成树。注意到题目只要求值不同而不是上面提到的模 3 与 cool_i 相同，故随意调整几次即可满足条件。

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
template <typename T>
void read(T &x) {
    T flag = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= flag;
}
const int maxn = 200005;
struct e{
    int u, v, val;
}ans[maxn];
int n, m;
char s[maxn];
int col[maxn], f[maxn], val[maxn], d[maxn];
vector<pair<int, int>> vec[maxn], t[maxn];
bool vis[maxn];
int tmp[maxn];
int flag, End;
int pre[maxn], num[maxn];
void dfs(int x, int fa, int id) {
    f[x] = fa;
    if (fa) t[x].pb(mp(fa, id));
    for (int i = 0; i < (int)vec[x].size(); i++) {
        int y = vec[x][i].first;
        if (f[y] > 0 || y == flag) continue;
        t[x].pb(mp(y, vec[x][i].second));
        dfs(y, x, vec[x][i].second);
    }
}
void get_ans(int x) {
    for (int i = 0; i < (int)t[x].size(); i++) {
        int y = t[x][i].first;
        if (y == f[x]) continue;
        get_ans(y);
        int m = col[y] - d[y];
        ans[t[x][i].second].val = m;
        d[y] = d[y] + m;
        d[x] = d[x] + m; 
    }
}
void get_ans2(int x) {
    for (int i = 0; i < (int)t[x].size(); i++) {
        int y = t[x][i].first;
        if (y == f[x]) continue;
        get_ans2(y);
        int m = tmp[y] - d[y];
        ans[t[x][i].second].val = m;
        d[y] = d[y] + m;
        d[x] = d[x] + m;
    }
}
void check(int x) {
    for (int i = 0; i < (int)vec[x].size(); i++) {
        int y = vec[x][i].first;
        if (tmp[y] == -1) tmp[y] = tmp[x] ^ 1, check(y);
        else {
            if (tmp[y] == tmp[x]) {
                flag = x;// 不是二分图 
            }
        }
    }
}
void yyy(int x) {
    for (int i =0; i < (int)vec[x].size(); i++) {
        int y = vec[x][i].first;
        if (tmp[y] != -1) continue;
        tmp[y] = tmp[x] ^ 1;
        yyy(y);
    }
}
int cnt[maxn];
void output() {
    for (int i = 1; i <= m; i++) {
        ans[i].val = (ans[i].val % 3 + 3) % 3;
        if (ans[i].val == 0) ans[i].val = 3;
        printf("%d\n", ans[i].val);
        cnt[ans[i].u] += ans[i].val;
        cnt[ans[i].v] += ans[i].val;
    }
}
void jjj(int x) {
    for (int i = 0; i < (int)vec[x].size(); i++) {
        int y = vec[x][i].first;
        if (tmp[y] == -1) tmp[y] = tmp[x] ^ 1, pre[y] = x, num[y] = vec[x][i].second, jjj(y);
        else {
            if (y == flag && tmp[x] == tmp[flag]) {
                End = x;
            }
        }
    }
}
void work() {
    tmp[1] = 0;
    check(1);
    if (flag) {// 不是二分图  
        dfs(flag, 0, 0);
        get_ans(flag);
        int m = (col[flag] - d[flag]);
        memset(tmp, -1, sizeof(tmp));
        tmp[flag] = 0;
        jjj(flag);
        for (int i = End; i != flag; i = pre[i]) {
            ans[num[i]].val += m;
            m = -m;
        }
        for (int i = 0; i < (int)vec[End].size(); i++) {
            if (vec[End][i].first == flag) ans[vec[End][i].second].val += m << 1;
        }
        output();
    } else {
        flag = 1;
        memset(tmp, -1, sizeof(tmp));
        tmp[1] = 0;

        yyy(flag);
        dfs(flag, 0, 0);
        get_ans2(flag);
        if ((d[1] % 3 + 3) % 3 == 1 && vec[1].size() > 1) {
            ans[vec[1][1].second].val++; ans[vec[1][2].second].val++;
        }
        output();
    }
}
int main() {
    memset(tmp, -1, sizeof(tmp));
    read(n); read(m);
    for (int i = 1; i <= n; i++) {
        read(col[i]); 
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        read(u); read(v);
        ans[i].u = u; ans[i].v = v;
        vec[u].pb(mp(v, i));
        vec[v].pb(mp(u, i));
    }
    for (int i = 1; i <= n; i++) reverse(vec[i].begin(), vec[i].end());
    work();
    return 0;
}

魔法屋

发现 a_i - (a_i mod j) 并不会改变

的值。记 L = lcm(1,2,...,k-1) ,于是可以分成两个部分，⌊a_i/L⌋ 和 a_i mod L , 前者在操作的过程中不会变，总共会对答案有 ×n^{k-1}×k 的贡献，后者较小，考虑动态规划。

记 f_{i,j} 代表值为 i 的数，第 j 次操作开始，后面对答案的总贡献。转移分成两部分，如果当前选中这个数，则从 f_{i-imodj,j+1} 转移，否则以 n-1 系数从 f_{i,j+1} 转移。即

其中 g_{i,j} 代表方案数，是辅助数组。转移即为 g_{i,j} = g_{i-imodj,j+1}+(n-1)g_{i,j+1}。

而答案即为 \sum_{i = 1}^{n} \ {f_{a_i} mod L,1}。注意到修改只是修改一个位置，那么其对答案的贡献可以 O(1) 表示，那么就做到了 O(1) 修改。有一些 dp 的做法可能无法做到 O(1) 修改，可惜hxydz太懒了脑子不够用了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5, mod = 1e9 + 7;
template <typename T>
void read(T &x) {
    T sgn = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= sgn;
}
int n, a[maxn], x, y, k, m, ans, cnt[maxn];
int f[20][720721], g[20][720721], pw[20], q;
int qmod(int x) { return x >= mod ? x - mod : x; }
int ksm(int a, int b = mod - 2) { int ret = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod; return ret; }
int main() {
    int lcm = 1;
    for (int i = 1; i <= 16; i++) lcm = lcm * i / __gcd(lcm, i);
    read(n); read(k);
    for (int i = 1; i <= n; i++) read(a[i]);
    pw[0] = 1;
    for (int i = 1; i <= k; i++) pw[i] = 1ll * pw[i - 1] * n % mod; 
    for (int i = 1; i <= n; i++)
        cnt[a[i] % lcm]++, ans = qmod(ans + 1ll * (a[i] / lcm * lcm) * pw[k - 1] % mod * k % mod);
    for (int i = 0; i < lcm; i++) g[k + 1][i] = 1;
    for (int i = k; i; i--)
    {
        for (int j = 0; j < lcm; j++)
        {
            f[i][j] = qmod(1ll * (n - 1) * f[i + 1][j] % mod + f[i][j]);
            f[i][j] = qmod(qmod(1ll * j * g[i + 1][j - j % i] % mod + f[i + 1][j - j % i]) + f[i][j]);
            g[i][j] = qmod(1ll * (n - 1) * g[i + 1][j] % mod + g[i + 1][j - j % i]);
        }
    }
    for (int i = 0; i < lcm; i++) ans = qmod(ans + 1ll * cnt[i] * f[1][i] % mod);
    printf("%d\n", ans);
    read(q);
    while (q--) {
        int x, y;
        read(x); read(y);
        ans = qmod(ans - 1ll * (a[x] / lcm * lcm) * pw[k - 1] % mod * k % mod + mod);
        ans = qmod(ans - f[1][a[x] % lcm] + mod);
        a[x] = y;
        ans = qmod(ans + 1ll * (a[x] / lcm * lcm) * pw[k - 1] % mod * k % mod);
        ans = qmod(ans + f[1][a[x] % lcm]);
        printf("%d\n", ans);
    }
    return 0;
}