Codeforces Round #668 A~D题解(div2)

本文主要是介绍Codeforces Round #668 A~D题解(div2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.Permutation Forgery

题目传送门：
Permutation Forgery

简单题，反向输出即可，就直接放代码

AC code

#include<bits/stdc++.h>
using namespace std;
int main()
{int t,a[105];scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=n;i>1;i--) printf("%d ",a[i]);printf("%d\n",a[1]);}//system("pause");return 0;
}

B.Array Cancellation

题目传送门
Array Cancellation

题意

给你一个和为0的数组，每次可以选择两个不同的数ai和aj，使ai减1，aj加1，如果i<j，操作免费，否则代价为1，求最小代价

思路

从前往后贪心，从前往后遍历，遇到正数就存起来，遇到负数如果前面有正数存着就把负数消掉。然后再重新遍历一遍，计算存留的负数的和即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N];
int main()
{int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);LL res=0,ans=0;for(int i=1;i<=n;i++){if(a[i]>=0) ans=ans+a[i];else{int k=min(ans,-a[i]);ans=ans-k;a[i]=a[i]+k;}}for(int i=1;i<=n;i++)if(a[i]<0) res=res-a[i];printf("%lld\n",res);}//system("pause");return 0;
}

C.Balanced Bitstring

题目传送门
Balanced Bitstring

题意

给你一个01字符串，可以将字符串中的问号变成0或者1，问你能不能使字符串的长度为k的所有子串里的0和1数量保持相同。

思路

我们可以发现比如k=4，第一段以0为首的子串s1占据了0123这4个位置，第二段以1为首的子串s2则占据了1234四个位置，由此可以看到两个子串共享了123三个字符，为了使这两段字符串中的0和1的数量保持相同，位置0的字符必须和位置4的字符一样。同理可得位置1的字符串必须和位置5的字符串一样。于是我们就可以以k个字符串为循环，判断i%k这个位置上的有没有01冲突，如果有就是不可行的，如果没有最后再判断能不能结合“？”使0和1的数量相等。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int t,n,k;
int ans[N];
int main()
{cin>>t;string str;while(t--){cin>>n>>k;cin>>str;int len=str.length();for(int i=0;i<len+10;i++) ans[i]=-1;int flag=0;for(int i=0;i<len;i++){int idx=i%k;if(str[i]=='?') continue;else{if(ans[idx]==-1) ans[idx]=str[i]-'0';else if(ans[idx]!=str[i]-'0'){flag=1;break;}}}int a=0,b=0;if(flag==0){for(int i=0;i<k;i++){if(ans[i]==0) a++;if(ans[i]==1) b++;}}if(a>k/2||b>k/2) flag=1;if(flag==1) printf("NO\n");else printf("YES\n");}//system("pause");return 0;
}

D.Tree Tag

(这题在比赛时并没有像清楚，赛后看了别人的思路（qaq）题目还是很有意思的)

题目传送门
Tree Tag

题意

在一颗顶点为n的树上，Alice和Bob开始位于两个不同的顶点，轮流移动，Alice先手。Alice可以移动到与当前顶点距离距离不超过da的顶点，Bob则不超过db，移动时允许停留在同一顶点上，执行移动时仅占据开始顶点和结束顶点，如果10^5步内Alice和Bob占据了同一个顶点，Alice胜否则Bob胜，求胜者。

思路

1、如果他们的距离不超过da，那么Alice第一步就可以获胜，因此一个dfs求两点距离特判一下。

2、如果2*da大于等于树的最长链，那么Alice只要占据树的中心，从而一步到达任意顶点取得胜利，因此要dfs计算最长链

3、db小于等于2*da，Alice获胜。比如此时Alice距离Bob的距离为da+1，Alice向Bob移动一个顶点，使距离为da，此时Bob不能移动到另一个子树使自己不被抓到。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,a,b,na,nb;
int h[N],cnt,ans;
int maxi=0,maxn=0;
struct tree
{int to;int next;
}tr[N*2];
void add(int x,int y)
{//加边函数tr[cnt].to=y;tr[cnt].next=h[x];h[x]=cnt++;
}
void dfs1(int now,int fa,int sum)
{for(int i=h[now];i;i=tr[i].next){if(ans!=0) return ;int to=tr[i].to;if(to==fa) continue;if(to==b){ans=sum+1;return ;} else dfs1(to,now,sum+1);}
}
void dfs2(int now,int fa,int sum)
{for(int i=h[now];i;i=tr[i].next){int to=tr[i].to;if(to==fa) continue;dfs2(to,now,sum+1);}if(sum>maxn){maxn=sum;maxi=now;}
}
int main()
{scanf("%d",&t);while(t--){scanf("%d%d%d%d%d",&n,&a,&b,&na,&nb);memset(h,0,sizeof(h));cnt=1;for(int i=1;i<=n-1;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}ans=0;dfs1(a,-1,0);//算出a,b直接的距离if(ans<=na) {printf("Alice\n");continue;}maxi=0,maxn=0;dfs2(1,-1,0);maxn=0;dfs2(maxi,-1,1);if(na<maxn/2&&nb>na*2) printf("Bob\n");else printf("Alice\n");}//system("pause");return 0;
}