【训练记录】6.5 训练笔记

啦啦啦啦

A.M.

A

简单题。

大概是说如果连上了两条边,那么这条边连接的两个点就可以直接合并起来。考虑为了保证复杂度,需要进行启发式合并。于是就可以拿一个 set 维护,但这样会多一个 log。考虑直接拿 vector 维护,对每个点设一个 vis 就不需要删除了。

「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
int fa[N] ;
int n, m, q ;
bool vis[N] ;
vector <int> s[N] ;

int find(int x){
if (fa[x] == x) return x ;
return fa[x] = find(fa[x]) ;
}
/*
void merge(int x, int y){
int f1 = find(x) ;
int f2 = find(y) ;
if (f1 != f2)
fa[f1] = f2 ;
}*/

int main(){
cin >> n >> m >> q ; int x, y ;
for (int i = 1 ; i <= n ; ++ i) fa[i] = i ;
for (int i = 1 ; i <= m ; ++ i)
x = qr(), y = qr(), s[x].p_b(y), s[y].p_b(x) ;
for (int i = 1 ; i <= q ; ++ i){
x = find(qr()) ;
y = find(qr()) ;
if (x == y){
putchar('1') ;
continue ;
}
for (auto z : s[x])
if (z == y) goto fuck ;
putchar('1') ;
if (s[x].size() > s[y].size())
swap(x, y) ; fa[x] = y ; vis[x] = 1 ;
for (auto z : s[x])
if (!vis[z]) s[z].p_b(y), s[y].p_b(z) ;
continue ;
fuck : putchar('0') ;
}
return 0 ;
}

B

简单题。

考虑一个性质,大概就是说剩下没有连起来的弦,不相交一定是最优的。于是就可以直接 dp 了。设 $f_{i,j}$ 表示考虑 $[i,j]$ 之间还没连的点,最小代价是多少。转移就考虑枚举一个 $[i,j]$ 之间和 $i$ 相连的点即可。注意到这样就需要 $[i,j]$ 里没有配对的点为偶数。

然后考虑方案数 $g_{i,j}$,就只需要在维护 $f_{i,j}$ 时顺便计数一下就好了。复杂度 $O(n^3)$ 。

C

比较神奇的题目…

给定一个插入序列。编号为 $i$ 的元素有一个颜色 $col_i$ 和一个阈值 $a_i$。插入 $i$ 的时候,$i$ 应当放到满足以下条件的最靠前的位置 $p$:

1、当前位于 $p$ 或者 $p+1$ 的元素颜色与 $col_i$ 相同。

2、不能有超过 $a_i$ 个元素因此而后移。

求最终插入全部元素后每个位置的元素编号。$1\leq n\leq 3\times 10^5$ 。

那必然是先莽一个 $50pts$ 的 vector 暴力然后就 250 滚粗了

大概是考虑如果知道了每个元素在当时插入完毕后在第几位,即 $rank_i$ ,就可以直接线段树二分出最后实际的 rank。具体的,考虑把数从后往前插入线段树,这样每次就需要从线段树中二分出第一个位置 $p$ 使得 $p-sum_p=rank_i$ ,其中 $sum_p$ 是前缀和。不难知道这样做是对的。

之后考虑怎么求出 $rank_i$ 。这个地方有个十分深刻的性质,大概是说考虑如果有多个相邻颜色的元素放在相邻的位置,那么我们并不关心靠后的那些元素,可以直接合并,因为边界比较好处理,并且这样转化之后就只会出现在后面插入新的元素,可以直接 push_back。那么现在如果要插入一个元素,那么可以先找到这个元素不考虑颜色时最少应该放在的位置 $p$,然后去对应颜色的 vector 里二分即可。这样每次插入就可以换成在线段树上进行单点加。注意可能存在一个颜色的连续段跨过 $p$ 的情况,判一下边界就好了。

「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
void chkmax(int &x, int y){ x = y > x ? y : x ; }

int n, m ;
int ans[N] ;
vint col[N] ;
int org_rk[N] ;
int seg[N * 3] ;

#define _ed end
#define _bg begin
#define p_b push_back

#define lc (rt << 1)
#define rc (rt << 1 | 1)

