Codeforces Round 699 题解

[比赛链接]

https://codeforces.com/contest/1481

[题解]

(A)

两维的坐标是独立的 ， 记录向上 ， 下 ， 左 ， 右共走的步数判断即可。

时间复杂度 : (O(N))

(B)

注意到 (max{a_{i}} leq 100) , 因此最多只会操作 (10000) 次。

不妨直接模拟这个过程 ， 其必然会在 (10000) 次后停止。

时间复杂度 : (O(N ^ 3))

(C)

首先考虑第 (M) 次涂色的位置不会被更改 (因为是最后一次涂色)。不妨首先固定一个 (B_{i} = C_{M}) 的 (i) (优先考虑 (A_{i} eq B_{i}))。

然后从前向后枚举每一次涂色 ， 每次仍然贪心地优先考虑 (B_{i} = C_{current} , A_{i} eq B_{i}) 的 (i) ， 如果找不到则对 (M) 次涂色的位置操作一次即可。

时间复杂度 : (O(N + M))

(D)

首先 ， 如果存在点对 ((u , v)) ， 使得 (val_{u , v} = val_{v , u})。构造一条 (u -> v -> u -> v ...) 的路径即可。

特判这种情况 ， 剩下的问题必然满足 (val_{u , v} eq val_{v , u})。

若 (M) 是奇数 ， 可构造一条在两点间来回移动的路径。

否则 ， 考虑三点 (u , v , w) 使得 (val_{u , v} = val_{v , w})。

若 (frac{M}{2}) 为奇数 ， 以环上的数字的顺序不断重复即可 (如下图)。

(frac{M}{2}) 为偶数的情况类似。

时间复杂度 : (O(N ^ 2))

(E)

首先对于每种颜色 (c) 找到其最左出现的位置 (l_{c}) , 最右 (r_{c}) ， 以及出现的次数 (f_{c})。

一个转化是问题等价于求最多保留的数的个数。

考虑倒着动态规划 ， 记 (dp_{i}) 表示后缀 ([i , n]) 最多保留的数的个数。

首先 (dp_{i}) 可以继承 (dp_{i + 1}) 的信息 (表示操作当前的左端点)

若 (i = l_{c}) ， 显然可以保留颜色 (c) , 此时 (dp_{i} = dp_{r_{c_{i}} + 1} + f_{c})

若 (i eq l_{c}) , 有 (dp_{i} = cf_{c}) ((cf_{c}) 表示 (c) 在当前 ([i , n]) 中出现次数)。

时间复杂度 : (O(N))

(F)

首先找出以 (1) 为根的最长链 ， 将其长度记为 (d)。

因为会出现 ((d + 1)) 种不同长度的字符串 ，显然 , (answer geq d + 1)。

为了使 (answer = d + 1) ， 需要使所有长度为 (i) 的字符串相等。考虑求出每个深度的节点出现的次数 (a_{i})。

那么等价于找出 (A) 的一个子集 ， 使其和为 (X) , 将其全部涂上 "a"。

注意到不同的 (a_{i}) 至多有 (O(sqrt{N})) 种 ， 不妨记录出现次数为 (i) 的深度个数 (freq_{i})。

考虑动态规划 ， 令 (dp_{i , j}) 表示后 (i) 种出现次数 ， 总和为 (j) 是否可行。

一种朴素的转移方式是枚举 (dp_{i + 1 , j - val_{i}} , dp_{i + 1 , j - 2 cdot val_{i}} , ... dp_{i + 1 , j - freq_{i} cdot val_{i}})。

进一步地 ， 注意到每次转移到的节点在模 (val) 意义下同余 ， 可以方便地记录 (last_{i}) 表示在模 (val) 意义下余 (i) 上次出现的位置。

这样就可以做到 (O(Nsqrt{N})) 了。

否则答案一定等于 ((d + 2)) ， 下面通过构造的方式证明这一点。

考虑枚举每一层节点。记当前在第 (i) 层 ， 还剩下 (m) 个字母可用 ， 其中有 (y) 个为 "a"。

若 (a_{i} leq max{y , m - y}) , 则直接给这层节点涂上一种颜色。

否则 ， 这层的非叶节点必须涂上同一种颜色 ， 因为每个非叶节点子树中必然存在至少 (1) 个节点 ， 非叶节点 (l geq frac{m}{2})。 又因为对于任意 (y) , (max{y , m - y} geq frac{m}{2})。 因此我们可以做到这一点。

这样就只剩下一种颜色了！ 我们成功构造出了 (answer = d + 2) !

时间复杂度 : (O(Nsqrt{N}))

[代码]

(A)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

char s[1000005];

