Codeforces 874 div3 A-G

A. Musical Puzzle

分析

每两个相邻的字母都要录制一段，开个set记录一下，然后输出set的大小

C++代码：

#include<iostream>
#include<set>
using namespace std;
void solve(){int n;string s;cin>>n>>s;set<string> se;for(int i=0;i<s.size()-1;i++)se.insert(s.substr(i,2));cout<<(int)se.size()<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

B. Restore the Weather

分析

这题的k只是个幌子，根本没用

a从小到大对应b的从小到大

直接让b排序，然后根据a的大小按照对应位置放好就行

C++代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
PII a[N];
int b[N],c[N],n,k;
void solve(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i].first;a[i].second=i;}sort(a+1,a+1+n);for(int i=1;i<=n;i++)cin>>b[i];sort(b+1,b+1+n);for(int i=1;i<=n;i++){c[a[i].second]=b[i];}for(int i=1;i<=n;i++)cout<<c[i]<<" ";cout<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

C. Vlad Building Beautiful Array

分析

如果全是奇数或者全是偶数，则输出Yes

如果存在奇数，则不可能将所有数都变成偶数，因为最小的那个奇数就不可能变成偶数

所以存在奇数就要把所有的偶数都变成奇数，则对于所有的偶数，都必须要有比当前数小的奇数，否则不可能全变成奇数

C++代码：

