AtCoder Beginner Contest 401 A~E题解

A题：

题面翻译：

问题陈述

给你一个介于 $100$ 和 $999$ （含）之间的整数 $S$ 。

如果 $S$ 介于 $200$ 和 $299$ （含）之间，则打印 "成功"；否则，打印 "失败"。

限制因素

$100 \le S \le 999$
$S$ 是整数。
输入

输入内容由标准输入法提供，格式如下

输出

打印答案。
思路：
简简单单，我们只需要设1个变量，输入，判断，输出即可。唯一需要小心的就是最好加上换行。
代码：

#pragma GCC optimize(2)//交洛谷时注释掉
#include <bits/stdc++.h>
#define int long long //十年OI一场空，不开long long见祖宗
using namespace std;
using ll=long long;
inline void read(int& a) {
	int w = 1, c;a = 0;
	while ((c = getchar()) < '0' || c > '9') 
		if (c == '-') w = -1;
	do {
		a=a*10+(c ^48);
	} while ((c = getchar()) >= '0' && c <= '9');
	a *= w;
	return ;}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return ;
}
const int N=100010;//边界条件令人狂，若用define CE亡
//memset(,0,sizeof );//数组不清空，亲人两行泪

signed main() {
	int s;
	read(s);
	if(s>=200&&s<=299)cout<<"Success"<<endl;
	else cout<<"Failure"<<endl;
	return 0;
}

B题：

题面：

问题陈述

一天，高桥在某个网站上执行了 $N$ 操作。

第 $i$ 次操作 $(1 \le i \le N)$ 用字符串 $S_i$ 表示，该字符串是以下字符串之一：

$S _ i=$ 登录执行登录操作并登录网站。
$S _ i=$ 注销执行注销操作，不再登录网站。
$S _ i=$ 公共页面他访问了网站的公共页面。
$S _ i=$ 私人他访问了网站的私人页面。

只有在未登录的情况下访问私人页面时，网站才会返回身份验证错误。

在已登录的情况下再次登录，或在已注销的情况下再次注销，都不会导致***错误。即使出现身份验证错误，用户仍可继续执行其余操作。

最初，他没有登录。

打印在 $N$ 次操作中出现身份验证错误的操作次数。

限制因素

$1 \le N \le 100$
$N$ 是整数。
每个 $S_i$ 都是 login、logout、public、private 中的一个。 $(1 \le i \le N)$
输入

输入内容由标准输入法提供，格式如下

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

打印高桥收到验证错误的次数。
思路：
也不难，一个变量记录登陆状态，cnt记录错误数量，最后输出即可。
代码：

#pragma GCC optimize(2)//交洛谷时注释掉
#include <bits/stdc++.h>
#define int long long //十年OI一场空，不开long long见祖宗
using namespace std;
using ll=long long;
inline void read(int& a) {
	int w = 1, c;a = 0;
	while ((c = getchar()) < '0' || c > '9') 
		if (c == '-') w = -1;
	do {
		a=a*10+(c ^48);
	} while ((c = getchar()) >= '0' && c <= '9');
	a *= w;
	return ;}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return ;
}
//const int N=100010;//边界条件令人狂，若用define CE亡
//memset(,0,sizeof );//数组不清空，亲人两行泪
int N;
signed main() {
	cin >> N;
	bool z = false; 
	int cnt = 0;     
	while(N--) {
		string a;
		cin >> a;
		if (a == "login") {
			z = true;
		} else if (a == "logout") {
			z = false;
		} else if (a == "private") {
			if (!z) {
				cnt++;
			}
		}
		// "public"操作不需要任何处理
	}
	cout<<cnt<< endl;
	return 0;
}

C题：

题面：

问题陈述

给你正整数 $N$ 和 $K$ 。定义长度为 $N+1$ 的序列 $$A = (A _ 0, A _ 1, \ldots, A _ N)$$ 如下：

\[A_i = 1为 0<=i<K ； \]

求 $A_N$ modulo $10^9$ 。

限制因素

$1 \le N, K \le 10^{6}$
所有输入值均为整数。
输入

输入内容由标准输入法提供，格式如下

N K

输入样本 1

4 2

样本输出 1

