【训练纪录】6.1 训练笔记

记录一下今天的两场比赛。懒得搬题面了。

A.M.

A

一开始写这题,在一眼二分之后摸了很久。原因是我觉得两个圆合并起来应该等效于一个大圆。写了一会儿挂了就去 Geogebra 上模拟了一组手捏的小样例发现自己假了= =

然后发现似乎本质上就是一个奶酪,于是就写了个 $k^2$ 的并查集去 check,喜提 $75$ 分。想了想觉得 $k^2\log V$ 大概过不去 $k=7000$ 就去搞 T2 了。

然后考虑满分。大概是首先把上下边界也作为点加进去。根据二分 check 的过程,是每次二分出一个半径然后把该半径下相交的圆都连边,然后去判断上下边界是否在一个 dsu 里,换句话说就是去 check 上下边界之间的所有路径中,是否存在一条路径的最长边小于二分出的 $v$ 。发现有单调性,只关心较小的那些边。于是就转化成求 MST,然后找一下 $k+1,k+2$ 之间的边权最大值即可。

MST 需要用 Prim (话说这还是我第一次写 Prim,根据百度百科 yy 出来的,感觉挺ez),因为本题是十分稠密的稠密图。

最后复杂度 $O(n^2)$,不知道为什么自己常数过大导致不能显式建边= =

「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

db ans ;
int cnt ;
db mx[N] ;
db mn[N] ;
int fa[N] ;
int n, m, k ;
db A[N][N] ;
struct Planet{
db x ; db y ; db r ;
Planet (db a = 0, db b = 0, db c = 0 ){ x = a, y = b, r = c ; }
}base[N], crs[N] ;

int find(int x){
if (x == fa[x]) return x ;
return fa[x] = find(fa[x]) ;
}
void merge(int x, int y){
// cout << x << " " << y << '\n' ;
int f1 = find(x) ;
int f2 = find(y) ;
if (f1 != f2){
fa[f1] = f2 ;
mn[f2] = min(mn[f1], mn[f2]) ;
mx[f2] = max(mx[f1], mx[f2]) ;
}
}
bool comp(const Planet &A, const Planet &B){
return A.x == B.x ? A.y < B.y : A.x < B.x ;
}
inline db dist(db a, db b, db c, db d){
return sqrt((a - c) * (a - c) + (b - d) * (b - d)) ;
}
inline db cross(const Planet &A, const Planet &B, db r){
db ds = dist(A.x, A.y, B.x, B.y) ;
return (bool)(ds <= r + r) ;
}
bool check(db r){
for (int i = 1 ; i <= k ; ++ i)
fa[i] = i, mx[i] = mn[i] = base[i].y ;
for (int i = 2 ; i <= k ; ++ i)
for (int j = 1 ; j < i ; ++ j)
if (cross(base[i], base[j], r))
merge(i, j) ;
//debug(r), debug(fa, 1, k) ;
// cout << mx[4] << " " << mn[4] << '\n' ;
for (int i = 1 ; i <= k ; ++ i)
if (mx[find(i)] + r >= m - r && mn[find(i)] - r <= r) return 0 ;
return 1 ;
}
vint E[N] ;
db val[N] ;
db cost[N] ;
bool vis[N] ;
int done[N] ;
int minv[N] ;
db dis(int a, int b){
if (b >= k - 1) base[b].x = base[a].x ;
if (a >= k - 1) base[a].x = base[b].x ;
return dist(base[a].x, base[a].y, base[b].x, base[b].y) ;
}
void Prim(){
vis[1] = 1 ;
done[++ cnt] = 1 ;
for (int i = 2 ; i <= k ; ++ i)
cost[i] = dis(1, i), minv[i] = 1 ;
while(cnt < k){
db cst = 1e18 ; int id = 0 ;
for (int i = 1 ; i <= k ; ++ i){
if (vis[i]) continue ;
if (cost[i] < cst)
cst = cost[id = i] ;
}
E[id].p_b(minv[id]) ;
E[minv[id]].p_b(id) ;
done[++ cnt] = id ; vis[id] = 1 ;
for (int i = 1 ; i <= k ; ++ i){
if (vis[i]) continue ;
if (cost[i] > dis(id, i))
cost[i] = dis(id, i), minv[i] = id ;
}
}
}
void dfs(int x, int fa){
// cout << x << " " << val[x] << '\n' ;
for (auto d : E[x])
if (d != fa){
val[d] = max(dis(x, d), val[x]) ; dfs(d, x) ;
}
}
int main(){
cin >> n >> m >> k ;
for (int i = 1 ; i <= k ; ++ i)
base[i].x = qr(), base[i].y = qr() ;
if (k <= 20){
sort(base + 1, base + k + 1, comp) ;
db l = 0.0, r = max(n, m), mid ;
while (fabs(r - l) > eps){
mid = (l + r) * 0.5 ;
if (check(mid))
ans = mid, l = mid + eps ;
else r = mid - eps ;
}
printf("%.7lf", ans) ;
}
else {
base[++ k] = Planet(0, m) ;
base[++ k] = Planet(0, 0) ;
Prim() ; dfs(k - 1, 0) ;
printf("%.8lf\n", 0.5 * val[k]) ;
}
return 0 ;
}

