AutumnKite's Blog

一个 ZJ 小蒟蒻的博客

终于上 IM 了(

A - Bad Ugly Numbers

题目传送门

题解

为什么您们都能想到构造 \(2333\cdots 333\) 啊 QAQ

显然一个能被 \(p\) 整除的数,加或减一个不能被 \(p\) 整除的数后,不能被 \(p\) 整除。

我们考虑 \(777\cdots 777\) 能被 \(7\) 整除,而 \(777\cdots 77x\)\(x > 0\))不能被 \(7\) 整除。

根据小学数学知识,能被 \(4\) 整除的数的特征是最后两位能被 \(4\) 整除,由于 \(74\bmod 4\ne 0\),所以我们构造 \(777\cdots 774\) 即可。

注意需要特判 \(n=1\)

代码

1
2
3
4
5
6
7
int n;
void solve(){
read(n);
if (n == 1) return print(-1), void(0);
for (register int i = 1; i < n; ++i) putchar('7');
putchar('4'), putchar('\n');
}

B - Maximums

题目传送门

题解

\(c_i\) 的定义可得 \[\begin{aligned} b_i&=a_i-c_i \\&=a_i-\max\{0,\max\limits_{j=1}^{i-1} a_j\} \end{aligned}\]

移项后可得 \[a_i=b_i+\max\{0,\max\limits_{j=1}^{i-1}a_j\}\]

我们只要在递推的同时维护 \(a_1,a_2,\cdots,a_{i-1}\) 的最大值即可。

时间复杂度 \(O(n)\)

代码

1
2
3
4
5
6
7
8
9
10
11
const int N = 200005;
int n, a[N];
void solve(){
read(n);
for (register int i = 1; i <= n; ++i) read(a[i]);
long long now = 0;
for (register int i = 1; i <= n; ++i)
if (a[i] > 0) now += a[i], print(now, ' ');
else print(now + a[i], ' ');
putchar('\n');
}

C - Permutation Partitions

题目传送门

题解

考场上我看到本题一脸懵逼,我发现我好像不会第一问...

冷静一下,发现显然答案的上界是取最大的 \(k\) 个数,即 \((n-k+1)+(n-k+2)+\cdots+n=\frac{(2n-k+1)k}{2}\)

我们可以在原排列中标记出这最大的 \(k\) 个数,记从左往右第 \(i\) 个被标记的位置为 \(x_i\)

我们要把原排列划分成 \(k\) 段意味着我们要找到 \(k-1\) 个分界点,并且我们现在要求两个分界点之间恰好包含一个被标记的数。

那么显然第 \(i\) 个分界点应该选在 \(x_i\)\(x_{i+1}\) 之间。

每个分界点的选择是独立的(即不会影响其他分界点的选择),所以根据乘法原理,把每个分界点的方案数相乘即可。