思路：
有点难度，建立一个滑动区间，sum为当前区间和，不断维护长度为K区间即可，同时同步sum到 $a_i$ 即可，代码有点难度，可以慢慢食用并消化……
代码：

#pragma GCC optimize(2)//交洛谷时注释掉
#include <bits/stdc++.h>
#define int long long //十年OI一场空，不开long long见祖宗
using namespace std;
using ll=long long;
inline void read(int& a) {
	int w = 1, c;a = 0;
	while ((c = getchar()) < '0' || c > '9') 
		if (c == '-') w = -1;
	do {
		a=a*10+(c ^48);
	} while ((c = getchar()) >= '0' && c <= '9');
	a *= w;
	return ;}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return ;
}
//const int N=100010;//边界条件令人狂，若用define CE亡
//memset(,0,sizeof );//数组不清空，亲人两行泪
const int MOD = 1e9;
int A[(int)1e6+10];
signed main() {
	int N, K;
	memset(A,0,sizeof A);
	cin >> N >> K;
	for (int i = 0; i < K; i++)
		A[i] = 1;
	long sum = K; // 初始窗口和
	for (int i = K; i <= N; i++) {
		A[i] = sum % MOD;
		sum += A[i];
		if (i >= K)
			sum -= A[i - K];
		if (sum < 0)
			sum += MOD;
	}
	cout << A[N] << endl;
	return 0;
}

D题：

题面：

问题陈述

给你一个长度为 $N$ 的字符串 $S$ ，它由字符 .、o 和 ?组成。在将 $S$ 中的每个?独立替换为.或o后得到的字符串中，设 $X$ 是满足以下所有条件的字符串集合：