B

谔谔题。根据某「平面最近点对」可以知道,平面撒点一定程度上可以乱搞。然后去可以考虑二分一个答案,观察到上边界和有边界都是单调不降的,于是 check 的时候考虑直接暴力 check 直到凑齐 $n$ 个点。似乎一开始 random_shuffle 一次就很难被卡掉了。

std 是什么诡异的分类讨论贪心,这东西怎么会有正常人写= =

「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

struct tr{
int x, y, id ;
bool operator <(const tr & t)
const { return t.x == x ? t.y < y : t.x < x ; }
}base[N] ;

int n ;
bool nt ;
int cnt ;
bool vis[N] ;

ll ans ;

bool check(ll v, bool ouf){
int x = 1 ;
int y = 1 ;
cnt = 0, nt = 0 ;
fill(vis + 1, vis + n + 1, 0) ;
while (1){
nt = 0 ; //cout << x << " " << y << '\n' ;
for (int i = 1 ; i <= n ; ++ i)
if (!vis[i] && max(x, base[i].x) - x + max(y, base[i].y) - y <= v){
if (ouf) printf("%d ", base[i].id) ; vis[i] = 1 ;
chkmax(x, base[i].x), chkmax(y, base[i].y), ++ cnt, nt = 1 ;
}
if (cnt == n) return 1 ; if (!nt) return 0 ;
}
return 1 ;
}

int main(){
cin >> n ; ll l, r, mid ;
for (int i = 1 ; i <= n ; ++ i)
base[i].x = qr(), base[i].y = qr(), base[i].id = i ;
random_shuffle(base + 1, base + n + 1) ;
l = 0, r = 1ll << 60 ;
while (l <= r){
mid = (l + r) >> 1 ;
// debug(mid) ;
if (check(mid, 0))
ans = mid, r = mid - 1 ;
else l = mid + 1 ;
}
// debug(ans) ;
return !check(ans, 1) ;
}

C

结论题,并且结论还不容易猜= =

大概就是考虑这么一种操作,把一只放在中间的鞋子当作工具人,不难发现周围 4 个都可以被调整好,同理他们之前也可以作为工具人去调整别的。所以不难发现直接把所有相邻的左右鞋连边做一个二分图匹配或许是对的,因为可以把所有不在匹配里的点当做工具人。但是这个思路有个问题,就是如果跑出来的匹配是完美匹配怎么办?

首先不难知完美匹配时答案会是 $\dfrac{n\times m}{2}$ 或者 $\dfrac{n\times m}{2} -1$ 。然后 emmm。

然后就变得奇怪起来了。大概是考虑将鞋子的朝向设个权值 $0,1,2,3$ 分别表示左上右下。那么如果设匹配之后鞋子的朝向的权值和 $\rm S_1$ ,匹配之前的权值和为 $\rm S_0$ ,那么如果这个匹配是完美匹配且成立,那么需要满足

证明的话考虑 1、完美匹配彼此之间一定是对 $4 $ 取模同余的。2、任意权值和模 $4$ 同余的状态两两可达。然后因为懒于是就直接放题解图片了= =

这种题到底该怎么做啊?考场上现证一遍?我寻思着这一点也不好猜啊 QAQ

「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
int cnt ;
int re1 ;
int re2 ;
int ans ;
int n, m ;
int mat[M] ;
int vis[M] ;
int Id[N][N] ;
int isleft[N][N] ;

char S[M] ;
char T[M] ;

vint E[M] ;

bool do_match(int x){
for (auto k : E[x]){
if (vis[k]) continue ; vis[k] = 1 ;
if (!mat[k] || do_match(mat[k]))
return mat[x] = k, mat[k] = x, 1 ;
}
return 0 ;
}

