发表更新题解25 分钟读完 (大约3720个字)

Educational Codeforces Round 141（CF1783）

【题解】Educational Codeforces Round 141（CF1783）

评价：educational

A.Make it Beautiful

题目描述：

如果一个数组中存在一个数恰好等于该数前面所有数之和，那么这个数组就是丑的。如果一个数组不是丑的，就是美的。

比如说：

  • 数组 [6,3,9,6][6, 3, 9, 6] 是丑的，因为 9=6+39 = 6 + 3 ；
  • 数组 [5,5,7][5, 5, 7] 是丑的，因为第二个 5=55 = 5 。
  • 数组 [8,4,10,14][8, 4, 10, 14] 是美的，因为 8≠08 \ne 0 , 4≠84 \ne 8 , 10≠8+410 \ne 8 + 4 , 14≠8+4+1014 \ne 8 + 4 + 10 ，没有任何一个数等于它前面的数之和。

给定数组 aa 满足 1≤a1≤a2≤⋯≤an≤1001 \le a_1 \le a_2 \le \dots \le a_n \le 100 。 你可以任意调整元素的顺序，也可以不调整，使它变成一个美的数组。

题目分析：

我们可以考虑从大到小排序，这样除了最大值可能出问题，其它的都没问题。
而最大值就可以只保留一个在序列开头，其余的放到结尾即可。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		vector<int> v;
		for(int i=n; i>=1; i--){
			if(a[i] == a[n] && i != n)	continue;
			v.push_back(a[i]);
		}
		for(int i=n; i>=1; i--){
			if(a[i] == a[n] && i != n)	v.push_back(a[i]);
		}
		bool flag = true;
		int sum = 0;
		for(int i=0; i<(int)v.size(); i++){
			if(v[i] == sum)	flag = false;
			sum += v[i];
		}
		if(flag){
			printf("YES\n");
			for(int i=0; i<(int)v.size(); i++)	printf("%d ",v[i]);
			printf("\n");
		}
		else	printf("NO\n");
	}
	return 0;
}

B.Matrix of Differences

题目描述：

对于一个 n×nn\times n 的矩阵，对于每一对相邻（有公共边）的值 a,ba,b，写下 ∣a−b∣|a-b|（即 aa 与 bb 差的绝对值）。定义这个矩阵的美丽度为写下的不同的值的个数。以如下的矩阵为例：

(1342)\left(\begin{matrix}1&3\\4&2\end{matrix}\right)

则所有相邻值的绝对值分别是 ∣1−3∣=2,∣1−4∣=3,∣3−2∣=1,∣4−2∣=2|1-3|=2,|1-4|=3,|3-2|=1,|4-2|=2。共有 1,2,31,2,3 三种不同的值，则这个矩阵的美丽度为 33。

给你 tt 次询问，每次询问给定一个正整数 nn。输出任意一个 n×nn\times n 的矩阵，满足 1∼n21\sim n^2 在矩阵中各出现一遍，并且该矩阵的美丽度最大。

1≤t≤49,2≤n≤501\le t\le49,2\le n\le50。

题目分析：

手摸了半天才搞出来的做法。
考虑 n−1n-1 会怎么得到，只有可能是 1,n1,n，那 n−2n-2 呢？
可以是 1,n−11,n-1 或者 2,n2,n，为了构造的漂亮程度我们就不妨将 n,n−1n,n-1 放到 11 的旁边，然后 22 继续放到下面，也就是下面这种方式：

1n−14n−5⋯n3n−4⋯2n−3⋯n−2⋯⋯\begin{matrix} 1 &n-1 &4 &n-5 &\cdots\\ n &3 &n-4 &\cdots\\ 2 &n-3 &\cdots\\ n-2 &\cdots\\ \cdots \end{matrix}