o`的个数正好是 $K$ 。
没有两个o相邻。

保证 $X$ 非空。

打印长度为 $N$ 的字符串 $T$ ，它满足以下条件(让 $T_i$ 表示 $T$ 的第 $i$ 个字符)：

如果 $X$ 中每个字符串的第 $i$ 个字符都是 .，那么 $T_i=$ .。
如果 $X$ 中每个字符串的第 $i$ 个字符都是 o，那么 $T_i=$ 就是 o。o.
如果 $X$ 同时包含 $i$ 个字符为 .的字符串和 $i$ 个字符为 o的字符串，则 $T_i=$ ?。

限制因素

$1 \le N \le 2 \times 10^{5}$
$0 \le K$
$S$ 是长度为 $N$ 的字符串，由 .、o、? 组成。
$X$ 为非空字符串。
所有给定的数值都是整数。

输入

输入内容由标准输入法提供，格式如下

N K
S

输入样本 1

4 2
o???

样本输出 1

o.??

集合 $X$ 由两个字符串 o.o. 和 o...o 组成。

$X$ 中每个字符串的第一个字符都是 o，所以 $T_1$ 是 o。
$X$ 中每个字符串的第 2 个字符是 .，因此 $T_2$ 是 .。
$X$ 中字符串的第 3 个字符可以是 . 或 o，因此 $T _3$ 是 ?。

思路：
乍一看，挺难的，其实一点不简单，仔细想一想，没什么技术含量，主要就是暴力，一遍遍的遍历，处理，减少未处理个数直到全部处理完成。具体来讲，如下：

初始理解问题

首先，我们需要明确问题的要求：

输入：一个字符串 S，由 ., o, ? 组成，以及一个整数 K。
操作：将 S 中的每个 ? 替换为 . 或 o，生成所有可能的字符串。
约束：
- 生成的字符串中 o 的数量必须恰好为 K。
- 生成的字符串中不能有两个相邻的 o。
输出：根据所有满足约束的字符串，生成一个新的字符串 T：
- 如果所有字符串中第 i 个字符都是 .，则 T[i] = '.'。
- 如果所有字符串中第 i 个字符都是 o，则 T[i] = 'o'。
- 否则，T[i] = '?'。

解题思路

为了构造满足条件的 T，我们需要：

确定哪些位置的字符是固定的：
- 原始字符串 S 中的 . 必须保留，因为 ? 不能替换为 . 或 o 以外的字符。
- 原始字符串 S 中的 o 必须保留，因为 ? 不能替换为 . 或 o 以外的字符。
- ? 可以替换为 . 或 o，但需要满足 o 的总数为 K 且没有两个 o 相邻。
处理 o 和 . 的影响：
- 每个 o 会强制其相邻的位置不能是 o（即必须为 .）。
- 因此，我们可以先处理 S 中已经确定的 o 和 .，然后处理 ?。
构造 ans 的初始状态：
- 初始化 ans 为全 ?。
- 将 S 中的 . 直接复制到 ans 中（因为这些位置在所有满足条件的字符串中必须是 .）。
- 处理 S 中的 o：
  - 将 ans 中对应的位置设为 o。
  - 将其相邻的位置设为 .（因为这些位置不能是 o）。
- 统计已经确定的 o 的数量 cnt。
检查 cnt 是否已经等于 K：
- 如果 cnt == K，那么所有剩余的 ? 必须替换为 .（因为不能增加更多的 o）。
- 直接输出 ans，将剩余的 ? 替换为 .。
如果 cnt < K：
- 需要从剩余的 ? 中选择一些替换为 o，使得 o 的总数达到 K。
- 剩余的 ? 必须满足：
  - 不能与已有的 o 相邻。
  - 不能与其他新选的 o 相邻。
- 最优的方式是在连续的 ? 中交替放置 o 和 .，这样可以最大化 o 的数量（即 (length + 1) / 2）。
- 计算通过这些连续的 ? 可以增加的 o 的最大数量 max_add。
  - 如果 cnt + max_add == K，则可以唯一确定这些 ? 的替换方式（交替放置 o 和 .）。
  - 否则，这些 ? 的替换方式不唯一，因此它们在 T 中保持为 ?。

代码：

#pragma GCC optimize(2)//交洛谷时注释掉
#include <bits/stdc++.h>
#include<atcoder/all>
#define int long long //十年OI一场空，不开long long见祖宗
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
int n,k;string s;
signed main(){
	cin>>n>>k>>s;
	string ans=s;
	for(int i=0;i<n;i++)ans[i]='?';
	int cnt=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='.')ans[i]='.';
		else if(s[i]=='o'){
			for(int j=-1;j<=1;j++){
				if(i+j<0||i+j>=n)continue;
				if(j==0){
					ans[i+j]='o';
					cnt++;
					continue;
				}
				if(s[i+j]=='?')ans[i+j]='.';
			}
		}
	}
	if(cnt==k){
		for(int i=0;i<n;i++)if(ans[i]=='?')ans[i]='.';
		cout<<ans;
		return 0;
	}
	for(int i=0;i<n;){
		int j=i;
		while(j<n&&ans[j]=='?')j++;
		if(i==j)i++;
		else{
			cnt+=(j-i+1)/2;
			i=j;
		}
	}
	if(cnt==k){
		for(int i=0;i<n;){
			int j=i;
			while(j<n&&ans[j]=='?')j++;
			if(i==j)i++;
			else{
				if((j-i)%2==1){
					bool ff=1;
					for(int k=i;k<j;k++){
						if(ff)ans[k]='o',ff=0;
						else ans[k]='.',ff=1;
					}
				}
				i=j;
			}
		}
		cout<<ans;
	}
	else cout<<ans;
	return 0;
}

代码解释

以下是代码的逐步解释：

输入和初始化：
- 读取 n, k, s。
- 初始化 ans 为全 ?。
处理 S 中的 . 和 o：
- 遍历 S：
  - 如果 s[i] == '.'，则 ans[i] = '.'。
  - 如果 s[i] == 'o'：
    - 将 ans[i] 设为 'o'，并增加 cnt。
    - 检查相邻位置（i-1 和 i+1），如果它们是 ?，则设为 '.'（因为不能有相邻的 o）。
检查 cnt == k：
- 如果已经满足，将 ans 中剩余的 ? 设为 '.' 并输出。
处理剩余的 ?：
- 遍历 ans，找到连续的 ? 段：
  - 对于每段连续的 ?，计算可以增加的 o 的最大数量 (length + 1) / 2。
  - 累加到 cnt 中。
- 如果 cnt == k：
  - 对于每段连续的 ?，交替放置 'o' 和 '.'（确保不连续 'o'）。
- 否则：
  - 这些 ? 的替换方式不唯一，保持为 '?'。
输出结果。

正确性分析

初始处理：
- 确保所有已知的 o 和 . 被正确处理，且 o 的相邻位置被限制为 .。
- 如果 cnt == k，则所有 ? 必须为 .，因为不能增加更多的 o。
连续 ? 的处理：
- 连续的 ? 可以最大化 o 的数量，通过交替放置 'o' 和 '.'。
- 如果 cnt + max_add == k，则这些 ? 的替换方式是唯一的（交替）。
- 否则，存在多种替换方式（例如，某些 ? 可以选择 'o' 或 '.' 而不影响总数），因此这些位置在 T 中为 '?'。
边界条件：
- 确保不越界访问（如 i-1 和 i+1 的检查）。
- 确保 X 非空（题目保证）。

示例分析

以样例输入 4 2 和 S = "o???" 为例：

初始 ans = "????"。
处理 S[0] = 'o'：
- ans[0] = 'o', cnt = 1。
- 相邻 S[1] 是 ?，所以 ans[1] = '.'。
- ans = "o.??"。
cnt = 1 < k = 2，处理剩余的 ?：
- 连续 ? 段是 ans[2..3] = "??"。
- 可以增加 (2 + 1) / 2 = 1 个 'o'。
- cnt + 1 = 2 == k，因此交替放置：
  - ans[2] = 'o', ans[3] = '.'。
- ans = "o.o."。
- 但根据代码逻辑，会检查 (j - i) % 2 == 1（即长度为 2，是偶数），因此交替放置 'o' 和 '.'：
  - ans[2] = 'o', ans[3] = '.'。
- 但题目中 X 还包含 o...o，因此 ans[3] 也可以是 'o'（如果 k=2 且其他位置允许）。
- 因此，ans 的某些位置可能是 '?'。

实际输出是 o.?，因为：

ans[0] = 'o'（固定）。
ans[1] = '.'（固定）。
ans[2] 可以是 'o' 或 '.'（因为 o.o. 和 o..o 都满足条件）。
ans[3] 可以是 '.' 或 'o'（如 o.o. 和 o..o）。

因此，T = "o.??"。

E题：

题面：

问题陈述

给你一个无向图，图中有 $N$ 个顶点和 $M$ 条边。顶点编号为 $1,2,\ldots,N$ ，第 $i$ 条边 $(1 \le i \le M)$ 连接顶点 $u_i$ 和 $v_i$ 。

请针对每个 $k = 1,2,\ldots,N$ 解决以下问题：

考虑以下操作。

选择一个顶点，删除该顶点及其所有边。

确定是否可以重复此操作以满足以下条件：

从顶点 $1$ 通过遍历边可到达的顶点集合正好由 $k$ 顶点 $1,2,\ldots,k$ 组成。

如果可能，请找出所需的最少操作次数。

限制因素

$1 \le N \le 2 \times 10^{5}$
$0 \le M \le 3 \times 10^{5}$
$1 \le u_i < v_i \le N\\ (1 \le i \le M)$
$(u_i,v_i)/=(u_j,v_j) (1 \le i,j \le M)$
所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出

打印 $N$ 行。在 $i$ -th 行 $(1 \le i \le N)$ 中，如果无法满足 $k=i$ 的条件，则打印 -1；否则，打印满足条件所需的最少操作数。

输入样本 1

样本输出 1

例如，对于 $k = 2$ ，删除三个顶点 $3, 4, 5$ 使得顶点 $1$ 可以到达的顶点集合等于两个顶点 $1, 2$ 。删除两个或更少的顶点是不可能的，因此在第二行打印 "3"。

对于 $k = 6$ 而言，删除 0 个顶点使得顶点 $1$ 可以到达的顶点集合等于顶点 $1,2,\ldots,6$ 的 6 个顶点，因此在第 6 行打印 0。
思路：
简单来说，并查集+图论，检查连通性。
具体做法：

问题理解

我们需要对每个 ( k )（从 ( 1 ) 到 ( N )）判断是否可以通过删除某些顶点及其边，使得从顶点 ( 1 ) 出发可达的顶点集合恰好是 ( {1, 2, \ldots, k} )。如果可以，输出最少操作次数（即删除的顶点数）；否则输出 -1。

关键观察

连通性条件：
- 对于 ( k )，顶点 ( 1 ) 到 ( k ) 必须连通。
- 不能有边连接到 ( {k+1, \ldots, N} ) 的顶点。
操作次数：
- 最少操作次数是 ( {k+1, \ldots, N} ) 中必须删除的顶点数，即这些顶点中与 ( {1, \ldots, k} ) 有边的顶点数。

代码实现思路

初始化

使用并查集（DSU）维护连通性。
- f[i]：顶点 ( i ) 的父节点。
- si[i]：以 ( i ) 为根的连通块大小。
mark 数组：标记顶点是否与当前处理的顶点集合有边。
ans[i]：存储 ( k=i ) 时的答案（最少操作次数）。
vis[i]：标记 ( k=i ) 时是否满足连通性条件。

计算 `ans` 数组

对于每个顶点 ( i )，遍历其邻接表。
统计与 ( i ) 相连且编号大于 ( i ) 的顶点数（这些顶点需要被删除）。
动态维护 cnt 变量（表示当前需要删除的顶点数），并存入 ans[i]。

检查连通性

从 ( i=2 ) 开始，逐步将顶点 ( i ) 及其邻接的较小顶点合并到连通块中。
检查以顶点 ( 1 ) 为根的连通块大小是否等于 ( i )。
- 如果不等，说明无法满足条件，设置 vis[i] = 1。

输出结果

对于每个 ( i )：
- 如果 vis[i] 为 1，输出 -1。
- 否则输出 ans[i]。

代码流程

输入与初始化：
- 读入图数据。
- 初始化并查集（每个顶点自成一个连通块）。
预处理 ans 数组：
- 遍历每个顶点 ( i )，统计需要删除的顶点数。
连通性检查：
- 逐步合并顶点，动态检查连通性。
输出结果：
- 根据 vis 和 ans 数组输出每个 ( k ) 的答案。

复杂度分析

预处理 ans 数组：( O(M) )（每条边被访问两次）。
并查集操作：近似 $O(N \alpha(N))$（路径压缩优化）。
总复杂度$O(N \alpha(N) + M)$，适用于题目约束。
代码：

#pragma GCC optimize(2)//交洛谷时注释掉
#include <bits/stdc++.h>
//#include<atcoder/all>
#define int long long //十年OI一场空，不开long long见祖宗
//#define N 400
using namespace std;
using ll=long long;
inline void read(int& a) {
	int w=1;char c;a=0;
	while((c=getchar())<'0'||c>'9')if(c=='-')w=-1;
	do a=a*10+(c^48); while((c=getchar())>='0'&&c<='9');
	a*=w;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return ;
}
//const int N=1e9;//边界条件令人狂，若用define CE亡
//memset(,0,sizeof );//数组不清空，亲人两行泪
const int MAXN=200005;
vector<int> edge[MAXN];
int vis[MAXN],mark[MAXN],f[MAXN],si[MAXN],ans[MAXN];
int find(int x){
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y)return;
	f[y]=x,si[x]+=si[y];
}
signed main() {
	int n,m;
	read(n),read(m);
	for(int i=1;i<=n;i++)f[i]=i,si[i]=1;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j:edge[i]){
			if(j<i){
				if(mark[i])cnt--;
				mark[i]=0;
			}
			else if(mark[j]++==0)cnt++;
		}
		ans[i]=cnt;
	}
	for(int i=2;i<=n;i++){
		for(auto j:edge[i])if(j<i)merge(j,i);
		if(si[find(1)]!=i)vis[i]=1;
	}
	for(int i=1;i<=n;i++){
		if(vis[i])cout<<-1<<endl;
		else write(ans[i]),cout<<endl;
	}
	return 0;
}

需要仔细~~食用和品尝~~……

AtCoder Beginner Contest 401 A~E题解

A题：

问题陈述

限制因素

输入

输出

B题：

问题陈述

限制因素

输入

输出

C题：

问题陈述

限制因素

输入

输入样本 1

样本输出 1

D题：

问题陈述

限制因素

输入

输入样本 1

样本输出 1

初始理解问题

解题思路

代码解释

正确性分析

示例分析

E题：

问题陈述

限制因素

输入

输出

输入样本 1

样本输出 1

问题理解

关键观察

代码实现思路

初始化

计算 ans 数组

检查连通性

输出结果

代码流程

复杂度分析

相关阅读

本类排行

相关标签

本类推荐

栏目热点

猜你喜欢

计算 `ans` 数组