A

若最终序列长为 $mm$ ，对于数字 $ii$ ，至少填 $\lceil \frac{m}{a_i}\rceil \backslash lceil\backslash frac\{m\}\{a\_i\}\backslash rceil$ 次 。那么理论上只需满足 ${\sum }_{i=1}^n\lceil \frac{m}{a_i}\rceil \le m\backslash sum\_\{i=1\}^n\; \backslash lceil\; \backslash frac\{m\}\{a\_i\}\backslash rceil\backslash leq\; m$ 即 ${\sum }_{i=1}^n\frac{1}{a_i}\le 1\backslash sum\_\{i=1\}^n\; \backslash frac\{1\}\{a\_i\}\backslash leq\; 1$ 即可有解。而题目保证 ${\sum }_{i=1}^n\frac{1}{a_i}\le \frac{1}{2}\backslash sum\_\{i=1\}^n\; \backslash frac\{1\}\{a\_i\}\backslash leq\; \backslash frac\{1\}\{2\}$ 。所以考虑把 $a_{i}a\_i$ 进行缩小：

令 $m=2^{k}m=2^k$ ，对于每一个 $ii$ ，让 $a_i^{\mathrm{\prime }}a\_i\text{'}$ 为小于等于 $a_{i}a\_i$ 的最大的 $22$ 的次幂。

然后按照 $a_i^{\mathrm{\prime }}a\_i\text{'}$ 从小到大地填放即可。因为 $a_i^{\mathrm{\prime }}\mathrm{\mid }ma\_i\text{'}|m$ ，所以能恰好填 $\frac{m}{a_i^{\mathrm{\prime }}}\backslash frac\{m\}\{a\_i\text{'}\}$ 个。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int n, ans[N], m;
pair<int, int> a[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a + 1, a + 1 + n);
    m = 1e6;
    for (int i = 1, b = 1; i <= n; b++, i++) {
        while (ans[b]) b++;
        for (int j = b;; j += a[i].first) {
            while (j > m || ans[j]) j--;
            ans[j] = a[i].second;
            if (m - j + b <= a[i].first)
                break;
        }
    }
    printf("%d\n", m);
    for (int i = 1; i <= m; i++) printf("%d ", ans[i] ? ans[i] : 1);
}

B

在 $\mathrm{d}\mathrm{f}\mathrm{s}\backslash rm\; dfs$ 的时维护 $\mathrm{d}\mathrm{f}\mathrm{n}\backslash rm\; dfn$ 栈 ，即可 $\mathcal{O}(1)\backslash mathcal\; O(1)$ 得到某个点的 $kk$ 级祖先。然后通过儿子对父亲进行树上差分即可解决。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 9;
vector<int> e[N];
int n, a[N], c[N], dis[N], sta[N], top;
void dfs(int now, int fa) {
    sta[++top] = now;
    c[now]++;
    c[sta[max(0, top - a[now] - 1)]]--;
    for (auto i : e[now]) {
        if (i == fa)
            continue;
        dfs(i, now);
        c[now] = c[now] + c[i];
    }
    top--;
}
int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    dfs(1, -1);
    for (int i = 1; i <= n; i++) printf("%d ", c[i]);
}

C

先对边按照（边权，编号）的双关键字排序，保证生成森林唯一。

考虑第 $ii$ 条边 $(u,v)(u,v)$ 在什么时候会被选择：即加完前 $i-1i-1$ 条边后 $u,vu,v$ 仍不连通。

那么就用所有边集的数量减去加完前 $i-1i-1$ 条边后能使 $u,vu,v$ 联通的边集数量。

而比这条边大的边是不影响的，所以最后乘上 $2^{n-i}2^\{n-i\}$ 。

枚举前 $i-1i-1$ 条边的边集构成的多个连通块中，包含 $(u,v)(u,v)$ 的连通块为 $SS$ 。那么两个端点在 $SS$ 外的边任取，一个端点在内的边不能取，两个端点都在 $SS$ 内的边需要满足能使 $SS$ 联通。

第一类和第二类是容易的。对于第三类设为 $f(i,S)f(i,S)$ 表示前 $ii$ 条边构成的连通块为 $SS$ 。

其中需要满足 $u\in T,v\in S\mathrm{/}Tu\backslash in\; T,v\backslash in\; S/T$

用子集卷积可以快速加速。否则朴素实现需要 $\mathcal{O}(m{3}^n)\backslash mathcal\; O(m3^n)$。

#include <bits/stdc++.h>
using namespace std;
const int p = 998244353;
const int N = 1 << 16;
int add(int a, int b) { return a + b >= p ? a + b - p : a + b; }
int mul(int a, int b) { return a == 0 || b == 0 ? 0 : 1ll * a * b % p; }
int n, m;
struct edge {
    int x, y, w;
} e[N];
bool cmp(edge a, edge b) { return a.w < b.w; }
int pw[N], f[N], pw2[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int w;
            cin >> w;
            if (i < j && w) {
                e[++m].x = i - 1;
                e[m].y = j - 1;
                e[m].w = w;
            }
        }
    }
    sort(e + 1, e + m + 1, cmp);
    for (int i = 0; i < (1 << n); i++) pw[i] = 1;
    pw2[0] = 1;
    for (int i = 1; i <= m; i++) pw2[i] = add(pw2[i - 1], pw2[i - 1]);
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        int S = (1 << e[i].x) | (1 << e[i].y);
        for (int T = S; T < 1 << n; T = (T + 1) | S) pw[T] = add(pw[T], pw[T]);
        f[0] = 1;
        int res = 0;
        for (int S = 1; S < 1 << n; S++) {
            if (S & 1 << e[i].y || !(S & 1 << e[i].x))
                continue;
            f[S] = pw[S];
            int l = 1 << e[i].x;
            for (int T = S ^ l; T; T = (T - 1) & (S ^ l)) {
                f[S] = add(f[S], p - mul(f[S ^ T], pw[T]));
            }
            res = add(res, mul(f[S], pw[((1 << n) - 1) ^ S]));
        }
        res = mul(res, pw2[m - i]);
        ans = add(ans, mul(res, e[i].w));
    }
    cout << ans << endl;
    return 0;
}

