【题解】Cf Round 250

首先呢,做这一场的原因是看了 vfk 的 blog(戳我)感觉很有趣,并且似乎以前的 CF 的 div1 难度比现在低一点,于是就打算做一下。

嗯,是一场 CNround,可能会更贴合国内的出题氛围?感觉质量还是很好的233.

题号是 $\rm CF437/438$。

向前辈们致敬!

$A$

给出一个四项选择题,三长选一短,三短选一长,否则选 $C$。

其中“短”和“长”限制了 2 倍关系。

我不会告诉你这题我交了5遍:(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pair<int, int> L[4] ;
char I[4][MAXN] ; int ans ;

int main(){
cin >> (I[0] + 1) >> (I[1] + 1) >> (I[2] + 1) >> (I[3] + 1) ;
L[0].sc = 0, L[1].sc = 1, L[2].sc = 2, L[3].sc = 3 ;
L[0].fr = strlen(I[0] + 1) - 2, L[1].fr = strlen(I[1] + 1) - 2 ;
L[2].fr = strlen(I[2] + 1) - 2, L[3].fr = strlen(I[3] + 1) - 2 ;
sort(L, L + 4) ;
if (L[3].fr >= L[2].fr * 2) ++ ans ;
if (L[0].fr * 2 <= L[1].fr) ans += 2 ;
//cout << ans << endl ;
if (ans == 1) printf("%c", L[3].sc + 'A') ;
else if (ans == 2) printf("%c", L[0].sc + 'A') ;
else puts("C") ;
}

$B$

给你两个整数$n$, $m$,要求在 $1\sim m$ 中选任意个数 $x_i$,使得 $\sum lowbit(x_i)=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
pair <int, int> p[MAXN] ;
int N, M, cnt, ans[MAXN] ;

int lowbit(int x){ return (x & (-x)) ; }

int main(){
cin >> N >> M ;
for (int i = 1 ; i <= M ; ++ i)
p[i] = make_pair(lowbit(i), i) ;
sort(p + 1, p + M + 1) ;
for (int i = M ; i >= 1 ; -- i)
if (N >= p[i].first)
N -= p[i].first, ans[++ cnt] = p[i].second ;
if (N) return puts("-1") ;
/*while (N){
// cout << N << endl ;
if (N == lowbit(N))
ans[++ cnt] = N ;
else ans[++ cnt] = lowbit(N) ;
if (ans[cnt] > M) return puts("-1") ;
else N -= lowbit(N) ;
}*/
cout << cnt << endl ;
while (cnt) printf("%d ", ans[cnt --]) ;
}

$C$

$n$ 个带权点,$m$ 条无向边,删除一个点就要付出所有与之有相连且没有被删除的点的点权之和的代价。

求删除所有点的最小代价。

$n,m\leq 200,000$

小清新题,可能需要想一会儿。由于发现最后每条边只会被删一次,且每条边显然都可以做到被小权值的点删掉,于是答案就是 $\sum _{k\in E} \min(val_{from(k)},val_{to(k)})$。

1
2
3
4
5
6
7
int main(){
cin >> N >> M ; int i, j, u, v ;
for (i = 1 ; i <= N ; ++ i) cin >> base[i] ;
for (i = 1 ; i <= M ; ++ i)
cin >> u >> v, ans += 1ll * min(base[u], base[v]) ;
cout << ans << endl ; return 0 ;
}

$D$

给定一张点权图,随机选两个点,求两点间所有简单路径中路径上最小点权的最大值的期望。

$n,m\leq 200,000$

开始时一直读不懂题我好难啊

大概就是考虑一遍建生成树一边建生成树一边同记。首先考虑路径一定会在最大生成树上。然后发现由于是最小点权,所以要用小的那个点来统计答案。于是排好序后,对于加入一个点 $u$ 之前的那些点,点权都大于 $u$ 。所以此时 $u$ 可以作为只剩下权值比他大的点时的图中的答案点,统计一下即可。

嗯,是个 trick。记得当时做“货车运输”那题是为了应付作业直接 copy 的同学的代码,导致后来一直不是很熟悉……233

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
LL ans ;
bool vis[MAXN] ;
struct Edge{
int to, next ;
}E[MAXN] ; int head[MAXN], cnt ;
int N, M, base[MAXN], fa[MAXN], sz[MAXN], Id[MAXN] ;

int find(int x){
return x == fa[x] ? x : fa[x] = find(fa[x]) ;
}
il void add(int u, int v){
to(++ cnt) = v, next(cnt) = head[u], head[u] = cnt ;
to(++ cnt) = u, next(cnt) = head[v], head[v] = cnt ;
}
il bool comp(int a, int b){ return base[a] > base[b] ; }
int main(){
cin >> N >> M ; int u, v ;
for (int i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
for (int i = 1 ; i <= N ; ++ i) sz[i] = 1, fa[i] = Id[i] = i ;
for (int i = 1 ; i <= M ; ++ i) scanf("%d%d", &u, &v), add(u, v) ;
sort(Id + 1, Id + N + 1, comp) ;
for (int i = 1 ; i <= N ; ++ i){
LL ctn = 0 ; int n = Id[i], f1, f2 ;
for (int j = head[n] ; j ; j = next(j)){
if (!vis[to(j)]) continue ;
f1 = find(n), f2 = find(to(j)) ;
if (f1 != f2){
ctn += 1ll * sz[f1] * sz[f2],
sz[f1] += sz[f2], fa[f2] = f1 ;
}
}
ans += 1ll * base[n] * ctn, vis[n] = 1 ;
}
return !printf("%lf\n", ans * 2.0 / (1.0 * N * (N - 1))) ;
}

$E$

给出 $n$ 个点,求这个多边形的三角剖分的方案数对 $1e9+7$ 取模。

$n\leq 200$

恕我直言…我对三角剖分唯一知道的就是能叉出多边形面积来233

根据数据范围猜算法,发现应该是区间 $dp$ 的形式。$f_{l,r}$ 表示区间 $l,r$ 内的点的三角剖分方案数。那么转移就是考虑

其中 $[]$ 还是艾佛森括号,$\rm convex$ 函数为一个 $0/1$ 函数,返回给定的三个点对于整个多边形是否是凸的。

然后为了快速判断这个东西,可以先把所有点按照一个方向排一圈,然后叉积求出是否在外侧。

以下是如何用叉积去判:

如果 $a\times b < 0$ 说明 $a$ 在 $b$ 的逆时针方向, $=0$ 说明同向, $>0$ 说明 $a$ 在 $b$ 的顺时针方向。

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
int N ;
double s ;
LL f[MAXN][MAXN] ;
struct nodes{
double x, y ;
nodes friend operator - (const nodes &a, const nodes &b){
return (nodes){a.x - b.x, a.y - b.y} ;
}
double friend operator * (const nodes &a, const nodes &b){
return a.x * b.y - a.y * b.x ;
}
}base[MAXN] ;

int main(){
cin >> N ; int i, j, k ;
for (i = 1 ; i <= N ; ++ i)
scanf("%lf%lf", &base[i].x, &base[i].y) ;
s += base[N] * base[1] ;
for (i = 1 ; i < N ; ++ i)
s += base[i] * base[i + 1], f[i][i + 1] = 1 ;
if (s > 0) reverse(base + 1, base + N + 1) ;
for (i = 1 ; i <= N ; ++ i)
for (j = i - 2 ; j >= 1 ; -- j)
for (k = j ; k <= i ; ++ k)
if ((base[i] - base[j]) * (base[k] - base[j]) > 0)
(f[j][i] += f[j][k] * f[k][i]) %= Mod ;
cout << f[1][N] << endl ;
}

$F$

给定数列,区间查询和,区间取模,单点修改。

$1\leq n,m\leq 100,000,\quad 0\leq a_i\leq 10^9$。

大概就是发现取模的一个性质,就是取模成功之后数值至少减半。可以分类讨论 $p>\frac{n}{2}$ 和 $p\leq \frac{n}{2}$ ,发现 $n$ 对 $p$ 取完膜之后肯定 $<\frac{n}{2}$ 。

于是这东西就是 $\log$ 的。于是就可以直接 $m \log n + m\log a_i$ 做了。

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 mk, n, m, base[N] ;
int val[N << 1] ; LL s[N << 1] ;

int Max(int a, int b){ return a > b ? a : b ; }
void build(int rt, int l, int r){
if (l == r)
return val[rt] = s[rt] = base[l], void() ;
int mid = (l + r) >> 1 ;
build(rt << 1, l, mid) ;
build(rt << 1 | 1, mid + 1, r) ;
s[rt] = s[rt << 1] + s[rt << 1 | 1] ;
val[rt] = Max(val[rt << 1], val[rt << 1 | 1]) ;
}
void _change(int rt, int l, int r, int p, int v){
if (l == r)
return val[rt] = s[rt] = v, void() ;
int mid = (l + r) >> 1 ;
if (p <= mid) _change(rt << 1, l, mid, p, v) ;
else _change(rt << 1 | 1, mid + 1, r, p, v) ;
s[rt] = s[rt << 1] + s[rt << 1 | 1] ;
val[rt] = Max(val[rt << 1], val[rt << 1 | 1]) ;
}
void update(int rt, int l, int r, int ul, int ur, int mod){
if (l == r)
return val[rt] %= mod, s[rt] %= mod, void() ;
int mid = (l + r) >> 1 ;
if (ul <= mid && val[rt << 1] >= mod)
update(rt << 1, l, mid, ul, ur, mod) ;
if (ur > mid && val[rt << 1 | 1] >= mod)
update(rt << 1 | 1, mid + 1, r, ul, ur, mod) ;
s[rt] = s[rt << 1] + s[rt << 1 | 1] ;
val[rt] = Max(val[rt << 1], val[rt << 1 | 1]) ;
}
LL query(int rt, int l, int r, int ql, int qr){
int mid = (l + r) >> 1 ; LL res = 0 ;
if (l >= ql && r <= qr) return s[rt] ;
if (ql <= mid)
res += query(rt << 1, l, mid, ql, qr) ;
if (qr > mid)
res += query(rt << 1 | 1, mid + 1, r, ql, qr) ;
return res ;
}
int main(){
cin >> n >> m ; int l, r, v ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]) ; build(1, 1, n) ;
while (m --){
scanf("%d", &mk) ;
if (mk == 1)
scanf("%d%d", &l, &r),
printf("%lld\n", query(1, 1, n, l, r)) ;
else if (mk == 2)
scanf("%d%d%d", &l, &r, &v),
update(1, 1, n, l, r, v) ;
else scanf("%d%d", &r, &v), _change(1, 1, n, r, v) ;
}
}

