Codeforces Round #652 (Div. 2)

Tsukkomi

这场补完感觉挺有意思,比上一场 Div.2 稍难 qwq


Problem A. FashionabLee

Description

给定 nn (3n109)\left(3\leq n\leq10^9\right) 求正 nn 边形是否存在两边相互垂直,输出字符串 YES / NO .
tt (1t104)\left(1\leq t\leq10^4\right) 组测试。

Solution

签到题。

显然正 nn 边形存在两边相互垂直 当且仅当 4n4\mid n .

时间复杂度:O(t)\mathcal O\left(t\right) .

Code

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

int t, n;

int main(void) {
scanf("%d", &t);
while (t--) scanf("%d", &n), puts(n % 4 ? "NO" : "YES");
return 0;
}

Problem B. AccurateLee

Description

给定长度为 nn (1n105)\left(1\leq n\leq10^5\right)0101ss .
i[1,n)\exists i\in\left[1,n\right) 使得 si=1, si+1=0s_i=1,\ s_{i+1}=0 ,则可从 ss 中删去 sis_isi+1s_{i+1} .
规定长度越短、字典序越小的 0101 串越优,求最优的 ss .
tt (1t104)\left(1\leq t\leq10^4\right) 组测试,保证 n105\sum n\leq10^5 .

Solution

显然 ss 的前导 00 和后导 11 无法删去,只需考虑夹在中间的子串。
若这个子串不为空,必定可 贪心 地删至剩余一个元素 0 / 10\ /\ 1 .

时间复杂度:O(n)\mathcal O\left(\sum n\right) .

Code

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

const int N = 1e5 + 5;
int t, n, s[N];

void solve(void);

int main(void) {
scanf("%d", &t);
while (t--) solve();
return 0;
}

void solve(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%1d", s + i);
int l = 0, r = n + 1;
while (l < n && !s[l + 1]) l++;
while (r && s[r - 1]) r--;
if (l + 1 == r) {
for (int i = 1; i <= n; i++) printf("%d", s[i]);
return putchar('\n'), void();
}
for (int i = 0; i <= l; i++) putchar('0');
for (int i = 1; i <= n - r + 1; i++) putchar('1');
putchar('\n');
}

Problem C. RationalLee

Description

给定长度为 nn (1n2×105)\left(1\leq n\leq2\times10^5\right) 的序列 aa (109ai109)\left(-10^9\leq a_i\leq10^9\right) .
现要将序列中的元素分配给 kk 个人,第 ii 个人要分配 wiw_i 个元素 (1k,win)\left(1\leq k,w_i\leq n\right) .
每个人的满意程度为所分配最大元素和最小元素之和。
存在一种分配方案使所有人的满意程度之和最大,求这个最大值。
tt (1t104)\left(1\leq t\leq10^4\right) 组测试,保证 i=1kwi=n, n2×105\sum\limits_{i=1}^kw_i=n,\ \sum n\leq2\times10^5 .

Solution

贪心 是显然的。
先考虑 wi=1w_i=1 的人,假定有 mm 个。
显然取剩余的 mm 个最大元素分配给这些人最优。
再考虑 wi>1w_i>1 的人,先取剩余的 nmn-m 个最大元素每人分配一个。
最后按 wiw_i 从大到小 考虑,每人分配剩余的 wi1w_i-1 个最小元素即可。

时间复杂度:O(nlogn)\mathcal O\left(\sum n\log n\right) .

Code

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;
typedef long long ll;

const int N = 2e5 + 5;
int t, n, k, a[N], w[N];
ll ans;

void solve(void);

int main(void) {
scanf("%d", &t);
while (t--) solve();
return 0;
}

void solve(void) {
scanf("%d%d", &n, &k), ans = 0;
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= k; i++) scanf("%d", w + i);
sort(a + 1, a + n + 1), sort(w + 1, w + k + 1), reverse(w + 1, w + k + 1);
for (; w[k] == 1; k--) ans += 2 * a[n--];
for (int i = 1, j = 1; j <= k; i += w[j] - 1, j++) ans += a[i] + a[n--];
printf("%lld\n", ans);
}

