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