AtCoder Beginner Conest 284 解题报告

\(\text{By DaiRuiChen007}\)

\(\text{Contest Link}\)

A. Sequence of Strings

模拟，时间复杂度 \(\Theta(n)\)

#include<bits/stdc++.h>
using namespace std;

signed main() {
	int n;
	cin>>n;
	vector <string> v(n);
	for(int i=n-1;i>=0;--i) cin>>v[i];
	for(auto p:v) cout<<p<<"\n";
	return 0;
}

B. Multi Test Cases

模拟，时间复杂度 \(\Theta(Tn)\)

#include<bits/stdc++.h>
using namespace std;

signed main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int n,ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i) {
			int a;
			scanf("%d",&a);
			if(a%2==1) ++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}

C. Count Connected Components

dfs 标记，时间复杂度 \(\Theta(n+m)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=301;
vector <int> G[MAXN];
bool vis[MAXN];
inline void dfs(int p) {
	vis[p]=true;
	for(int v:G[p]) if(!vis[v]) dfs(v);
}
signed main() {
	int n,m,ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;++i) if(!vis[i]) ++ans,dfs(i);
	printf("%d\n",ans);
	return 0;
}

D. Happy New Year 2023

枚举 \(\min(p,q)\)，注意到 \(\min(p,q)\) 应该是 \(\sqrt[3]n\) 级别的，因此时间复杂度 \(\Theta(T\sqrt[3]n)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int sqr(int x) {
	int k=sqrt(x);
	for(int ret=k-10;ret<=k+10;++ret) {
		if(k<0) continue;
		if(k*k==x) return k;
	}
	return -1;
}
inline void solve() {
	int n;
	scanf("%lld",&n);
	for(int i=2;i*i*i<=n;++i) {
		if(n%i==0) {
			if(n%(i*i)==0) printf("%lld %lld\n",i,n/(i*i));
			else printf("%lld %lld\n",sqr(n/i),i);
			return ;
		}
	}
}
signed main() {
	int T;
	scanf("%lld",&T);
	while(T--) solve();
	return 0;
}

E. Count Simple Paths

大力 dfs，搜索的时候用数组记录一下每个点是否已经在路径中即可

注意到每次搜到一个点后答案会 \(+1\)，因此最多访问 \(10^6\) 个点，而每搜到一个点至多遍历与其相邻的 \(10\) 个点

时间复杂度 \(\Theta(k\deg(v))\)，其中 \(k=\min(10^6,\text{ans})\)，\(\deg(v)\) 表示最大度数

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1,LIM=1e6;
int ans=0;
vector <int> G[MAXN];
bool inq[MAXN];
inline void dfs(int p) {
	inq[p]=true;
	++ans;
	if(ans==LIM) {
		printf("%d\n",LIM);
		exit(0);
	}
	for(int v:G[p]) if(!inq[v]) dfs(v);
	inq[p]=false;
}
signed main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

F. ABCBAC

对原序列做从左至右和从右至左的字符串哈希，对于每个 \(i\) 计算哈希值并比较即可

时间复杂度 \(\Theta(n)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e6+1,BASE=13331,MOD=998244353;
char str[MAXN],rev[MAXN];
int p[MAXN],s[MAXN][2];
inline int q(int l,int r,int op) {
	return (s[r][op]+MOD-s[l-1][op]*p[r-l+1]%MOD)%MOD;
}
signed main() {
	int n;
	scanf("%lld%s",&n,str+1);
	for(int i=1;i<=2*n;++i) rev[i]=str[2*n-i+1];
	p[0]=1;
	for(int i=1;i<=2*n;++i) {
		p[i]=p[i-1]*BASE%MOD;
		s[i][0]=(s[i-1][0]*BASE+str[i]-'a')%MOD;
		s[i][1]=(s[i-1][1]*BASE+rev[i]-'a')%MOD;
	}
	for(int i=0;i<=n;++i) {
		if((q(1,i,0)*p[n-i]%MOD+q(n+i+1,2*n,0))%MOD==q(n-i+1,2*n-i,1)) {
			for(int j=1;j<=i;++j) printf("%c",str[j]);
			for(int j=n+i+1;j<=2*n;++j) printf("%c",str[j]);
			printf("\n%lld\n",i);
			return 0;
		}
	}
	puts("-1");
	return 0;
}

G - Only Once

考虑在所有的 \((a_i,i)\) 之间连边，我们能够得到一棵基环树，而 \(s_i\) 事实上就是 \(i\) 到基环树中环的距离

我们可以把 \(s_i\) 理解为一条长度为 \(s_i\) 的链接一个环，考虑拆贡献，对于每个 \(1\sim n\) 的 \(k\)，我们统计有多少种情况使得图中有一个恰好长度为 \(k\) 的链

首先确定长度为 \(k\) 的链，我们先从 \(n\) 个数里任选 \(k\) 个，然后对其进行排列，得到这一步的方案数为 \(\binom nk\times k!\) 种

而在确定了链之后，我们要在链的后面接一个环，假设其长度为 \(j\)，我们同样在剩下的 \(n-k\) 个数里任选 \(j\) 个然后进行排列，不过注意到不同的点与链相连算不同的方案，因此此处的排列方案数为 \(j\times(j-1)!\) 种，总方案数为 \(\binom {n-k}j\times j!\)

而剩下的 \(n-k-l\) 个点随意选择连接的节点，方案数 \(n^{n-k-l}\)

因此我们得到答案的表达式：

\[\begin{aligned}
\text{answer}
&=\sum_{k=0}^n k\times\binom nk\times k!\times\sum_{j=1}^{n-k} \binom{n-k}j\times j!\times n^{n-k-j}\\
&=\sum_{k=0}^n\sum_{j=1}^{n-k} k\times\binom nk\times k!\times\binom{n-k}j\times j!\times n^{n-k-j}\\
&=\sum_{k=0}^n\sum_{j=1}^{n-k}k\times\dfrac{n!}{k!\times(n-k!)}\times k!\times\dfrac{(n-k)!}{j!(n-k-j)!}\times j!\times n^{n-k-j}\\
&=\sum_{(j+k)=1}^n\sum_{k=0}^{(j+k)-1} k\times \dfrac{n!}{(n-j-k)!}\times n^{n-j-k}\\
&=\sum_{i=1}^n \dfrac{n!}{(n-i)!}\times n^{n-i}\times\sum_{k=0}^{i-1}k\\
&=\sum_{i=1}^n\dfrac{n!}{(n-i)!}\times n^{n-i}\times \dfrac{i\times(i-1)}2
\end{aligned}
\]

其中在化简的过程中我们令 \(i=j+k\) 方便表达

注意到 \(\dfrac{n!}{(n-i)!}\) 可以在递推预处理得到，因此时间复杂度为 \(\Theta(n\log n)\)，\(\Theta(\log n)\) 为快速幂复杂度

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1;
int f[MAXN];
inline int ksm(int a,int b,int m) {
	int ret=1;
	while(b) {
		if(b&1) ret=ret*a%m;
		a=a*a%m;
		b=b>>1;
	}
	return ret;
}
signed main() {
	int n,mod,ans=0;
	scanf("%lld%lld",&n,&mod);
	f[n]=1;
	for(int i=n;i>=1;--i) f[i-1]=f[i]*i%mod;
	for(int k=1;k<=n;++k) ans=(ans+k*(k-1)/2%mod*ksm(n,n-k,mod)%mod*f[n-k]%mod)%mod;
	printf("%lld\n",ans);
}