#include<iostream>
#include<algorithm>
using namespace std;
void solve(){int n,sum1=0,sum2=0;cin>>n;int a[n+5];for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%2==0)sum1++;else sum2++;}if(sum1==n||sum2==n)puts("Yes");else{sort(a+1,a+n+1);//如果有奇数，则必须全变成奇数,那么对于每个偶数都必须要有比他小的奇数 int t=0,flag=0;for(int i=1;i<=n;i++)//a[i]为偶数且没有比a[i]小的奇数if(a[i]%2==0&&!t)flag=1;else if(a[i]%2)t=1;if(flag)puts("No");else puts("Yes");}
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

D. Flipper

分析

要数组最大，则让n在第一个数最大

如果n本来就在第一个数，进行操作则n不可能还在第一个数，那么让n-1在第一个数

所以让要找的数的下标的前一个下标作为右端点 r ,如果要找的数的下标为n，则让n作为右端点r，然后暴力枚举左端点，找进行操作后最大的数组

C++代码：

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> get(int l,int r,vector<int> a){vector<int> res;for(int i=r+1;i<=n;i++)res.push_back(a[i]);//[r+1,n]变成前缀 for(int i=r;i>=l;i--)res.push_back(a[i]);//反转区间[l,r] for(int i=1;i<=l-1;i++)res.push_back(a[i]);//[1,l-1]变成后缀 return res;
}
void solve(){cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++)cin>>a[i];int t=find(a.begin(),a.end(),n)-a.begin();//找到n的位置if(t==1){//如果n是第一个数 t=find(a.begin(),a.end(),n-1)-a.begin();//找到n-1的位置 }int r=t==n?t:t-1;vector<int> ans(n,1);for(int l=1;l<=r;l++)ans=max(ans,get(l,r,a));//vector可以直接这样比大小for(int i=0;i<n;i++)cout<<ans[i]<<" \n"[i==n-1];
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

E. Round Dance

分析

直接用并查集记录连通块的个数，然后看有几个连通块有环的存在

这题是n个点n条边，每个点最多只有两个邻点，且可能有重边，所以一个连通块最多一个环，在合并两个点的时候，记录是否有环，如果有，则sum3++，记录连通块的个数sum2

所以最多sum2个，最少sum3+(sum2-sum3>0)个，除了环剩下的都可以接在一起合并成一个

C++代码：

#include<iostream>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N=200010;
int p[N];
map<PII,int> st;
int n;
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
int merge(int a,int b){int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;return true;}return false;//会形成环 
}
void solve(){cin>>n;st.clear();for(int i=1;i<=n;i++)p[i]=i;int sum1=0,sum2=0,sum3=0;for(int i=1;i<=n;i++){int x;cin>>x;if(!st[{i,x}]){if(!merge(i,x))sum3++;//如果有环}st[{i,x}]++,st[{x,i}]++;}for(int i=1;i<=n;i++)if(p[i]==i)sum2++;sum1=sum3+(sum2-sum3>=1);cout<<sum1<<" "<<sum2<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

F. Ira and Flamenco

分析

区间内数的个数等于m且互不相同，且区间极值小于m，显然这m个数只能是连续的数

先记录数组a中每个数出现的次数，然后对a排序去重

对于第一个样例，m=4,n=7

8 10 10 9 6 11 7

排序去重后的结果为6，7，8，9，10，11，个数分别为1，1，1，1，2，1

合法区间：

6，7，8，9，该方案的个数为1*1*1*1=1

7，8，9，10，该方案的个数为1*1*1*2=2

8，9，10，11，该方案的个数为1*1*2*1=2

一共有1+2+2=5种方案

从前往后搜索每个数

假设搜到了一个合法的区间，假设当前区间每个数个数相乘之和为 t，然后到了下一个区间，就要将该区间的第一个数去掉，类似于滑动窗口，把数去掉的同时还要除以第一个数的个数，新加一个数就要乘以新加的数的个数

这题如果直接做会爆long long，但是看到有除法还有对质数取模，就可以考虑用逆元来做了，直接把除法变成乘法

C++代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010,mod=1e9+7;
typedef long long LL;
int n,m;
LL qmi(LL a,LL k,LL p){LL res = 1;while(k){if(k&1)res=res*a%p;a=a*a%p;k>>=1;}return res;
}
void solve()
{cin>>n>>m;vector<int> a(n);map<int,int> cnt;for(int i=0;i<n;i++)cin>>a[i],cnt[a[i]]++;sort(a.begin(),a.end());//排序 a.erase(unique(a.begin(),a.end()),a.end());//去重 if(m==1){int ans=0;for(auto t:cnt)ans=(ans+t.second)%mod;cout<<(ans+mod)%mod<<endl;return;}LL sum=1,ans=0,t=cnt[a[0]];for(int i=1;i<a.size();i++){if(a[i]==a[i-1]+1)sum++,t=(t*cnt[a[i]])%mod;else sum=1,t=cnt[a[i]];if(sum==m){ans=(ans+t)%mod;sum--;t=t*qmi(cnt[a[i-m+1]],mod-2,mod)%mod;}}cout<<(ans+mod)%mod<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

G. Ksyusha and Chinchilla

分析

连续的三个节点即可连成一条树枝

直接dfs搜索整棵树，然后记录以每个节点为根的子树的大小，如果当前子树大小刚好为3，则让该子树大小变成0（因为已经用过了，不能让别的节点再用该子树种的任何节点），然后把连接该子树的边的编号加入到答案种去，详见代码

C++代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
const int N=200010,M=N*2;
typedef pair<int,int> PII;
void solve(){int n;cin>>n;vector<PII> e[n+1]; for(int i=1;i<n;i++){int a,b;cin>>a>>b;//加边，a-b这条边的编号为ie[a].push_back({b,i});e[b].push_back({a,i}); }vector<int> ans,sz(n+1);//ans记录答案,sz记录子树大小//第一次尝试这样写函数，不写在外面，边写边学hhfunction<void(int,int,int)> dfs=[&](int u,int fa,int from){//from表示从哪条边过来的sz[u]=1;//以u为根的子树大小for(auto [v,i]:e[u]){//u的所有邻点if(v==fa)continue;dfs(v,u,i);sz[u]+=sz[v];}if(sz[u]==3){//如果子树大小刚好为3，则让子树大小为0，防止u的父节点加上这三个点sz[u]=0;if(from)ans.push_back(from);//加上编号为from的边}};dfs(1,-1,0);//dfs遍历整棵树if(sz[1]!=0)cout<<-1<<'\n';else{cout<<ans.size()<<endl;for(auto x:ans)cout<<x<<" ";cout<<'\n';}
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}