int main(){
cin >> n >> m ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
Id[i][j] = ++ cnt ;
for (int i = 1 ; i <= n ; ++ i){
cin >> (S + 1) ;
for (int j = 1 ; j <= m ; ++ j)
if (S[j] == 'L') isleft[i][j] = 1 ;
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j){
if ((isleft[i][j] ^ isleft[i + 1][j]) && i + 1 <= n)
E[Id[i][j]].p_b(Id[i + 1][j]), E[Id[i + 1][j]].p_b(Id[i][j]) ;
if ((isleft[i][j] ^ isleft[i][j + 1]) && j + 1 <= m)
E[Id[i][j]].p_b(Id[i][j + 1]), E[Id[i][j + 1]].p_b(Id[i][j]) ;
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
if ((i + j) & 1){
fill(vis + 1, vis + cnt + 1, 0) ;
ans += do_match(Id[i][j]) ; //debug(ans) ;
}
if (n * m & 1){
cout << ans << '\n' ;
return 0 ;
}
// debug(ans) ;
for (int i = 1 ; i <= n ; ++ i){
cin >> (T + 1) ;
for (int j = 1 ; j <= m ; ++ j){
if (T[j] == 'L') ++ re1 ;
else if (T[j] == 'U') re1 += 2 ;
else if (T[j] == 'R') re1 += 3 ;
else if (T[j] == 'D') re1 += 4 ;
}
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= m ; ++ j)
if ( ((i + j) & 1) && (mat[Id[i][j]] == Id[i - 1][j] || mat[Id[i][j]] == Id[i + 1][j])) re2 += 2 ;
if (re1 % 4 == re2 % 4 || ans != n * m / 2) cout << ans << '\n' ; else cout << ans - 1 << '\n' ; return 0 ;
}

P.M.

A

真 · 找性质题。可能是因为 dls 也觉得纯找性质太无聊了就给了暴力 $50$ 。

感觉做这题的时候就是发现,自己归纳的能力不太行。对于一些现象很难给出一般化的结论。如果再来个什么分类讨论之类的就彻底歇菜了。

1、如果存在 $\geqslant 2$ 个人是自己的超集那就没救了。

2、如果存在恰好 $1$ 个人是自己的超集那么就一定有解。

以上两点因为比较水所以当时想到了,但是由于多测所以并没啥用。

然后考虑直接去枚举第一名 $i$。然后考虑如果设自己为 $k$,对于一个其他人 $j$ 满足

那么这些 $j$ 就一定可以被放到后面。这是个很强的性质,也比较好推。接着考虑那些 $s_k\cap s_i = s_k\cap s_{j’}$ 的 $j’$ 。发现如果存在某一道题 $o$ 是自己没做过且 $j’$ 都没做过的,那么就有一组合法解,否则无论怎样也找不到合法解。

于是就可以暴力判了。复杂度 $O\left(\dfrac{n^2\times m}{w}\right)$ 。

「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

int T ;
int cnt ;
int mxp ;
int val ;
int n, m ;
int t[N] ;
int buc[N] ;
int pos[N] ;
char In[N] ;
bitset <N> base ;
bitset <N> otr[N] ;

bool comp(int a, int b){ return buc[a] > buc[b] ; }

int main(){
cin >> T ;
while (T --){
cin >> n >> m >> (In + 1) ;
val = 0 ; -- n ; base.reset() ;
for (int i = 1 ; i <= m ; ++ i)
base[i] = (bool)(In[i] == 'Y') ;
for (int i = 1 ; i <= n ; ++ i){
cin >> (In + 1) ; otr[i].reset() ;
for (int j = 1 ; j <= m ; ++ j)
otr[i][j] = (bool)(In[j] == 'Y') ;
}
for (int i = 1 ; i <= n ; ++ i)
if ((base & otr[i]) == base) ++ val ;
if (val >= 2) goto NO ;
else if (val >= 1) goto YES ;
for (int i = 1 ; i <= n ; ++ i){
bitset <N> cap, res ;
res.reset(), cap = base & otr[i] ;
for (int j = 1 ; j <= n ; ++ j)
if (i != j && (otr[j] & cap) == cap) res = res | otr[j] ;
for (int j = 1 ; j <= m ; ++ j)
if (!base[j] && otr[i][j] && !res[j]) goto YES ;
}
NO : puts("NO") ; continue ;
YES : puts("YES") ; continue ;
}

return 0 ;
}

B

唉,自己 dp 真是菜的可怜。和找性质结合起来就挂了。

设 $f_{l,r,0/1}$ 表示已经走完了 $l\sim r$ 这个区间,当前在 $l/r(0/1)$ 时,走完 $[1,n]$ 最少还需要多少个砖块。那么考虑转移。首先一个观察,根据贪心我们是不会留箱子的,一定是恰好放到墙的高度 。那么考虑从 $l-1,r$ 转移到 $l,r$ ,发现有转移

其中 $rs(l,r)$ 是在走完 $(l,r)$ 可以剩下多少石块。意思是首先至少要 $f_{l-1,r,0}$ 这么多,其次也必须要可以跨过 $h_l$ 这堵墙。同时这种 $0/1$ 判断方位的还会有转移

但是不一定能走过去。这部分可以考虑枚举一个最初携带的石块个数 $t$ 然后模拟,这样转移就是 $O(n)$ 的。但是也可以通过观察发现是需要

的石块就可以了。原因是考虑每次默认把所站在的端点处的石块拿在身上,这样就相当于从 $0$ 开始要爬过 $\max h$ 至少需要的石块量。

同时可以发现,$l\to r$ 和 $r \to l$ 本质相似,因为墙还是那些墙,只是换了个方向经过而已。

于是最后复杂度 $O(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
int n ;
int s1[N] ;
int s2[N] ;
int blk[N] ;
int base[N] ;
int mx[N][N] ;
int f[N][N][2] ;

int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
s1[i] = s1[i - 1] + (base[i] = qr()) ;
for (int i = 1 ; i < n ; ++ i)
s2[i] = s2[i - 1] + (blk[i] = qr()) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i ; j <= n ; ++ j)
mx[i][j] = max(mx[i][j - 1], blk[j]) ;
memset(f, 127, sizeof(f)) ;
f[1][n][0] = f[1][n][1] = 0 ; int rst ;
for (int l = 1 ; l <= n ; ++ l)
for (int r = n ; r >= l ; -- r){
if (l == 1 && r == n) continue ;
rst = s1[r] - s1[l - 1] - s2[r - 1] + s2[l - 1] ;
if (l > 1) chkmin(f[l][r][0], max(f[l - 1][r][0], blk[l - 1] - rst)) ;
if (r < n) chkmin(f[l][r][1], max(f[l][r + 1][1], blk[r] - rst)) ;
chkmin(f[l][r][0], max(f[l][r][1], mx[l][r - 1] - rst)) ;
chkmin(f[l][r][1], max(f[l][r][0], mx[l][r - 1] - rst)) ;
}
for (int i = 1 ; i <= n ; ++ i)
printf("%d ", min(f[i][i][0], f[i][i][1])) ;
return 0 ;
}

