【题解】[Codeforces Global Round#5 A~F] 口胡记

单独整理这一场,一是因为这一场的题目质量整体比较高,二是因为这一场的 E 是实在是有点神仙…

托老师还是宝刀不老鸭!

以下部分简单题是在宿舍自习室里口胡出来的。

A

秒了。题面太长了。考虑一定可以让正数和负数各余出 $1$ 的贡献,然后就做完了。

B

秒了。一开始觉得可能是什么俩排列的 LCS 之类的。后来重读了一遍题发现原来只需要记一个前缀 $\max$ 去判断是否有车被自己之后的超了就完了。

C1 & C2

这个 C 不知为何把我给狙了…于是就只胡出来了 C1。

C1 大概是考虑先 $n^2$ 求一遍交,然后不断删相距最近的相交的弦,删到都不相交为止,然后随便配对就好了。

C2 翻车的原因是推了个假结论…觉得如果排个序之后,从最中间的两个开始匹配,l--,r++ 这种就一定可以。然后发现理解错题意了…三个点的偏序顺序并不需要相同。

冷静下来发现,可以对每一维分治。即 $x,y$ 相同的可以相邻匹配,删掉之后 $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
struct nd{
int id ;
int x, y, z ;
}base[N], re1[N], re2[N] ;

int n ;
int cnt ;

inline bool comp(const nd &a, const nd &b){
return a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x < b.x ;
}
inline bool x_y_equal(const nd &a, const nd &b){
return (a.x == b.x && a.y == b.y) ;
}
inline bool x_equal(const nd &a, const nd &b){
return (a.x == b.x) ;
}
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i){
base[i].x = qr(), base[i].id = i ;
base[i].y = qr(), base[i].z = qr() ;
}
sort(base + 1, base + n + 1, comp) ;
base[n + 1] = (nd) {0, -P, -P, -P} ;
for (int i = 1 ; i <= n ; ++ i){
if (x_y_equal(base[i], base[i + 1]))
printf("%d %d\n", base[i].id, base[i + 1].id), ++ i ;
else re1[++ cnt] = base[i] ;
}
swap(re1, base) ;
n = cnt ; cnt = 0 ;
base[n + 1] = (nd){0, -P, -P, -P} ;
for (int i = 1 ; i <= n ; ++ i){
if (x_equal(base[i], base[i + 1]))
printf("%d %d\n", base[i].id, base[i + 1].id), ++ i ;
else re2[++ cnt] = base[i] ;
}
swap(re2, base) ;
n = cnt ; cnt = 0 ;
base[n + 1] = (nd){0, -P, -P, -P} ;
for (int i = 1 ; i <= n ; i += 2)
printf("%d %d\n", base[i].id, base[i + 1].id) ; return 0 ;
}

D

秒了。虽然一开始没啥想法,但是直觉告诉我应该找上界,然后发现上界是 $2n$ 。于是就可以把数组拼三遍,然后就可以对每个位置 $i$,由于都具有单调性,二分出第一个 $k\in[i+1,i+2\cdot n]$ 使得后缀 $\min$ < 前缀 $\max\times \dfrac{1}{2}$ 的位置就好了。

E

这个找性质题…有点强。

求有多少棵点数为 $n(n\leqslant 10^6)$ 的,键值为 $1\sim n$ 的排列的二叉搜索树满足以下条件:

$(1)$ balanced每个点的总深度和最小。

$(2)$ striped.1 对于每个点,如果它有左儿子,那么左儿子的键值和它的键值奇偶性不同

$(3)$ striped.2 对于每个点,如果它有右儿子,那么右儿子的键值和它的键值奇偶性相同

答案对 $998,244,353$ 取模。

【以下是心路历程】

读题的时候由于旁边只有过时的牛津字典,于是查了查发现 parity 是什么 平价 ,然后 striped 是什么有条纹的。我就 ??? 。不过想了一会儿就猜出来应该是在说奇偶性了。

然后就向着要一个一个条件地去容斥…大概是首先发现合法的二叉排序树严格对应于不同形态的二叉树,换句话说每一种形态的二叉树都有恰好一个填充方式使之成为二叉搜索树。尝试证明发现显然,因为每种形态的二叉树的中序遍历唯一,而二叉搜索树的中序遍历的键值序列恰好是 $1\sim n$ 的排列。所以发现这部分答案就是卡特兰数。

…事实证明如果基础掌握不扎实,就可能会花上那么几十秒的时间去现推一波已知结论…

但,这个结论,最后也根本没有用上。因为发现剩下两个条件根本没什么简洁的方法直接容斥出来。直到今天早上早读——


