Educational Codeforces Round 91
/ / 阅读耗时 10 分钟 Educational Codeforces Round 91。因为前面的题太水了，这里只写几个不这么水的题。
E. Merging Towers
注意到答案起初应该是$n-1$，当某一个塔中存在两个相邻的数时，答案便会减少一。于是我们只需要维护每一次合并后，每一个塔中相邻数对的数量之和即可。
由于只涉及合并操作，可以使用集合的启发式合并来解决这个问题，复杂度$O(nlogn)$。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
using namespace std;
const int N = 200000 + 5;
typedef long long ll;
int setTo[N], n, m;
set<int> ssp[N];
int ans = 0;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) setTo[i] = i;
for (int i = 1, x; i <= n; i++) scanf("%d", &x), ssp[x].insert(i);
ans = n - 1;
for (int i = 1; i <= m; i++) {
for (int j : ssp[setTo[i]]) {
if (j != n && ssp[setTo[i]].count(j + 1)) --ans;
}
}
printf("%d\n", ans);
for (int ss = 1; ss < m; ss++) {
int a, b;
scanf("%d%d", &a, &b);
if (ssp[setTo[a]].size() < ssp[setTo[b]].size()) {
for (int i : ssp[setTo[a]]) {
if (i != n && ssp[setTo[b]].count(i + 1)) --ans;
if (i != 1 && ssp[setTo[b]].count(i - 1)) --ans;
}
for (int i : ssp[setTo[a]]) ssp[setTo[b]].insert(i);
setTo[a] = setTo[b];
} else {
for (int i : ssp[setTo[b]]) {
if (i != n && ssp[setTo[a]].count(i + 1)) --ans;
if (i != 1 && ssp[setTo[a]].count(i - 1)) --ans;
}
for (int i : ssp[setTo[b]]) ssp[setTo[a]].insert(i);
}
printf("%d\n", ans);
}
return 0;
}
F. Strange Addition
一个很容易想到的方法是$DP$，规定$dp(i)$表示前$i$位（位按从低位到高位排序，并且从$1$开始）的所有方案数。
在第$i$位的数字不是$1$时（假设为$s_i$），答案为：
如果为$1$，则可能与后面的数形成一个二位数，这样就有了另一种转移情况：
我们统一这两种情况，可以化为：
这是一个线性的递推式，可以在$O(n)$复杂度下求解。但是题目中有修改操作，需要考虑如何快速修改。我们将线性递推式化为矩阵式：
于是问题转化为求若干矩阵的积，每一次修改只会修改其中两个矩阵，用线段树维护矩阵乘积即可。复杂度$O(nlogn)$。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
using namespace std;
const int N = 500000 + 5;
const int MOD = 998244353;
typedef long long ll;
int n, m;
char op[N];
struct Matrix
{
int op[2][2];
Matrix operator*(Matrix s)
{
Matrix ans;
ans.op[0][0] = ans.op[0][1] = ans.op[1][0] = ans.op[1][1] = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) ans.op[i][j] = (ans.op[i][j] + 1ll * op[i][k] * s.op[k][j] % MOD) % MOD;
}
}
return ans;
}
} nd[N << 2];
void build(int l = 1, int r = n, int k = 1)
{
if (l == r) {
nd[k].op[0][0] = op[l] - '0' + 1, nd[k].op[0][1] = (op[l] == '1') * (9 - op[l - 1] + '0');
nd[k].op[1][0] = 1, nd[k].op[1][1] = 0;
return;
}
int mid = (l + r) >> 1;
build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1);
nd[k] = nd[k << 1 | 1] * nd[k << 1];
}
void modify(int x, int l = 1, int r = n, int k = 1)
{
if (l == r) {
nd[k].op[0][0] = op[l] - '0' + 1, nd[k].op[0][1] = (op[l] == '1') * (9 - op[l - 1] + '0');
nd[k].op[1][0] = 1, nd[k].op[1][1] = 0;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
modify(x, l, mid, k << 1);
else
modify(x, mid + 1, r, k << 1 | 1);
nd[k] = nd[k << 1 | 1] * nd[k << 1];
}
int main()
{
scanf("%d%d%s", &n, &m, op + 1);
reverse(op + 1, op + n + 1);
build();
// printf("%d\n", nd[1].op[0][0]);
while (m--) {
int x, d;
scanf("%d%d", &x, &d), op[n - x + 1] = d + '0';
// cout << op + 1 << endl;
modify(n - x + 1);
if (n - x + 2 <= n) modify(n - x + 2);
printf("%d\n", nd[1].op[0][0]);
}
return 0;
}
G. Circular Dungeon
考虑怎样才能使收益尽可能小。
对于$k$个$mimics$，它必然把其它箱子划分为$k$段，每一段假设有$cnt_i$这么多的箱子。并且有$cnt_i\geq0$且$\sum_{i=1}^kcnt_i=n-k$。
我们证明$cnt_i$中最大值和最小值差值不能超过$1$。
假设现在在$cnt_i$中有两段，它们的长度分别为$x$和$y$，并且有$x\leq y-2$，假设它们的段中箱子收益为$a_1,\cdots,a_x$和$b_1,\cdots,b_y$，那么它们的收益和可以表示为：
把$b_y$放到前一个段中，并且规定$a_{x+1}=b_y$，则有：
前者为交换后的收益和，而明显$(y-x-1)b_y>0$，于是交换之后收益减少。这说明最优方案中$cnt_i$最大值最小值之差总是不超过$1$。
若按每一个权值收益出现的次数讨论，则可以使用下面的方法构造出一个答案。将权值从$0$编号到$n-1$，使得每一个权值出现的次数为$\lfloor\frac {i}{k}\rfloor$。可以发现这种构造方式可以满足上面的理论，然后会保证有$k$个$mimics$。为了最小化收益，根据排序不等式，应该对权值数组进行降序排列，然后就可以计算答案了。假设排序后的权值数组为$v$，则答案为：
这样算是$O(n^2)$的，注意到$\lfloor\frac {i}{k}\rfloor$每$k$段才会改变一次，于是可以预处理前缀和，然后只枚举改变的位置，这样复杂度降至$O(nlogn)$。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
using namespace std;
const int N = 300000 + 5;
const int mod = 998244353;
typedef long long ll;
int n;
ll op[N];
inline int qpow(int x, int y)
{
int ans = 1, sta = x;
while (y) {
if (y & 1) ans = 1ll * ans * sta % mod;
sta = 1ll * sta * sta % mod, y >>= 1;
}
return ans;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lld", op + i);
sort(op, op + n, greater<ll>());
for (int i = 1; i < n; i++) op[i] += op[i - 1], op[i] %= mod;
for (int i = 1; i <= n; i++) {
ll ans = 0;
for (int j = i; j < n; j += i) {
ans = (ans + j / i * (op[min(n - 1, j + i - 1)] - op[j - 1]) % mod) % mod;
}
ans = ans * qpow(n, mod - 2) % mod;
printf("%lld ", (ans + mod) % mod);
}
return 0;
}