C

给定一个 $n\times 3$ 的数表 $\{a\}$ 。初始时每个数都 $\leq m$ ,求至少修改多少个数可以使得

对所有 $i\in[1,n-1]$ 成立。其中修改之后的数也要 $\in[0,m]\cap\mathbb{Z}$ 。

$1\leq n\leq 10^5,0\leq m\le 10^{10}$ 。

这题是真神w

一开始的时候十分懵圈,因为没有任何一档部分分是可以带着值域进行 dp。

那么首先给出一个推断:

考虑每个位置的 $a_{i,j}$ 的和 $s_i$ ,修改完后的 $s_i$ 只会是第 $i$ 个位置修改 $0,1,2,3$ 次的值域区间的端点。

感觉有点可以猜出来。大概是说反正横竖都是改,还不如改的标准点。然后考虑这样放在一起离散化一下,本质不同的状态就有 $O(7\times n)$ 个了。于是可以设 $f_{i,j}$ 表示考虑了前 $i$ 个位置,当前第 $i$ 个位置的 $s_i=j$ 且合法时的最小代价的是多少。那么考虑就有转移

其中 $val(i,j)$ 是把第 $i$ 个位置的和调整成 $j$ 的最小代价。于是这样就可以喜提 $50pts$ 。

然后考虑满分。首先有两个 Observation:

1、 $f_{i,j}$ 一定是随着 $j\uparrow$ 而单调不降。既可以感性理解也可以打个表。

2、设 $[l_{i,k},r_{i,k}]$ 表示第 $i$ 个位置修改了 $k$ 次后的值域区间,不难发现有

也就是说最终整个 $f_{i,j}$ 在取后缀最小值后加上的数会是这样:

总共有 $7$ 段。其中后面 $4$ 段根据第一个观察可以知道可以直接暴力加(根据单调性转化成后缀加),因为这不影响单调性。而前面几段可能会影响。考虑怎么修改前面几段,发现修改的次数少、量也少。于是可以对于每个不同的一段,二分出第一个加上 $1$ 之后不会比这一段的末尾 $+1$ 的位置的 $dp$ 值大的,当前段中那个关键位置 $p$ 来,然后进行 $1\sim p$ 的区间加。最后复杂度 $O(n\log n)\sim O(n\log ^2 n)$。