void upd(int rt, int l, int r, int p, int v){
if (l == r)
return void(seg[rt] += v) ;
int mid = (l + r) >> 1 ;
if (p <= mid) upd(lc, l, mid, p, v) ;
else upd(rc, mid + 1, r, p, v) ;
seg[rt] = seg[lc] + seg[rc] ;
}
int fd(int rt, int l, int r, int p){
if (l == r) return l ;
int mid = (l + r) >> 1 ;
if (seg[lc] >= p) return fd(lc, l, mid, p) ;
else return fd(rc, mid + 1, r, p - seg[lc]) ;
}
int qry(int rt, int l, int r, int p){
int mid = (l + r) >> 1 ;
if (l == r) return seg[rt] ;
if (p <= mid) return qry(lc, l, mid, p) ;
else return seg[lc] + qry(rc, mid + 1, r, p) ;
}
int main(){
qr(n) ;
int x, y, z, o, p, q ;
for (int i = 1 ; i <= n ; ++ i){
qr(x), qr(y) ;
z = fd(1, 0, n, i - y - 1) ;
o = lower_bound(col[x]._bg(), col[x]._ed(), z) - col[x]._bg() ;
if (o == col[x].size()) col[x].p_b(++ m) ; o = col[x][o] ;
org_rk[i] = qry(1, 0, n, o - 1) + 1 ;
chkmax(org_rk[i], i - y) ;
upd(1, 0, n, o, 1) ;
}
for (int i = 1 ; i <= n * 3 ; ++ i) seg[i] = 0 ;
for (int i = 1 ; i <= n ; ++ i) upd(1, 1, n, i, 1) ;
for (int i = n ; i >= 1 ; -- i){
p = fd(1, 1, n, org_rk[i]) ;
ans[p] = i ; upd(1, 1, n, p, -1) ;
}
qwa(ans + 1, n, ' ', '\n') ; return 0 ;
}

233

P.M.

下午的题比较水…

A

简单题。

一开始的想法就是把棋盘转个 $45°$ 可能会比较好做。后来发现完全可以直接记一下对角线的编号。之后就考虑先算副对角线,然后算主对角线。这样的话,算主对角线时就需要对与所有副对角线的交点的贡献进行容斥,但是发现和一条主对角线的副对角线编号是连续的,就比较好算。

细节在于,要考虑编号奇偶性,因为经过 $(1,2),(2,1)$ 的对角线和经过 $(1,1),(2,2)$ 的对角线虽然相交,但是交点不是整点。然后对奇偶编号分别拿个桶维护就好了。复杂度 $O(n+m)$ 。

「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
int abs(int x){ return x > 0 ? x : -x ; }

int main(){
qr(n), qr(m) ; int z = 3 * n ;
for (int i = 1 ; i <= m ; ++ i){
qr(base[i].fr), qr(base[i].sc) ;
vis0[base[i].fr + base[i].sc - 1] = 1 ;
vis1[n - base[i].sc + base[i].fr] = 1 ;
}
for (int i = 1 ; i <= n + n - 1 ; ++ i){
ans += vis0[i] * (n - abs(n - i)) ;
buc1[i] = buc1[i - 1] + (i & 1) * vis0[i] ;
buc0[i] = buc0[i - 1] + (!(i & 1)) * vis0[i] ;
}
if (n & 1){
for (int i = 1 ; i <= n ; ++ i){
if (!vis1[i])
continue ;
ans += n - abs(n - i) ;
if (i & 1)
ans -= buc1[i + n - 1] - buc1[n - i] ;
else ans -= buc0[i + n - 1] - buc0[n - i] ;
}
for (int i = n + 1 ; i <= n + n - 1 ; ++ i){
if (!vis1[i])
continue ;
ans += n - abs(n - i) ;
if (i & 1)
ans -= buc1[z - i - 1] - buc1[i - n] ;
else ans -= buc0[z - i - 1] - buc0[i - n] ;
}
}
else {
for (int i = 1 ; i <= n ; ++ i){
if (!vis1[i])
continue ;
ans += n - abs(n - i) ;
if (!(i & 1))
ans -= buc1[i + n - 1] - buc1[n - i] ;
else ans -= buc0[i + n - 1] - buc0[n - i] ;
}
for (int i = n + 1 ; i <= n + n - 1 ; ++ i){
if (!vis1[i])
continue ;
ans += n - abs(n - i) ;
if (!(i & 1))
ans -= buc1[z - i - 1] - buc1[i - n] ;
else ans -= buc0[z - i - 1] - buc0[i - n] ;
}
}
qw(ans, '\n') ; return 0 ;
}

B

比较简单的分类讨论题。

一开始读错题了,以为每个点的编号都必须是 $1\sim n$ …后来发现只要 $\lt 10^6$ 就好了。然后如果是 $\lt n$ 也不是没有办法,只是只能做小一点,大概就是考虑显然只需要管那些 $\deg_x$ 是奇数的 $x$ ,然后相当于从这些里面选择恰好 $k$ 个可以改变编号的元素使之异或和等于一个定值 $c$ 。这显然是可以 $n^3$ dp 的。

