【赛题整理】[ARC103] C~F

做之前不知道这套题怎么样。做到一半发现后面三道都是构造题…都是构造…构造沙我.jpg

这好像就是ARC正式赛的最后一场了。可惜我一场ARC都没现场打过。

难度大概是 $\rm B>C>D>A$ ?

A

给定一个偶数长度的序列 $\{a_n\}$,定义「合法」表示 $\forall i<n-1,a_{i}=a_{i+2}$ 且整个序列共有两种数字。

定义操作:每次选择一个数替换掉某个位置。

求最少需要操作多少次使得序列合法。

$1\leq n\leq 100000,1\leq a_i\leq 100000$。

比较常规的最优化题目。不难发现如果某个数出现次数很多,就要用这个去替换别的数而不是被换掉。所以不难想到分别拿桶记录奇偶位置的出现次数,然后两个都选最多的即可。

然而显然这个做法是不对的。因为限制了必须有两种数字,所以奇偶位置的取值必须不同。定一找二即可。

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
const int N = 200010 ;

int n ;
int res ;
int ans ;
int t[N] ;
int s[N] ;
int _odd[N] ;
int _eve[N] ;
int base[N] ;

bool compo(int x, int y){
return _odd[x] > _odd[y] ;
}
bool compe(int x, int y){
return _eve[x] > _eve[y] ;
}
int main(){
cin >> n ; res = n ;
for (int i = 1 ; i <= n ; ++ i){
cin >> base[i] ;
if (i & 1) _odd[base[i]] ++ ;
else _eve[base[i]] ++ ;
}
for (int i = 1 ; i < N ; ++ i) s[i] = t[i] = i ;
sort(s + 1, s + N, compo) ;
sort(t + 1, t + N, compe) ;
ans = n / 2 - _odd[s[1]] ;
for (int i = 1 ; i < N ; ++ i)
if (t[i] != s[1]){ ans += n / 2 - _eve[t[i]] ; break ; }
res = min(res, ans) ;
ans = n / 2 - _eve[t[1]] ;
for (int i = 1 ; i < N ; ++ i)
if (s[i] != t[1]){ ans += n / 2 - _odd[s[i]] ; break ; }
res = min(res, ans) ;
cout << res << endl ; return 0 ;
}

B

给定 $n$ 组坐标。构造长度为 $m$ 的序列 $\{c_n\}$ 和 $n$ 组包含 LRUD 的路径,满足对于每一组坐标:

  • $c_i$ 表示第 $i$ 步「步长」。
  • 对于每个坐标,从 $(0,0)$ 开始走,共走 $m$ 步。第 $i$ 步可以让 $(x,y)$ 变成 $(x±c_i,y)$ 或 $(x,y±c_i)$ 。
  • 走完 $m$ 次之后,恰好走到这组坐标。
  • 要求 $m\leq 40,c_i\leq 10^{12}$ 。

$1\leq n\leq 1000$

不会啊…感觉可能是对这种套路不是很熟啊。

首先无解很容易判断。因为多走一步和少走一步之间的差值总是 $2\times$步长 ,所以如果 $x_i+y_i$ 的奇偶性不同的话,就不能同时满足条件。

后来就不会了x

发现这个题的本质是拆分问题。那么大概可以引导到「二进制拆分」这种泛式的拆分方式上。不妨考虑对于一组 $\{1,2,4\cdots 2^k\}$ 可以拼出哪些坐标。那么考虑对于一组坐标 $(x,y)$ ,他可以被通达,那么可以知道如果想要减小某一维坐标,比如 $x\to x’$,那有两种情况:

1、只是单纯地拿掉几个元素。比如 $16\to11$ 就是简单地拆出 $4$ 和 $1$ 。

2、拿出几个元素并且换进去几个元素。比如 $12\to11$ 就是拆出 $2$ 和 $1$ 放进一个 $4$ 。

可以看出,这是可以相互通达的。

更详细一点。因为对于四个象限,情况都是等价的。所以只考虑第一象限。发现对于 $\{1,2,4\cdots 2^k\}$ ,它可以维护到的位置至少是所有 $|x+y|=\sum _{i=0}^k 2^i=2^{k+1}-1$。但是不仅限于此。发现如果将将其中某个元素的贡献取负,那么就可以访问到所有 $|x+y| - \sum 2^p$ 的格子。换句话说,这个方式可以访问到所有与 $2^{k+1}-1$ 奇偶性相同的格子。