时间复杂度 \(O(n)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 200005, P = 998244353;
int n, k, a[N];
void solve(){
read(n), read(k);
long long sum = 0;
int lst = 0, ans = 1;
for (register int i = 1; i <= n; ++i){
read(a[i]);
if (a[i] > n - k){
sum += a[i];
if (lst) ans = 1ll * ans * (i - lst) % P;
lst = i;
}
}
print(sum, ' '), print(ans);
}

D2 - Prefix-Suffix Palindrome (Hard version)

题目传送门

题解

考场上看到本题的第一想法是枚举前后缀匹配的长度 \(l\),然后要求从 \(l+1\) 开始的最长回文串或者以 \(n-l\) 结尾的最长回文串。

刚打算去隔壁 最长双回文串 复制一个代码,意识到了不对...

如果求出来的回文串与前后缀有重叠怎么办?

考虑上面这个想法用暴力怎么实现。在我们将原串中间插入 # 后,用 manacher 算法以 \(i\) 为回文中心的回文半径 \(d_i\)

然后我们枚举前后缀匹配长度 \(l\),分两种情况:

  • 对于所有 \(l+1\le i\le \frac{|s|+1}{2}\)\(i-d_i+1\le l+1\),求出 \(i\) 的最大值;
  • 对于所有 \(\frac{|s|+1}{2}\le i\le n-l\)\(i+d_i-1\ge n-l\),求出 \(i\) 的最小值。

可以发现,\(l\) 越大,越容易满足限制,越容易使得 \(i\) 取到极值。

所以我们求出最大的 \(l\) 以后用上面的暴力实现即可。

如果你不怕被 hack 的话 manacher 也可以用哈希实现。

时间复杂度 \(O(n)\)

代码

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
const int N = 2000005; // 注意数组开大一倍
int n, d[N];
char s[N];
void manacher(int *d, char *s, int n){
for (register int i = 1, m = 0, r = 0; i <= n; ++i){
d[i] = i > r ? 0 : std::min(r - i + 1, d[m - (i - m)]);
while (i - d[i] > 0 && i + d[i] <= n && s[i - d[i]] == s[i + d[i]]) ++d[i];
if (i + d[i] - 1 > r) m = i, r = i + d[i] - 1;
}
}
void solve(){
n = reads(s + 1);
for (register int i = n; i; --i) s[i << 1] = s[i], s[i << 1 | 1] = '#';
s[1] = '#', n = n * 2 + 1;
manacher(d, s, n);
// for (register int i = 1; i <= n; ++i) debug("%d ", d[i]); debug("\n");
int len = 0;
for (register int i = 1; i <= n / 2; ++i)
if (s[i] != s[n - i + 1]) break;
else ++len;
// debug("%d\n", len);
int d1 = 0, d2 = 0;
for (register int i = len + 1; i <= (n + 1) / 2; ++i)
if (i - d[i] + 1 <= len + 1) d1 = std::max(d1, (i - len) * 2 - 1);
for (register int i = (n + 1) / 2; i <= n - len; ++i)
if (i + d[i] - 1 >= n - len) d2 = std::max(d2, (n - len - i + 1) * 2 - 1);
if (d1 > d2){
for (register int i = 1; i <= len + d1; ++i)
if (s[i] != '#') putchar(s[i]);
for (register int i = n - len + 1; i <= n; ++i)
if (s[i] != '#') putchar(s[i]);
}
else{
for (register int i = 1; i <= len; ++i)
if (s[i] != '#') putchar(s[i]);
for (register int i = n - len - d2 + 1; i <= n; ++i)
if (s[i] != '#') putchar(s[i]);
}
putchar('\n');
}

E - Bombs

题目传送门

题解

发现答案单调递减,可以考虑枚举答案 \(x\)

\(> x\)(即必须炸掉的数)的位置置为 \(1\),炸弹置为 \(-1\),其他位置置为 \(0\)

则合法的条件是所有后缀和 \(\le 0\)

用线段树维护即可。

时间复杂度 \(O(n\log n)\)

别问我为什么对,感觉挺对的就行了(雾

代码

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
const int N = 300005;
int n, p[N], q[N], pos[N];
struct Segment_Tree{
int mx[N << 2], lz[N << 2];
void add(int u, int v){ mx[u] += v, lz[u] += v; }
void down(int u){
add(u << 1, lz[u]), add(u << 1 | 1, lz[u]), lz[u] = 0;
}
void modify(int u, int l, int r, int L, int R, int v){
if (L <= l && r <= R) return add(u, v), void(0);
int md = (l + r) >> 1;
down(u);
if (L <= md) modify(u << 1, l, md, L, R, v);
if (R > md) modify(u << 1 | 1, md + 1, r, L, R, v);
mx[u] = std::max(mx[u << 1], mx[u << 1 | 1]);
}
}T;
void solve(){
read(n);
for (register int i = 1; i <= n; ++i) read(p[i]), pos[p[i]] = i;
for (register int i = 1; i <= n; ++i) read(q[i]);
print(n, ' ');
int now = n;
T.modify(1, 1, n, 1, pos[n], 1);
for (register int i = 1; i < n; ++i){
T.modify(1, 1, n, 1, q[i], -1);
while (T.mx[1] <= 0) --now, T.modify(1, 1, n, 1, pos[now], 1);
print(now, ' ');
}
}

F1 - Wise Men (Easy Version)

题目传送门

题解

考场上看到 Easy Version \(n\le 14\),Hard Version \(n\le 18\),莫名就想到了 meet in middle...

可以预处理出 \(f_{S,T,i}\) 表示当前排列中数的集合为 \(S\),导出的 01 字符串为 \(T\),且排列中最后一个数为 \(i\) 的方案数。

然后考虑 meet in middle,合并两边的方案。

问题来了,我好像不会快速合并两边的方案 QAQ

但是问题不大,我们可以 暴力合并

直接枚举左边的数集 \(S\),最后的 01 串 \(T\),以及中间相邻的两个数,显然方案数可以利用 \(f\) 进行计算。

但是,你可能需要一些卡常技巧(设两边的大小分别为 \(B_1,B_2\)):

  1. \(f\) 数组只需要预处理所有 \(|S|=B_1\)\(|S|=B_2\) 的位置,可以直接枚举所有排列进行统计,不需要进行 DP。
  2. 显然 01 串反转以后答案是不变的,所以我们只计算 \(T\le \operatorname{rev}(T)\) 的位置即可。
  3. 可以预处理 \(2^n-1,2^{B_1-1}-1,2^{B_2-1}-1\) 的值来减少运算次数。
  4. 由于枚举 \(T\) 以后我们可以知道中间相邻两个数是否有边,我们可以预处理出与一个点有边/无边的点来快速枚举。
  5. 根据代码常数调整 \(B_1,B_2\) 的大小。

为了保险,你可以再加上 Ofast 和 O3 优化。

理论时间复杂度 \(O(C_{n}^{B_1}(B_1!+B_2!+2^n n^2))\),事实上有好几个 \(\frac{1}{2}\) 的常数。

代码

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
int n, E[14][14], bitcnt[1 << 14], rev[1 << 14], p[14], f[1 << 14][1 << 6][14];
long long ans[1 << 14];
std::vector<int> G[14][2];
void solve(){
read(n);
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < n; ++j){
while (!isdigit(E[i][j] = getchar())) ;
E[i][j] ^= '0';
G[i][E[i][j]].push_back(j);
}
bitcnt[0] = 0;
for (register int i = 1; i < (1 << n); ++i) bitcnt[i] = bitcnt[i >> 1] + (i & 1);
rev[0] = 0;
for (register int i = 1; i < (1 << (n - 1)); ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << (n - 2);
int B1 = n >> 1, B2 = n - B1;
for (register int S = 0; S < (1 << n); ++S)
if (bitcnt[S] == B1 || bitcnt[S] == B2){
int cnt = 0;
for (register int i = 0; i < n; ++i)
if (S >> i & 1) p[cnt++] = i;
while (1){
int T = 0;
for (register int i = 0; i < cnt - 1; ++i)
if (E[p[i]][p[i + 1]]) T |= 1 << i;
++f[S][T][p[cnt - 1]];
if (!std::next_permutation(p, p + cnt)) break;
}
}
int U = (1 << n) - 1, U1 = (1 << (B1 - 1)) - 1, U2 = (1 << (B2 - 1)) - 1;
for (register int S = 0; S < (1 << n); ++S)
if (bitcnt[S] == B1){
for (register int T = 0; T < (1 << (n - 1)); ++T)
if (T <= rev[T]){
int T1 = T & U1, T2 = rev[T] & U2, t = (T >> (B1 - 1)) & 1, _S = U ^ S;
for (register int i = 0; i < n; ++i)
if (f[S][T1][i])
for (int j : G[i][t])
ans[T] += f[S][T1][i] * f[_S][T2][j];
}
}
for (register int T = 0; T < (1 << (n - 1)); ++T)
if (T <= rev[T]) print(ans[T], ' '); else print(ans[rev[T]], ' ');
putchar('\n');
}

最后一分钟绝杀的感觉真的非常舒适(

F2 - Wise Men (Hard Version)

题目传送门

来了来了,来填坑了。

题解

发现既有有边又有没边的限制非常难搞,于是我们考虑容斥,即计算 \(ans_A\) 为对于所有 \(A\) 中为 \(1\) 的位置 \(i\),满足 \(p_i\)\(p_{i+1}\) 有边的排列 \(p\) 的数量(对于 \(0\) 的位置没有限制)。

计算出 \(ans_A\) 后,只要用类似于「逆高维前缀和」的方法,就可以在 \(O(2^nn)\) 求出真正的答案。

考虑如何计算 \(ans_A\)。发现 \(ans_A\) 的值只与 \(A\)\(1\) 连续段的长度形成的可重集合有关。如 \(A=\{0,1,1,1,0,0,1\}\) 时,所有 \(1\) 连续段长度形成的集合就是 \(\{1,1,2,4\}\)(原长加 \(1\))。

可以发现,对于任意 \(A\),对应的 \(1\) 连续段长度形成的可重集合中所有元素的和一定恰好为 \(n\)。这意味着不同的集合数量等于 \(n\) 的划分数。

对于一个划分 \(P=\{a_1,a_2,\cdots,a_k\}\),可以发现对应的方案数实质上是在原图中选出 \(k\) 条不相交的简单路径,满足第 \(i\) 条路径的点数为 \(a_i\) 的方案数。

那么我们先考虑选 \(1\) 条路径。可以用 DP 求出 \(f_{u,S}\) 表示当前在节点 \(u\),经过的点集为 \(S\) 时的路径条数,进而求出 \(g_S\) 表示经过的点集为 \(S\) 的路径条数。

那么对于一个划分 \(P=\{a_1,a_2,\cdots,a_k\}\),答案即为 \[\sum_{S_1,S_2,\cdots,S_k} \left[|S_i|=a_i\right]\left[\forall i\ne j:S_i\cap S_j=\varnothing\right]\left[\bigcup\limits_{i=1}^{k}S_i=U\right]\prod\limits_{i=1}^{k} g_{S_i}\]

其中 \(U\) 表示全集。

注意到由于 \(\sum\limits_{i=1}^{k} a_i=n\),后面两个条件只需要保留一个即可。第二个条件很难处理,我们考虑保留第三个。若不考虑前两个条件,只考虑第三个条件,只需要用 FWT 即可方便地求出答案。

存在第一个条件时,我们只要将 \(g\) 加上一维,\(g_{l,S}\) 表示长度为 \(l\),经过点集为 \(S\) 的简单路径数量。对于 \(|S|\ne l\) 的位置就置为 \(0\)。那么答案式子变成了 \[\sum_{S_1,S_2,\cdots,S_k} \left[\bigcup\limits_{i=1}^{k}S_i=U\right]\prod\limits_{i=1}^{k} g_{a_i,S_i}\]

直接将所有 \(g_i\) 进行一次 FWT 后,枚举划分时直接点乘。由于我们实际只需要卷积结果中 \(2^n-1\) 位置的值,所以我们不需要每次 IFWT,直接根据实际意义用容斥就可以 \(O(2^n)\) 求出这个值。

总时间复杂度 \(O(2^n(P(n)+n^2))\),其中 \(P(n)\) 表示 \(n\) 的划分数。

实现得不好可能会变成 \(O(2^n(S(n)+n^2))\)\(O(2^nn(P(n)+n))\),其中 \(S(n)\) 表示 \(n\) 的所有划分的大小之和。

代码

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
int n;
std::vector<int> bitcnt;
std::vector<std::vector<long long>> f;
std::vector<std::vector<long long>> g;
std::map<std::vector<int>, std::vector<int>> part;
std::vector<long long> ans;
void dfs(int r, const std::vector<int> &l, const std::vector<long long> &s){
if (!r){
long long res = 0;
int mask = (1 << n) - 1;
for (register int i = 0; i < (1 << n); ++i)
if (bitcnt[mask ^ i] & 1) res -= s[i]; else res += s[i];
const std::vector<int> &p = part[l];
for (int v : p) ans[v] += res;
return;
}
int lst = l.empty() ? 1 : l.back();
for (register int k = lst; k <= r; ++k){
if (k < r && r - k < k) continue;
std::vector<int> nl(l);
std::vector<long long> ns(s);
nl.push_back(k);
for (register int i = 0; i < (1 << n); ++i) ns[i] *= g[k - 1][i];
dfs(r - k, nl, ns);
}
}
void solve(){
read(n);
std::vector<std::vector<int>> E(n);
for (register int i = 0; i < n; ++i)
for (register int j = 0; j < n; ++j){
char ch;
while (!isdigit(ch = getchar())) ;
if (ch == '1') E[i].push_back(j);
}
bitcnt.resize(1 << n);
bitcnt[0] = 0;
for (register int i = 1; i < (1 << n); ++i) bitcnt[i] = bitcnt[i >> 1] + (i & 1);
f.resize(n, std::vector<long long>(1 << n, 0));
g.resize(n, std::vector<long long>(1 << n, 0));
for (register int i = 0; i < n; ++i) f[i][1 << i] = 1;
for (register int S = 1; S < (1 << n); ++S)
for (register int i = 0; i < n; ++i)
if (f[i][S]){
g[bitcnt[S] - 1][S] += f[i][S];
for (int v : E[i]) if (!(S >> v & 1)) f[v][S | (1 << v)] += f[i][S];
}
for (register int k = 0; k < n; ++k)
for (register int i = 0; i < n; ++i)
for (register int S = 0; S < (1 << n); ++S)
if (S >> i & 1) g[k][S] += g[k][S ^ (1 << i)];
for (register int S = 0; S < (1 << (n - 1)); ++S){
std::vector<int> p;
int x = 1;
for (register int i = 0; i < n - 1; ++i)
if (S >> i & 1) ++x; else p.push_back(x), x = 1;
p.push_back(x);
std::sort(p.begin(), p.end());
part[p].push_back(S);
}
ans.resize(1 << (n - 1), 0);
dfs(n, std::vector<int>(), std::vector<long long>(1 << n, 1));
for (register int i = 0; i < n - 1; ++i)
for (register int S = 0; S < (1 << (n - 1)); ++S)
if (S >> i & 1) ans[S ^ (1 << i)] -= ans[S];
for (long long v : ans) print(v, ' ');
putchar('\n');
}

G - Spiderweb Trees

题目传送门

tourist 都没过的题,鸽了鸽了。


深深明白自己的弱小

评论

如需要头像服务请在「邮箱」中填写 Gravatar 中绑定的邮箱