int main() {
	
	 int T; cin >> T;
	 while (T--) {
	 	 int xx , yy; cin >> xx >> yy;
	 	 string ss; cin >> ss;
	 	 int u = 0 , d = 0 , l = 0 , r = 0;
	 	 for (int i = 0; i < ss.size(); ++i) {
	 	 	 if (ss[i] == 'U') ++u;
			 else if (ss[i] == 'R') ++r;
			 else if (ss[i] == 'D') ++d;
			 else ++l;  	
		 }
		 if (xx > 0 && r >= xx) xx = 0;
                 if (xx < 0 && l >= -xx) xx = 0;
                 if (yy > 0 && u >= yy) yy = 0;
                 if (yy < 0 && d >= -yy) yy = 0;
                 if (xx == 0 && yy == 0) puts("YES");
                 else puts("NO");
	 }
         return 0;
}

(B)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

const int MN = 5e5 + 5;

int A[MN];

int main() {
	 
	 int T; scanf("%d" , &T);
	 while (T--) {
	 	 int N , K; scanf("%d%d" , &N , &K);
	 	 for (int i = 1; i <= N; ++i) scanf("%d" , &A[i]);
	 	 int ans = -1;
	 	 for (int cur = 1; cur <= K; ++cur) {
			ans = -1;
			for (int i = 1; i < N; i++) if (A[i] < A[i + 1]) { ans = i; ++A[i]; break;}
			if (ans == -1) break;
		}
		printf("%d
" , ans);
	 }
         return 0;
}

(C)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

const int MN = 1e6 + 5;

int N , M , A[MN] , B[MN] , C[MN] , ans[MN];
vector < int > g[MN];

inline void solve() {
	scanf("%d%d" , &N , &M);
	for (int i = 1; i <= N; ++i) g[i].clear();
	for (int i = 0; i < N; ++i) scanf("%d" , &A[i]);
	for (int i = 0; i < N; ++i) {
		scanf("%d" , &B[i]);
		if (B[i] != A[i])
			g[B[i]].emplace_back(i);
	}
	for (int i = 0; i < M; ++i)
		scanf("%d" , &C[i]);
	int last = -1;
	if ((int) g[C[M - 1]].size() > 0) {
		last = g[C[M - 1]].back();
		g[C[M - 1]].pop_back();
	} else {
		for (int i = 0; i < N; ++i) {
			if (B[i] == C[M - 1]) {
				last = i;
				break;
			}
		}
	}
	if (last == -1) {
		printf("NO
");
		return;
	}
	ans[M - 1] = last;
	for (int i = 0; i < M - 1; ++i) {
		if (g[C[i]].size() == 0)
			ans[i] = last;
		else {
			ans[i] = g[C[i]].back();
			g[C[i]].pop_back();
		}
	}
	for (int i = 1; i <= N; ++i)
		if ((int) g[i].size() > 0) {
			printf("NO
");
			return;
		}
	printf("YES
");
	for (int i = 0; i < M; ++i) {	
		if (i) putchar(' ');
		printf("%d" , ans[i] + 1);
	}
	printf("
");
}
int main() {
	 
	 int T; scanf("%d" , &T);
	 while (T--) solve();
     return 0;
}

(D)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

const int MN = 1005;

int N , M , has[MN][2];
char grid[MN][MN];

inline void solve() {
	scanf("%d%d" , &N , &M);
	for (int i = 0; i <= N; ++i)
		has[i][0] = has[i][1] = -1;
	for (int i = 0; i < N; ++i) {
		scanf("%s" , grid[i]);
		for (int j = 0; j < N; ++j) {
			if (i == j) continue;
			has[i][grid[i][j] - 'a'] = j;
		}
	}
	if (M & 1) {
		printf("YES
");
		for (int i = 0; i <= M; ++i) {
			if (i) putchar(' ');
			printf("%d" , (i & 1) + 1);
		}
		printf("
");
		return;
	}
	for (int i = 0; i < N; ++i)
		for (int j = i + 1; j < N; ++j)
			if (grid[i][j] == grid[j][i]) {
				printf("YES
");
				for (int k = 0; k <= M; ++k) {
					if (k) putchar(' ');
					printf("%d" , (k & 1 ? i + 1 : j + 1));
				}
				puts("");
				return;
			}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i == j) continue;
			if (has[j][grid[i][j] - 'a'] == -1) continue;
			printf("YES
");
			int cur = has[j][grid[i][j] - 'a'];
			if ((M / 2) & 1) {
				for (int k = 0; k <= M; ++k) {
					if (k) putchar(' ');
					if (k % 4 == 0)
						printf("%d" , i + 1);
					else if (k % 4 == 2) 
						printf("%d" , cur + 1);
					else printf("%d" , j + 1);
				}
				printf("
");
				return;
			}
			printf("%d" , j + 1);
			for (int k = 0; k < M / 2; ++k)
				if (k & 1) printf(" %d" , j + 1);
				else printf(" %d" , cur + 1);
			for (int k = 0; k < M / 2; ++k)
				if (k & 1) printf(" %d" , j + 1);
				else printf(" %d" , i + 1);
			printf("
");
			return;
		}
	}
	printf("NO
");
}
int main() {
	 
	 int T; scanf("%d" , &T);
	 while (T--) solve();
         return 0;
}

(E)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

const int MN = 5e6 + 5;

int N , A[MN] , l[MN] , r[MN] , f[MN] , cnt[MN];

int main() {
	
	 scanf("%d" , &N);
	 for (int i = 1; i <= N; ++i) {
	 	 scanf("%d" , &A[i]); 
	 	 if (!l[A[i]]) l[A[i]] = i;
		 r[A[i]] = i; 
	 }
	 for (int i = N; i >= 1; --i) {
	 	 ++cnt[A[i]];
	 	 f[i] = f[i + 1];
	 	 if (i == l[A[i]])
	 	 	f[i] = max(f[i] , cnt[A[i]] + f[r[A[i]] + 1]);
	 	 else
	 	 	f[i] = max(f[i] , cnt[A[i]]);
	 }
	 printf("%d
" , N - f[1]);
         return 0;
}

(F)

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

typedef pair < int , int > pii;

#define mp make_pair
#define F first
#define S second

const int MN = 1e5 + 5 , SQ = 500;

int N , X , mx , sz[MN] , dp[SQ][MN] , f[MN];
char c[MN];
vector < pii > v , v2;
vector < int > g[MN] , cur[MN];
pair < int , char > a , b;

inline void go(int i , int j) {
	if (i == (int) v2.size())
		return;
	while (!dp[i + 1][j]) {
		++f[v2[i].first];
		j -= v2[i].first;
	}
	go(i + 1 , j);
}
inline void chkmin(int &x , int y) {
	x = min(x , y);
}
inline void chkmax(int &x , int y) {
	x = max(x , y);
}
inline bool cmp(int u , int v) {
	return sz[u] < sz[v];
}
inline int DFS(int u , int d) {
	chkmax(mx , d);
	cur[d].emplace_back(u); sz[u] = 1;
	for (int v : g[u])
		sz[u] += DFS(v , d + 1);
	return sz[u];
}

int main() {
	 
	 scanf("%d%d" , &N , &X);
	 a = mp(X , 'a'); b = mp(N - X , 'b');
	 if (a > b) swap(a , b);
	 for (int i = 2; i <= N; ++i) {
	 	 int x; scanf("%d" , &x);
	 	 g[x].emplace_back(i);
	 }
	 DFS(1 , 0);
	 for (int i = 0; i <= mx; ++i)
	 	v.emplace_back(mp((int) cur[i].size() , i));
	 sort(v.begin() , v.end());
	 for (int i = 0; i < v.size(); ++i)
	 	 if (i == 0 || v[i].F != v[i - 1].F) 
	 		 v2.emplace_back(mp(v[i].F , 1));
	 	 else
		  	 ++v2.back().second;
	 dp[(int)v2.size()][0] = true;
	 for (int i = (int) v2.size() - 1; i >= 0; --i) {
	 	 int val = v2[i].first , frq = v2[i].second;
	 	 vector < int > last (val , -1);
	 	 for (int j = 0; j <= X; ++j) {
	 	 	 if (dp[i + 1][j] == true)
			   	last[j % val] = j;
			 if (last[j % val] == -1 || ((j - last[j % val]) / val) > frq)
			 	dp[i][j] = false;
			 else 
			 	dp[i][j] = true;	
		 }
	 }
	 if (dp[0][X]) {
	 	 go(0 , a.F);
	 	 for (int i = 1; i <= N; ++i) c[i - 1] = b.S;
	 	 for (int i = 0; i <= mx; ++i) {
	 	 	 if (f[(int) cur[i].size()] == 0) continue;
			 --f[(int) cur[i].size()];	 
			 for (auto x : cur[i])
			 	 c[x - 1] = a.S;
		 } 
		 printf("%d
" , mx + 1); c[N] = '';
		 puts(c);
		 return 0;
	 }
	 printf("%d
" , mx + 2);
	 for (int i = 0; i <= mx; ++i) {
	 	 sort(cur[i].begin() , cur[i].end() , cmp);
	 	 if (a.F < b.F) swap(a , b);
	 	 while (cur[i].size() > 0 && a.F > 0) {
	 		 c[cur[i].back() - 1] = a.S;
			 cur[i].pop_back();
			 --a.F;	
		 }
		 while (cur[i].size() > 0 && b.F > 0) {
		 	 c[cur[i].back() - 1] = b.S;
		 	 cur[i].pop_back();
		 	 --b.F;
		 } 
	 }
	 c[N] = ''; 
	 puts(c);
         return 0; 
}