【训练记录】6.8 训练笔记

今天因为补 CF 就又只打了一场。咕咕咕。

A

比较传统的一道简单题。但是俩 log 被卡了= =

大概就是说考虑最大值最小,可能可以想到要去二分答案。然后考虑判定,考虑一个权值 $v$ 合法,当且仅当可以选出一个长度 $\geqslant k$ 的子序列使之和 $\leq v$ 。这个可以用 ds 维护,也可以直接贪。

感觉个人比较看不透这个贪心,换句话说你要让我写我肯定写不出来,有点反直觉。具体来说就是考虑每次将一个元素 push 到一个栈里,然后如果当前元素与栈顶元素之和 $\gt v$ 就不把当前元素入栈,否则如果当前元素 $\lt$ 栈顶元素就先弹栈再入栈。最后判一下头尾就好了。

感觉这么贪心的道理在于, 最后一个元素要么是序列末尾的元素,要么就是后缀中最小的那个。所以判头尾才不会锅。

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

#include <algorithm>

using std :: max ;
using std :: min ;

const int N = 200010 ;

const int M = 2000000001 ;

int cnt ;
int ans ;
int n, k ;
int tmp[N] ;
int base[N] ;
int mxv, mnv ;

bool check(int x){
tmp[cnt = 1] = base[1] ;
for (int i = 2 ; i <= n ; ++ i){
if (1ll * tmp[cnt] + base[i] <= x) tmp[++ cnt] = base[i] ;
else if (tmp[cnt] > base[i]) tmp[cnt] = base[i] ;
}
if (cnt > k) return 1 ;
if (cnt == k && 1ll * tmp[1] + tmp[cnt] <= x) return 1 ;
return 0 ;
}
int main(){
scanf("%d%d", &n, &k) ;
int l, r, mid ; mnv = M ;
for (int i = 1 ; i <= n ; ++ i){
scanf("%d", &base[i]) ;
mnv = min(mnv, base[i]) ;
mxv = max(mxv, base[i]) ;
}
l = mnv << 1 ;
r = mxv << 1 ;
while (l <= r){
// printf("%d %d\n", l, r) ;
mid = (1ll * l + r) >> 1 ;
if (check(mid))
ans = mid, r = mid - 1 ;
else l = mid + 1 ;
}
printf("%d\n", ans) ; return 0 ;
}

B

挺有意思的一道结论题…主要是(标算的)思考过程挺妙,不过猜完就走人了谁还证啊。

大概是考虑从二分答案出发。把 $\geqslant v$ 的所有位置置为 $1$,其余位置置为 $0$ 。那么答案 $v$ 合法当且仅当存在一行的所有数都为 $1$。首先充分性不难知道,小 D 只要忽略这一行,每次删其他的,这样小 Y 由于每次只能删一列,所以最后必然是小 D 获胜。

必要性考虑归纳。$n=1$ 不难知道,然后考虑 $n=k\to n=k+1$ 。发现此时剩下了 $k$ 行 $k+1$ 列,轮到小 Y 操作,那么考虑每一行从左往右第一个 $0$,由鸽笼原理可知,必定存在一列不包含这些 $0$ 中的任意一个。所以剩下的局面就可以归纳到 $n=k$ 里面。证毕。

观察这个过程,发现其实不需要二分,每一行中最小的数,所有行中的最大值即为答案。扫一遍就完了。

C

这题对我这种数位 DP 萌新很不友好…

一开始想了个暴力求 count_of_1 的东西,发现并不是这么算的…即发现改变的位置是 $r$ 二进制下 $1$ 的位数和 $l-1$ 二进制下 $1$ 的和,但是要减去那些改了两遍的,经过冷静找性质可以发现,这部分就是两者从高位到低位的最长公共前缀里面 $1$ 的数量乘二。

