【题解】[CF Round#474(Combined) A~G] 题解

感觉这场的题目质量还是不错的?确实比以前 vp 过的几场 (Div1+Div2) 要好很多。

大概是把除了 H 之外一整场的题目都做掉了。有些不是十分必要写的题目当然就是口胡啦。

A

秒了。

人口普查题。

B

有两个长度均为 $n$ 的序列 $a,b$,定义 ${\rm cost}(a,b)$ :

现在必须恰好对 $a$ 进行 $k_1$ 次操作,对 $b$ 进行 $k_2$ 次操作。操作内容是将某一项加一或者减一。求操作后的最小 $\rm cost$。

$1\leq n\leq 2000$。

秒了。

降智贪心?不知道为什么就想了一会儿,发现 $n=2000$ 之后就秒掉了= =

大概是考虑分类讨论现在操作是让两个数列尽量靠近还是尽量远离。第一种情况每次操作前找到可以使 $\Delta$ 变小最多的,第二种找到让 $\Delta$ 变大最小的就可以了。

C

皮卡丘和他排成一列。他在纸上写下了数组的所有非空子序列。同时他删除了所有的「子序列的最大元素-子序列的最小元素 $\geq d$」的子序列,最终剩下 $X$ 个子序列。现在给出 $X,d$ ,构造一个合法的原序列。

输出数组中的元素数不应大于 $10^4$,数值大小不应超过 $10^{18}$ 。保证 $1\leq X,d\leq 10^9$ 。

秒了。

比较 naive 的一道构造题。大概就是考虑长度为 $n$ 的序列会产生 $2^n-1$ 个子序列,那么考虑直接对 $X$ 进行二进制拆分,之后就是一段 $1$ 一个 $d+1$ 的形式构造就完了。

D

给出一颗无限层的满二叉树。 如果 $x$ 是根,孩子的值是 $2\times x$,右孩子的值是 $2\times x+1$ 。

现在有三种操作:

$(1,x,k)$ :将 $x$ 所在层的所有节点整体向右循环地移动 $k$ 个单位。

$(2,x,k)$ :将 $x$ 所在的层的所有节点及其子树向右循环地移动 k 个单位。

$(3,x)$ :输出从 $x$ 到根的路径。

$1\leq x,k,\leq 10^{18}$ 。

比较麻烦的找性质+模拟题,但还是秒了。但是由于各种细节实现上花了好久

一开始的想法就是,对操作 $(1)$ 的每一层打反向的标记,然后向上跳的时候遇到这一层反向跳一下,第二个操作打另一种正向的标记就好了。写了半天才写出来,这里说几个小细节:

1、两个操作的标记都打在当前层而不是上一层。但是两个标记释放的时刻不同。第二个标记每次要在跳之前下传当前层的,而第一个标记要在跳之后下传下一层的。原因是第一个标记是整体有效的,第二个标记是暂时有效的。

2、第一个标记在输出之后要清除。

3、注意到操作 $(1)$ 标记反向是因为跳的时候要走相对位移。但是如果一开始起点时存在标记,这个标记的作用应该是正向的。判一下即可。

4、<cmath> log2() 贼慢,甚至比手写的还要慢…

于是最后就做到了 log_2 外线性。迄今为止是 Codeforces 全站最快的代码。

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 T ;
ll buc1[70] ;
ll buc2[70] ;

il int i_lg2(ll n){
int m = 0 ;
if (n >> 32) m |= 32, n >>= 32 ;
if (n >> 16) m |= 16, n >>= 16 ;
if (n >> 8) m |= 8, n >>= 8 ;
if (n >> 4) m |= 4, n >>= 4 ;
if (n >> 2) m |= 2, n >>= 2 ;
if (n >> 1) m |= 1, n >>= 1 ;
return m ;
}

int main(){
qr(T) ; int p ;
ll x, y, z, s, t, yf ;
while (T --){
qr(x), qr(y) ;
if (x == 1)
y = i_lg2(y), qr(z), buc1[y] -= z ;
else if (x == 2)
y = i_lg2(y), qr(z), buc2[y] += z ;
else {
qw(y, ' ') ;
p = i_lg2(y) ;
z = 1ll << p ;
s = (z << 1) - 1 ;
t = - buc1[p] & (z - 1) ;
if (t < 0)
t = (t + z) & (z - 1) ;
x = y + t ;
if (x > s)
x = (x & s) + z ;
y = x ;
while (p > 0){
s = (z << 1) - 1 ;
t = buc2[p] & (z - 1) ;
if (t < 0)
t = (t + z) & (z - 1) ;
x = y + t ;
if (x > s)
x = (x & s) + z ;
y = x ;

-- p ;
s = z - 1 ;
z = z >> 1 ;
y = y >> 1 ;
t = buc1[p] & (z - 1) ;
if (t < 0)
t = (t + z) & (z - 1) ;
x = y + t ;
if (x > s)
x = (x & s) + z ;
yf = y ; y = x ;
qw(y, ' '), y = yf ;
}
putchar('\n') ;
}
}
}

E

给定一棵带点权的树,求所有有向路径的权值和。

一条有向路径的权值如下定义:

设这条路径依次经过的点的权值分别为 $a_1, a_2, …, a_k$。

则路径的权值为 $a_1\times (-1)^2+a_2\times (-1)^3+…+a_n\times (-1)^{(n+1)}$。

答案对 $10^9+7$ 取模。

秒了。指想出来但写了一年

然后一眼就是点分…不过好像比较麻烦的样子。

或者考虑直接树形 $dp$ 。就只需要统计出每个点在多少条路径上是奇数位置,多少条路径上是偶数位置。这个可以用比较 trivial 的 up_and_down 技巧来做。具体的,考虑对于奇偶位置分别维护三个信息,$f,g,h$ 分别表示「起点在子树外、终点在子树内」、「起点在子树内,终点在子树外」、「起点在子树内,终点在子树内」三种信息,其中第三种依赖于第二种,第一种需要第二种进行 up_and_down 。这样就可以结合子树 $size$ 直接算出贡献来了。

有小细节需要注意。就是 $f_x,g_x$ 在处理奇数的时候需要判一下 $x$ 的边界。

「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
#include <cstdio>

#include <vector>

typedef long long ll ;

typedef std :: vector <int> vint ;

#define il inline

#define p_b push_back

const int N = 200010 ;

const int P = 1000000007 ;

using namespace std ;

ll ans ;

int n ;
ll f[N][3] ;
ll g[N][3] ;
int size[N] ;
int base[N] ;

vint E[N] ;

template <typename T>
il void add(T &x, ll y, int mod = P){
x += y ; x = x >= mod ? x - mod : x ;
}
template <typename T>
il void dec(T &x, ll y, int mod = P){
x -= y ; x = x < 0 ? x + mod : x ;
}

void dfs(int x, int fa){
f[x][0] = size[x] = 1 ;
for (auto y : E[x]){
if (y == fa) continue ;
dfs(y, x) ; size[x] += size[y] ;
f[x][0] += g[y][0] ; g[x][0] += f[y][0] ;
}
for (auto y : E[x]){
if (y == fa) continue ;
add(f[x][2], (size[x] - size[y] - 1) * g[y][0] % P) ;
add(g[x][2], (size[x] - size[y] - 1) * f[y][0] % P) ;
}
}
void dfs2(int x, int fa){
for (auto y : E[x]){
if (y == fa) continue ;
f[y][1] = g[x][1] ;
g[y][1] = f[x][1] ;
f[y][1] += (g[x][0] - f[y][0]) ;
g[y][1] += (f[x][0] - g[y][0]) ;
dfs2(y, x) ;
}
}
void solve(){
for (int x = 1 ; x <= n ; ++ x){
add(ans, f[x][2] * base[x] % P) ;
dec(ans, g[x][2] * base[x] % P) ;
dec(ans, base[x]) ;
// printf("%lld\n", ans) ;
add(ans, (f[x][1] + 1) * size[x] % P * base[x] % P) ;
// printf("%lld\n", ans) ;
add(ans, f[x][0] * (n - size[x] + 1) % P * base[x] % P) ;
// printf("%lld\n", ans) ;
dec(ans, g[x][1] * size[x] % P * base[x] % P) ;
// printf("%lld\n", ans) ;
dec(ans, g[x][0] * (n - size[x] + 1) % P * base[x] % P) ;
// printf("%lld\n", ans) ; puts("-----------") ;
}
}
int main(){
scanf("%d", &n) ; int x, y ;
for (int i = 1 ; i <= n ; ++ i) scanf("%d", &base[i]) ;
for (int i = 1 ; i < n ; ++ i)
scanf("%d%d", &x, &y), E[x].p_b(y), E[y].p_b(x) ;
dfs(1, 0) ; dfs2(1, 0) ; solve() ; printf("%lld\n", ans % P) ;
}

F

给定 $n$ 个点 $m$ 条边的有向图,可能不连通,可能有重边,也可能会有自环。求最长的路径(可以经过重复节点),使得这条路径的编号和权值都严格单调递增,其中编号指输入的顺序。

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

比较巧的一道题。考虑这题本质其实是一个有向图上边的 LIS。对每个 $x$ 维护一个 map (或者动态开点线段树),存入边权值为 $v$ 时的最长递增路径。考虑每次加进来一条边 $(u,v,w)$,答案就是从 $u$ 的 map 里找出最大的小于 $w$ 的值,根据单调性可知这一定是小于 $w$ 的那个最大值。然后暴力改就好了。不难知道这样做每条边至多被加一次、删一次,复杂度是 $O(m\log n)$ 。

思考了一下,这本质上就是一个 DP。设 $f_k$ 为最后一条边为第 $k$ 条边的最大值,那么转移就是从以边 $k$ 始点为终点的所有路径里选出一个来转移。其实如果考虑到 DP 的话,就变成一道中规中矩的题目了。

「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
#include <map>

#include <cstdio>

#include <algorithm>

using std :: map ;

using std :: lower_bound ;

#define en end
#define be begin

#define lbd lower_bound

const int N = 300010 ;

typedef long long ll ;

int ans ;
int res ;
int n, m ;

map <int, ll> lis[N] ;

int search(int x, int v){
int ret = 0 ;
auto p = lis[x].lbd(v) ;
ret = (p == lis[x].be()) ? 0 : ((-- p) -> second) ; return ret ;
}

int main(){
scanf("%d%d", &n, &m) ; int x, y, z ;
for (int i = 1 ; i <= m ; ++ i){
scanf("%d%d%d", &x, &y, &z) ;
res = search(x, z) ; ++ res ;
if (res > search(y, z)){
auto p = lis[y].lbd(z) ; lis[y][z] = res ;
for (auto q = p ; q != lis[y].en() ; ){
if ((q -> second) > res) break ; q = lis[y].erase(q) ;
}
}
ans = std :: max(ans, res) ;
}
printf("%d\n", ans) ; return 0 ;
}

G

给你三个正整数 $n$,$a$,$b$,定义 $A$ 为一个排列中是前缀最大值的数的个数,定义 $B$ 为一个排列中是后缀最大值的数的个数,求长度为 $n$ 的排列中满足 $A = a$ 且 $B = b$ 的排列个数。

$1\le n \le 10^5$ 。答案对 $998,244,353$ 取模。

感觉这题暴力的话本身也是一个比较有趣的计数题了。自己一开始设的状态是 $f_{i,j,k}$ 表示考虑了 $1\sim i$ 的排列,前缀最大值个数为 $j$,后缀最大值个数为 $k$ 时方案数,但是发现无论是插入最大值还是插入最小值都不是很容易转移。

但是发现如果确定了最大值在哪里,最后的答案就会比较容易计算。具体的,设 $f_{i,j}$ 表示考虑了 $1\sim i$ 的排列,前缀最大值个数为 $j$ 的方案数。那么最后答案就是

然后考虑 $f$ 怎么算,因为最大值会直接影响前缀最大值的个数,所以转移考虑插入最小值。

分别对应了插在第一位和插在中间或者末尾。

不难看出 $\{f\}$ 就是 $\begin{bmatrix} n \ k \end{bmatrix} $ 。然后如果直接暴力的话是 $O(n^2)$ 的。

考虑直接从 $(1)$ 式的组合意义出发计算贡献。发现对于后面两项第一维的指标和是一定的,换句话说后面两项可以看做就是在 $n-1$ 里找出了 $a+b-2$ 个圈来。前面的那个二项式系数就可以看做是对选取的一个组合系数。那么可以知道最后答案就应该是

于是就转化成如何快速求斯特林数某一项的问题了。但是这个并没有什么快速的做法…于是就只能求出一整行。

这还是我第一次写 $s_1$ 求一行。大概是说有恒等式

后面那个单项式显然是可以分治做的。于是最后复杂度 $n\log ^2n$ 。

不过这东西是有单 $\log$ 的倍增做法的。不过感觉一般这种题也没有卡 $\log ^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
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

namespace Poly{
int k, d ;
int rev[N] ;
int g[20][N] ;
ll expow(ll x, ll y){
ll ret = 1 ;
while (y){
if (y & 1)
ret = ret * x % P ;
x = x * x % P ; y >>= 1 ;
}
return ret ;
}
void pre_rt(){
for (rg int i = 0 ; i < 19 ; ++ i){
int* r = g[i], ut ; r[0] = 1 ;
ut = r[1] = expow(3, 998244352 / (1 << (i + 1))) ;
for (int j = 2 ; j < (1 << i) ; ++ j) r[j] = (ll)r[j - 1] * ut % P ;
}
}
template <typename T>
void NTT(T *f, int L, bool mk){
int l = 0 ;
for (rg int i = 0 ; i < L ; ++ i)
if (rev[i] < i) swap(f[i], f[rev[i]]) ;
for (rg int i = 1 ; i < L ; i <<= 1, ++ l){
int *r = g[l], o = i << 1, rt, irt ;
for (rg int j = 0 ; j < L ; j += o)
for (rg int k = j ; k < i + j ; ++ k){
rt = f[k], irt = f[k + i] * r[k - j] % P ;
f[k] = addn(rt, irt), f[k + i] = decn(rt, irt) ;
}
}
if (!mk) return ;
reverse(f + 1, f + L) ;
int o = expow(L, P - 2) ;
for (rg int i = 0 ; i < L ; ++ i) (f[i] *= o) %= P ;
}
void getlen(int x){
d = 1, k = 0 ;
while (d <= x) d <<= 1, ++ k ;
for (rg int i = 0 ; i < d ; ++ i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1)) ;
}
ll tl[N] ;
ll tr[N] ;
int len[N * 3] ;
vll poly[N * 3] ;
#define lc (rt << 1)
#define rc (rt << 1 | 1)
void cdq(int rt, int l, int r){
if (l == r){
len[rt] = 1 ;
poly[rt].p_b(1) ;
poly[rt].p_b(l) ;
return ;
}
int mid = (l + r) >> 1 ;
cdq(lc, l, mid) ;
cdq(rc, mid + 1, r) ;
getlen(len[rt] = len[lc] + len[rc]) ;
memset(tl + len[lc] + 1, 0, sizeof(ll) * (d - len[lc])) ;
memset(tr + len[rc] + 1, 0, sizeof(ll) * (d - len[rc])) ;
// for (int i = len[lc] + 1 ; i <= d ; ++ i) tl[i] = 0 ;
// for (int i = len[rc] + 1 ; i <= d ; ++ i) tr[i] = 0 ;
rg auto lp = poly[lc].begin(), rp = poly[rc].begin() ;
for (rg int i = 0 ; i <= len[lc] ; ++ i) tl[i] = *(lp ++) ;
for (rg int i = 0 ; i <= len[rc] ; ++ i) tr[i] = *(rp ++) ;
NTT(tl, d, 0) ; NTT(tr, d, 0) ;
for (rg int i = 0 ; i <= d ; ++ i) (tl[i] *= tr[i]) %= P ;
NTT(tl, d, 1) ;
for (int i = 0 ; i <= len[rt] ; ++ i) poly[rt].p_b(tl[i]) ;
}
}

int n ;
int a, b ;

ll ans ;
ll fac[N] ;
ll inv[N] ;

int binom(int x, int y){//\binom{x}{y}
return fac[x] * inv[y] % P * inv[x - y] % P ;
}
void prework(int mx){
fac[0] = inv[0] = 1 ; ans = 0 ;
for (int i = 1 ; i <= mx + 1 ; ++ i)
fac[i] = fac[i - 1] * i % P ;
inv[mx + 1] = Poly :: expow(fac[mx + 1], P - 2) ;
for (int i = mx ; i >= 1 ; -- i)
inv[i] = inv[i + 1] * (i + 1) % P ;
}

int main(){
gi(n) ; gi(a) ; gi(b) ; prework(n << 1) ;

if (n == 1) { print(a & b) ; return 0 ; }
if (!a || !b || a + b - 1 > n) { pc('0') ; return 0 ; }

Poly :: pre_rt() ; Poly :: cdq(1, 0, n - 2) ;
reverse(Poly :: poly[1].begin(), Poly :: poly[1].end()) ;
ans = Poly :: poly[1][a + b - 2] * binom(a + b - 2, a - 1) % P ;
print(ans) ; return 0 ;
}