Problem D. TediousLee

Description

定义树高为 ii 的一类有根树 RiR_i ,其生成过程如下:

  • i=1i=1 ,则 R1R_1 只有一个结点。
  • i>1i>1 ,则生成 Ri1R_{i-1} 并考虑每一个点 uu
    • uu 无子结点,则给 uu 添加一个子结点。
    • uu 只有一个子结点,则给 uu 添加两个子结点。
    • uu 有两个或以上的子结点,则不做处理。

称一个结点和三个子结点构成的结构为爪。
给定 nn (1n2×106)\left(1\leq n\leq2\times10^6\right) ,现要给 RnR_n 染色。
规定只能给由非染色点组成的爪染色,求最大染色数。
tt (1t104)\left(1\leq t\leq10^4\right) 组测试,结果对 109+710^9+7 取模。

Solution

注意到当 i>2i>2RiR_i 相当于根结点和一个 Ri1R_{i-1} ,两个 Ri2R_{i-2} 相连。
考虑 DP ,可根据根结点的染色情况分类。
dpi0dp^0_i根结点不染色RiR_i 的最大染色数,dpi1dp^1_iRiR_i 的最大染色数。
显然有状态转移方程

dpi0=dpi11+2dpi21dp^0_i=dp^1_{i-1}+2dp^1_{i-2}

dpi1=max(dpi0,dpi10+2dpi20+4)dp^1_i=\max\left(dp^0_i,dp^0_{i-1}+2dp^0_{i-2}+4\right)

边界条件 dp10=dp11=dp20=dp21=0dp^0_1=dp^1_1=dp^0_2=dp^1_2=0 .

上述 DP 方式虽然可行,但实际上还能继续化简。
dpidp_iRiR_i 的最大染色数,rir_iRiR_i 染色数最大时根结点的 最小贡献
亦即若 RiR_i 染色数最大时根结点必须染色则 ri=1r_i=1 ,否则 ri=0r_i=0 .
显然有状态转移方程

dpi=dpi1+2dpi2+4ridp_i=dp_{i-1}+2dp_{i-2}+4r_i

观察易知 ri=[ri1=ri2=0]=[3i]r_i=\left[r_{i-1}=r_{i-2}=0\right]=\left[3\mid i\right] .
于是

dpi=dpi1+2dpi2+4[3i]dp_i=dp_{i-1}+2dp_{i-2}+4\left[3\mid i\right]

边界条件 dp1=dp2=0dp_1=dp_2=0 .

时间复杂度:O(n)\mathcal O\left(n\right) .

Code

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

const int N = 2e6 + 5;
const int p = 1e9 + 7;
int t, n;
int dp[N];

void init(void);

int main(void) {
init(), scanf("%d", &t);
while (t--) scanf("%d", &n), printf("%d\n", dp[n]);
return 0;
}

void init(void) {
for (int i = 1; i < N; i++)
dp[i] = (dp[i - 1] + 2 * dp[i - 2] % p + 4 * (i % 3 == 0)) % p;
}

Challenge

出题人在 Editorial 中表示不用矩阵快速幂这题也有 n1018n\leq10^{18} 的解法。
emmm 很好,你成功引起了蒟蒻的注意!

Solution 1

考虑 矩阵快速幂 你不让我用,我偏要用
注意状态转移方程

dpi=dpi1+2dpi2+4[3i]dp_i=dp_{i-1}+2dp_{i-2}+4\left[3\mid i\right]

难点在于 [3i]\left[3\mid i\right] 的处理。
注意 4[3i]4\left[3\mid i\right] 的含义,每转移三次即 +4+4 ,如此 循环
根据这个特点可得

