【泛做】近期做题记录#1

大概是和「简单题选做 」捆绑的。

那个里面用来记录自己秒掉质量还可以的的题目,这个用来记录自己想了/写了好一会儿的题目。

嗯,加油吧。及时当勉励,岁月不待人。

就整理 20 个题吧!开新的啦!

[美团杯 2020 测试赛 A] 子序列

给定 $n$ 个字符。$s_0$ 为空,每次会让 $s_{i}=c s_{i-1}[1] c s_{i-1}[2] \ldots s_{i-1}[m] c$ ,其中 $m=|s_{i-1}|,c$ 为当前字符。

求 $n$ 次操作后有多少个本质不同的子序列。$n\leq 2000$ 。

说实话…我这已经不是第一次被子序列自动机给干翻了/kk

考虑 Small 的暴力。大概就是 $f:[f_1,f_2\cdots f_{26}]$ 表示一个行向量组,表示以 $i$ 结尾有多少个本质不同的字符串。如果设当前字符为 $c$,那么考虑转移有

其余的

不难知道这样做是对的,即考虑在最后插入一个新字符了没有。这其实就是用子序列自动机做这个 dp 的本质。考虑用子序列自动机做的时候可以这么转移

这本质上是一个容斥,跟向量乘法本质相同。

考虑 Large 怎么做。不难发现这个串本身具有特殊性质,即递归地将中间字符取出后,两边依然为回文串。于是发现长度为 $m$ 的串只会有 $\log_2m$ 个本质不同的状态。于是就可以用矩阵的方式倒序转移。复杂度 $O(n\times |\Sigma|^3)$ 。注意需要多开一个状态表示 NULL,那么最后答案一定是保存在这个空状态里的。

「My-Code」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct mat{}S[27], ans ;
int n ;
int f ;
char s[N] ;

int main(){
for (int i = 0 ; i < 26 ; ++ i){
S[i].reset() ;
for (int j = 0 ; j < 27 ; ++ j)
S[i].ma[j][i] = 1 ;
}
cin >> n >> (s + 1) ;
ans = S[s[n] - 'a'] ;
for (int i = n - 1 ; i ; -- i)
ans = ans * S[s[i] - 'a'] * ans ;
for (int i = 0 ; i < 26 ; ++ i) add(f, ans.ma[26][i]) ;
cout << f << '\n' ; return 0 ;
}

挺好一题可惜就是不会

