A. Musical Puzzle
题意：给出一个字符串，求有多少个不同的长度为2的子串
Solution
直接set存即可
void solve()
{
int n;cin>>n;
string s;cin>>s;
set<string>st;
for(int i=0;i<n-1;i++)
{
st.insert(s.substr(i,2));
}
cout<<st.size()<<"\n";
}
B. Restore the Weather
题意：给出a,b两个数组，构造出一种组合，使得|a[i]-b[i]|<=k
Solution
直接把a，b数组从小到大排序即可
struct node
{
int x,y;
bool operator < (const node &t)const &{
if(y!=t.y)return y < t.y;
else return x < t.x;
}
}e[N];
int ans[N];
int b[N];
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
e[i].x=i,e[i].y=x;
}
for(int i=1;i<=n;i++)cin>>b[i];
sort(e+1,e+1+n);
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
ans[e[i].x]=b[i];
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<"\n";
}
C. Vlad Building Beautiful Array
题意：给出一个数组a，现在要求构造另一个数组b，要求数组b中全为正奇数或者全为正偶数，b[i]可以为a[i]或者a[i]-a[j]
Solution
可以全构造为奇数或者偶数，将数组从小到大排序
对于构造全奇数的情况，对于一个偶数，前面必须要有比它小的奇数
对于构造全偶数的情况，对于一个奇数，前面必须要有比它小的奇数(所以有奇数的话其实是不可能的？)
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int ans=1;
int flag=0;
for(int i=1;i<=n;i++)
{
if(a[i]&1)
{
if(!flag)
{
ans=0;
break;
}
flag=1;
}
}
if(ans)
{
cout<<"YES\n";
return;
}
flag=0;
ans=1;
for(int i=1;i<=n;i++)
{
if(a[i]&1)
{
flag=1;
}else
{
if(!flag)
{
ans=0;
break;
}
}
}
if(ans)cout<<"YES\n";
else cout<<"NO\n";
}
D. Flipper
题意：给出一个数组，可以任选一个区间[l,r]，将其中的数翻转，然后再将左边的数整体放到区间右边，右边的数整体放到区间左边，求字典序最大的情况
Solution
分情况讨论，因为求字典序最大的，所以跟最大值n的位置脱不了关系
当n的位置在最右边时，要把n放在第一位，那么区间就要包含n，然后向左移动看，如果a[l-1]比a[1]大，那么将l-1加进来的字典序是比不加要大的
当n的位置在最左边，此时无论怎么操作字典序都会变小，我们就要看n-1的位置，如果n-1在最右边，同上一种情况我们可以知道，n-1和n之间的数都比n小，答案就是[n,n]，如果n-1在中间位置，答案是[pos-1,pos-1]，因为如果多选的话会使得n的位置在更后面
当n的位置在中间，同第一种情况，把左边所有大于a[1]的数都纳入区间
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int pos;
for(int i=1;i<=n;i++)
{
if(a[i]==n)
{
pos=i;
break;
}
}
int l,r;
if(pos==n)
{
l=n,r=n;
while(l-1>=1&&a[l-1]>a[1])l--;
}else if(pos==1)
{
int pp;
for(int i=1;i<=n;i++)
{
if(a[i]==n-1)
{
pp=i;break;
}
}
if(pp==n)
{
l=n,r=n;
}else
{
l=pp-1,r=pp-1;
}
}else
{
l=pos-1,r=pos-1;
while(l-1>=1&&a[l-1]>a[1])l--;
}
for(int i=r+1;i<=n;i++)cout<<a[i]<<" ";
for(int i=r;i>=l;i--)cout<<a[i]<<" ";
for(int i=1;i<l;i++)cout<<a[i]<<" ";
cout<<"\n";
}
E. Round Dance
题意：有n个人跳舞，在每一组里每个人有两个相邻的人(如果一组人里面只有两个人跳舞，那么他们相邻的人相同)，每个人只记得一个相邻的人，问跳舞的组数最大最小是多少
Solution
并查集求出联通分块数量num，该答案就是最大值，然后再找含有度数不为2的点的连通分块数量cnt，最小值答案是num-max(0,cnt-1)
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
t[i]=i;
l[i]=0;
}
int cnt=n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<i&&a[a[i]]==i)
{
continue;
}else
{
l[a[i]]++;
l[i]++;
}
int aa=find(i),b=find(a[i]);
if(aa!=b)
{
t[aa]=b;
cnt--;
}
}
unordered_map<int,int>mp;
for(int i=1;i<=n;i++)
{
int z=find(i);
if(l[i]!=2)mp[z]++;
}
cout<<cnt-max(0LL,(long long)mp.size()-1)<<" "<<cnt<<"\n";
}
F. Ira and Flamenco
题意：有n个人跳舞，每个学生都有一个等级，要求找到满足以下要求的组的个数
1.该组有且仅有m个学生跳舞
2.每个学生的等级互不相同
3.每个学生的等级差严格小于m
Solution
从条件里面可以看出，满足条件的必须是一个公差为1的等差数列
那我们把它们的等级排序，然后把满足条件的答案加起来即可
int a[N];
struct node
{
int x,y;
bool operator < (const node &t)const &{
if(y!=t.y)return y<t.y;
else return x<t.x;
}
}e[N];
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(cnt==0||a[i]!=e[cnt].y)
{
e[++cnt].y=a[i];
e[cnt].x=1;
}else
{
e[cnt].x++;
}
}
int ans=0;
int res=0;
int num=0;
int last=-1;
for(int i=1;i<=cnt+1;i++)
{
if(last==-1)
{
last=e[i].y;
num++;
res=e[i].x%mod;
}
else if(i==cnt+1||e[i].y-last!=1)
{
if(num==m)
{
ans=(ans+res)%mod;
}
num=1;
res=e[i].x%mod;
last=e[i].y;
}else
{
if(num==m)
{
ans=(ans+res)%mod;
res=(res*ksm(e[i-m].x,mod-2))%mod;
num--;
}
res=res*e[i].x%mod;
last=e[i].y;
num++;
}
//cout<<res<<" ";
}
//cout<<"\n";
cout<<ans<<"\n";
}
G. Ksyusha and Chinchilla
题意：给出一个树，问删除哪些边可以使得每个点仅属于一个长度为3的枝条
Solution
首先树的大小必须为3的倍数，然后删除的边的个数必须为n/3-1，这样才能保证满足条件
然后我们跑一遍dfs，把遇到大小为3的子树就把他删除，记录删除的边即可
vector<pii>e[N];
int sz[N];
int vis[N];
int dfs(int x,int pre,int id)
{
int res=0;
sz[x]=1;
for(auto it:e[x])
{
if(it.first==pre)continue;
res+=dfs(it.first,x,it.second);
sz[x]+=sz[it.first];
}
if(sz[x]-res==3)
{
vis[id]=1;
res+=3;
}
return res;
}
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
vis[i]=0;
e[i].clear();
}
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
e[u].push_back({v,i});
e[v].push_back({u,i});
}
if(n%3!=0)
{
cout<<"-1\n";
return;
}
dfs(1,0,0);
int num=0;
for(int i=1;i<=n;i++)
{
if(vis[i])num++;
}
if(num!=n/3-1)
{
cout<<"-1\n";
return;
}
cout<<num<<"\n";
for(int i=1;i<=n;i++)
{
if(vis[i])cout<<i<<" ";
}
cout<<"\n";
}