抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

ひと結び、人を結んで

记录

比赛的那天 KS 酱办生日聚会,所以玩的有点晚——于是为了避免掉分就又开了个小号——结果还真的算是预防成功了((只能说不愧是我==

上一场一样的出题人,也是熟悉的五个题目;但是这场总感觉比之前那一场要难一些——可能出题人不经意间触及了我较多的知识盲区吧(

题解

A - Tit for Tat

右手就行可是我白给了一发;只要取出前面的加到最后一个元素上就行了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 100;
int a[N];

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int T = $.nextInt(), n, k;
while (T --) {
input, n, k;
$.nextArray(a + 1, a + 1 + n);
int l = 1, r = n;
while (k && l < r) {
auto ded = min(k, a[l]);
k -= ded, a[l] -= ded, a[r] += ded;
++ l;
}
$.putArray(a + 1, a + 1 + n);
}

return 0;
}

到底是什么样的小天才才能写出 ++ l, -- r 这种代码呢?以为很对称🐎(

B - AGAGA XOOORRR

考虑到最后只可能剩下两个相同的元素或三个相同的元素——因为更多的元素都可以合并到这两种情况上,所以只需要分别处理即可:

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
const int N = 2060;
uint a[N], sum[N];

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int T = $.nextInt(), n;
while (T --) {
$(n).nextArray(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++ i)
sum[i] = sum[i - 1] ^ a[i];
bool found = false;
for (int i = 1; i <= n; ++ i)
if (sum[i] == (sum[n] ^ sum[i]))
found = true;
for (int i = 1; i <= n; ++ i)
for (int j = i; j <= n; ++ j)
if (sum[i] == (sum[j] ^ sum[i]) &&
sum[i] == (sum[n] ^ sum[j]))
found = true;
$.put(found ? "YES" : "NO");
}

return 0;
}

之前白给成了直接排除一个元素,显然这是不科学的(

C - Baby Ehab Partitions Again

提供长度为 \(n \leq 100\) 的数组 \(a\),你要从中删除一些元素,使得不可以将这个数组拆分成两个部分,使得两个部分的和相等;要求最小化删除元素的数量并输出删除元素的坐标。

首先,显然当 \(\sum_{i = 1}^n a_i\) 是奇数的时候不用删除任何元素;然后,为偶数情况下可以进行背包 \(DP\) 来判断是否可能完成这样的划分;如果可以,那么问题就变成了如何删除元素。

不难想到最多只会删除一个元素,那么问题就是删除什么样的元素;我最开始因为删除最小的元素然后白给了一罚时,因为这样是不正确的——比如删除 2,可以通过交换两个 2 和一个 5 来使得再次平衡;那么我们在考虑其他的一定可行的情况,就不难想到删除一个奇数。

如果整个数组都是偶数怎么办?那么我们可以整体右移 \(1\) 位,显然和原数组是等价的;我们可以一直右移,直到我们找到了可以删除的奇数为止;显然,这一定可以找到;

从右移等价,我们可以联想到整个数组除以任何同一个数都是等价的;所以,一个最简单的方法就是首先约去整个数组的 \(\gcd\),然后找到一个奇数删除就行了——因为是等价的,所以这样的删除是合理的;

代码实现

这个使用 bitset 的可行性背包实现属实颇有雅趣(

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
const int N = 2050, M = 110;
int a[N];

bool check(int n) {
int sum = accumulate(a + 1, a + 1 + n, 0);
if (sum % 2) return false;
bitset<N * M> dp;
dp.set(0);
for (int i = 1; i <= n; ++ i)
dp |= (dp << a[i]);
return dp[sum / 2];
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int n = $.nextInt();
$.nextArray(a + 1, a + 1 + n);
if (check(n)) {
int g = 0;
for (int i = 1; i <= n; ++ i)
g = gcd(g, a[i]);
for (int i = 1; i <= n; ++ i)
if (a[i] / g % 2) {
$.put(1).put(i);
break;
}
} else $.put(0);

return 0;
}

于是这个卵题我白给了近十发,,我是真的菜(

D - Cut

给一个长度为 \(n \leq 10^5\) 的数组 \(a\),进行 \(q\leq10^5\) 次询问:每次询问关于一个区间 \([l, r]\),将它分成的最少的段数,使得每一段的 \(\text{LCM}\) 都和连乘的乘积相等;求这个段数。

首先,不难意识到 \(\text{LCM}\) 和连乘积相等就是说这一段的 \(\gcd\)\(1\)。那么问题就转化为了对于任意段 \([l, r]\),将它划分成互质的最小的段数。

那么一种很显然的想法就是对于范围内的所有质数(约 \(9600\) 个)分别维护一个列表,包含了包含它为质因数的数字的下标;然后对于一个位置,对于它的每一个质因子在对应的表上二分查找出下一个位置,取最小值作为下一个区间开始的备选位置;但是这样做显然非常的啥b,因为有显而易见地简单优化但是我也显而易见的没有想到

  • 我们可以倒着维护每一个质数的下一个位置,这样就不用对每个质数二分查找了
  • 倒着转移的时候也考虑后一个位置的备选位置,这样就不用考虑到备选区间之间的冲突了

那么这样,我们就可以维护出一个表 \(F_i\),表示从 \(i\) 开始可以转移到的最远的备选位置;

但是这样还存在一个问题:如果所有的数字都是 \(1\),那么上面的做法会被卡成 \(n^2\);因此,为了能够快速的跳转求出区段数,我们可以利用倍增的思想,维护下两个、下四个备选位置;这样,就可以在 \(\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
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
const int N = 1e5 + 5;
const int M = 9600;
int a[N], f[20][N], to[M];

auto decomposition(const int n) {
static vector<int> p;
static vector<vector<int>> de(n);
for (int i = 2; i < n; ++i)
if (de[i].empty()) {
for (int j = i; j < n; j += i)
de[j].push_back(i);
p.push_back(i);
}
return make_pair(ref(p), ref(de));
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int n, q, l, r;
$(n, q).nextArray(a + 1, a + 1 + n);
auto [p, de] = decomposition(N);

unordered_map<int, int> desc;
const auto ps = p.size();
const auto bound = n + 1;
desc.reserve(ps * 4);
for (int i = 0; i < ps; ++ i) {
desc[p[i]] = i, to[i] = bound;
}

f[0][bound] = bound;
for (int i = n; i; -- i) {
f[0][i] = f[0][i + 1];
for (auto j : de[a[i]]) {
minimize(f[0][i], to[desc[j]]);
to[desc[j]] = i;
}
}
for (int i = 1; i < 20; ++ i)
for (int j = 1; j <= bound; ++ j)
f[i][j] = f[i - 1][f[i - 1][j]];

while (q --) {
$(l, r);
uint ans = 0;
for (int i = 19; i >= 0; -- i)
if (f[i][l] <= r) {
ans += (1u << i);
l = f[i][l];
}
$.put(ans + 1);
}

return 0;
}

即使可以想到正确的维护方法,但是倍增的思想也不能不说是十分的高妙…… 学到许多(

E - Baby Ehab Plays with Permutations

现在有长度为 \(n \leq 10^9\) 的排列 \(\{1, \dots,n\}\),可以进行对于两个不同的下标两两交换的操作 \(k \leq 200\) 次;问对于 \([1, k]\) 次操作可以得到的不同的排列数量;

首先,先说明一种贪心地将长度为 \(n\) 的排序 \(p\) 复位的做法——对于排列的最后一个位置 \([n]\)

  • 如果 \(p_n = n\),那么可以忽略这个位置;将原排列看作长度为 \(n - 1\)
  • 否则,将 \(p_n\)\(p_{p_n}\) 交换位置;此时至少可以使得 \(p_n\) 复位,继续递归,但是操作次数 \(+1\)

可以证明,这样处理完整个序列就可以得到将序列 \(p\) 复位的最小操作次数。

那么,基于这种思想,我们可以构造出一种递推关系——假设 \(F_{n, j}\) 表示了进行 \(j\) 次交换后可以复位的、长度为 \(n\) 的排列(或者说从复位的排列开始,进行 \(j\) 次交换可以产生的排列)的数量:

  • \(j = 0\):此时,只有初始复位的排列一种情况;因此总是为 \(1\)
  • 现在,我们考虑通过 \(F_{n - 1}\)\(F_n\) 转移;即每次将 \(n\) 放入长度为 \(n - 1\) 的排列中:
    • 如果新放入的 \(n\) 不进行交换,那么对答案没有贡献:可以直接转移
    • 如果和前面的 \(n - 1\) 个位置中的一个进行交换:那么贡献 \(1\) 次次数,有 \(n - 1\) 种转移方法
  • 综上所述,可以得到递推公式 \(F_{n, j} = F_{n - 1, j} + (n - 1) \cdot F_{n - 1, j - 1}\)

那么,基于这个动态规划,我们可以有两种不同的做法:

阳间做法

注意到题目中的 \(k\) 非常的小,所以即使进行 \(k\) 次交换,最多只会使得 \(2k\) 个位置错位;所以我们每次只需要能选出错位的位置长度,然后对于在这个范围内的长度求 \(F_{n, j}\) 即可;那么,一种很显然的做法就是确定一个允许的错位位置的长度 \(i\),对于这个长度求 \(F\),最后统一考虑——

那么,答案长下面这样吗? \[ \text{ans?}_{j} = \sum_{i = 0}^{\min(2j, n)} \mathbf{C}_n^{i} \times F_{i, j} \] 不,当然不对——因为我们的 \(F_{n, j}\) 可能实际上只变动了其中很少一部分的位置——而这样的话就会不可避免的和其他情况重合,导致计数的不准确;所以为了解决这个问题,我们可以考虑在错排问题种采用的解决方法——使用容斥原理包含/排除重复的部分:

  • 现在,我们定义 \(G_{n, j}\)\(F_{n, j}\) 类似,但是每一个位置都是错排的情况数量
  • 然后,我们在 \(F_{n, j}\) 中选择一个位置固定,然后剩下的位置的任何排序就都符合要求,需要排除
  • 但是这样的话,就会导致两个位置固定的情况被多排除了一次,需要重新包含
  • ……

所以,我们就可以在 \(\mathcal{O}(k^2)\) 的时间内完成一次 \(G\) 的求解;算法总复杂度是 \(\mathcal{O}(k^3)\)

代码实现

一个很容易注意到的事情就是 \(\text{ans}_i\) 可以由 \(\text{ans}_{i - 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
46
47
48
49
50
51
52
const int N = 500;
const int mod = 1e9 + 7;
longs inv[N], c[N][N], f[N][N];

void initInverse(int n, longs p) {
inv[0] = inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = (p - p / i) * inv[p % i] % p;
inv[0] = 0;
}

longs nCr(int n, int r) {
longs ret = 1;
for (int i = n - r + 1; i <= n; ++ i)
ret = ret * i % mod;
for (int i = 1; i <= r; ++ i)
ret = ret * inv[i] % mod;
return ret;
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int n = $.nextInt(), k = $.nextInt();
c[0][0] = 1;
for (int i = 1; i <= 2 * k; ++ i) {
f[i][0] = 1, c[i][0] = 1;
for (int j = 1; j <= 2 * k; ++ j) {
f[i][j] = (f[i - 1][j] + (i - 1) * f[i - 1][j - 1]) % mod;
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
initInverse(2 * k, mod);
longs ans[] = {1, 0};
vector<int> out;
for (int j = 1; j <= k; ++ j) {
const auto lim = min(n, 2 * j);
for (int i = 1; i <= lim; ++ i) {
longs cnt = 0, fix, fl;
for (fix = 0, fl = 1; fix <= i; ++ fix, fl = -fl) {
cnt = cnt + fl * c[i][fix] * f[i - fix][j] % mod;
do cnt = (cnt + mod) % mod; while (cnt < 0);
}
ans[j % 2] = (ans[j % 2] + nCr(n, i) * cnt) % mod;
}
out.push_back((int) ans[j % 2]);
}
$.putArray(out.begin(), out.end());

return 0;
}

一些说明:很显然 \(\mathbf{C}_i^j = \mathbf{C}_{i - 1}^j + \mathbf{C}_{i - 1}^{j - 1}\)

阴间做法

首先,我们需要先观察上面得到的那个递推公式,并考虑更深刻的理解它:

  • 考虑到 \(F_{n, 0} = 1\),除了递推的转移引入之外,都是通过 \(n - 1\) 的形式引入的;
  • 什么情况下会引入 \(n - 1\)?当新加入的 \(n\) 不放在 \([n]\) 而是参与了与前面的位置交换的场合下;
  • 引入时产生了什么副作用?因为进行了交换,所以奉献了一次交换次数,\(j = j + 1\)
  • 所以,我们可以将 \(F_{n, j}\) 看作从“下标”集合 \([0, n - 1]\) 中选出一个大小 \(j\) 的子集求积后求和的结果;

形式化的说,我们可以得到下面的 \(F_{n, j}\) 的表示形式: \[ F_{n, j} = \sum_{s \subset [0, n - 1] \and |s| = j} \ \prod_{i = 1}^j s_i \] 那么接下来,对于全部需要的 \(j\),我们考虑从 \(F_{n}\) 转移到 \(F_{2n}\)

  • 一个很显然的想法,就是我们从 \([0, n - 1]\) 中选择 \(l\) 个,从 \([n, 2n - 1]\) 中选出剩下的,组成上面所提到的从集合 \([0, 2n-1]\) 中选出的大小为 \(j\) 子集;形式化地说就是将两部分的结果乘起来

  • 前半部分的答案很显然是 \(F_{n, l}\),而后半部分的答案我们没有维护;但是我们可以把它看作从 \([0, n - 1]\) 中选择了 \(j - l\) 个,然后对于每一个都加上了 \(n\),也就是下面这样: \[ F'_{n, j'} = \sum_{s\subset [n, 2n-1] \and |s| = j'} \ \prod_{i = 0}^{j'}s_{i} = \sum_{s\subset [0, n-1] \and |s| = j'} \ \prod_{i = 0}^{j'}(s_{i} + n) \] 那么这个式子展开是什么样的呢?因为这个连乘长得非常像二项式展开但是不是,残念(,所以我们可以想象一下它展开后的样子: \[ F'_{n, j'} = \sum_{l = 0}^{j'} \mathbf{C}_{n - l}^{j'-l} \times n^{j'-l} \times \sum_{s\subset [0, n-1] \and |s| = l} \prod_{i = 0}^{l}s_i \] 上面的式子中,有 \(\mathbf{C}_{n - l}^{j' - l} = \mathbf{C}_n^{j'} \times \mathbf{C}_{j'}^l\);首先是选出坐标的组合数,然后乘上“二项式系数”。

  • 然后,观察上面的式子的后半部分,我们会惊喜地发现它就是 \(F_{n, l}\),是我们已经维护的东西!

综上所述,我们可以通过下面的转移方程完成从 \(F_{n}\)\(F_{2n}\) 的转移: \[ F_{2n, J} = \sum_{j = 0}^J F_{n, j} \times F'_{n, j'}, \ \ j + j' = J \] 上式中的 \(F'_{n, j}\) 可以通过 \(F_{n, j}\) 通过下面的多项式乘法转移得到: \[ F'_{n, j} = \sum_{l = 0}^j \mathbf{C}_{n - l}^{j - l} \times n^{j - l} \times F_{n, l} \] 当然,基础的从 \(F_{n - 1, j}\)\(F_{n - 1, j - 1}\)\(F_{n, j}\) 的转化仍然有效;因此我们可以转化到任何的 \(n\):相当于我们从 \(n = 1\) 出发,然后使用 \(\times2\)\(+1\) 操作构造任何的 \(n\) ——在构造的过程中完成上面的转移就可以了;一种很显然的思路就是二进制拆位,然后按位构造 \(n\)

代码实现

基本的思路就是每次扩增 \(\times2\),如果这一位为 1 就再额外进行一次 \(+1\) 扩增:

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
const int N = 500;
const int mod = 1e9 + 7;
longs inv[N], f[N], big[N], np[N], tmp[N];

void initInverse(int n, longs p) {
inv[0] = inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = (p - p / i) * inv[p % i] % p;
inv[0] = 0;
}

longs nCr(longs n, longs r) {
longs ret = 1;
for (auto i = n - r + 1; i <= n; ++ i)
ret = ret * i % mod;
for (int i = 1; i <= r; ++ i)
ret = ret * inv[i] % mod;
return ret;
}

void calculateBig(int k, longs n) {
memset(big, 0, sizeof(longs) * (k + 1));
memset(np, 0, sizeof(longs) * (k + 1));
np[0] = 1;
for (int i = 1; i <= k; ++ i)
np[i] = n * np[i - 1] % mod;
const auto lim = min((longs)k, n);
for (int i = 0; i <= lim; ++ i)
for (int j = 0; j <= i; ++ j) {
auto t = nCr(n - j, i - j) * f[j] % mod * np[i - j] % mod;
big[i] = (big[i] + t) % mod;
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int n = $.nextInt(), k = $.nextInt();
const bitset<32> binary = n;
initInverse(N - 1, mod);
longs now = f[0] = 1;
for (int i = 30 - __builtin_clz(n); i >= 0; -- i) {
calculateBig(k, now);
memset(tmp, 0, sizeof(longs) * (k + 1));
for (int s = 0; s <= k; ++ s)
for (int b = 0; b <= k; ++ b)
if (s + b <= k)
tmp[s + b] = (tmp[s + b] + f[s] * big[b]) % mod;
else break;
memcpy(f, tmp, sizeof(longs) * (k + 1));
now *= 2;
if (binary.test(i)) {
memset(tmp, 0, sizeof(longs) * (k + 1));
tmp[0] = 1;
for (int j = 1; j <= k; ++ j)
tmp[j] = (f[j] + now * f[j - 1]) % mod;
memcpy(f, tmp, sizeof(longs) * (k + 1));
++ now;
}
}
longs ans[] = {1, 0};
vector<int> out;
for (int j = 1; j <= k; ++ j) {
ans[j % 2] = (ans[j % 2] + f[j]) % mod;
out.push_back((int) ans[j % 2]);
}
$.putArray(out.begin(), out.end());

return 0;
}

上面的代码中的 30 - __builtin_clz(n) 的含义是: int 类型的 n 的最高位的 1 的所在的位置的低一位的下标;我们使用它作为扩增起点——不使用最高位的原因是我们已经从 \(1\) 出发了,所以不需要对于首位的 \(1\) 进行额外的扩增。

当然,上面的实现中的每次转移的时间复杂度是 \(\mathcal{O}(k^2)\) 的,进行 \(\log_2n\) 次转移;如果可以使用各种手段加快单次转移的速度,理论上可以做到 \(k \leq 10^5\)(时间复杂度 \(\mathcal{O}(k\cdot \log k\log n)\)但是我不会,原作者也不会

后记

罚时是真的多,,明明还是可以回到 1700 的场嗯给我打成了防掉分场,只能说非常地不行了(

JVS2TR2_F28UCRC3K_YG_3B.jpg

最近的准度不行啊,还是以后要多加注意才行;补题也要进行的更加迅速才行,不然题目真的补不完力昨天半夜的 Div.1 + Div.2 还没有下落呜呜(呜呜呜

评论