D

E

对于一个大小为 $nn$ 的排列 $pp$ ，一次操作后的 $f(p)=\sum a_{i,p_i}f(p)=\backslash sum\; a\_\{i,p\_i\}$ 是不会变的。因此若 则必然无解。而这个可以用二分图最小权匹配求出。

而当 $\min f(p)\ge 0\backslash min\; f(p)\backslash geq\; 0$ 的时候一定有解。因为随意交换行列，$f(p)f(p)$ 是不会变的，那我们假设最小权匹配在主对角线且和为 $00$ 。（若和大于零，则不会更劣）对 $(i,n)(i,n)$ 各操作一次就能使得主对角线上全是 $00$ 。

然后只对 $(i,i)(i,i)$ 进行操作。假设操作的参数为 $x_{i}x\_i$ ，即第 $ii$ 行加上 $x_{i}x\_i$，第 $ii$ 列减去 $x_{i}x\_i$ ，则需要满足 $\mathrm{\forall }1\le i,j\le n,x_i-x_j+a_{i,j}\ge 0\backslash forall\; 1\backslash leq\; i,j\backslash leq\; n,x\_i-x\_j+a\_\{i,j\}\backslash geq\; 0$ 。这是个差分约束的形式，直接用 $\mathrm{S}\mathrm{P}\mathrm{F}\mathrm{A}\backslash rm\; SPFA$ 跑一遍就好了。由于 $11$ 当起点，最短路直接为 $00$ ，从而使得总操作数为 $2n-22n-2$。