[dpidpi14[imod3=2]4[imod3=1]4[3i]]=[1210010000000100000100100][dpi1dpi24[(i1)mod3=2]4[(i1)mod3=1]4[3(i1)]]\begin{bmatrix} dp_i\\ dp_{i-1}\\ 4\left[i\bmod3=2\right]\\ 4\left[i\bmod3=1\right]\\ 4\left[3\mid i\right] \end{bmatrix}=\begin{bmatrix} 1&2&1&0&0\\ 1&0&0&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&1&0&0 \end{bmatrix}\begin{bmatrix} dp_{i-1}\\ dp_{i-2}\\ 4\left[\left(i-1\right)\bmod3=2\right]\\ 4\left[\left(i-1\right)\bmod3=1\right]\\ 4\left[3\mid\left(i-1\right)\right] \end{bmatrix}

翻了翻 Editorial 的评论区,发现了两种更优的转移。
将原本的三次转移合并为一次,则

[dp3k+2dp3k+1dp3k1]=[56012320412040001][dp3k1dp3k2dp3k31]\begin{bmatrix} dp_{3k+2}\\ dp_{3k+1}\\ dp_{3k}\\ 1 \end{bmatrix}=\begin{bmatrix} 5&6&0&12\\ 3&2&0&4\\ 1&2&0&4\\ 0&0&0&1 \end{bmatrix}\begin{bmatrix} dp_{3k-1}\\ dp_{3k-2}\\ dp_{3k-3}\\ 1 \end{bmatrix}

[dpidpi14]=[12[3i]010001][12[imod3=1]010001][12[imod3=2]010001][dpi3dpi44]\begin{bmatrix} dp_i\\ dp_{i-1}\\ 4 \end{bmatrix}=\begin{bmatrix} 1&2&\left[3\mid i\right]\\ 0&1&0\\ 0&0&1 \end{bmatrix}\begin{bmatrix} 1&2&\left[i\bmod3=1\right]\\ 0&1&0\\ 0&0&1 \end{bmatrix}\begin{bmatrix} 1&2&\left[i\bmod3=2\right]\\ 0&1&0\\ 0&0&1 \end{bmatrix}\begin{bmatrix} dp_{i-3}\\ dp_{i-4}\\ 4 \end{bmatrix}

Solution 2

不用矩阵快速幂只能考虑 推导通式

一种方法是利用 Solution 1 中前面两种转移的转移矩阵。
将矩阵 相似对角化 后即可求矩阵幂的一般形式,进而推出通式。
这种方法计算量比较大,不赘述。

另一种比较简单的方法则是利用 生成函数
记序列 dpdp 的生成函数为 g(x)=i=1dpixig\left(x\right)=\sum\limits_{i=1}^\infty dp_ix^i ,则

(1x2x2)g(x)=i=3(dpidpi12dpi2)xi=4i=3[3i]xi=4i>0, 3ixi=4x31x3\begin{aligned} \left(1-x-2x^2\right)g\left(x\right)&=\sum_{i=3}^\infty\left(dp_i-dp_{i-1}-2dp_{i-2}\right)x^i\\ &=4\sum_{i=3}^\infty\left[3\mid i\right]x^i\\ &=4\sum_{i>0,\ 3\mid i}x^i\\ &=\frac{4x^3}{1-x^3} \end{aligned}

于是