$G$

求每个结点都有个权值只在 $c_1, c_2, …, c_n$中取的,总点权为 $s$ 的二叉树的个数。对于每个 $1 \leq s \leq m$ 计算答案。

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

发现其实是一个卡特兰数的转移形式。令 $f_n$ 表示总点权为 $n$ 的二叉树个数,那么转移应该这么转移:

发现后面是 $p + q + m-p-q=m$ ,正好是卷积的形式。

那如果设 $\\{ f_n\\}$ 的生成函数为 $\rm F$, $g_x=[x\in c]$,$\\{g_n\\}$ 的生成函数为 $\rm G$,则有:

那么解一下可以得到

发现改变一下形式之后:

这东西,在取负号的时候,分母是不存在逆元的。所以分母取正号。

然后就多项式一顿套就完了233。

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
const int Gp = 3 ;
int N, M, K, Gi, R[MAXN] ;
LL G[MAXN], H[MAXN], F[MAXN], t[MAXN] ;

inline int expow(int a, int b){
LL res = 1 ;
while (b){
if (b & 1) (res *= a) %= P ;
a = 1ll * a * a % P, b >>= 1 ;
}
return res ;
}
void NTT(LL *J, int L, int flag){
rr LL Gn, Gi = 1 ;
for (rr int i = 0 ; i < L ; ++ i)
if (i < R[i]) J[i] ^= J[R[i]] ^= J[i] ^= J[R[i]] ;
for (rr int i = 1 ; i < L ; i <<= 1){
Gn = expow(Gp, (P - 1) / (i << 1)) ;
for (rr int j = 0 ; j < L ; Gi = 1, j += (i << 1)){
for (rr int k = 0 ; k < i ; ++ k, Gi = Gi * Gn % P){
rr int real = J[j + k], iroot = J[j + k + i] * Gi % P ;
J[j + k] = (real + iroot) % P, J[j + k + i] = (real - iroot + P) % P ;
}
}
}
if (flag > 0) return ;
int Inv = expow(L, P - 2) ; reverse(J + 1, J + L) ;
for (rr int i = 0 ; i < L ; ++ i) J[i] = 1ll * J[i] * Inv % P ;
}
void _Inv(LL *f, LL *g, int len){
if (len <= 1) {
g[0] = expow(f[0], P - 2) ;
return ;
}
rr int i, l = 0, Len = 1 ;
_Inv(f, g, (len + 1) >> 1) ;
while (Len < (len << 1)) Len <<= 1, ++ l ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
for (i = 0 ; i < len ; ++ i) t[i] = f[i] ; NTT(g, Len, 1), NTT(t, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) g[i] = (2ll - t[i] * g[i] % P + P) % P * g[i] % P ;
NTT(g, Len, -1) ; for (i = len ; i < Len ; ++ i) g[i] = 0 ;
}
LL Ig[MAXN], pf[MAXN] ;
void _sqr(LL *f, LL *g, int len){
if (len <= 1){ g[0] = 1 ; return ; }
rr int i, l = 0, Len = 1 ;
_sqr(f, g, (len + 1) >> 1) ;
while (Len < (len << 1)) Len <<= 1, ++ l ;
for (i = len ; i < Len ; ++ i) pf[i] = Ig[i] = 0 ;
for (i = 0 ; i < len ; ++ i) Ig[i] = 0, pf[i] = 2 * g[i] % P ;
_Inv(pf, Ig, len) ; for (i = 0 ; i < Len ; ++ i) /* */ t[i] = 0 ;
for (i = 1 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << ( l - 1 )) ;
NTT(g, Len, 1) ; for (i = 0 ; i < Len ; ++ i) g[i] = g[i] * g[i] % P ;
NTT(g, Len, -1) ; for (i = 0 ; i < len ; ++ i) g[i] = (g[i] + f[i]) % P ;
NTT(g, Len, 1) ; NTT(Ig, Len, 1) ; for (i = 0 ; i < Len ; ++ i) g[i] = g[i] * Ig[i] % P ;
NTT(g, Len, -1) ; for (i = len ; i < Len ; ++ i) g[i] = 0 ;
}
int main(){
rr int i, j, l = 1 ;
Gi = expow(Gp, P - 2) ;
cin >> N >> K, ++ K, M = 1 ;
for (i = 1 ; i <= N ; ++ i)
scanf("%d", &j), F[j] = 1 ;
F[0] = 1 ;
for (i = 1 ; i < K ; ++ i)
F[i] = (-4ll * F[i] % P + P) % P ;
// for (i = 0 ; i < K ; ++ i) cout << F[i] << " " ;
_sqr(F, G, K), (G[0] += 1) %= P ;
// for (i = 0 ; i < K ; ++ i) cout << G[i] << " " ;
_Inv(G, H, K) ;
for (i = 1 ; i < K ; ++ i)
printf("%lld\n", H[i] * 2ll % P) ;
return 0 ;
}