考虑无解时，说明图中出现了负环，假设负环为 $\{b_1,b_2,b_3\mathrm{.}\mathrm{.}\mathrm{.}{b}_k\}\backslash \{b\_1,b\_2,b\_3...b\_k\backslash \}$ ，那么走过的边集为 $\{a_{b_1,b_2},a_{b_2,b_3}\mathrm{.}\mathrm{.}\mathrm{.}{a}_{b_k,b_1}\}\backslash \{a\_\{b\_1,b\_2\},a\_\{b\_2,b\_3\}...a\_\{b\_k,b\_1\}\backslash \}$ 。而若更改原本的排列 $P=\{1,2,3,\mathrm{4...}n\}P=\backslash \{1,2,3,4...n\backslash \}$（因为移动到主对角线了）中的几个数 $P_{b_1}=b_2,P_{b2}=b_3\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}{P}_{b_k}=b_{1}P\_\{b\_1\}=b\_2,P\_\{b2\}=b\_3....P\_\{b\_k\}=b\_1$ ，仍是一个排列，且 $f(p)f(p)$ 减少了，不满足上述假设求出的最小的 $f(p)f(p)$，所以一定有解。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 9;
const int inf = 1e9;
int n;
int a[N][N];
int ex[N], ey[N], slack[N], pre[N], mat[N], vis[N];
void bfs(int x) {
    memset(slack, 0x3f, sizeof slack);
    memset(pre, 0, sizeof pre);
    memset(vis, 0, sizeof vis);
    int y = 0, yy = 0;
    mat[0] = x;
    while (mat[y]) {
        x = mat[y], vis[y] = 1;
        int d = inf;
        for (int i = 1; i <= n; i++) {
            if (vis[i])
                continue;
            int val = ex[x] + ey[i] + a[i][x];
            if (val < slack[i])
                slack[i] = val, pre[i] = y;
            if (slack[i] < d)
                d = slack[i], yy = i;
        }
        for (int i = 0; i <= n; i++)
            if (vis[i])
                ex[mat[i]] -= d, ey[i] += d;
            else
                slack[i] -= d;
        y = yy;
    }
    while (y) mat[y] = mat[pre[y]], y = pre[y];
}
int sum;
void KM() {
    for (int i = 1; i <= n; i++) bfs(i);
    for (int i = 1; i <= n; i++) sum += a[i][mat[i]];
}
void output(int x, int y, int z) {
    printf("%d %d %d\n", x, y, z);
    for (int i = 1; i <= n; i++) a[x][i] += z, a[i][y] -= z;
}
int id[N];
int e[N][N], dis[N];
void spfa() {
    static int inq[N];
    for (int i = 2; i <= n; i++) dis[i] = inf;
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int x = q.front();
        q.pop();
        inq[x] = 0;
        for (int i = 1; i <= n; i++) {
            if (dis[i] > dis[x] + e[x][i]) {
                dis[i] = dis[x] + e[x][i];
                if (!inq[i])
                    q.push(i), inq[i] = 1;
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
    KM();
    if (sum < 0) {
        puts("-1");
        return 0;
    }
    printf("%d\n", n + n - 2);
    for (int i = 1; i < n; i++) output(i, mat[n], -a[i][mat[i]]);
    for (int i = 1; i <= n; i++) id[mat[i]] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == id[j])
                continue;
            int k = id[j];
            e[i][k] = a[i][j];
        }
    }
    spfa();
    for (int i = 2; i <= n; i++) output(i, mat[i], dis[i]);
    return 0;
}

F

这里给出的是题解的做法。

构造一个大小为 $3737$ 的树，把 $2\sim 372\backslash sim\; 37$ 号点平均分成 $66$ 组。从每组选择 $u,v_1,v_{2}u,v\_1,v\_2$ 三个点。并把 $v_1,v_{2}v\_1,v\_2$ 的父亲改为 $uu$ 。这样每组方案数有 $6\times \left(\genfrac{}{}{0px}{}{5}{2}\right)=606\backslash times\; \backslash binom\{5\}\{2\}=60$ 种，总方案有 $60^{6}60^6$ 种。由于 $X,Y,ZX,Y,Z$ 都是随机的，所以可以把每一次操作的增量也看成随机的，那么一定能有一种方案使得最终的 $H(T)H(T)$ 为所求。至此只需要双向搜索即可解决。时间复杂度 $\mathcal{O}(60^3\log (60^3))\backslash mathcal\; O(60^3\backslash log\; (60^3))$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
const int N = 60;

int T, X, Y, Z;
int xp[N], yp[N], zp[N];
void init() {
    xp[0] = yp[0] = zp[0] = 1;
    for (int i = 1; i < N; i++) {
        xp[i] = xp[i - 1] * X % mod;
        yp[i] = yp[i - 1] * Y % mod;
        zp[i] = zp[i - 1] * Z % mod;
    }
}

