AtCoder Beginner Conest 284 解题报告
\(\text{By DaiRuiChen007}\)
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);
}