然后考虑正常版本,$\lt 10^6$ 的。考虑这样的话权值一定程度上就可以 xjb 找。具体的,把可以修改权值并且度数不为偶数的节点称作 pks 点,那么分类讨论一下 pks 点的数量(0/1/2/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

int cnt ;
int res ;
int n, m ;
int col[N] ;
int ans[N] ;
int deg[N] ;
int able[N] ;

bool out_put(){
puts("Yes") ;
for (int i = 1 ; i <= n ; ++ i)
qw(ans[i], ' ') ; putchar('\n') ;
return 0 ;
}
int main(){
int x, y, z ;
qr(n) ; res = n ;
for (int i = 1 ; i <= n ; ++ i)
qr(col[i]), ans[i] = i ;
for (int i = 1 ; i < n ; ++ i){
qr(x), qr(y), res ^= x ^ y ;
deg[x] ^= 1, deg[y] ^= 1 ;
}
if (!res) return out_put() ;
for (int i = 1 ; i <= n ; ++ i)
if (col[i] && deg[i]) able[++ cnt] = i ;
if (!cnt) return puts("No"), 0 ;
else if (cnt <= 1){
x = able[1] ;
y = res ^ x ; ans[x] = y ;
if (y <= n){
if (!col[y])
return puts("No"), 0 ;
ans[y] = MAXV ;
}
return out_put() ;
}
else {
z = 0 ;
x = able[++ z] ;
y = able[++ z] ;
if (res == (x ^ y)){
if (z == cnt)
return puts("No"), 0 ;
else y = able[++ z] ;
}
z = x ^ y ^ res ;
ans[x] = MAXV ; ans[y] = MAXV ^ z ;
return out_put() ;
}
}

C

给定一个序列,支持如下两个操作:

1、单点修改。

2、给出一个 $x_i$ 。全局查询有多少个极长的连续段,满足连续段内的数都 $\geqslant x_i$

$5\times 10^5$ 。

感觉是比较经典的思路。考虑连续段可以看做连通块,更进一步是一棵树,那么就会有 $s$ 个点和 $s-1$ 条边。于是考虑所有连通块里点的数量之和减去边的数量之和就是连通块个数,接下来就可以分别维护「有多少个 $a_i\geqslant x$ 」和有多少个「 $\min\{a_i,a_{i-1}\}\geqslant 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
58
59
60
61
62

#define lwb lower_bound

struct BIT{
int _b[N], v_max ;
#define low(x) (x & -x)
void ins(int p, int v){
for ( ; p <= v_max ; p += low(p)) _b[p] += v ;
}
int qry(int p){
int ret = 0 ;
for ( ; p ; p -= low(p)) ret += _b[p] ;
return ret ;
}
}_b1, _b2 ;

int cnt ;
int n, q ;
int v[N] ;
int qm[N] ;
int qp[N] ;
int qv[N] ;
int base[N] ;


int main(){
cin >> n >> q ; int p ;
for (int i = 1 ; i <= n ; ++ i)
v[++ cnt] = base[i] = qr() ;
for (int i = 1 ; i <= q ; ++ i){
qm[i] = qr() ;
if (qm[i] == 1) v[++ cnt] = qv[i] = qr() ;
else qp[i] = qr(), v[++ cnt] = qv[i] = qr() ;
}
sort(v + 1, v + cnt + 1) ;
cnt = unique(v + 1, v + cnt + 1) - (v + 1) ;
_b1.v_max = _b2.v_max = cnt ;
for (int i = 1 ; i <= n ; ++ i){
base[i] = lwb(v + 1, v + cnt + 1, base[i]) - v ;
_b1.ins(base[i], 1) ; if (i > 1) _b2.ins(min(base[i], base[i - 1]), 1) ;
}
// debug(base, 1, n) ;
// debug(_b1.qry(_b1.v_max)) ;
// debug(_b2.qry(_b1.v_max)) ;
for (int i = 1 ; i <= q ; ++ i){
qv[i] = lwb(v + 1, v + cnt + 1, qv[i]) - v ;
// debug(qv[i]) ;
if (qm[i] == 1)
printf("%d\n", (n - _b1.qry(qv[i] - 1)) - (n - 1 - _b2.qry(qv[i] - 1))) ;
else {
p = qp[i] ;
_b1.ins(qv[i], 1) ;
_b1.ins(base[p], -1) ;
if (p < n) _b2.ins(min(qv[i], base[p + 1]), 1) ;
if (p > 1) _b2.ins(min(qv[i], base[p - 1]), 1) ;
if (p < n) _b2.ins(min(base[p], base[p + 1]), -1) ;
if (p > 1) _b2.ins(min(base[p], base[p - 1]), -1) ;
base[p] = qv[i] ;
}
}
return 0 ;
}

下午完完全全就是在划水啊!?