然后就考虑分别对这两个进行数位 $dp$ 。发现对于 $r\geq l$ 的限制完全可以去掉,因为容斥的时候会被直接容斥掉。那么总方案数就可以直接乘一个系数 $n$,就只需要计算「$1\sim n$ 之间所有数的二进制下 $1$ 的个数」 和 「$1\sim n$ 内所有的数对 $(l,r)$ 的 count_of_1(LCP) 」。

设 $g_{i,j,0/1}$ 表示从高到低考虑了前 $i$ 位,有 $j$ 个 $1$ , $r$ 是否等于 $n$ 的方案数。转移时需要考虑分类讨论 $n$ 的当前位是否为 $1$ ,具体转移大概就是判断一下转移前后 $r$ 是否依旧 $=n$ 之类的。同时设 $f_{i,j,0/1,0/1}$ 表示考虑前 $i$ 位,最大公共前缀中 $1$ 的个数为 $j$,$l=r?,r=n?$ 的方案数。然后转移依旧是根据边界分类讨论当前位放 $1$ 还是 $0$,注意到由于加上了 $l,r$ 的限制,所以要分类讨论 $l,r$ 分别放不放,所以会有个系数。

然后最后答案就是

复杂度 $O(T\log n^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
int T ;
int cnt ;
ll n, m ;
ll ans1 ;
ll ans2 ;
int base[N] ;
int g[N][N][2] ;
int f[N][N][2][2] ;

int main(){
cin >> T ;
while (T --){
ans1 = ans2 = 0 ;
memset(g, 0, sizeof(g)) ;
memset(f, 0, sizeof(f)) ;
cin >> n ; m = n ; cnt = 0 ;
while (m) base[++ cnt] = m & 1, m >>= 1 ;
reverse(base + 1, base + cnt + 1) ;
g[0][0][1] = 1, f[0][0][1][1] = 1 ;
for (int i = 0 ; i < cnt ; ++ i){
if (base[i + 1]){
for (int j = 0 ; j <= i ; ++ j){
add(g[i + 1][j][0], g[i][j][0]) ;
add(g[i + 1][j][0], g[i][j][1]) ;
add(g[i + 1][j + 1][1], g[i][j][1]) ;
add(g[i + 1][j + 1][0], g[i][j][0]) ;
}
}
else {
for (int j = 0 ; j <= i ; ++ j){
add(g[i + 1][j][0], g[i][j][0]) ;
add(g[i + 1][j][1], g[i][j][1]) ;
add(g[i + 1][j + 1][0], g[i][j][0]) ;
}
}
}
for (int i = 0 ; i < cnt ; ++ i){
if (base[i + 1]){
for (int j = 0 ; j <= i ; ++ j){
add(f[i + 1][j][0][1], f[i][j][1][1]) ;
add(f[i + 1][j][1][0], f[i][j][1][1]) ;
add(f[i + 1][j + 1][1][1], f[i][j][1][1]) ;
add(f[i + 1][j][0][0], f[i][j][1][0]) ;
add(f[i + 1][j][1][0], f[i][j][1][0]) ;
add(f[i + 1][j + 1][1][0], f[i][j][1][0]) ;

add(f[i + 1][j][0][1], 2ll * f[i][j][0][1] % P) ;
add(f[i + 1][j][0][0], 2ll * f[i][j][0][1] % P) ;

add(f[i + 1][j][0][0], 4ll * f[i][j][0][0] % P) ;
}
}
else {
for (int j = 0 ; j <= i ; ++ j){
add(f[i + 1][j][1][1], f[i][j][1][1]) ;
add(f[i + 1][j][0][0], f[i][j][1][0]) ;
add(f[i + 1][j][1][0], f[i][j][1][0]) ;
add(f[i + 1][j + 1][1][0], f[i][j][1][0]) ;

add(f[i + 1][j][0][1], 2ll * f[i][j][0][1] % P) ;

add(f[i + 1][j][0][0], 4ll * f[i][j][0][0] % P) ;
}
}
}
for (int i = 1 ; i <= cnt ; ++ i)
add(ans1, 1ll * i * addn(g[cnt][i][1], g[cnt][i][0]) % P) ;
for (int i = 1 ; i <= cnt ; ++ i)
add(ans2, 1ll * i * addn(f[cnt][i][0][1], f[cnt][i][0][0]) % P) ;
cout << decn(1ll * ans1 * (n % P) % P, 2ll * ans2 % P) << '\n' ;
}
}

D

$1\leq n\leq 100$ 。

$1\leq X\leq 10^6$ 。

发现变量有俩,楼的高度和楼之间的距离。发现限制之间是有关系的,于是考虑定住一个,比如楼的高度。考虑设两栋楼之间的距离是 $x_i$ ,那么要满足 $x_i\geqslant \max\{h_i,h_{i-1}\}$ 。设

那么可知方案数就是

这就是一个 $n+1$ 元一次不定方程组的问题。这个地方涉及到一个技巧。就是考虑首先值域是 $[1,X]$ ,所以取值有 $X-1$ 个。其次由于要求总和 $\leqslant X$,那么可以考虑多设出一个变量用来保存余出去的 $X-s$,所以就是 $n+1$ 个元素。

然后就是考虑对 $s$ 进行 dp。具体的,设 $f_{i,j,k}$ 表示现在考虑了 $1\sim i$ 的排列,还有 $j$ 个位置没有闭合,即还有 $j$ 个位置可能还会插入更大的数,当前 $s$ 值为 $k$ 的方案数。然后考虑每次相当于选一个位置插入一个 $i$ ,此时会产生两个新的空位,然后分类讨论一波闭合不闭合就好了。注意到如果插入开头或者结尾,那么就只会产生 $1$ 个空位,特判一下这个边界就好了。最后复杂度 $O(n^4+X)$ 。

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 res ;
int ans ;
int n, m ;
int inv[N] ;
int fac[N] ;
int f[2][M][N] ;

int expow(int a, int b){
int ret = 1 ;
while (b){
if (b & 1)
ret = (ll)ret * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return ret ;
}
int binom(int x, int y){//\binom{x}{y}
return (ll)fac[x] * inv[y] % P * inv[x - y] % P ;
}
void prework(int mx){
fac[0] = inv[0] = 1 ; ans = res = 0 ;
for (int i = 1 ; i <= mx + 1 ; ++ i)
fac[i] = 1ll * fac[i - 1] * i % P ;
inv[mx + 1] = expow(fac[mx + 1], P - 2) ;
for (int i = mx ; i >= 1 ; -- i)
inv[i] = 1ll * inv[i + 1] * (i + 1) % P ;
}
int main(){
cin >> n >> m >> P ; int t ;
prework(m) ; f[0][0][0] = 1 ;
for (int i = 1, d = 0 ; i < n ; ++ i){
t = i * i ;
for (int j = 0 ; j <= i ; ++ j)
for (int k = 0 ; k <= t ; ++ k) f[d ^ 1][j][k] = 0 ;
for (int j = 0 ; j <= i ; ++ j){
if (j){
int p = j + 1, q = j + 2 ;
for (int k = 0 ; k <= t ; ++ k){
add(f[d ^ 1][j - 1][k + (i + 1) * 2], 1ll * j * f[d][j][k] % P) ;
add(f[d ^ 1][j][k + i + 1], 2ll * p * f[d][j][k] % P) ;
add(f[d ^ 1][j + 1][k], 1ll * q * f[d][j][k] % P) ;
}
}
else {
int p = j + 1, q = j + 2 ;
for (int k = 0 ; k <= t ; ++ k){
add(f[d ^ 1][j][k + i + 1], 2ll * p * f[d][j][k] % P) ;
add(f[d ^ 1][j + 1][k], 1ll * q * f[d][j][k] % P) ;
}
}
}
d ^= 1 ;
}
for (int i = 0 ; i <= m ; ++ i)
add(ans, 1ll * f[!(n & 1)][0][i] * binom(m - i + n - 1, n) % P) ;
cout << ans << '\n' ; return 0 ;
}