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);

}

AtCoder Beginner Conest 284 解题报告