又血崩了一场

1237A Sum of Odd Integers

给一个数$n$，问能否分成$k$个奇数的和。

可以等差数列算出$k$个奇数最小的和，之后判断它和$n$的关系就好，$O(1)$。

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

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, k;
        cin >> n >> k;

        ll mi = ll(1 + 2 * (k - 1) + 1) * k / 2;
        if (n - mi >= 0 && (n - mi) % 2 == 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

1237B Princesses and Princes

有$n$个公主和$n$个王子，每个公主有一列喜欢的王子，如果一个公主喜欢的王子没被分配的时候，她会和最小编号的王子结合。现在可以给一个公主加一个喜欢的人，问是否需要，如果需要，方案是什么。

如果一个公主剩下了，那么一定有一个王子剩下，那么选择一对结合就好，$O(n)$。

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, la = -1;
        cin >> n;
        vector<int> b(n + 1);
        for (int i = 0; i < n; ++i) {
            int k, t, f = 0;
            cin >> k;
            while (k--) {
                cin >> t;
                if (!f && !b[t]) b[t] = f = 1;
            }
            if (!f) la = i + 1;
        }
        if (la == -1) {
            cout << "OPTIMAL" << endl;
            continue;
        }
        for (int i = 1; i <= n; ++i) {
            if (!b[i]) {
                cout << "IMPROVE" << endl
                     << la << ' ' << i << endl;
                break;
            }
        }
    }
    return 0;
}

1237C Game with Chips

在一个$n\times m$的格子上有$n$个可移动点以及对应$n$个目标点，每次操作可以让所有可移动的点全部上下左右移动一格，要求在$2nm$次操作内让所有点经过目标点至少一次，输出方案。

先用$n+m-2$次操作将所有点移动到一角，再用$n\times m-1$次操作遍历所有格子，$O(nm)$。

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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k, a, b;
    cin >> n >> m >> k;
    for (int i = 0; i < k * 2; ++i) {
        cin >> a >> b;
    }
    cout << n + m - 2 + n * (m - 1) + n << endl;
    for (int i = 1; i < m; ++i)
        cout << 'L';
    for (int i = 1; i < n; ++i)
        cout << 'U';
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            if (i & 1)
                cout << 'L';
            else
                cout << 'R';
        }
        cout << 'D';
    }
    cout << endl;
    return 0;
}

1237D Infinite Path

有一个长为$n$的排列，每个位置有一个颜色，问最少做几次置换后某些位置可以产生一个同色的环。

对于一个长$m$的小环来说，有一个性质是：$p^k[x_i] = x_{(i+k)\;mod\;m}$，那么第$k$次置换可以将原来的环分为$GCD(k, m)$个小环，只需要对$p^0$的每个小环枚举因子取同色成立的最小值就好，$O(n^{\frac {4}{3}})$。