然后就可以过了。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N][N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		int l = 1,r = n*n,tot = 0;
		for(int i=1; i<=n; i++){
			++tot;
			int nx = i,ny = 1;
			while(nx >= 1 && ny <= n){
				if(tot & 1)	a[nx][ny] = l,l++;
				else a[nx][ny] = r,--r;
				nx --,ny ++;
			}
		}
		for(int i=2; i<=n; i++){
			++tot;
			int nx = n,ny = i;
			while(nx >= 1 && ny <= n){
				if(tot & 1)	a[nx][ny] = l,l++;
				else a[nx][ny] = r,--r;
				nx --,ny ++;
			}
		}
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

C.Yet Another Tournament

题目描述：

有 nn 个选手，编号为 11 至 nn ，每两个选手对战时，编号大的将会胜利。

你可以准备 mm 单位时间，每准备 aia_i 时间就可以赢 ii 号选手。

按胜利的总次数排名，求你最高多少名。

题目分析：

一个想法就是我们直接将 aa 最小到大排序，这样就可以赢尽可能多的场，看上去就是很好的排名。
但是我们的排名还与我们赢了哪些人有关，所以就有点不可做的样子。
注意到，当我们赢了 xx 场就相当于要选择 n−xn-x 个人多赢一场，然后寻找赢场数大于 xx 的人的个数，而只有赢场数等于 xx 的人会受到我们选择加一的影响，所以其实此时只需要判断能不能通过调整使得我们可以赢过胜场为 xx 的人即可。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int a[N],b[N];
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%lld",&T);
	while(T--){
		int n,m;scanf("%lld%lld",&n,&m);
		for(int i=1; i<=n; i++)	scanf("%lld",&a[i]),b[i] = a[i];
		sort(b+1,b+n+1);
		int pos = 0;
		for(int i=1; i<=n; i++){
			if(m - b[i] >= 0){
				pos = i;
				m -= b[i];
			}
		}
		if(!pos){
			printf("%lld\n",n+1);
			continue;
		}
		if(pos != n && a[pos+1] <= m + b[pos])	++pos;
		printf("%lld\n",n-pos + 1);
	}
	return 0;
}

D.Different Arrays

题目描述：

给你一个有 nn 个元素的序列，你需要进行 n−2n-2 次操作。

对于第 ii 次操作，你可以选择让 ai−ai+1a_i-a_{i+1} 且 ai+2+ai+1a_{i+2}+a_{i+1} 或者可以选择让 ai+ai+1a_i+a_{i+1} 且 ai+2−ai+1a_{i+2}-a_{i+1}

问最后能产生多少个不同的序列。

题目分析：

一个想法就是判断什么样的序列是能被表示的，但是想了一会发现根本没有任何头绪，所以考虑换个想法，也就是直接使用 dpdp 去决策每一次的操作。
为了方便理解，我们将第 ii 次操作，成为操作第 i+1i+1 个数。
但是这样看上去有很多重复的情况就很难办，注意一点就是要使得产生相同的序列则必然满足存在 ai=0a_i = 0 的情况，然后操作 aia_i，否则一定不会产生相同的情况，所以我们完全不用考虑什么去重之类的问题，只需要判断 ai=0a_i = 0 即可。
所以可以考虑设 dpi,jdp_{i,j} 表示操作完了前 ii 个数，ai+1=ja_{i+1} = j 的方案数，记第二维的原因是我们此时需要决策第 i+1i+1 次操作就必须知道对应的 aa 是什么。
转移就是显然的，也就是直接枚举 ai+1a_{i+1} 是怎么操作的，以及特判 ai+1=0a_{i+1} = 0。
注意到第二维可以为负，所以加一个偏移量。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int MAX = 90000;
int dp[305][90005 * 2];
int a[305];
void add(int &a,int b){
	a = (a + b)%MOD;
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
	dp[1][MAX+a[2]] = 1;
	for(int i=1; i<n; i++){
		for(int k=-MAX; k<=MAX; k++){
			if(!dp[i][k+MAX])	continue;
			if(k == 0){
				dp[i+1][a[i+2]+MAX] = (dp[i+1][a[i+2]+MAX] + dp[i][k+MAX])%MOD;
			}
			else{
				dp[i+1][a[i+2]+k+MAX] = (dp[i+1][a[i+2]+k+MAX] + dp[i][k+MAX])%MOD;
				dp[i+1][a[i+2]-k+MAX] = (dp[i+1][a[i+2]-k+MAX] + dp[i][k+MAX])%MOD;
			}
		}
	}
	int ans = 0;
	for(int j=-MAX; j<=MAX; j++)	add(ans,dp[n-1][j+MAX]);
	printf("%d\n",ans);
	return 0;
}

E.Game of the Year

题目描述：

Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：nn 个编号从 11 到 nn 的BOSS。

他俩将用以下方式与BOSS战斗

  • Monocarp 进行 kk 次尝试撒掉boss;
  • Polycarp 进行 kk 次尝试撒掉boss;
  • Monocarp 进行 kk 次尝试撒掉boss;
  • Polycarp 进行 kk 次尝试撒掉boss;
  • …

Monocarp 在第 aia_i 次尝试中撒掉了第 ii 只BOSS。Polycarp 在第 bib_i 次尝试中撒掉了第 ii 只BOSS。其中一个人撒掉第 ii 只BOSS后，他们就会尝试撒第 (i+1)(i+1) 只BOSS。并且他们的尝试计数器都会清空。撒掉第 nn 只BOSS后，游戏结束。

