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;
}