Codeforces Round 1003 (Div. 4)（A~G题题解）

A. Skibidus and Amog'u

思路：把字符串最后的us变成i就可以了，水题一个

#include <iostream>  
#include <string>  int main() {  int t;  std::cin >> t;  std::cin.ignore();  while (t--) {  std::string W;  std::getline(std::cin, W); if (W.length() >= 2 && W.substr(W.length() - 2) == "us") {  std::string root = W.substr(0, W.length() - 2);  std::string plural = root + "i";  std::cout << plural << std::endl;  }  }  return 0;  
}

B. Skibidus and Ohio

 思路，有一对相邻的相同就可以把整个序列的长度变成1，否则就是原长度

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];
string s;
void solve()
{cin>>s;for(int i=0;i<s.size()-1;i++){if(s[i]==s[i+1]){cout<<1<<"\n";return ;}}cout<<s.size()<<"\n";
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

C1. Skibidus and Fanum Tax (easy version)

思路：本题b数组只有一个数，那么我们将a数组所有数都与b数组进行计算，

我们设x=a[i],y=b[i]-a[i],

1.假设x和y都大于等于前面一个，我们就选择min(x,y)作为a[i]

2.如果只有x大于等于前面一个，就选择x作为a[i]

3.如果只有y大于等于前面一个，就选择y作为a[i]

4.如果都不大于，就输出NO结束这次测试数据

如果运行到最后就是输出YES

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m;
int a[200005];
int b[200005];
string s;
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}a[0]=-0x3f3f3f3f;int flag=1;for(int i=1;i<=n;i++){if(b[1]-a[i]<=a[i]&&b[1]-a[i]>=a[i-1]){a[i]=b[1]-a[i];}else if(b[1]-a[i]>=a[i-1]&&a[i]<a[i-1]){a[i]=b[1]-a[i];}if(a[i]<a[i-1]){flag=0;break;}}if(flag==0){cout<<"NO\n";}else{cout<<"YES\n";}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

C2. Skibidus and Fanum Tax (hard version)

思路：一眼二分，我们还是上面的处理思路，但是我们该如何选取b[j]-a[i]呢？

我们可以用lower_bound去寻找第一个大于a[i]+a[i-1]的b[i]的位置，找到之后，就是c1的处理方式，直接去操作就可以了

分四步走战略

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m;
int a[200005];
int b[200005];
string s;
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}b[m+1]=1e12;sort(b+1,b+1+m);a[0]=-1e12;a[1]=min(a[1],b[1]-a[1]);for(int i=2;i<=n;i++){int flag=a[i-1]+a[i];int pos=lower_bound(b+1,b+2+m,flag)-b;if(pos==m+1&&a[i]<a[i-1]){cout<<"NO\n";return ;}else if(pos>=1&&pos<=m&&a[i]<a[i-1]&&b[pos]-a[i]>=a[i-1]){a[i]=b[pos]-a[i];}else if((pos>=1&&pos<=m&&a[i]>=b[pos]-a[i]&&b[pos]-a[i]>=a[i-1])){a[i]=b[pos]-a[i];}}cout<<"YES\n";
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

D. Skibidus and Sigma

思路：其实就是按照顺序单行数组的累加和大小排序就行，然后计算一遍累加和就过了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m;
int x;
int sum;
string s;
pair<int,int> p[200005];
void solve()
{cin>>n>>m;int a[n+1][m+1];for(int i=1;i<=n;i++){sum=0;for(int j=1;j<=m;j++){cin>>a[i][j];sum+=a[i][j];}p[i].first=sum;p[i].second=i;}sort(p+1,p+1+n);sum=0;int ans=0;for(int i=n;i>=1;i--){for(int j=1;j<=m;j++){sum+=a[p[i].second][j];ans+=sum;}}cout<<ans<<"\n";
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

 E. Skibidus and Rizz

思路：我们首先要排除两种可能得情况

1，n<k,m<k，如果都小于k，就算单纯连起来也不可能达到要求，直接输出NO

2，abs(n-m)>k,整体都大于k了，呢么已经超过了最大平衡值k，所以不满足直接输出NO

3.否则，我们就先用最多的数构建一个长度为k的序列，如果是0，那么后续就跟10，直到其中一个没有了，如果剩下的是0，就补到最后面，如果剩下的是1，就补到前面，反之依然，就可以解决了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m,k;
int a[200005];
void solve()
{cin>>n>>m>>k;if(abs(n-m)>k){cout<<-1<<"\n";}else if(k>n&&k>m){cout<<-1<<"\n";}else{string s="";if(n>=m){n-=k;for(int i=1;i<=k;i++){s+="0";}for(int i=1;i<=min(n,m);i++){s+="10";}if(n>=m){for(int i=1;i<=n-m;i++){s+="0";}}else{for(int i=1;i<=m-n;i++){s+="1";}}}else{m-=k;for(int i=1;i<=k;i++){s+="1";}for(int i=1;i<=min(n,m);i++){s+="01";}if(n>=m){for(int i=1;i<=n-m;i++){s+="0";}}else{for(int i=1;i<=m-n;i++){s+="1";}}}cout<<s<<"\n";}}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

F. Skibidus and Slay

思路：直接去寻找每一个点链接的子节点，只要出现的次数大于等于2，就可以将其标注为1

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[500005];
int u,v;
vector<int> e[500005];
string s;
void dfs(int v,int fa,vector<int> &vis)
{map<int,int> mp;mp.clear();mp[a[v]]++;for(int u:e[v]){mp[a[u]]++;if(mp[a[u]]==2){vis[a[u]]=1;}}for(int u:e[v]){if(u!=fa){dfs(u,v,vis);}}
}
void solve()
{cin>>n;vector<int> vis(n+1,0);for(int i=1;i<=n;i++) {  e[i].clear();  }  for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-1;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,-1,vis);for(int i=1;i<=n;i++)cout<<vis[i]; cout<<"\n";
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--)solve();return 0;
}

 G. Skibidus and Capping

思路：直接找到1~200000，里面的所有的素数，我们只需要统计三种情况的结果即可，

1，如果是素数的话，要找到所有和他能匹配的素数

2.如果是pq和pq的话，我们直接计算即可 

3.如果是pq的话，我们要找到所有的p和q的数量

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
int a[200005];
int pri[200005];//素数集合 
int vis[200005];//判断是否是素数
int cnt=0;//统计素数数量 
int p[200005];//每个数的最小质数 
int shu[200005];
void ini()
{vis[1]=1;for(int i=2;i<=200000;i++){if(vis[i]==0){cnt++;pri[cnt]=i;}for(int j=1;j<=cnt&&i*pri[j]<=200000;j++){vis[i*pri[j]]=1;p[i*pri[j]]=pri[j];if(i%pri[j]==0)break;}} 
}
//三种情况
//1.两个都是素数
//2.pq和pq这种
//3.p和pq这种 
void solve()
{cin>>n;int num=0;//用于统计素数个数 for(int i=1;i<=n;i++){cin>>a[i];if(vis[a[i]]==0){num++; }shu[a[i]]++;}int ans=(num+1)*num/2;for(int i=2;i<=n;i++){//第一种 if(vis[i]==0){ans-=shu[i]*(shu[i]+1)/2;continue;}int q=i/p[i];if(vis[q]==1){continue;}//第二种 ans+=shu[i]*(shu[i]+1)/2;//第三种ans+=shu[i]*shu[p[i]];if(q!=p[i]){ans+=shu[i]*shu[q]; }}cout<<ans<<"\n";for(int i=1;i<=200000;i++){shu[i]=0;}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ini();cin>>t;while(t--)solve();return 0;
}