然后大概是要进行一个类似线段树上二分的操作。这个地方跟 ymzqwq 学了一下用的树状数组。大概是考虑首先把 $m$ 补齐成 $2^k$ 的形式,这样二分就可以直接加 $mid$ ,之后根据 BIT 的特性把问题翻转一下变成要在前缀里二分出一个位置来。实测常数比较优。

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
int n ;
int len ;
ll s[N] ;
ll pd[M] ;
ll dp[M] ;
ll m, f[M] ;
ll base[3][N] ;

vll tmp ;
pll t[N][4] ;

int _bit[N] ;

void ins(int p, int v){
for ( ; p <= m ; p += (p & -p)) _bit[p] += v ;
}
int qry(int p){
int ret = 0 ;
for ( ; p ; p -= (p & -p)) ret += _bit[p] ;
return ret ;
}
void modify(int l, int r){
// cout << l << " " << r << '\n' ;
ins(l, 1), ins(r + 1, -1) ;
}
int main(){
cin.tie(0) ;
cout.tie(0) ;
cin >> n >> m ;
for (int i = 1 ; i <= n ; ++ i)
for (int o = 0 ; o < 3 ; ++ o)
base[o][i] = qr(), s[i] += base[o][i] ;
// debug(base[0], 1, n) ;
for (int i = 1 ; i <= n ; ++ i){
t[i][0].fr = t[i][0].sc = s[i] ;
t[i][1].fr = 3ll * m, t[i][1].sc = 0 ;
t[i][2].fr = 3ll * m, t[i][2].sc = 0 ;
for (int j = 0 ; j < 3 ; ++ j){
chkmin(t[i][1].fr, s[i] - base[j][i]) ;
chkmax(t[i][1].sc, s[i] - base[j][i] + m) ;
chkmin(t[i][2].fr, base[j][i]) ;
chkmax(t[i][2].sc, 2ll * m + base[j][i]) ;
}
t[i][3].fr = 0, t[i][3].sc = 3ll * m ;
for (int j = 0 ; j <= 3 ; ++ j)
tmp.p_b(t[i][j].fr), tmp.p_b(t[i][j].sc) ;
}
sort(tmp.begin(), tmp.end()) ;
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()) ;
len = int(tmp.size()) ; //debug(len) ;
for (int i = 1 ; i <= n ; ++ i){
for (int j = 0 ; j <= 3 ; ++ j){
t[i][j].fr = lower_bound(tmp.begin(), tmp.end(), t[i][j].fr) - tmp.begin() + 1 ;
t[i][j].sc = lower_bound(tmp.begin(), tmp.end(), t[i][j].sc) - tmp.begin() + 1 ;
// debug(t[i][j].fr, ' '), debug(t[i][j].sc, ' ') ;
}
// puts("") ;
}
// debug(tmp, 0, len - 1, '\n') ;
// ; debug(len) ;
m = 1 ; while (m <= len) m <<= 1 ;
// cout << m << '\n' ;
for (int i = n ; i >= 1 ; -- i){
// debug(i) ;
for (int j = 0 ; j < 3 ; ++ j)
if (t[i][j].fr >= 1) modify(1, t[i][j].fr - 1) ;
for (int j = 0 ; j < 3 ; ++ j){
int pos = qry(t[i][j].sc) ; //cout << pos << '\n' ;
int l = 1, r = m, mid, res = 0 ; ll now = 0 ;
while (l <= r){
mid = (l + r) >> 1 ;
if (now + _bit[mid] >= pos)
now += _bit[mid], res = mid, l = mid + 1 ;
else r = mid - 1 ;
}
// cout << res << '\n' ;
modify(res + 1, m) ;
}
}
/*
for (int i = 1 ; i <= n ; ++ i){
for (int j = 3 ; j >= 1 ; -- j)
for (int k = t[i][j].fr ; k < t[i][j - 1].fr ; ++ k)
dp[k] += j ;
for (int j = 1 ; j <= 3 ; ++ j)
for (int k = t[i][j - 1].sc + 1 ; k <= t[i][j].sc ; ++ k)
dp[k] += j ;
for (int j = len - 1 ; j >= 1 ; -- j)
chkmin(dp[j], dp[j + 1]) ;
}*/
// debug(dp, 1, len) ;
// for (int i = 1 ; i <= m ; ++ i) cout << qry(i) << " " ;
cout << qry(len) << '\n' ;
return 0 ;
}

c