D.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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int p[N], c[N];

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> p[i];
        for (int i = 1; i <= n; ++i) cin >> c[i];

        int ans = INF32;
        vector<int> tmp;
        for (int i = 1; i <= n; ++i) {
            if (c[i]) {
                tmp.clear();
                int j = i;
                while (c[j]) {
                    tmp.emplace_back(c[j]);
                    c[j] = 0; j = p[j];
                }
                int m = tmp.size();
                for (int k = 1; k * k <= m; ++k) {
                    if (m % k) continue;
                    for (int strt = 0; strt < k; ++strt) {
                        bool ok = true;
                        j = strt;
                        while (j < m) {
                            if (tmp[j] != tmp[(j + k) % m]) {
                                ok = false; break;
                            }
                            j += k;
                        }
                        if (ok) ans = min(ans, k);
                    }
                    for (int strt = 0; strt < m / k; ++strt) {
                        bool ok = true;
                        j = strt;
                        while (j < m) {
                            if (tmp[j] != tmp[(j + m / k) % m]) {
                                ok = false; break;
                            }
                            j += m / k;
                        }
                        if (ok) ans = min(ans, m / k);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

1237E Count The Blocks

一个长为$n$的字符串，每个位置由$0\sim 9$组成，一个串中连续相同的数字分成一个长$x$的段，问所有字符串中长为$1\sim n$的段的数目分别是多少。

分三种情况DP：

  • 长为$n$的段只有10种；
  • 从左/右开始的，自己有$1$种选法，相邻的位置有$9$种选法，剩下位置任选，$10*9*10^{n-len-1}$；
  • 从中间放的，与上边类似，$10*9*9*10^{n-len-2}$。

也可以找规律，公式是：

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
26
27
28
29
30
31
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

ll a[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef MYDEBUG
    freopen("../0in.txt", "r", stdin);
    freopen("../0out.txt", "w", stdout);
#endif

    int n;
    cin >> n;
    a[n] = 10;
    a[n - 1] = 180;
    if (n > 1)
        a[n - 2] = 2610;
    for (int i = n - 3; i > 0; --i) {
        a[i] = (20 * a[i + 1] - 100 * a[i + 2] % mod + mod) % mod;
    }
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << ' ';
    }
    cout << endl;
    return 0;
}

1237F AND Segments

有一个长为$n$的数列，$m$个形如$\{l,r,x\}$的限制，要$a[l] \& a[l+1] \& \dots \& a[r] = x$，问有多少种不同的数列满足条件。

每一位分开考虑，对于某个$x_i$式这一位为$1$的限制，那么$a[l],a[l+1],…,a[r]$的这一位必须都为$1$。反之，$a[l],a[l+1],…,a[r]$的这一为至少有1个为$0$，可以预处理出某些位置必须放$1$或$1,0$都可以。
设$dp[i][j]$表示处理到第$i$位时上一次放$0$的是第$j$个数：

  • 如果放$1$，那么$dp[i][j] = dp[i-1][j]$；
  • 如果放$0$，那么$dp[i][i] = \sum_{j=1}^{i-1} {dp[i-1][j]}$。
    对于某段必须为0，也就是将$dp[r][0]$到$dp[r][l+1]$置$0$。很明显可以滚动数组，放$0$操作可以用前缀和转移，而清$0$后前面就不用考虑了，也就是每个$j$只会被删$1$次，维护一个指针就好，$O(n)$。
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

int n, m;
vector<int> l, r, x;

ll calc(int p) {
    vector<int> has(n + 2), las(n + 2);
    vector<ll> dp(n + 2);
    p = 1 << p;
    for (int i = 0; i < m; ++i) {
        if (x[i] & p) {
            ++has[l[i]];
            --has[r[i] + 1];
        } else
            las[r[i]] = max(las[r[i]], l[i]);
    }
    for (int i = 1; i <= n; ++i) {
        has[i] += has[i - 1];
    }

    int last = 0;
    ll sum = 1;
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        if (!has[i]) {
            dp[i] = sum;
            sum = sum * 2 % mod;
        }
        ll tmp = 0;
        while (last < las[i]) {
            tmp = (tmp + dp[last++]) % mod;
        }
        sum = (sum - tmp + mod) % mod;
    }
    return sum;
}

int main() {
    int k;
    cin >> n >> k >> m;
    l.resize(m);
    r = x = l;
    for (int i = 0; i < m; ++i)
        cin >> l[i] >> r[i] >> x[i];

    ll ans = 1;
    for (int i = 0; i < k; ++i) {
        ans = ans * calc(i) % mod;
    }
    cout << ans << endl;
    return 0;
}

1237G Letters and Question Marks

有$k$个模式串$t_1,t_2,…,t_k$，每个串带有一个权值，和一个文本串$S$，均有$a\sim n$组成，定义$S$的值是$t_i$在$S$出现的次数$\times$自己的权值。$S$中至多出现$14$个问号，用$a\sim n$内不同的字母填入后，$S$最大的权值是多少。

AC自动机+DP，设$dp[i][j][k]$表示处理到第$i$个字符，在自动机节点$j$，已用字符集的状态是$k$，在枚举到问号的时候枚举转移字符，一路加上权值就可以得到答案，但这样复杂度是$O(\lvert S \rvert*2^{14}*\sum {t})$。
很明显，对于被$?$分割出来的字串，只要知道开头在自动机的节点，就可以确定末尾转移到的节点，那么预处理自动机每个节点开始，$S$中第$i$个字串转移的结果，就可以$O(1)$转移。重设$dp[i][j][k]$，其中$i$表示处理到第$i$个问号，可以发现$i=k$中使用过的字符数量，只需要设二维，$O(|S|*\sum {t} + 14*2^{14}*\sum {t})$

G.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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
const int sz = (1 << 14);

namespace String {
    const int csize = 14;

    class ahcm {
#define nd node[u]
    public:
        struct NODE {
            int ch[csize];
            int fail, val;
        } node[N];
        int numv;
        queue<int> Q, q;

        ahcm() {
            numv = 0;
        }

        void insert(string &s, int &v) {
            int u = 0;
            for (char &c : s) {
                if (!nd.ch[c - 'a'])
                    nd.ch[c - 'a'] = ++numv;
                u = nd.ch[c - 'a'];
            }
            nd.val += v;
        }

        void build() {
            for (int &i : node[0].ch) {
                if (i)
                    Q.emplace(i);
            }
            while (!Q.empty()) {
                int u = Q.front();
                Q.pop();

                q.emplace(u);
                for (int i = 0; i < csize; ++i) {
                    if (nd.ch[i]) {
                        node[nd.ch[i]].fail = node[nd.fail].ch[i];
                        node[nd.ch[i]].val += node[node[nd.ch[i]].fail].val;
                        Q.emplace(nd.ch[i]);
                    } else
                        nd.ch[i] = node[nd.fail].ch[i];
                }
            }
        }

        pil calc(int u, string &s) {
            ll v = 0;
            for (char &c : s) {
                u = nd.ch[c - 'a'];
                v += nd.val;
            }
            return {u, v};
        }
    };
}
using namespace String;

ahcm am;
pil go[1005][18];
ll dp[1005][sz];

int main() {
    int n, v;
    cin >> n;
    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s >> v;
        am.insert(s, v);
    }
    am.build();

    cin >> s;
    int la = 0;
    vector<string> seg;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '?') {
            seg.push_back(s.substr(la, i - la));
            la = i + 1;
        }
    }
    seg.push_back(s.substr(la));
    for (int i = 0; i < seg.size(); ++i) {
        for (int j = 0; j <= am.numv; ++j) {
            go[j][i] = am.calc(j, seg[i]);
        }
    }

    for (int i = 0; i <= am.numv; ++i) {
        for (int j = 0; j < sz; ++j) {
            dp[i][j] = -INF64;
        }
    }
    dp[go[0][0].first][0] = go[0][0].second;
    for (int i = 0; i < sz; ++i) {
        for (int j = 0; j <= am.numv; ++j) {
            if (dp[j][i] == -INF64) continue;
            for (int k = 0; k < 14; ++k) {
                if ((i >> k) & 1) continue;
                int to = am.node[j].ch[k];
                int ns = i | (1 << k);
                int count = __builtin_popcount(ns);
                if (count >= seg.size()) continue;
                int end = go[to][count].first;
                ll val = go[to][count].second + am.node[to].val;
                dp[end][ns] = max(dp[end][ns], dp[j][i] + val);
            }
        }
    }
    ll ans = -INF64;
    int cnt = seg.size() - 1;
    for (int i = 0; i < sz; ++i) {
        for (int j = 0; j <= am.numv; ++j) {
            if (__builtin_popcount(i) == cnt)
                ans = max(ans, dp[j][i]);
        }
    }
    cout << ans << endl;
    return 0;
}