g(x)=4x3(1x3)(1x2x2)=4x31x311+x112x=4(i>0, 3ixi)(i=0(1)ixi)(i=0xi)=43(i>0, 3ixi)(i=0(2i+1(1)i+1)xi)=43i=1(18i3182imod3+11(1)i31(1)(1)imod3+1)xi\begin{aligned} g\left(x\right)&=\frac{4x^3}{\left(1-x^3\right)\left(1-x-2x^2\right)}\\ &=\frac{4x^3}{1-x^3}\cdot\frac1{1+x}\cdot\frac1{1-2x}\\ &=4\left(\sum_{i>0,\ 3\mid i}x^i\right)\left(\sum_{i=0}^\infty\left(-1\right)^ix^i\right)\left(\sum_{i=0}^\infty x^i\right)\\ &=\frac43\left(\sum_{i>0,\ 3\mid i}x^i\right)\left(\sum_{i=0}^\infty\left(2^{i+1}-\left(-1\right)^{i+1}\right)x^i\right)\\ &=\frac43\sum_{i=1}^\infty\left(\frac{1-8^{\left\lfloor\frac i3\right\rfloor}}{1-8}\cdot2^{i\bmod3+1}-\frac{1-\left(-1\right)^{\left\lfloor\frac i3\right\rfloor}}{1-\left(-1\right)}\cdot\left(-1\right)^{i\bmod3+1}\right)x^i \end{aligned}

dpi=43(18i3182imod3+11(1)i31(1)(1)imod3+1)dp_i=\frac43\left(\frac{1-8^{\left\lfloor\frac i3\right\rfloor}}{1-8}\cdot2^{i\bmod3+1}-\frac{1-\left(-1\right)^{\left\lfloor\frac i3\right\rfloor}}{1-\left(-1\right)}\cdot\left(-1\right)^{i\bmod3+1}\right)


Problem E. DeadLee

Description

nn (2n105)\left(2\leq n\leq10^5\right) 种食物和 mm (1m2×105)\left(1\leq m\leq2\times10^5\right) 个人。
食物 iiwiw_i (0wi106)\left(0\leq w_i\leq10^6\right) 份,第 ii 个人喜欢食物 xi,yix_i,y_i (xiyi)\left(x_i\neq y_i\right) .
一个人进食时两种喜欢的食物都会尝试吃一份,若无食物可吃则会不满意。
求是否存在一种进食顺序使得没有人不满意。
若存在输出字符串 ALIVE 和进食顺序,否则输出字符串 DEAD​ .

Solution

记喜欢食物 ii 的人的数量为 fif_i ,考虑 贪心
fiwif_i\leq w_i ,显然将喜欢食物 ii 的人安排在末尾进食最优。
此时可视为这 fif_i 个人每人至少能吃到一份食物 ii .
分别考虑这 fif_i 个人,设当前考虑的是第 jj 个人。
注意到第 jj 个人必定能吃到食物 ii 且放到了末尾。
故此时不需关心另一种喜欢的食物,可令 fxj+yji=fxj+yji1f_{x_j+y_j-i}=f_{x_j+y_j-i}-1 .
不断进行上述操作,若所有人都被安排好了则此时的进食顺序满足要求。
否则相当于剩下的食物均满足 fi>wif_i>w_i .
考虑未被安排的人中最后进食者,设为第 kk 个人。
由于 fxk>wxk, fyk>wykf_{x_k}>w_{x_k},\ f_{y_k}>w_{y_k} ,故第 kk 个人最后无食物可吃。
亦即此时不存在满足要求的进食顺序。

时间复杂度:O(n+m)\mathcal O\left(n+m\right) .

Code

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

const int N = 1e5 + 5;
const int M = 1e6 + 5;
int n, m, w[N], x[N << 1], y[N << 1];
int f[M];
vector<int> ans, e[M];
bool vis[N << 1];
queue<int> q;

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", w + i);
for (int i = 1; i <= m; i++) {
scanf("%d%d", x + i, y + i), f[x[i]]++, f[y[i]]++;
e[x[i]].push_back(i), e[y[i]].push_back(i);
}
for (int i = 1; i <= n; i++) f[i] <= w[i] ? q.push(i) : void();
for (int fd; !q.empty();) {
fd = q.front(), q.pop();
for (int id : e[fd]) {
if (vis[id]) continue;
vis[id] = true, ans.push_back(id);
int nf = x[id] + y[id] - fd;
if (--f[nf] == w[nf]) q.push(nf);
}
}
if (ans.size() < m) return puts("DEAD"), void();
puts("ALIVE"), reverse(ans.begin(), ans.end());
for (int i = 0; i < m; i++) printf("%d%c", ans[i], " \n"[i == m - 1]);
}