找到从11 到 nn所有的 kk 值， 使得 Monocarp 可以杀死所有的BOSS。

1≤n≤2×1051 \le n \le 2\times 10^5

题目分析：

题目说的实在是太抽象了，转化一下题意就是要找到满足以下条件的 kk：

∀i∈[1,n]⌈aik⌉≤⌈bik⌉\begin{aligned} &\forall i\in[1,n] & \lceil \frac{a_i}{k} \rceil \le \lceil \frac{b_i}{k} \rceil \end{aligned}

首先就是可以直接整除分块就能找到所有满足条件的 kk，复杂度 O(nn)O(n\sqrt{n}) 但是常数有点逆天据说不能过，考虑优化。
一个经典的想法就是既然不能枚举约数，那么我们就枚举倍数，即枚举 kk 然后枚举 kk 的倍数。
可以发现 kk 的倍数将序列分成了 O(nk)O(\frac{n}{k}) 段，而要使得上述条件满足就是 aia_i 所在的块不在 bib_i 所在的块后面。
如果原来就满足 ai≤bia_i \le b_i 则无论如何都满足条件，就不管了。
如果 ai>bia_i > b_i 条件其实就是 aia_i 所在的块与 bib_i 所在的块相同，这个不是很好判，那么什么时候是不在一块呢？
既然不在一块也就是说 [bi,ai][b_i,a_i] 跨过了一个分界点，如果我们以 kk 的倍数作为每一段的右端点，也就是 [bi,ai)[b_i,a_i) 包含 kk 的倍数。
可以直接预处理出每一个位置是否可以作为右端点，然后对于每一个 kk 的倍数判断一下即可。
复杂度 O(nlog⁡n)O(n \log n)

代码：

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int a[N],b[N],sum[N];
vector<int> v;
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
		for(int i=1; i<=n; i++)	scanf("%d",&b[i]);
		for(int i=1; i<=n; i++){
			if(a[i] > b[i])	sum[b[i]]++,sum[a[i]]--;
		}
		for(int i=1; i<=n; i++)	sum[i] += sum[i-1];
		for(int i=1; i<=n; i++){
			bool flag = true;
			for(int j=i; j<=n; j+=i){
				if(sum[j])	flag = false;
			}
			if(flag)	v.push_back(i);
		}
		printf("%d\n",v.size());
		for(int i=0; i<v.size(); i++)	printf("%d ",v[i]);
		printf("\n");
		for(int i=0; i<=n; i++)	sum[i] = 0;
		v.clear();
	}
	return 0;
}

F.Double Sort II

题目描述：

有两个 1..n1..n 的排列 a,ba,b。

你可以进行若干次操作，每次操作流程如下：

  • 选择一个整数 i∈[1,n]i \in [1,n]。

  • 找出两个整数 x,yx,y，使得 ax=by=ia_x=b_y=i。

  • 交换 axa_x 和 aia_i，以及 byb_y 和 bib_i。

问把 aa 和 bb 从小到大排序的最小操作次数

题目分析：

考虑将排列看作一个置换，然后建图，也就是连边 i→aii \to a_i 与 i→bii \to b_i，注意这是两张图。
我们的一次操作相当于将某个点缩成一个自环，其他点不受影响，所以对于每一个置换环设其长度为 lenlen 只需要操作 len−1len-1 次就可以将所有点缩成自环，即我们可以对于每一个环钦定一个点使得这个点不被操作，要最大化钦定点的数量。
而两张图其实也是差不多的，如果钦定 ii 不被操作，也就是说 ii 在 a,ba,b 中的环上均只能选择 ii 这一个点不被操作，这个其实就是一个匹配的感觉。
所以可以对于每一个点 ii，找到其在 a,ba,b 上的环，将这两个环连边，最后跑一个最大匹配就是最多的不用被操作的点数。