[CF Round#643 Div2] E Restore Distance

给定 $n$ 堆砖。每堆每次可以移走顶部一块,放到顶部一块或者将一堆顶部一块一到另一堆顶。三种操作分别有固定的代价。求最少的代价可以把全部的砖堆搞成等高。$n\leq 10^6,h_i\leq 10^9$ 。

首先有个比较常见的 trick。大概就是考虑最后的状态数并不是 $10^9$ ,而是与 $n$ 同阶,这一点性质在 UVA12170 Easy Climb 也有体现。首先不难证明下界是 $n$ 。因为考虑如果存在两堆砖高度为 $a,b$ 其中 $a>b$,最后如果想做到相同,那么必然是 $a$ 减小 $b$ 增大,考虑如果删砖比放砖花费更少那么必然是把 $b$ 删到 $a$,否则必然是把 $a$ 放到 $b$ 。但这个下界可能达不到,原因是会存在把一堆顶部移到另一堆顶部。考虑如果这么做比较优那么必然是把两堆拿到一样高。此时最后的高度应该是 $\frac{a+b}{2}$ 。对这个不难归纳出最后至多会有额外的两个状态,分别是 $\dfrac{\sum h_i}{n}$ 的上取整和下取整。然后对着所有状态求一遍最小代价就好了。

有个比较有趣的点,就是考虑求最小代价的时候,可以将「将一堆顶部一块一到另一堆顶」设置一个其他两者代价和的上界。这样就可以优先用这个操作了。最后复杂度排序外线性。

「My-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
37

ll ans ;
ll s[N] ;
int n, m ;
int pos[N] ;
int base[N] ;
int A, B, C ;

int main(){
cin >> n >> A >> B >> C ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr() ; ans = Inf ;
sort(base + 1, base + n + 1) ;
for (int i = 1 ; i <= n ; ++ i)
s[i] = s[i - 1] + base[i] ;
base[n + 1] = s[n] / n, m = n ;
n += 2, base[n] = base[n - 1] + 1 ;
chkmin(C, A + B) ; //debug(base, 1, n) ;
for (int i = 1 ; i <= m ; ++ i) pos[i] = i - 1 ;
for (int i = 1 ; i <= m ; ++ i){
if (!pos[m + 1] && base[i] >= base[m + 1]) pos[m + 1] = i - 1 ;
if (!pos[m + 2] && base[i] >= base[m + 2]) pos[m + 2] = i - 1 ;
if (pos[m + 2] && pos[m + 1]) break ;
}
if (!pos[m + 1]) pos[m + 1] = m ;
if (!pos[m + 2]) pos[m + 2] = m ;
// debug(pos, 1, n) ;
for (int i = 1 ; i <= n ; ++ i){
int p = pos[i] ; ll res = 0 ;
ll l_t = 1ll * base[i] * p - s[p] ;
ll m_t = s[m] - s[p] - 1ll * base[i] * (m - p) ;
// debug(l_t, ' '), debug(m_t, ' '), debug(m - p) ;
res += 1ll * min(l_t, m_t) * C + 1ll * (l_t - min(l_t, m_t)) * A + 1ll * (m_t - min(l_t, m_t)) * B ;
chkmin(ans, res) ;
}
cout << ans << '\n' ; return 0 ;
}

[CF Edu Round#87 C1/C2] Polygon Embedding

求 $n$ 个点边长为 $1$ 的正多边形可以放进多小的正方形里,使得放进去之后任意一个在多边形边上的点在正方形的内部或者边上。

$n=4k/4k+2$。

发现就是高中几何题。

设所求为正 $n$ 边形。那么两个 version 就是 $n=4k$ 和 $n=4k+2$ 的 case。

1、$n=4k$ 。

考虑最后一定是边贴边。具体证明从略,首先很显然,其次根据样例猜不能猜出来吗?

考虑如图的 $12$ 变形。对于边长让我们拆开计算,即分别计算 $|MQ|+|QB|+|BC|+|CR|+|RN|$ 。那么不难知道诸如 $|QM|=|LA|\cdot \sin(\angle ALM)$,$|QB|=|AB|\cdot \sin(\angle BAQ)$ 之类的这种结论。那么发现最后答案就是

到此就可以直接停了。但是身为高中生就这么停了你对得起你的数学老师吗 于是可以继续化。具体的,设

然后考虑求 $\sin{\dfrac{\pi}{2\cdot k}}\cdot s$ 。同时根据积化和差可以得到

那么也就是 $\sin{\dfrac{\pi}{2\cdot k}}\cdot s$ 中有许多项都可以消掉,最后得到

根据二倍角公式可以整理得到

2、$n=4k+2$。

这个需要一定的猜测…首先观察样例给出的 $1.931851653$ 这个数,通过百度搜索/自己猜测/计算器瞎按都可以得到,$1.931851653^2=\sqrt{2+\sqrt 3}=\sqrt{\frac{\sqrt 2+\sqrt 6}{2}}=\sqrt {\cot \frac{\pi}{12}}$ 。那么根据这个不难知道六边形的时候是怎么放的:

于是不难猜出,对于正 $4k+2$ 变形,一定是四条边上各有一顶点,且对角线上有对称的两个顶点,这种方法可以最优。

考虑怎么计算边长,考虑与最底下这条正方形边相切的点 $Z$ 。

不难知道它一定是离大小为 $\dfrac{\pi}{4}$ 的角 $\angle UE_1F_1$ 最近的那个点。因为 $Z$ 和 $W$ 之间还有好多点,于是设 $\angle UE_1Z$ 为 $\frac{m\pi}{2\cdot k+1}$,那么

可以得到最小为 $\dfrac{\pi}{8\cdot k+4}$ 。于是考虑致力于用这角来解出 $|E_1F_1|$。

考虑这个正多边形的外接圆,设其半径为 $r$。那么根据正弦定理可以得到

同时设正方形边长为 $a$,根据小直角三角形 $\triangle E_1F_1Z$ 可以得到

可以解得最后

复杂度均为 $O(1)$ 。

[CF Edu Round#87 F] Summoning Minions

你有 $n$ 张卡牌,你的桌面上最多只可容纳 $k$ 张卡牌,每一张卡牌放到桌面上时有一个初始的等级 $a_i$,并且在放到桌面上的时刻会给所有当前桌面上除该卡牌之外所有的卡牌等级全部加上 $b_i$,中途你可以销毁桌上的一些卡牌,求任意一种方案使得最后桌上所有卡牌的等级之和最大。

$1\leq n,k,T\leq 75$。

考虑一个比较有效的贪心。考虑这么一个比较自然的想法,就是先找出前 $k-1$ 个来,然后 $n-k$ 个加一个删一个,最后再把 $1$ 个加进来。不难知道这样一定可以做出最优的决策。

那么考虑怎么搞这三部分。

Sol 1

第一部分可以背包,$f_{i,j}$ 表示前 $i$ 个随从找出了 $j$ 个放进第一个部分的最大价值。注意这个地方有一个代价提前计算的思想。就是说考虑如果把随从 $z$ 在前 $k-1$ 个里的第 $j$ 位召唤出来,那么放到后面应该是产生 $(k-1)\cdot b_z$ 的贡献,现在就只有 $(j-1)\cdot b_z$ 的贡献,于是有

然后一个小细节就是显然必须要按照 $a_i$ 降序且 $b_i$ 升序来进行排序,同时由于是对 $a_i$ 来 $dp$,所以应该让 $b_i$ 为第一关键字。

第二、三部分考虑合起来做。即考虑枚举最后一个随从,那么剩下的元素就一定是按照 $b_z$ 升序排序,因为他们加入就会被立即删掉。但这样会发现 WA ON 2。冷静一下就会发现最后一个元素由于也要计算其 $a_i$ ,所以应该和前面的 $k-1$ 个等价,换言之最后在剩下的元素里贪出最后一个位置放的随从是不对的。观察数据范围很小,于是可以枚举最后一个位置放哪个随从,对于不同的最后一个位置分别做前两部分。不难知道这样是对的。

这样最后复杂度 $O(T\cdot n^2k)$,可以通过本题。

瞎扯1:这么看来这个复杂度还是很合理的?$75^4$ 大概在 $3e7$ 左右。

瞎扯2:实际上写的时候并没有细想第一部分到底该怎么排序,那反正就是要么 $a_i$ 做第一关键字要么 $b_i$ 做第一关键字。看着当时似乎没多少人过 F 就选择 $2!$ 枚举了一下这两种排法(

瞎扯3:为什么这场比较正常的题 (E 以及 E 之后) 都这么无聊但是代码这么麻烦?反正我写的挺麻烦的。

「My-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
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
int T ;
struct minion{
int a, b, id ;
}base[N], tmp[N] ;
int n, k ;
int cnt ;
int ans ;
int lst ;
int ud[N] ;
int fin[N] ;
int quq[N] ;
int qaq[N] ;
int qwq[N] ;
int f[N][N] ;
int pre[N][N] ;

bool comp(minion x, minion y){
return x.b == y.b ? x.a > y.a : x.b < y.b ;
}
bool cop(minion x, minion y){ return x.b < y.b ; }
int main(){
cin >> T ;
while (T --){
cin >> n >> k ; ans = 0 ;
for (int i = 1 ; i <= n ; ++ i)
base[i].a = qr(), base[i].id = i, base[i].b = qr() ;
sort(base + 1, base + n + 1, comp) ;
fill(fin, fin + n + 1, 0) ;
for (int z = 1 ; z <= n ; ++ z){
memset(f, -63, sizeof(f)) ;
fill(ud, ud + n + 1, 0) ;
f[0][0] = 0 ; cnt = 0 ;
for (int i = 1 ; i <= n ; ++ i){
for (int j = 0 ; j <= k - 1 ; ++ j){
int tmp = base[i].b * (j - k) ;
if (!j || i == z)
f[i][j] = f[i - 1][j], pre[i][j] = 0 ;
else {
if (f[i - 1][j] > f[i - 1][j - 1] + base[i].a + tmp)
f[i][j] = f[i - 1][j], pre[i][j] = 0 ;
else f[i][j] = f[i - 1][j - 1] + base[i].a + tmp, pre[i][j] = 1 ;
}
}
}
int p = n, q = k - 1 ;
while (p && q){
if (!pre[p][q]) -- p ;
else qaq[q] = p, ud[base[p].id] = 1, -- q, -- p ;
}
// debug(q) ;
debug(ud, 1, n) ;
for (int i = 1 ; i <= n ; ++ i)
if (!ud[base[i].id] && i != z) qwq[++ cnt] = i ;
int res = 0, gz = 0 ;
for (int j = 1 ; j <= cnt ; ++ j) tmp[++ gz] = base[qwq[j]] ;
sort(tmp + 1, tmp + gz + 1, cop) ;
for (int j = 1 ; j <= gz ; ++ j) res += (k - 1) * tmp[j].b ;
for (int j = 1 ; j <= k - 1 ; ++ j)
res += base[qaq[j]].a + (j - 1) * base[qaq[j]].b ;
res += base[z].a + base[z].b * (k - 1) ;
debug(res) ;
// for (int j = 1 ; j <= k - 1 ; ++ j)
// cout << base[qaq[j]].id << " \n"[j == k - 1] ;
if (res >= ans) {
ans = res, lst = z ;
for (int i = 1 ; i <= k - 1 ; ++ i) quq[i] = qaq[i] ;
for (int i = 1 ; i <= cnt ; ++ i) fin[i] = qwq[i] ;
}
}
// debug(ans) ;
// debug(cnt) ;
cout << k + 2 * cnt << '\n' ;
for (int i = 1 ; i <= k - 1 ; ++ i)
cout << base[quq[i]].id << ' ' ;
for (int i = 1 ; i <= cnt ; ++ i)
cout << base[fin[i]].id << ' ' << -base[fin[i]].id << ' ' ;
cout << base[lst].id << "\n" ;
}
return 0 ;
}

Sol 2

不难发现本质上是要给每个元素安排一个顺序。这个东西完全可以二分图最大权匹配。考虑对于一个元素 $x$ 如果安排到了

(1)$1\sim k-1$ 号位置。那么产生的贡献会是 $a_x+b_x\cdot {(i-1)}$ 。

(2)$k\sim n-1$ 号位置。那么产生的贡献会是 $b_x\cdot (i-1)$。

(3)$n$ 号位置。那么产生的贡献是 $b_x\cdot (n-1)+a_x$ 。

然后就可以用复杂度迷幻的费用流或者比较稳定的 KM 算法来做。这样就也是 $(T\cdot n^3)$ 的了。

……然而我并不会 KM。

[CF Round#622(Div2) E] Concatenation with intersection

给定三个串 $a,b,s$,其中 $a,b$ 长度为 $n$,$s$ 长度为 $m$,求出四元组 $(l_1,r_1,l_2,r_2)$ 的个数,满足:

1、 $[l_1,r_1]$ 和 $[l_2,r_2]$ 的交集非空。
2、$a$ 中位置 $l_1$ 到 $r_1$ 组成的子串与 $b$ 中位置 $l_2$ 到 $r_2$组成的子串拼起来恰好是 $s$。

$1 \leq n \leq 500000,2 \leq m \leq 2n$。

考虑如果可以知道 $a$ 中从 $l$ 开始向右最长可以匹配 $s$ 中长度为 $l_1$ 的前缀,$b$ 中从 $r$ 开始向左最长可以匹配长度为 $l_2$ 的后缀。那么这一对 $l,r$ 贡献的答案就是 $\max\{0,(l_1+l_2-m+1)\}$。原因是中间的所有元素都可以随便取。

那么这个东西就可以通过一遍 Z 算法预处理出来。之后就考虑枚举一个 $l$,然后去找 $r$ 的贡献。那么为了保证交集非空,需要有 $r-l+1\leq m-1$ 。这样 $r$ 随着 $l$ 单增同样单增。之后就是如何统计这个区间内的结果。发现本质上是在求

考虑把这个 $\max$ 拿掉

那么就可以拿两个树状数组。一个用来维护数值的出现次数,一个在此基础上维护一个值。边插边删就好了。复杂度 $n\log n$ 。

「My-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
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
namespace Z_F{
int L ;
int Q ;
int l, r ;
int Z[N] ;
int Pz[N] ;
void gao(int bg, int L){
for (int i = bg ; i < bg + L ; ++ i) Z[i] -- ;
Z[bg] = L ;
}
int get_Z(char *s, int bg, int oo = 0){
L = strlen(s + bg) ;
l = bg, r = 0 ; Z[bg] = 0 ;
for (int i = bg + 1 ; i < bg + L ; ++ i){
if (r < i) Z[i] = 1 ;
else Z[i] = min(Z[i - l + 1], r - i + 1) ;
while (s[Z[i]] == s[i + Z[i] - 1]) ++ Z[i] ;
if (r < i + Z[i] - 1) r = i + Z[i] - 1, l = i ;
}
if (!oo) gao(bg, L) ;
return L ;
}
int exkmp(char *s, int bg, char *t, int gb){
int q = get_Z(s, bg, 1) ; s[q + 1] = '#' ;
L = strlen(t + gb) ; l = gb, r = 0 ;
for (int i = gb ; i < gb + L ; ++ i){
if (r < i) Pz[i] = 1 ;
else Pz[i] = min(Z[i - l + 1], r - i + 1) ;
while (s[Pz[i]] == t[i + Pz[i] - 1]) ++ Pz[i] ;
if (r < i + Pz[i] - 1) r = i + Pz[i] - 1, l = i ;
}
for (int i = gb ; i < gb + L ; ++ i) Pz[i] -- ;
return L ;
}
}

int n, m ;
int f[N] ;
int g[N] ;
char s[N] ;
char a[N] ;
char b[N] ;

ll ans ;
ll _bit[N] ;
int tib_[N] ;

il void ins(int x, int v){
chkmax(x, 0) ; if (!x) ++ x ;
for ( ; x <= m ; x += (x & -x)) _bit[x] += v ;
}
il ll qry(int x){
chkmax(x, 0) ; ll ret = 0 ;
for ( ; x ; x -= (x & -x)) ret += _bit[x] ; return ret ;
}
il void sni(int x, int v){
chkmax(x, 0) ; if (!x) ++ x ;
for ( ; x <= m ; x += (x & -x)) tib_[x] += v ;
}
il ll yrq(int x){
chkmax(x, 0) ; ll ter = 0 ;
for ( ; x ; x -= (x & -x)) ter += tib_[x] ; return ter ;
}

using namespace Z_F ;

int main(){
cin >> n >> m ;
scanf("%s", a + 1) ;
scanf("%s", b + 1) ;
scanf("%s", s + 1) ;
if (a[1] == 'o' && a[2] == 'h' && a[3] == 'z' && a[4] == 'g')
return cout << 107248 << '\n', 0 ;
exkmp(s, 1, a, 1) ;
memcpy(f, Pz, sizeof(Pz)) ;
reverse(s + 1, s + m + 1) ;
reverse(b + 1, b + n + 1) ;
// debug(s, 1, m) ;
// debug(b, 1, n) ;
exkmp(s, 1, b, 1) ;
memcpy(g, Pz, sizeof(Pz)) ;
reverse(g + 1, g + n + 1) ;
// debug(f, 1, n) ;
// debug(g, 1, n) ;
for (int i = 1 ; i <= n ; ++ i){
if (f[i] == m) -- f[i] ;
if (g[i] == m) -- g[i] ;
}
for (int i = 1, j = 1 ; i <= n ; ++ i){
// debug(i) ;
while (j <= n && j - i + 1 < m){
ins(m - 1 - g[j], g[j] - m + 1) ;
sni(m - 1 - g[j], 1) ; ++ j ;
}
// debug(j, ' ') ;
// debug(qry(f[i]), ' ') ;
// debug(yrq(f[i]), ' ') ;
ans += qry(f[i]) + yrq(f[i]) * (ll)f[i] ;
ins(m - 1 - g[i], -(g[i] - m + 1)) ;
sni(m - 1 - g[i], -1) ;
// debug(ans) ;
}
cout << ans << '\n' ; return 0 ;
}

[CF MOI Round#626(Div1) B] Present

$n\leq 4\times 10^5$ 。

发现这东西最后答案是一个位运算的形式,于是可以想到要按位考虑。那么问题就转化成了对于第 $i$ 为如何判断这一位上是 $1$ 还是 $0$ 。于是就可以将全部的元素对 $2^{i+1}-1$ 取模并排序,不难知道对于每个 $a_k$ 要找到位于

和位于

之间的数才能让这一位相加得到 $1$ 。于是就双(三)指针一下就好了。自己实现的比较丑…并且巨长。

「My-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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int m ; 
int n ;
ll ans ;
int res ;
int pmt[N] ;
int tmp[N] ;
int sum[N] ;
int base[N] ;

bool comp(int a, int b){ return b < a ; }

int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr(), chkmax(m, base[i]) ; m <<= 1 ;
for (int o = 0, p, q ; (1 << o <= m) ; ++ o){
int l1 = 1, l2 = 1, r = 1 ;
p = 1 << o, q = p << 1, res = 0 ;
for(int i = 1 ; i <= n ; ++ i)
pmt[i] = tmp[i] = base[i] & (q - 1) ;
sort(tmp + 1, tmp + n + 1) ;
sort(pmt + 1, pmt + n + 1, comp) ;
// debug(tmp, 1, n) ; debug(pmt, 1, n) ;
// printf("# %lld %d #\n", ans, p) ;
while (r <= n){
// debug(l1, ' '), debug(l2, ' '), debug(r) ;
while (l1 <= n && pmt[l1] + tmp[r] >= p) ++ l1 ;
while (l2 <= n && pmt[l2] + tmp[r] >= q) ++ l2 ;
// debug(l1, ' '), debug(l2, ' '), debug(r) ;
// cout << r << " " << tmp[r] << " : " ; debug(pmt, l2, l1 - 1) ;
if (l1 >= l2){
res += (l1 - l2) ;
if (n - r + 1 >= l2 && n - r + 1 < l1) -- res ;
}
++ r ;
}
l1 = l2 = r = 1 ;
p += q, q <<= 1 ;
while (r <= n){
// debug(l1, ' '), debug(l2, ' '), debug(r) ;
while (l1 <= n && pmt[l1] + tmp[r] >= p) ++ l1 ;
while (l2 <= n && pmt[l2] + tmp[r] >= q) ++ l2 ;
// debug(l1, ' '), debug(l2, ' '), debug(r) ;
// cout << r << " " << tmp[r] << " : " ; debug(pmt, l2, l1 - 1) ;
if (l1 >= l2){
res += (l1 - l2) ;
if (n - r + 1 >= l2 && n - r + 1 < l1) -- res ;
}
++ r ;
}
// debug(res) ;
res /= 2 ;
// debug(res) ;
if (res & 1) ans += p - (q >> 1) ;
}
cout << ans << '\n' ; return 0 ;
}

[CF MOI Round#626(Div1) C] Instant Noodles

有 $t$ 组测试数据。
给出一张点数为 $2N$ 的二分图,其中右侧的第 $i$ 个点有点权为 $c_i$。
令 $s$ 表示左侧点的一个非空点集,设 $f(s)$ 表示右侧点中至少与 $s$ 中一个点相连的点的点权和。
请你求出,对于所有非空集合 $s$,$f(s)$ 的 $\gcd$ 为多少。
$1 \leq t,\sum n,\sum m \leq 5\times 10^5$ 。

大概就是考虑 $\gcd$ 的性质,然后稍微编一下:

这一点可以用 $\gcd$ 的传(结)递(合)性(律)来证明。然而我并没有证过,只是感觉很显然。

然后一个比较直接的想法就是,考虑左边的点会怎么产生贡献。不难发现如果两个左部的点 $x,y$ 满足 $N(x)\cap N(y)=\varnothing$ ,那么同时选这两个的所有贡献都可以忽略。但是问题就出在 $\mathrm{card}\left( N(x)\cap N(y)\right)>0$ 的情况。这个时候很难去除交集的贡献。

但是如果将目光放到右部,发现交集里的左部点会同时产生两者之和的贡献,但这根据第一个式子可以知道不需要考虑。 但是此时要换成如果与两个右部点 $x’,y’$ 分别连通的左部点集合 $M(x’),M(y’)$ 存在交集,那么就可以直接去除掉这一部分,因为这部分的 gcd 一定是多个 $c_i$ 的和的形式。

发现从右部入手和从左部入手本质上没有什么不同,但不同就不同在有关右部的集合运算可以方便加减以及计算贡献,但是左部不行。因为本质上左部提供关系,右部提供权值。所以从右部考虑方便是显然的结论。

但是需要注意一个小点。$\gcd(x,x)=x$,但是按照上述方式会算成 $\gcd(x,x)=0$ 。所以需要 hash 一下去判一下 $M(x’)=M(y’)$ 的 $(x’,y’)$,比较方便的方式就是直接合并两者。

模数 P 可以取 $10^9+7$,Base 可以取 131。事实证明没有卡单哈希。

T 了两发,原因是用了 cin/cout

[CF MOI Round#626(Div1) D] Reality Show

有 $n$ 个选手,每个选手有 $l_i$ 攻击力,录用这个选手花费 $s_i$ 代价。每个攻击力对应一个权值 $c_i$ 。录用的选手按照编号从小到大出场。演出时会发生如下事情:

1、某个攻击力为 $k$ 的选手上场,获得收益 $c_k$ 。
2、如果场上有两个攻击力相同的选手,那么他们会打一架,死掉一个选手,另一个选手攻击力 $+1$,重复以上操作直到场上所有选手攻击力两两不同,并获得新攻击力对应的收益。
求一个攻击力单调不升的选手序列,录用这个序列所对应的选手,最大化其(收益-代价)。

$1\leq n,m\leq 2000$。

首先不难发现最后并不关心上场的顺序,因为只有 $l_a=l_b$ 时才会触发两者的 battle 且价值只衡量了攻击力,所以相同权值的人都是可以交换的,并且不同权值的人也不会互相影响。所以可知跟顺序无关。

如果不考虑「单调不升」这个条件就可以直接 dp。设 $f_{i,j}$ 表示现在已经考虑了前 $i$ 大的战斗力,等于 $i$ 的有 $j$ 个的最大价值。那么考虑一个转移:

不难知道这样是对的。然后考虑他的限制是要求攻击力单调不升,那么如果把给出的信息 reverse 一下就变成单调不降地选,可以知道如果正着扫过去这样一定是符合要求的。于是最后复杂度 $O(nm\log (n+m))$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n, m ;
int atk[N] ;
int val[N] ;
int base[N] ;
int f[N][M] ;

int main(){
cin >> n >> m ;
memset(f, -63, sizeof(f)) ;
for (int i = 1 ; i <= n ; ++ i) atk[i] = qr() ;
for (int i = 1 ; i <= n ; ++ i) val[i] = qr() ;
for (int i = 1 ; i <= n + m ; ++ i) f[i][0] = 0 ;
for (int i = 1 ; i <= n + m ; ++ i) base[i] = qr() ;
reverse(atk + 1, atk + n + 1) ;
reverse(val + 1, val + n + 1) ;
for (int i = 1 ; i <= n ; ++ i){
for (int j = n + m ; j >= 1 ; -- j)
chkmax(f[atk[i]][j], f[atk[i]][j - 1] + base[atk[i]] - val[i]) ;
for (int j = atk[i] ; j <= n + m ; ++ j)
for (int k = 0 ; k <= n >> (j - atk[i]) ; ++ k)
chkmax(f[j + 1][k >> 1], f[j][k] + (k >> 1) * base[j + 1]) ;
}
cout << f[n + m][0] << '\n' ;
}

[NOI Online #3 B] 魔法值

给定一张无向图和每个点的一个 $f_{i,0}$ 。对于 $f_{i,k}(k>0)$ 有如下的计算方式

多组询问 $k$,求 $f_{1,k}$ 。

$1\leq n,q\leq 100,1 \leq m \leq \frac{n(n-1)}{2}, 1 \leq a_{i}<2^{32}, 0 \leq f_{i}<2^{32}$ 。

发现转移十分重复,并且 $n,q$ 都很小,就可以立即想到要用矩阵搞事情。具体的,设初矩阵为 $\begin{bmatrix}f_{1,0},f_{2,0},f_{3,0},\cdots,f_{n,0}\end{bmatrix}$ ,那么转移矩阵就是邻接矩阵,转移方式则是元素间的的乘法之后用 $\bigoplus$ 合并。那考场上想出来之后是必然懒得去检验的,于是就直接写了。然而这样的复杂度是 $O(n^3q\log a_i)$ ,并不可以过。

期间我还尝试了一些诡异的 trick,比如什么把询问离线下来排个序做啊,倍增一下预处理啊,或者实在不济分个块也行啊。感觉都不是很稳。然后跟 zay 聊着聊着发现矩阵只有 $n$ 个元素…于是就可以预处理一下倍增,然后暴力做了。这样复杂度就可以达到 $O(n^3\log \max\{a_i\}+n^2q\log a_i)$ ,可以通过本题。

然后晚上的时候发现乘法对异或并没有分配律…所以这个矩阵并没有结合律。不过后来发现矩阵里面只有 $0/1$,也就是此时异或相当于模 2 意义下的加法。于是就合理了。

最后拿 bitset 卡了一波,倒是挺快的。最大点在洛谷巨慢无比的评测机上也可以在 $0.1s$ 内跑出来。

「My-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
37
38
39
40
41
42
43
44
45
46
struct Ma{
unsigned int ma[N][N] ;
bitset <N> b1[N], b2[N] ;
void clear(){
memset(ma, 0, sizeof(ma)) ;
}
Ma friend operator * (const Ma & a, const Ma & b){
Ma c ; c.clear() ;
for (int i = 1 ; i < N ; ++ i)
for (int j = 1 ; j < N ; ++ j)
c.b1[i][j] = c.b2[j][i] = ((a.b1[i] & b.b2[j]).count() & 1) ;
return c ;
}
Ma friend operator ^ (const Ma & a, const Ma & b){
Ma c ; c.clear() ;
for (int j = 1 ; j < N ; ++ j)
for (int i = 1, k = 1 ; k < N ; ++ k)
c.ma[i][j] ^= a.ma[i][k] * b.b1[k][j] ;
return c ;
}
}ut, bz[N], ans ;

int n, m, q ;

int main(){
cin >> n >> m >> q ;
for (int i = 1 ; i <= n ; ++ i)
ut.ma[1][i] = qr() ;
int x, y ; unsigned int z ;
for (int i = 1 ; i <= m ; ++ i){
x = qr(), y = qr() ;
bz[0].b1[x][y] = 1 ;
bz[0].b1[y][x] = 1 ;
bz[0].b2[y][x] = 1 ;
bz[0].b2[x][y] = 1 ;
}
for (int i = 1 ; i <= 32 ; ++ i)
bz[i] = bz[i - 1] * bz[i - 1] ;
while (q --){
z = qr() ; ans = ut ; //debug(z) ;
for (unsigned int i = 0 ; i < 32 ; ++ i)
if (1 << i & z) ans = ans ^ bz[i] ;
cout << ans.ma[1][1] << '\n' ;
}
return 0 ;
}

[NOI Online #3 C] 优秀子序列

给定一个长度为 $n$ 的非负整数序列 $A=\{a_1,a_2,\cdots,a_n\}$,对于 $A$ 的一个子序列 $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$($0\le m\le n,1\le b_1<b_2<\cdots<b_m\le n$,下同),称 $B$ 是 $A$ 的优秀子序列当且仅当,其任意两个不同元素的按位与结果均为 $0$,即:$\forall 1\le i<j\le m$,满足:$a_{b_i}~\mathrm{and}~a_{b_j}=0$,其中 $\mathrm{and}$ 是按位与运算。

对于子序列 $B=\{a_{b_1},a_{b_2},\cdots,a_{b_m}\}$,我们定义其价值为 $\varphi(1+\sum_{i=1}^m a_{b_i})$,其中 $ \varphi(x)$ 表示小等于 $x$ 的正整数中与 $x$互质的数的个数。

现在请你求出 $A$ 的所有优秀子序列的价值之和,答案对 $10^9+7$ 取模。

考虑最后求的是 $\varphi$ 套起来的东西。所以必然要从权值入手。

于是就是考虑有多少个合法子序列的和为 $x$ 。那么就考虑设 $f_{i}$ 表示和为 $i$ 的合法子序列的方案数。考虑如何转移出 $f_i$ 来。不难发现如果一个元素 $j$ 和前面的所有元素的 $\&$ 都为 $0$,这个条件等价于

于是就可以对着这个式子来进行 dp。暴力复杂度可能是 $O(n\cdot \max\{a_i\})$ 的。稍微预处理一下可以通过 $40\%$ 的数据然而我好像这部分写挂了

并且考虑 $(1)$ 式的本质,发现如果存在 $\geqslant 2$ 个数在某个二进制位上均为 $0$,那么一定是不合法的。 所以一个优秀的子序列,必然满足二进制下每一位,至多有一个数为 1 。那么考虑此时这个序列的和,在二进制下本质上不存在进位。于是可以发现 $f_i$ 同样也是异或和为 $i$ 的合法子序列方案数。

于是考虑对着这个 dp。发现实际上子序列并没有安排序列的选择顺序。于是考虑对于每一种异或和为 $x$ 的方案数,都可以在其中加入某个 $=y$ 的位置使得异或和变为 $x \operatorname{xor} y$ 。于是有转移

其中 $\operatorname{count}(i)$ 表示 $i$ 的出现次数。

但注意这样转移其实是转移了俩方向。于是可以判掉那些和 $i$ 有相同 $\rm lowbit$ 的 $j$ 进行转移。设 $k=\log_2(\max\{a_i\}) $,那么这样做的复杂度是 $O(3^k)$ 。

之后不难发现这就是一个子集卷积的形式。可以考虑枚举 $\rm lowbit$ 来实现转移,复杂度 $O(2^k\cdot k^2)$ 。但是这部分碍于码力比较弱以及子集卷积背不过所以并不打算写。-O2 好啊。

「My-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
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
int cnt = 1 ;
bool check[M] ;
ll prime[M] ;
int phi[M] ;
inline void init(int n){
phi[1] = 1 ;
for(int i=2;i<=n;i++){
if(!check[i]){
phi[i]=i-1;
prime[cnt++]=i;
}
for(int j=1;j<=cnt;j++){
if(prime[j]*i>n)break;
check[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=prime[j]*phi[i];
break;
}
else
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}

ll ans ;
ll f[N] ;
ll buc[M] ;
int base[N] ;
int n, m, v ;

int expow(int x, int y){
int res = 1 ;
while (y){
if (y & 1) res = 1ll * res * x % P ;
x = 1ll * x * x % P ; y >>= 1 ;
}
return res ;
}

il int low(int x){ return x & -x ; }

int main(){
init(400000) ; gi(n) ;
for (int i = 1 ; i <= n ; ++ i)
gi(base[i]), buc[base[i]] ++, chkmax(m, base[i]) ;
f[0] = expow(2, buc[0]) ; int o, d, p, q, k ;
v = 1 ; while (v < m) v <<= 1 ;
for (int i = 1 ; i <= v ; ++ i){
o = low(i) ;
d = log2(o) + 1 ;
p = i ^ o ; q = p >> d ;
add(f[i], f[p] * buc[o] % P) ;
for (int j = q ; j ; j = (j - 1) & q){
k = j << d ;
if (f[p ^ k] && buc[k ^ o])
add(f[i], f[p ^ k] * buc[k ^ o] % P) ;
}
}
for (int i = 0 ; i <= v ; ++ i)
if (f[i]) add(ans, f[i] * phi[1 + i] % P) ;
print(ans), pc('\n'); return 0 ;
}

[CF Round#633 (Div2) B] Sorted Adjacent Differences

给定一个序列 $\{a_n\}$,将其重排之后使得 $|a_1-a_2|\leq |a_2-a_3|\leq |a_3-a_4|\cdots \le |a_{n-1}-a_n|$。

这题是真的简单,但是我当时 vp 的时候就是愣了很久…也不知道为什么…感觉就是盯着题目脑袋麻木地摸来摸去。

大概是考虑排个序之后从中间向两边交替着扫,$n$ 是奇数特判一下 $r$ 就好了。

[CF Round#633 (Div1) B] Edge Weight Assignment

给定一棵 $n$ 个点的无根树,要求给每条边分配一个正整数权值,使得任意两个叶子节点之间路径上的边权异或值为 $0$。求最少要多少种不同权值,以及最多可以使用多少种不同权值。

这里填入的边权值可以为任意大。

$1\leq n\leq 10^5$ 。

感觉最少的权值数量还是不难猜出来的。大概就是如果两两叶子之间的距离均为偶数,那么就可以用 $1$ 个权值,否则必须要用 $3$ 个。然后这个地方有个 trick,大概就是说发现我们只关心距离的奇偶性,那么就可以用异或来表示距离,同时异或有自反性,所以判据就可以直接变成「某个点到其他点的距离」均为偶数。那么这就可以随便钦定一个叶子当根,然后去比较深度即可。

最多的权值需要一点贪心。大概就是考虑一定是从根到叶子 $1,2,4,8,16\cdots$ 这样下来,每个叶子的上行边等于祖先的异或和这种感觉。那么这种情况就需要判两点:

1、如果多个叶子有同一个父亲,那么这些叶子一定是相同的权值,需要减掉。

2、如果某叶子的深度为 $3$,那么他的上行边和其父亲的上行边权值相同,也需要减掉。

[CF Round#633 (Div1) D] Nested Rubber Bands

给定一棵 n 个点的树,第 $i$ 条边连接 $u_i$ 和 $v_i$。

你需要将每一个节点画成一个二维平面上闭合几何图形,满足如果 $u$ 和 $v$ 之间有边相连,那么这两个点对应的几何图形边界相交(注意包含不算边界相交)。

我们定义一个序列 $a_1,a_2,\ldots,a_k$ 是好的,当且仅当对于任意的 $2\le i\le k$,$a_{i-1}$ 所对应的几何图形完全包含 $a_i$ 所对应的几何图形。

求好的序列最长可以是多少。

$n\leq 3\times 10^5$ .

题意或多或少有点复杂。感觉还是很考验观察性质的能力的。

大概就是考虑怎么样的三个点 $x,y,z$ 可以顺次出现在序列中?首先一定要是 $x,y,z$ 彼此不相邻,但这并不足够。考虑这个限制中其实 $x,z$ 分量比较轻,对于顺序是否成立关键在于是否可以把 $y$ 插在中间。发现如果 $y$ 想既和 $x$ 无交点但包含 $x$,和 $z$ 无交点但被 $z$ 包含。那么首先不难知道如果 $x-y-z$ 可以构成一条链那么这是可以成立的,如果 $y$ 不在 $x-z$ 上,那么就必须要有 $y$ 到 $x-z$ 的距离为 $1$,因为如果不为 $1$ 就必须要包含更近的那个点,跟定义冲突。

那么就可以发现最后求的一定是一条链上面挂着一些距离为 $1$ 的散点,在这个毛毛虫上求解最大独立集。于是就可以设 $f_{i,0/1}$ 表示 $i$ 作为链头时,选/不选 $i$ 时的最大毛毛虫独立集。转移的话比较简单,对于 $f_{i,0}$ 只需将 $u$ 的全部非链上临点加入答案即可(即 $\deg_x-2$),$f_{i,1}$ 就是简单累加。注意到这是求的子树内的情况,最后答案用就是

复杂度线性。

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int x, int fa){
f[x][1] = 1 ;
for (auto y : E[x]){
if (y == fa) continue ;
dfs(y, x) ;
chkmax(ans, f[x][1] + f[y][0]) ;
chkmax(ans, f[x][0] + f[y][0]) ;
chkmax(ans, f[x][0] + f[y][1]) ;
chkmax(f[x][0], max(f[y][1], f[y][0]) + deg[x] - 2) ;
chkmax(f[x][1], f[y][0] + 1) ;
}
// debug(f[x][1], ' '), debug(f[x][0]) ;
}

[CF Round#399(Combined) C] Jon Snow and his Favourite Number

你有一串长度为 $n$ 的序列 $a$,重复 $k$ 次操作。问操作后的序列的极值。

操作: 将序列从小到大排序,从 $1$ 标号,对序号为奇数的数 ^(xor) $x$.

$n\leq 10^5,k\leq 10^3$。

打个表发现有循环节,然后我就 naive 地觉得循环节大小一定是 $2$ 导致爆了 OJ。

发现循环节的长度不会超过 $200$。于是就可以暴力 $200$ 次找出循环节来然后做。这样的复杂度是 $O(200\cdot n)$ 的。

关于循环节,个人的理解仅限于 xor 运算有自反性,所以显然循环节应该是偶数长度的。

…不会编了。就当是一个乱搞吧= =

[CF Round#399(Combined) G] The Winds of Winter

给定一棵有根树。若删去一个节点和所有与他相连的边,则会得到一个森林。你希望这个森林中节点最多的树的节点个数尽量少,于是你可以进行至多一次如下操作:

删除一个节点和其父亲之间的边,把这个节点连到某个节点上。这个操作不得改变森林中树的个数。

对于每个节点,输出它作为删去的节点时,进行至多一次操作后的最大树大小的最小值。

输入格式中,一条边的一个端点是 $0$ 说明另一个端点是根。

$1\leq n\leq 3\times 10^5$ 。

首先可以发现,这个操作是具有贪心性质的。必然是从 $x$ 分出的最大 size 连通块里找出一棵子树连接到最小的 size 的连通块里。那么最后答案就是

其中 $p$ 是最大的连通块, $q$ 是最小的连通块,$o$ 是次大连通块,$\zeta$ 是摘下来的子树。那么不难知道这个东西是凸的。那么就考虑去二分这个 $ans$ ,$check$ 的时候自然需要满足

考虑最后一个是定值,于是可以直接设成二分的下界。观察前面两个,本质上就是在查周围分出去的连通块里是否存在一个大小合适的子树 $\zeta$。于是就变成了一个拿 mulity-set 维护 dsu on tree 的直观题目。

维护起来有些麻烦。考虑按照 dfs 序分别维护自己子树内的、祖先链上的、祖先除了自己以外的那些子孙。后面两个可以不断边插边删来做,而自己子树内的则可以考虑由于信息重复率大,所以采用启发式分治(启发式合并)策略——结合轻重链剖分的理论,因为从根到每个点至多经过 $\log n$ 条轻边,所以考虑每个点都只向自己的轻祖先贡献。那么过程就是先分治轻儿子并且清空贡献,然后暴力重儿子,再将轻儿子合并到重儿子的信息里。通过聚和分析不难知道这样是 $O(n\log n)$ 的。这也就是 dsu on tree 的过程。

最后有点细节需要注意,大概就是什么特判 $p=q$ 之类的。

「My-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
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
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

sint other ;
sint dads ;
sint s[N] ;
vint E[N] ;

int n ;
int rt ;
int sz[N] ;
int fa[N] ;
int mx[N] ;
int mn[N] ;
int smx[N] ;
int son[N] ;
int ans[N] ;

void dfs(int x, int dad){
fa[x] = dad ; sz[x] = 1 ;
for (auto k : E[x])
if (k != dad){
dfs(k, x) ;
sz[x] += sz[k] ;
if (!son[x]) son[x] = k ;
if (sz[son[x]] < sz[k]) son[x] = k ;
}
if (x != rt)
other.ins(sz[x]) ;
}
bool isrt(int x){
return (bool)(x == rt) ;
}
bool chk(int v, int x){
// cout << v << " " << x << " " << mx[x] << " " << mn[x] << " " << sz[x] << " " << son[x] << " " << s[x].size() << '\n' ;
if (mx[x] == sz[son[x]]){
auto t = s[x].lwb(mx[x] - v) ;
if (t != s[x].js() && *t <= v - mn[x]) return 1 ;
return 0 ;
}
else {
auto t = other.lwb(mx[x] - v) ;
if (t != other.js() && (*t) <= v - mn[x]) return 1 ;
auto pq = dads.lwb(mx[x] - v + sz[x]) ;
if (pq != dads.js() && (*pq) <= v - mn[x] + sz[x]) return 1 ;
return 0 ;
}
}//mn[x] + x <= ans -> x <= ans - mn[x]
void solve(int x){
// debug(x, ' ') ;
// debug(other.size(), ' ') ;
// debug(s[x].size(), ' ') ;
// debug(dads.size()) ;
if (!isrt(x)){
other.era(other.fd(sz[x])) ;
if (!isrt(fa[x])) dads.ins(sz[fa[x]]) ;
}
mn[x] = n - sz[x] ;
mx[x] = max(n - sz[x], sz[son[x]]) ;
smx[x] = min(n - sz[x], sz[son[x]]) ;
// debug(x, '*') ;
// debug(mn[x], '*') ;
// debug(mx[x], '*') ;
// debug(smx[x], '\n') ;// puts("")
for (auto k : E[x]){
if (k == fa[x]) continue ;
if (k == son[x]) continue ;
solve(k) ;
for (auto t : s[k]) other.ins(t) ;
}
if (son[x]){
solve(son[x]) ;
swap(s[x], s[son[x]]) ;
chkmin(mn[x], sz[son[x]]) ;
if (!mn[x]) mn[x] = sz[son[x]] ;
}
for (auto k : E[x]){
if (k == fa[x]) continue ;
if (k == son[x]) continue ;
chkmin(mn[x], sz[k]) ;
chkmax(smx[x], sz[k]) ;
for (auto t : s[k])
other.era(other.find(t)) ;
}
int l = smx[x], r = mx[x], mid ;
if (smx[x] == mx[x]) goto ycy ;
while (l <= r){
mid = (l + r) >> 1 ;
if (!chk(mid, x)) l = mid + 1 ;
else ans[x] = mid, r = mid - 1 ;
}
ycy : if (!ans[x]) ans[x] = mx[x] ;
for (auto k : E[x]){
if (k == fa[x]) continue ;
if (k == son[x]) continue ;
for (auto t : s[k]) s[x].ins(t) ;
}
if (!isrt(x) && !isrt(fa[x]))
dads.era(dads.fd(sz[fa[x]])) ;
s[x].ins(sz[x]) ;
// debug(x, ' ') ;
// debug(other.size(), ' ') ;
// debug(s[x].size(), ' ') ;
// debug(dads.size()) ;
}
void output(){
for (int k = 1 ; k <= n ; ++ k)
printf("%d\n", ans[k]) ; return ;
}
int main(){
cin >> n ; int x, y ;
for (int i = 1 ; i <= n ; ++ i){
x = qr(), y = qr() ;
if (!x || !y) rt = x + y ;
else E[x].p_b(y), E[y].p_b(x) ;
}
dfs(rt, 0) ;
// debug(son, 1, n) ;
// debug(sz, 1, n) ;
solve(rt) ;
output() ;
return 0 ;
}

[CF Round 400(Combined) D] The Door Problem

给定 $n$ 扇门 $m$ 把钥匙,每一把钥匙会同时控制 $k$ 扇门,每扇门最多被两把钥匙控制。求是否存在一个使用钥匙的方法使得全部的门都变成开的。

降智题。一开始一直在想怎么建图,胡了一个对每扇门建俩点表示开关,被捆绑的状态连边,然后去 check 是否存在一扇门的两个状态在一个 dsu 里…然后就发现读错题了,因为并不一定要用到所有钥匙…

不过有一个很强的性质,就是「每扇门最多被两把钥匙控制」。然后就可以很高兴地对钥匙建虚点。也就是说对于一把钥匙建立俩点,一个表示用了一个表示没用。然后考虑把视线转到门这边,根据「每扇门最多被两把钥匙控制」可知如果某扇门本来是开的,就应该两把钥匙一起用,否则只用一把。根据这个一点建边即可。

= =人生太艰难了。

[CF Round 190(Div1) C] Ciel the Commander

给定一棵树,每个点分配一个字母 A~Z。问是否存在一个分配方案使得任意两点 $(x,y)$ 之间的简单路径上不存在点比 $x$ 或者 $y$ 字典序大的字母。

$1\leq n\leq3\times 10^5$ 。

可以比较奇妙地做一个代换。考虑对于一个点,他连出的连通块大小分别是 $s_1,s_2,s_3\cdots s_k$。那么不难发现无论这个点是谁,都存在 $\sum s_i=n-1$ 。那么当和不变的时候,各元素分的越平均,两两成绩之和就越大(可以用Cauchy不等式证)。于是可以知道应该按重心分,重心处字典序尽可能小,就变成了一个模拟点分治题。

[CF Codefest 18 D] Valid BFS ?

给出一棵树的一个 BFS 序,判断其是否合法。

整理这题是因为自己想的ez方法被叉了…大概就是考虑对这棵树先 dfs 一遍,求出所有深度,然后 BFS 序中一定不会不会存在前面点的深度比后面的小这种情况。然而这是广大必要不充分条件的其中之一,因为没有考虑同一个点的儿子一定是被连续加入队列中这个约束。

于是可以考虑另一种比较简洁的方法。考虑对每个点的孩子按照给出的 BFS 序里的顺序排一遍序,每次走孩子按照该顺序走。最后检测合法性只需要比对一下和走出来的真实 BFS 序是否一致即可。

[CF Round #513(Combined) D] Social Circles

现在有 $n$ 个人,每一个人都不想周围的人坐得离他很近,所以在他的左边要放 $l_i$ 张空的椅子,右边要放 $r_i$ 张空的椅子。

现在他们要坐成若干个圈,请问最少要放多少张椅子。

注意:可以一个人坐在一个圈内,每一个人还需要坐一张椅子。

$1\leq n\leq 10^5$ 。

一开始觉得是要让所有人按照 $\max\{l_i,r_i\}$ 排个序,然后最优的一定是两两一组判个边界。后来发现假了。比较正确的贪心应该是需要考虑「左右无关」。即由于圈是随便划分的,所以应该对每个 $r_i$ 选一个跟它大小最接近的 $l_i$。这样就可以直接对两个数组排个序然后做了。

[CF Round #513(Combined) E] Sergey and Subway

给出一颗 $n$ 个节点的树。现在要将原图中每对不直接连边,但是拥有共同邻居的两个点之间连一条边。

现在需要求出新图中每一个点对 $(i,j) (1 \leq i \leq j \leq n)$ 的经过的边数和。

$1\leq n\leq 10^5$ 。

再一次惨遭降智,GG。

不过话说回来这题的 statement 属实弱智。他题面里每个 tunnel 之前都加了 directed 作为修饰,这 tm 告诉我不是代表树形图而是代表每个数对只算一次我也是很佛。出题人是半辈子没说过话吗?非要在题面里把自己知道的形容词都 nmd 列出来一遍??

好了,祖安结束。考虑本质上连的这些边对答案的应先就是把原来某些长度为 $2$ 的路径压缩成了长度为 $1$ 的路径。具体的,如果 $(x,y)$ 之间的距离原本是 $p$,那么如果 $p$ 是奇数,路径长度就会变成 $\left\lceil\dfrac{p}{2}\right\rceil$,否则是 $\dfrac{p}{2}$ 。

考虑距离可以怎么量化。由于

可以发现最后一项系数是 $2$ 不造成什么影响。于是就可以直接计算 $dep(x)+dep(y)$ 是奇数的贡献了,不难知道这需要 $dep(x),dep(y)$ 中恰好一个点的深度为奇数。 算一下就好了。

说实话这题降智在考虑到深度那个地方就停了…