int gethash(int p, int q, int l) {
    if (p > q)
        swap(p, q);
    return xp[p] * yp[q] % mod * zp[l] % mod;
}
map<int, tuple<int, int, int>> group[6];
vector<int> nums[6];
int fa[N];
void solve() {
    cin >> T >> X >> Y >> Z;
    init();
    int base = 0;
    for (int i = 0; i < 6; i++) {
        nums[i].clear();
        group[i].clear();
    }
    for (int i = 1; i <= 37; i++)
        for (int j = i + 1; j <= 37; j++) (base += gethash(i, j, 1)) %= mod;
    for (int i = 2; i <= 37; i++) fa[i] = 1;
    int cnt = 0;
    for (int i = 2; i <= 37; i += 6) {
        nums[cnt].emplace_back(0);
        group[cnt][0] = { 1, 1, 1 };
        for (int j = i; j < i + 6; j++) {
            for (int x = i; x < i + 6; x++) {
                if (x == j)
                    continue;
                for (int y = x + 1; y < i + 6; y++) {
                    if (y == j)
                        continue;
                    int t = 0;
                    t -= gethash(x, y, 1);
                    t -= gethash(y, j, 1);
                    t -= gethash(x, j, 1);

                    t += gethash(x, y, j);
                    t += gethash(x, j, j);
                    t += gethash(y, j, j);

                    t = (t % mod + mod) % mod;
                    group[cnt][t] = { x, y, j };
                    nums[cnt].emplace_back(t);
                }
            }
        }
        cnt++;
    }
    map<int, tuple<int, int, int>> mp;
    for (auto i : nums[0])
	for (auto j : nums[1])
	for (auto k : nums[2]) 
		mp[i + j + k] = { i, j, k };
    for (auto i : nums[3])
    for (auto j : nums[4])
    for (auto k : nums[5]) {
        int need = ((T - base - i - j - k) % mod + mod) % mod;
        if (mp.count(need)) {
            int a = get<0>(group[3][i]);
            int b = get<1>(group[3][i]);
            int c = get<2>(group[3][i]);
            fa[a] = c;
            fa[b] = c;
            a = get<0>(group[4][j]);
            b = get<1>(group[4][j]);
            c = get<2>(group[4][j]);
            fa[a] = c;
            fa[b] = c;
            a = get<0>(group[5][k]);
            b = get<1>(group[5][k]);
            c = get<2>(group[5][k]);
            fa[a] = c;
            fa[b] = c;
            int p, q, r;
            tie(p, q, r) = mp[need];
            a = get<0>(group[0][p]);
            b = get<1>(group[0][p]);
            c = get<2>(group[0][p]);
            fa[a] = c;
            fa[b] = c;
            a = get<0>(group[1][q]);
            b = get<1>(group[1][q]);
            c = get<2>(group[1][q]);
            fa[a] = c;
            fa[b] = c;
            a = get<0>(group[2][r]);
            b = get<1>(group[2][r]);
            c = get<2>(group[2][r]);
            fa[a] = c;
            fa[b] = c;
            cout << 37 << endl;
            for (int i = 2; i <= 37; i++) 
                cout << i << " " << fa[i] << endl;
            return;
        }
    }
}
signed main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

G

只需要细心按照题意模拟即可。

#include <bits/stdc++.h>
using namespace std;
char s[99][99];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= 13 * n + 19; i++) s[1][i] = s[4 * n + 5][i] = '*';
    for (int i = 1; i <= 4 * n + 5; i++) s[i][1] = s[i][13 * n + 19] = '*';
    for (int i = n + 2, j = n + 3; i <= 3 * n + 4; i++, j++) {
        s[i][n + 3] = s[i][3 * n + 5] = '@';
        s[i][4 * n + 7] = s[i][7 * n + 11] = '@';
        s[i][j] = '@';
        s[i][i <= 2 * n + 3 ? (10 * n + 15) : (12 * n + 17)] = '@';
    }
    for (int i = 4 * n + 7; i <= 6 * n + 9; i++) s[n + 2][i] = s[2 * n + 3][i] = '@';
    for (int i = 7 * n + 11; i <= 9 * n + 13; i++) s[3 * n + 4][i] = '@';
    for (int i = 10 * n + 15; i <= 12 * n + 17; i++) s[n + 2][i] = s[2 * n + 3][i] = s[3 * n + 4][i] = '@';

    for (int i = 1; i <= 4 * n + 5; i++) {
        for (int j = 1; j <= 13 * n + 19; j++) printf("%c", s[i][j] == 0 ? '.' : s[i][j]);
        printf("\n");
    }
}