代码：

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct edge{
	int nxt,to,id;
	edge(){}
	edge(int _nxt,int _to,int _id){
		nxt = _nxt,to = _to,id = _id;
	}
}e[2 * N];
int cnt,col1[N],col2[N],head[N],flag[N],match[N],a[N],b[N];
bool vis[N],tag[N];
void add_edge(int from,int to,int id){
	e[++cnt] = edge(head[from],to,id);
	head[from] = cnt;
}
bool dfs(int now){
	if(vis[now])	return false;
	vis[now] = true;
	for(int i=head[now] ;i ; i=e[i].nxt){
		int to = e[i].to;
		if(!match[to] || dfs(match[to])){
			match[now] = to,match[to] = now;
			flag[now] = flag[to] = e[i].id;
			return true;
		}
	}
	return false;
}
void dfs1(int now,int col){
	if(col1[now])	return;
	col1[now] = col;
	if(!col1[a[now]])	dfs1(a[now],col);
}
void dfs2(int now,int col){
	if(col2[now])	return;
	col2[now] = col;
	if(!col2[b[now]])	dfs2(b[now],col);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%d",&n);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]);
	for(int i=1; i<=n; i++)	scanf("%d",&b[i]);
	int tot = 0;
	for(int i=1; i<=n; i++){
		if(col1[i])	continue;
		++tot;dfs1(i,tot);
	}
	int tmp = tot;
	memset(vis,false,sizeof(vis));
	for(int i=1; i<=n; i++){
		if(col2[i])	continue;
		++tot;dfs2(i,tot);
	}
	for(int i=1; i<=n; i++){
		add_edge(col1[i],col2[i],i);
		add_edge(col2[i],col1[i],i);
//		printf("%d %d\n",col1[i],col2[i]);
	}
	int ans = 0;
	for(int i=1; i<=tmp; i++){
		memset(vis,false,sizeof(vis));
		ans += dfs(i);
	}
	printf("%d\n",n - ans);
	for(int i=1; i<=tmp; i++){
		tag[flag[i]] = true;
	}
	for(int i=1; i<=n; i++){
		if(!tag[i])	printf("%d ",i);
	}
	return 0;
}

G.Weighed Tree Radius

题目描述：

给你一个nn个点的树和n−1n-1条边。第ii个点的初始权值为aia_i。

定义结点vv到结点uu的距离dv(u)d_v(u)等于vv和uu之间的边的数量。注意:dv(u)=du(v),dv(v)=0d_v(u)=d_u(v),d_v(v)=0

定义结点vv到结点uu的权值距离wv(u)=dv(u)+auw_v(u)=d_v(u)+a_u。注意：wv(v)=av,wv(u)≠wu(v)w_v(v)=a_v,w_v(u) \neq w_u(v)如果au≠ava_u \neq a_v

与通常的距离类似，让我们定义结点vv的偏心距e(v)e(v)是从vv到其他结点的最大权值距离（包括vv本身），即e(v)=max⁡1≤u≤nwv(u)e(v)=\max\limits_{1\leq u \leq n} w_v(u)。

最后，我们定义树的半径rr是所有偏心距的最小值，即r=min⁡1≤v≤ne(v)r=\min\limits_{1\leq v\leq n} e(v)

你需要对mm次询问进行回答，对于第jj次询问，给出两个数vjv_j和xjx_j，表示将avja_{v_j}的值修改为xjx_j。

在每次询问后，输出当前该树的半径rr。

2≤n≤2×105，1≤m≤1052 \le n \le 2 \times 10^5，1\le m \le 10^5

题目分析：

题目已经提示了这东西叫做半径，那么是不是直接求直径然后除以 22 就可以呢？
我们定义 w′(u,v)=au+av+dis(u,v)w'(u,v) = a_u + a_v + dis(u,v)，那么满足 w′(u,v)w'(u,v) 最大的两个点 u,vu,v 之间的路径的长度我们称为直径。
这里我们将 aua_u 理解为挂在 uu 上长度为 aua_u 的链，ava_v 理解为挂在 vv 上长度为 ava_v 的链。
设直径的中点为 midmid，若 midmid 在直径的某一个节点上，则显然 r=⌈w′(u,v)2⌉r = \lceil \frac{w'(u,v)}{2} \rceil，可是如果 midmid 不在直径的某一个节点上呢。
若 midmid 在 aua_u 对应的链上，则必然满足 eu=aue_u = a_u，则对于其它的任意一个点 xx 都必然满足 ex≥dis(u,x)+au>au=eue_x \ge dis(u,x) + a_u > a_u = e_u，即 r=aur = a_u，但是这样的话就必然满足直径为 w′(u,u)w'(u,u) 就不可能不存在了。

下面我们的问题就转化为了维护直径。
考虑假设我们原来的直径为 (u,v)(u,v) 现在将 axa_x 增大了一些，那么我们新直径的端点必然是 u,v,xu,v,x 其中的两个，可以直接分类讨论得到答案。
而如果我们将 axa_x 减小了一些，我们就无法判断直径端点的变化，所以可以考虑使用线段树分治维护修改，这样每次将值从 00 开始变化，这样每次都是加的操作了。

Educational Codeforces Round 141（CF1783）

http://linyihdfj.github.io/2023/09/13/Educational-Codeforces-Round-141-CF1783/

作者

linyihdfj

发布于

2023-09-13

更新于

2023-09-14

许可协议

×