到这一步就已经很完美了,但是依然存在问题。如果 $|x+y|$ 都是偶数,这就挂了。所以此时可以随便向 $x$ 轴或者 $y$ 轴偏移 $1$ ,比如把 $(1,0)$ 变换成原点,就解决了。

实现方面,发现最合法区域后是个内部镂空的菱形。找出来之后,对于一组坐标 $(x,y)$ ,考虑对称着找。反向从大到小枚举每一个步长,如果新的点的 $|x|+|y|$ 之和严格小于当前的步长,就是可以拼出来的。不难知道这样做是对的。

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
int n ;
int cnt ;
int _eve ;
ll nx, ny ;
int bc[N] ;
struct rg{
int l ;
int r ;
int t ;
}base[N] ; //D R U L
int dx[4] = {0, 1, 0, -1} ;
int dy[4] = {-1, 0, 1, 0} ;
char s[4] = {'U', 'L', 'D', 'R'} ;

int main(){
cin >> n ;
bc[0] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
cin >> base[i].l >> base[i].r ;
base[i].t = abs(base[i].l + base[i].r) & 1 ;
}
for (int i = 2 ; i <= n ; ++ i)
if (base[i].t != base[1].t) return puts("-1"), 0 ;
for (int i = 1 ; i <= 30 ; ++ i) bc[++ cnt] = 1 << i ;
cout << cnt + 1 + (bool)(!(base[1].t & 1)) << '\n' ;
if (!(base[1].t & 1)) cout << 1 << " " ;
for (int i = cnt ; ~i ; -- i) printf("%d%c", bc[i], " \n"[!i]) ;
for (int i = 1 ; i <= n ; ++ i){
nx = base[i].l ;
ny = base[i].r ;
if (!(base[i].t & 1))
ny -= 1, putchar('U') ;
//cout << nx << " " << ny << endl ;
for (int j = cnt ; ~j ; -- j){
for (int k = 0 ; k < 4 ; ++ k){
ll kx = nx + (ll)dx[k] * bc[j] ;
ll ky = ny + (ll)dy[k] * bc[j] ;
if (abs(kx) + abs(ky) < bc[j]){
nx = kx ; ny = ky ;
//cout << nx << " " << ny << endl ;
printf("%c", s[k]) ; break ;
}
}
}
puts("") ;
}
return 0 ;
}

C

给定一个长度为 $n$ 的 $01$ 序列 $\{s_n\}$。尝试构造一棵具有如下性质的 $n$ 个结点的树:

$\forall i\in[1,n]\cap\mathbb{Z_+}$,$s_i$ 若为 $1$ ,则一定存在大小为 $i$ 的连通块;$s_i$ 若为 $0$ ,则一定不存在大小为 $i$ 的连通块。

$1\leq n\leq10^5$ 。

神仙构造orz。

首先显然的是 $s_n=0$,$s_1=1$ ,否则无解。并且这东西是有对称性的,割掉一个大小为 $k$ 的连通块一定也会割出一个大小为 $n-k$ 的连通块。所以可以如此判断是否存在解。

这种构造,如果强行定义的话,可能存在某种套路。思考这一种比较自然的构造方式:找到最大的连通块,让其成为 $1$ 的一棵子树,这样迭代做下去,最后再拿散点连上去,看上去有点合理,因为 $1$ 的连通块必然存在。但仔细思考就会发现这样做会使得很多不应该存在的大小的连通块出现。

但是至少发现,连散点是个比较好的方式,而上一个方法欠缺的就是难以准确构造连通块。这就可以把思路引到「菊花」上。发现对于一个 $k$ 阶菊花,只会产生大小为 $k-1$ 和 $1$ 的连通块。那么可以知道大概可以如此设计思路:枚举连通块大小 $p$ ,如果 $s_p=0$ ,那么就应该把 $p+2$ 号点也连在之前的某个菊花上 ,这样就不会出现 $size=p$ 的连通块;否则把 $p+2$ 连向单独拿出来作为一个新的新的菊花的重心连向 $p+1$ ,这样就会有 $size=p$ 的连通块了。

形式化地讲,考虑设 $1<q_1<q_2<\cdots <q_m<n$ 表示 $\{s_n\}$ 中那些值为 $1$ 的位置。那么构造出来的只需要是一个链套菊花,每个菊花大小是 $q_k-q_{k-1}$ 即可(差分)。