H

I

枚举向量 $ii$ ，然后把所有已有的点朝这个方向分别平移 $1,\mathrm{2...}d-11,2...d-1$ 次，得到新的点。这样即可使向量 $ii$ 满足有 $dd$ 个点共线。

但为了防止平移后的点会使得之前的向量有超过 $dd$ 个点共线，每个向量平移距离应是上一个向量平移距离的倍数。

#include <bits/stdc++.h>
using namespace std;
int n, d, vx[7], vy[7];
int inv(int x, int base) {
    int res = 1;
    while (base) {
        if (base & 1)
            res = res * x;
        x = x * x;
        base >>= 1;
    }
    return res;
}
void dfs(int x, int y, int p) {
    if (p == n) {
        printf("%d %d\n", x, y);
        return;
    }
    for (int i = 0; i < d; ++i) dfs(x + i * vx[p], y + i * vy[p], p + 1);
}
int main() {
    scanf("%d%d", &n, &d);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &vx[i], &vy[i]);
        for (int j = 0; j < i; ++j)
            if (vx[i] * vy[j] == vx[j] * vy[i]) {
                --i, --n;
                break;
            }
    }
    for (int i = 0; i < n; ++i) vx[i] *= inv(31, i), vy[i] *= inv(31, i);
    printf("%d\n", inv(d, n));
    dfs(0, 0, 0);
    return 0;
}

J

若进行连续两次相同操作，则相当于没有操作。所以一定是两个操作交替进行。

模拟前几步发现，最终的 $C\mathrm{’}C’$ 会和 $CC$ 相差 $A-2BA-2B$ 的倍数。那么只需判断 $x-Cx-C$ 和 $A-2BA-2B$ 之间的关系。然后令 $C^{\mathrm{\prime }}=B-CC\text{'}=B-C$ 再判断一次。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int A, B, C, x, T;
    cin >> T;
    while (T--) {
        cin >> A >> B >> C >> x;
        if (C == x || B - C == x ||
            A != 2 * B && ((x - C) % (A - 2 * B) == 0 || (x + C - B) % (A - 2 * B) == 0))
            puts("Yes");
        else
            puts("No");
    }
}

K

L

M

设 $f(i,j)f(i,j)$ 表示走到格子 $i,ji,j$ 的情况。当先手必胜时 A 格子为 $11$ 。当先手必败时 B 格子为 $11$ ，当平局时，则 $f(n,m)=1f(n,m)=1$ 且不能走非 . 的格子。

根据 $i+ji+j$ 奇偶性判断先后手，所以先手取 $\max \backslash max$ 转移，后手取 $\min \backslash min$ 转移。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2+9;
char s[N][N];
int f[N][N], n, m;
int dfs(int x, int y) {
    if (f[x][y] >= 0)
        return f[x][y];
    if (s[x][y] == 'A')
        return 1;
    if (s[x][y] == 'B')
        return 4;
    if (x == n && y == m)
        return 2;
    if (x == n)
        return f[x][y] = dfs(x, y + 1);
    if (y == m)
        return f[x][y] = dfs(x + 1, y);
    if ((x + y) % 2 == 0)
        return f[x][y] = dfs(x + 1, y) | dfs(x, y + 1);
    else
        return f[x][y] = dfs(x + 1, y) & dfs(x, y + 1);
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        memset(f, -1, sizeof(f));
        for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
        int ans = dfs(1, 1);
        if (ans & 1)
            printf("yes ");
        else
            printf("no ");
        if (ans & 2)
            printf("yes ");
        else
            printf("no ");
        if (ans & 4)
            puts("yes");
        else
            puts("no");
    }
}