发现这个 balanced 是个很强的约束,可以观察到在第一个条件下根节点只能是 $\left\lceil\dfrac{n}{2} \right\rceil$ 或者 $\left\lfloor\dfrac{n}{2} \right\rfloor$ 。然后紧接着可以发现每个子树在第一个约束下都只能是类似状态。然后考虑第二个条件,一个很重要的事实在于,可以发现键值 $n$ 永远是在最右侧的链,所以可以知道 $n$ 一定和 $root$ 的键值奇偶性相同。接着,由于右子树的点集是 $[root,n]$ ,那么不难知道每个根的右子树 $size$ 都必然是偶数

有了这些性质,可以发现对于每个 $n$ ,答案至多为 $1$ 。

证明可以考虑假设有两个均满足条件的树 $T_1,T_2$ ,那么他们一定有某部分同构,剩下的部分不同构。考虑不同构的那部分,由于要满足 perfect balanced ,所以可以知道「不同构」只能是把某个点的某个子树的一个点移到另一颗子树里,这要满足两个子树 size 之前相差 $1$ ,所以 $T_1,T_2$ 中必然有一棵树满足存在一个点,其右子树的 size 是奇数。所以可知答案至多为 $1$ 。

于是就可以直接从 $size=1$ 开始构造了。复杂度 $\log n$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>

int n ;
int ans ;

int main(){
ans = 1 ;
scanf("%d", &n) ;
while (ans <= n){
if (ans == n || ans == n - 1) return puts("1"), 0 ;
if (ans & 1) (ans <<= 1) += 2 ; else (ans <<= 1) += 1 ;
}
return puts("0"), 0 ;
}

F

比较简单的计数题?大概就是考虑无论是横着的牌占了某一列或竖着占了某一列,都是占(也叫做「横竖都是占」),所以可以用行列无关的思想来 DP。具体的,设 $f_{i,j}$ 表示前 $i$ 行选了 $j$ 对相邻的两行,$g_{i,j}$ 表示前 $i$ 列选了 $j$ 对相邻的两列。那么会有转移

其中 $\{\tau\}$ 可以看做通配符。转移注意特判一下合法性。然后就可以合并出答案来

其中 ${\rm P}(n,m)$ 是从 $n$ 个元素里面选 $m$ 个元素的排列数。之所以是排列数是因为对于某些确定横着放的骨牌,$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
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
#include <cstdio>

#include <algorithm>

using namespace std ;

#define il inline

const int N = 5050 ;

typedef long long ll ;

const int P = 998244353 ;

int ans ;
int fac ;
int smax ;
int sn, sm ;
int n, m, k ;
int visr[N] ;
int visc[N] ;
int f[N][N] ;
int g[N][N] ;
int perm[N][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 T addn(T x, ll y, int mod = P){
x += y ; return (x = x > mod ? x - mod : x) ;
}

int chkr(int x, int y){
return ((!visr[x] && !visr[x - 1]) && y && (bool)(x - 1)) ;
}
int chkc(int x, int y){
return ((!visc[x] && !visc[x - 1]) && y && (bool)(x - 1)) ;
}

int main(){
int a, b, c, d ;
scanf("%d%d%d", &n, &m, &k) ;
smax = max(sn = n, sm = m), fac = 1 ;
for (int i = 0 ; i <= smax ; ++ i) perm[i][0] = 1 ;
for (int i = 1 ; i <= smax ; ++ i)
for (int j = 1 ; j <= i ; ++ j)
perm[i][j] = addn(perm[i - 1][j], perm[i - 1][j - 1]) ;
for (int j = 0 ; j <= smax ; ++ j){
for (int i = j ; i <= smax ; ++ i)
perm[i][j] = 1ll * perm[i][j] * fac % P ;
fac = 1ll * fac * (j + 1) % P ;
}
for (int i = 1 ; i <= k ; ++ i){
scanf("%d%d", &a, &b) ;
scanf("%d%d", &c, &d) ;
if (a == c){
-- sn, -- sm, -- sm ;
visr[a] = 1, visc[b] = visc[d] = 1 ;
}
if (b == d){
-- sm, -- sn, -- sn ;
visc[d] = 1, visr[a] = visr[c] = 1 ;
}
}
f[0][0] = g[0][0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 0 ; j <= (sn >> 1) ; ++ j)
f[i][j] = addn(chkr(i, j) * f[i - 2][j - 1], f[i - 1][j]) ;
for (int i = 1 ; i <= m ; ++ i)
for (int j = 0 ; j <= (sm >> 1) ; ++ j)
g[i][j] = addn(chkc(i, j) * g[i - 2][j - 1], g[i - 1][j]) ;
for (int i = 0 ; i <= (sn >> 1) ; ++ i)
for (int j = 0 ; j <= (sm >> 1) ; ++ j)
add(ans, 1ll * f[n][i] * g[m][j] % P * perm[sn - (i << 1)][j] % P * perm[sm - (j << 1)][i] % P) ;
printf("%d\n", ans) ; return 0 ;
}

然后就没有然后了,G和H是不可能做的 (x