Problem F. BareLee

Description

两人玩一个游戏,规则如下:

  • 游戏共 tt (1t105)\left(1\leq t\leq10^5\right) 轮,每轮给定两个整数 si,eis_i,e_i (1siei1018)\left(1\leq s_i\leq e_i\leq10^{18}\right) .
  • ii 轮游戏开始时 a=sia=s_i ,每人轮流操作。
    每次操作可令 a=2aa=2aa=a+1a=a+1 ,先使得 a>eia>e_i 的一方输。
  • 每轮游戏输的人下一轮游戏先手,赢得最后一轮游戏的人获胜。

求第一轮游戏先手者是否能必胜,是否能必败,输出 0 / 10\ /\ 1 .

Solution

考虑某一轮游戏 (s,e)\left(s,e\right) ,显然可以 DP .
dps,e1dp^1_{s,e} 表示先手能否必胜,若能 dps,e1=1dp^1_{s,e}=1 ,否则 dps,e1=0dp^1_{s,e}=0 .
同理记 dps,e0dp^0_{s,e} 表示先手能否必败。
有状态转移方程

dps,e1={02s, 2e12s, 2e12s, 2e, e2<se02s, 2e, e2<se12e, e4<se2dps,e412e, se4dp^1_{s,e}=\begin{cases} 0&2\nmid s,\ 2\nmid e\\ 1&2\mid s,\ 2\nmid e\\ 1&2\nmid s,\ 2\mid e,\ \frac e2<s\leq e\\ 0&2\mid s,\ 2\mid e,\ \frac e2<s\leq e\\ 1&2\mid e,\ \frac e4<s\leq\frac e2\\ dp^1_{s,\left\lfloor\frac e4\right\rfloor}&2\mid e,\ s\leq\frac e4\\ \end{cases}

dps,e0={1s>e2dps,e21se2dp^0_{s,e}=\begin{cases} 1&s>\frac e2\\ dp^1_{s,\left\lfloor\frac e2\right\rfloor}&s\leq\frac e2 \end{cases}

考虑整局游戏。
对于第一轮游戏先手者:

  • i[1,t]\exists i\in\left[1,t\right] 使得 dpsi,ei1=dpsi,ei0=1dp^1_{s_i,e_i}=dp^0_{s_i,e_i}=1 ,则能掌握整局的输赢。
  • i[1,t]\exists i\in\left[1,t\right] 使得 dpsi,ei1=dpsi,ei0=0dp^1_{s_i,e_i}=dp^0_{s_i,e_i}=0 ,则不能掌握整局的输赢。
  • 若对 i[1,t], dpsi,ei1dpsi,ei0\forall i\in\left[1,t\right],\ dp^1_{s_i,e_i}\neq dp^0_{s_i,e_i} ,则每轮游戏只能选择必胜或必败。

时间复杂度:O(tlogs)\mathcal O\left(t\log s\right) .

Code

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;
typedef long long ll;

const int N = 1e5 + 5;
int t;
ll s, e;
bool w[N], l[N];

void solve(void);
bool isw(ll s, ll e);
bool isl(ll s, ll e);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &t);
for (int i = 1; i <= t; i++) {
scanf("%lld%lld", &s, &e);
w[i] = isw(s, e), l[i] = isl(s, e);
}
int iw = 0, il = 1;
for (int i = 1; i <= t && iw ^ il; i++) il = l[i] ^ iw, iw ^= w[i];
printf("%d %d\n", iw, il);
}

bool isw(ll s, ll e) {
if (e & 1) return !(s & 1);
if (2 * s > e) return s & 1;
return 4 * s > e ? true : isw(s, e / 4);
}

bool isl(ll s, ll e) { return 2 * s > e ? true : isw(s, e / 2); }

Welcome to my other publishing channels