显然这种构造方式能凑出所有 $s_p=1$ 的 $p$ 来。接下来只需要考虑这样做为什么也可以保证 $s_p=0$ 的位置不构造出来。发现如果砍掉的边是菊花边而不是链边,那么只会有 $n-1$ 和 $1$ 这两种连通块;如果是链边,那么只会是某个 $q_k$ 和 $n-q_k$ ,由于之前已经判过了对称性,所以不难证明这样做是对的。

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
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std ;

const int N = 200010 ;

int n ;
int m ;
int top ;
int cnt ;
char s[N] ;
int sz[N] ;
int stk[N] ;

int main(){
cin >> (s + 1) ;
n = strlen(s + 1) ;
if (s[1] == '0') return puts("-1"), 0 ;
if (s[n] == '1') return puts("-1"), 0 ;
for (int i = 1 ; i < n ; ++ i)
if (s[i] != s[n - i]) return puts("-1"), 0 ;
/*
for (int i = 1 ; i < n ; ++ i)
if (s[i] == '1') stk[++ top] = i ;
stk[++ top] = n ; int k ; cnt = 0 ;
while (top) sz[++ cnt] = stk[top --] ;
for (int i = 1 ; i < cnt ; ++ i)
printf("%d %d\n", i, i + 1), sz[i] -= sz[i + 1] ;
k = cnt ;
for (int i = 1 ; i <= cnt ; ++ i)
for (int j = 1 ; j <= sz[i] ; ++ j)
printf("%d %d\n", i, ++ cnt) ;
*/
m = 1 ;
for (int i = 1 ; i < n ; ++ i){
cout << i + 1 << " " << m << endl ;
if (s[i] == '1') m = i + 1 ;
}
return 0 ;
}

D

给定一棵树上每个点到其他点的距离和。保证均不相同。构造这样的一棵树。

$1\leq n\leq 200,000$

嗯。其实树上如果是考虑距离的话,也就那么点事儿。

首先要知道的是,一个经典的 $dp$ 。根据 $f_u$ 推出 $f_v$ ,此处假设 $fa_v=u$ 。那么有:

并且考虑一个很自然的思路。对于树而言,其最特殊的节点就是根和叶子。

发现 $f$ 值最小的那个是重心。那么如果令重心当根,那么随深度增大,$f$ 是单增的。同时可以知道,如果根是重心的话,一定不会存在某棵子树的 $size>\lfloor \frac{n}{2}\rfloor$ ,这就可以作为判断无解的依据。

于是就从底向上不断删叶子就可以了。合法随便判一判即可。

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
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>

#define to(k) E[k].to
#define next(k) E[k].next
#define fuck_it_up return !puts("-1")

using namespace std ;

typedef long long ll ;

const int N = 200010 ;

int n ;
ll minx ;
int cnt ;
int sz[N] ;
int fa[N] ;
ll dis[N] ;
int head[N] ;
struct tree{
int id ;
ll val ;
}base[N] ;
struct Edge{
int to ;
int next ;
}E[N * 2] ;
map <ll, int> s ;

bool comp(tree a, tree b){
return a.val > b.val ;
}
void add(int u, int v){
to(++ cnt) = v ;
next(cnt) = head[u] ;
head[u] = cnt ;
}
void dfs(int x){
for (int k = head[x] ; k ; k = next(k))
dis[to(k)] = dis[x] + n - 2 * sz[to(k)], dfs(to(k)) ;
}
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i) sz[i] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
scanf("%lld", &base[i].val) ;
s[base[i].val] = base[i].id = i ;
}
sort(base + 1, base + n + 1, comp) ;
for (int i = 1 ; i < n ; ++ i){
int x = base[i].id ;
ll y = base[i].val ;
int delta = n - 2 * sz[x] ;
if (delta <= 0) fuck_it_up ;
if (!s.count(y - delta)) fuck_it_up ;
fa[x] = s[y - delta] ; minx += sz[x] ;
sz[fa[x]] += sz[x] ; add(fa[x], x) ;
}
for (int i = 1 ; i <= n ; ++ i) cout << fa[i] << " " ;
dis[base[n].id] = minx ; dfs(base[n].id) ;
for (int i = 1 ; i <= n ; ++ i)
if (dis[base[i].id] != base[i].val) fuck_it_up ;
for (int i = 1 ; i < n ; ++ i)
cout << base[i].id << " " << fa[base[i].id] << '\n';
}