这把打的不顺,开头交不上去就慌了。后面的T2,T3wa麻了。
目录
4082. 子序列【签到】
https://www.acwing.com/problem/content/description/4085/
暴力做法:
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
string s;
cin>>s;
int cnt=0;
for(int i=0;i<s.size();i++)
for(int j=i+1;j<s.size();j++)
for(int z=j+1;z<s.size();z++)
if(s[i]=='Q'&&s[j]=='A'&&s[z]=='Q') cnt++;
cout<<cnt;
return 0;
}
前缀和做法:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int sum[N];
int main(void)
{
string s;
cin>>s; s="0"+s;
int cnt=0,n=s.size()-1;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(s[i]=='Q'?1:0);
for(int i=1;i<=n;i++)
if(s[i]=='A') cnt+=sum[i-1]*(sum[n]-sum[i]);
cout<<cnt;
return 0;
}
4083. 最大公约数【分解因子】
https://www.acwing.com/problem/content/description/4086/
对每一个数,分解因子,最后枚举所有的因子,取一个max即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,x,cnt[N];
int main(void)
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x; cnt[x]++;
for(int j=2;j<=x/j;j++)
{
if(x%j==0)
{
cnt[j]++;
if(x/j!=j) cnt[x/j]++;
}
}
}
int ans=1;
for(int i=2;i<N;i++) ans=max(ans,cnt[i]);
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,x,cnt[N];
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>x,cnt[x]++;
int ans=1;
for(int i=2;i<N;i++) //直接暴力枚举所有的公共因子即可
{
int s=0;
for(int j=i;j<N;j+=i) s+=cnt[j];//计算该因子所对应的个数
ans=max(ans,s);
}
cout<<ans;
return 0;
}
4084. 号码牌【并查集】
https://www.acwing.com/problem/content/4087/
根据题意建图,然后枚举每一个点,看是否可以到达目的地即可。
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int g[N][N],st[N],n,a[N],b[N];
bool dfs(int u,int ed)
{
if(u==ed) return true;
bool flag=0;
st[u]=1;
for(int i=1;i<=n;i++)
{
if(st[i]) continue;
if(g[u][i]) flag=max(flag,dfs(i,ed));
}
return flag;
}
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++)
{
if(i+b[i]<=n) g[i][i+b[i]]=1,g[b[i]+i][i]=1;
if(i-b[i]>=1) g[i][i-b[i]]=1,g[i-b[i]][i]=1;
}
for(int i=1;i<=n;i++)
{
memset(st,0,sizeof st);
if(!dfs(i,a[i])) //不可以到达
{
puts("NO");
return 0;
}
}
puts("YES");
}
其实不用建图,因为都是双向边,故直接用并查集,判断当前的点和目的地是不是同一个集合即可。
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int p[N],n,a[N],b[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=n;i++)
{
if(i+b[i]<=n) p[find(i+b[i])]=find(i);
if(i-b[i]>=1) p[find(i-b[i])]=find(i);
}
for(int i=1;i<=n;i++)
{
if(find(i)!=find(a[i]))
{
puts("NO");
return 0;
}
}
puts("YES");
}