忘记比赛时间了…

1332A Exercising Walk

有一个机器人开始位于$(x,y)$，现在要求上下左右分别走$a,b,c,d$步，要求路径在$(x1,y1),(x2,y2)$为对角的矩形范围内，问是否可行。

横竖可以分别考虑，如果最终点在限制范围内，一定可以有满足条件的路，但当给的矩形长或宽为$1$的时候要特判，$O(1)$。

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d, x, y, x1, y1, x2, y2, f = 0;
        cin >> a >> b >> c >> d
            >> x >> y >> x1 >> y1 >> x2 >> y2;
        if ((x1 == x2) && (a || b))
            f = 1;
        if ((y1 == y2) && (c || d))
            f = 1;
        b -= a, d -= c;
        if (b + x < x1 || b + x > x2)
            f = 1;
        if (d + y < y1 || d + y > y2)
            f = 1;
        if (f)
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    return 0;
}

1332B Composite Coloring

有$n$个$\le 1000$的数，要求涂色相同的数字不互质，最多$11$种颜色，问一种合法的涂色方案。

读反要求了，刚了好一会。。只要按最小质因子涂色就行，因为第$11$个因子是$31$，那么比它大的合数一定在这$11$个质数内有质因子，$O(n^2)$。

B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, t;
        cin >> n;
        vector<int> ans(n), tmp[1001];
        for (int i = 0; i < n; ++i) {
            cin >> t;
            for (int j = 2; j < 1001; ++j) {
                if (t % j == 0) {
                    tmp[j].emplace_back(i);
                    break;
                }
            }
        }
        int cnt = 0;
        for (auto &i : tmp) {
            if (!i.empty()) ++cnt;
            for (int j : i) ans[j] = cnt;
        }

        cout << cnt << endl;
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    }
    return 0;
}

1332C K-Complete Word

一个字符串$S$，要求$T$是回文的，且$k$是它的周期，一次操作可以换一个字符，问最少操作次数让$S$满足要求。

因为$S$对应的合法串是固定的，那么按题意取某些对应位置暴力就行了，每个位置只访问一次，$O(n)$。

C.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    string s;
    while (q--) {
        int n, k;
        cin >> n >> k >> s;
        int ans = 0;
        vector<int> v(n);
        for (int i = 0; i < k; ++i) {
            vector<int> cnt(26);
            int tmp = 0, num = 0;
            for (int j = i; j < n; j += k) {
                if (!v[j]) {
                    v[j] = 1;
                    ++cnt[s[j] - 'a'];
                    ++num;
                }
                if (!v[n - j - 1]) {
                    v[n - j - 1] = 1;
                    ++cnt[s[n - j - 1] - 'a'];
                    ++num;
                }
            }
            for (int j = 0; j < 26; ++j) {
                tmp = max(tmp, cnt[j]);
            }
            tmp = num - tmp;
            ans += tmp;
        }
        cout << ans << endl;
    }
    return 0;
}

1332D Walk on Matrix

现在有一个假$DP$算法，求一个矩阵从左上到右下角路径各店权值$\&$起来的最大权值，要求构造一个矩阵$(n\leq 500)$，是真实值和算法得到的结果相差$k$。

假的原因是贪心对$\&$不成立。其实只要构造两条路的矩阵，一条的值稍大，另一条稍小，但到终点的时候大值没办法取就好，$O(1)$。
（听说了很多乱搞的做法，但其实样例2提醒挺明显的。。。）

D.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main() {
    int k;
    cin >> k;
    cout << "3 3" << endl;
    int c = 1 << (32 - __builtin_clz(k));
    cout << (c + k) << ' ' << k << " 0" << endl
         << c << ' ' << k << " 0" << endl
         << c << ' ' << (c + k) << ' ' << k << endl;
    return 0;
}

1332E Height All the Same

一个大小为$n\times m$的矩阵，初始值为${ij}$，每次操作可以把一个位置增加$2$，或把相邻的两个位置各增加$1$，要求$L \leq a_{ij} \leq R$，问这样的矩阵有几个。

其实很容易想到奇偶性的问题，操作二可以把相邻的两个数奇偶性取反，第一个操作可以把奇偶性相同的数补成相同值。那么如果原始矩阵里奇数的个数或偶数的个数为偶数，就一定可以把所有数奇偶性转化相同。
问题就变成了$n\times m$各数字有几种放法，我们把总数分奇偶考虑：

  • 如果$n\times m$是奇数，那么所有数字可以随便放，答案就是$(R-L+1)^{n\times m}$
  • 如果$n\times m$是偶数，设$odd$为$a_{ij}$为奇数个数，$even$为偶数个数，那么$odd$和$even$都需要取偶数，设$x$为$[L,R]$中的奇数个数，$y$为$[L,R]$中的偶数个数，答案就是$\sum_{odd=2k}^{n\times m}C_{odd}^{n\times m - odd}x^{odd}y^{even}$。可以发现这其实就是二项式中的偶数项的和，因此化简为：$O(\log nm)$
E.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return res;
}

int main() {
    ll l, r, n, m;
    cin >> n >> m >> l >> r;
    n *= m;
    if (n & 1) {
        cout << qpow(r - l + 1, n) << endl;
    } else {
        ll odd = (r + 1) / 2 - l / 2;
        ll even = r / 2 - (l - 1) / 2;
        cout << ((qpow(even + odd, n) + qpow(even - odd, n)) * (mod + 1) / 2) % mod << endl;
    }
    return 0;
}

1332F Independent Set

有一颗无根树，现在求出各个边导出子图各独立集个数的和。

首先一颗树的独立集个数可以树$dp$得到，此题要求所有的边导出子图求和，实际上相当于删掉了一些边，其中如果有孤立点的话不能选中这个点。做法是维护$3$个值，$dp[u][0]$表示点$u$不被选中时的答案，$dp[u][1]$表示点$u$不被选中时的答案，$dp[u][2]$表示点$u$和子结点一条边都不连时的答案。在$DFS$中用$num0$表示以$u$的子结点$v$为根的子树的全部答案，用$num1$表示子树的全部答案去掉$v$孤立的答案，那么转移：

  • $dp[u][0]=\prod (num0+num1)$，即当$u$选中时，子结点状态任意:
    • 当$u$不选时，选$e(u,v)$这条边，那么有$num1$的贡献。
    • 当$u$不选时，不选$e(u,v)$这条边，那么有$num0$的贡献（因为不能让$v$孤立且被选）。
  • $dp[u][1]=\prod (num0+dp[v][0])$，当$u$选中时，子结点不能被选；
    • 当$u$选中时，选$e(u,v)$这条边，那么有$dp[v][0]$的贡献（因为相邻结点不能再被选中）。
    • 当$u$选中时，不选$e(u,v)$这条边，那么有$num0$的贡献（同上$2$）。
  • $dp[u][2]=\prod num0$，
    • 当$u$孤立时，那么有$num0$的贡献（同上$2$）。
F.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;

ll dp[N][3];
vector<int> g[N];

void dfs(int u, int fa = 0) {
    dp[u][0] = dp[u][1] = dp[u][2] = 1;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        ll num1 = dp[v][0] + dp[v][1] - dp[v][2];
        ll num0 = dp[v][0] + dp[v][1];
        dp[u][0] = dp[u][0] * (num1 + num0) % mod;
        dp[u][2] = dp[u][2] * (num1) % mod;
        dp[u][1] = dp[u][1] * (num1 + dp[v][0]) % mod;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    dfs(1);
    cout << (dp[1][0] + dp[1][1] - dp[1][2] - 1 + 2 * mod) % mod << endl;
    return 0;
}