A. Reorder

判斷一下所有元素加和是否等于m即可，

#include <bits/stdc++.h>
using namespace std;
int T;
int n,m;
int sum;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int x;
        sum=0;
        while(n--)
        {
            scanf("%d",&x);
            sum+=x;
        }
        if(sum==m)
        puts("YES");
        else
        puts("NO");
    }
    return 0;
}

B. Prime Square

n很小隨便搞，我是直接+4,+6,+8…這樣做的，也可以像答案一樣用0，1（比賽時候以為不能用0QAQ）

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
long long su[maxn],cnt;
bool isprime[maxn];
int a[maxn];
void prime()
{
    cnt=1;
    memset(isprime,1,sizeof(isprime));//初始化認為所有數都是素數
    isprime[0]=isprime[1]=0;//0和1不是素數
    for(long long i=2;i<=maxn;i++)
    {
        if(isprime[i])
        su[cnt++]=i;//保存素數i
        for(long long j=1;j<cnt&&su[j]*i<=maxn;j++)
        {
            isprime[su[j]*i]=0;//篩掉小于等于i的素數和i的積構成的合數
        }
    }
}
int main()
{
    int T;
    prime();
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        a[0]=1;
        int sum=1;
        for(int i=1;i<n;++i)
        {
            for(int j=4;;j+=2)
            {
                if(isprime[sum+j])
                {
                    a[i]=j;
                    sum+=j;
                    break;
                }
            }
        }
        for(int j=0;j<n;++j)
        {
            for(int i=0;i<n;++i)
            {
                printf("%d ",a[(i+j)%n]);
            }
            puts("");
        }
    }
    return 0;
}

C. Binary Search

利用二分的程序，判斷一下必須向右跳的有幾個，必須向左跳的有幾個，然后排列計算一下即可，

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e3+5;
int n,x,pos;
ll A[N][N];
int main()
{
    scanf("%d%d%d",&n,&x,&pos);
    A[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        A[i][0]=1;
        for(int j=1;j<=i;++j)
        {
            A[i][j]=(i-j+1)*A[i][j-1]%mod;
        }
    }
    int le,gr;
    le=gr=0;
    int l=0;
    int r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(mid<=pos)
        {
            if(mid!=pos)
            le++;
            l=mid+1;
        }
        else
        {
            gr++;
            r=mid;
        }
    }
    //cout<<le<<" "<<gr<<endl;
    printf("%lld\n",A[x-1][le]*A[n-x][gr]%mod*A[n-le-gr-1][n-le-gr-1]%mod);
    return 0;
}

D. Bandit in a City

這題就是要使葉子節點的權值盡可能平均，那對于一個節點如何知道怎樣分配才能使其葉子節點平均呢，只需要從葉子節點向上，維護當前葉子節點最大值，葉子節點數，葉子節點權值和，然后判斷當前所有葉子節點的權值和 sum + 當前點的值v 是否> 當前葉子節點最大值max*當前葉子節點數，如果小于說明還不能使所有葉子節點權值到max，否則就可以讓所有節點權值到max，然后利用平均分配原則，使剩下的值平均的分給每個葉子，更新max，最后根節點的max就是答案，

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int head[N];
struct node
{
    int to,next;
}edge[N];
ll a[N];
struct e
{
    ll ma;
    ll num;
    ll sum;
}p[N];
int n;
int cnt;
void add(int x,int y)
{
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int u,int fa)
{
    bool flag=0;
    ll ma=0;
    ll s=0;
    ll nb=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        flag=1;
        int v=edge[i].to;
        dfs(v,u);
        ma=max(ma,p[v].ma);
        s+=p[v].sum;
        nb+=p[v].num;
    }
    if(!flag)//р╤вс╫з╣Ц
    {
        p[u].ma=a[u];
        p[u].sum=a[u];
        p[u].num=1;
    }
    else
    {
        if(a[u]+s>ma*nb)
        {
            ll t=a[u]+s-ma*nb;
            ma+=t/nb;
            if(t%nb)
            ma++;
        }
        p[u].ma=ma;
        p[u].sum=s+a[u];
        p[u].num=nb;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        add(x,i);
    }
    for(int i=1;i<=n;++i)
    scanf("%lld",&a[i]);
    dfs(1,0);
    printf("%lld\n",p[1].ma);
    return 0;
}

E. Complicated Computations

我們需要找到最后mex序列的所有元素,那么考察每一個元素是否出現在最后mex即可，對于一個數k，如果其為某序列mex，那么其在序列肯定沒出現，并且1~k-1都出現了，那么在原始序列，就是看1~k-1最小的位置，是否出現在上一次k出現的位置之前，如果出現在上一次k出現的位置之前，那么此時mex就是最小的那個，否則就是k，這個程序可以用線段樹模擬，

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
bool vis[N];//記錄該數是否出現過
int last[N];//記錄該數上一次出現的位置
int mi[N<<4];//維護1-k-1最小出現位置
void push_up(int k)
{
    mi[k]=min(mi[k<<1],mi[k<<1|1]);
}
void update(int k,int l,int r,int pos,int v)
{
    if(l==r)
    {
        mi[k]=v;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
    update(k<<1,l,mid,pos,v);
    else
    update(k<<1|1,mid+1,r,pos,v);
    push_up(k);
}
int query(int k,int l,int r,int v)
{
    if(l==r)
    return l;
    int mid=(l+r)>>1;
    if(mi[k<<1]<v)
    return query(k<<1,l,mid,v);
    else
    return query(k<<1|1,mid+1,r,v);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        int x=a[i];
        if(last[x]+1<i)
        vis[query(1,1,N-1,last[x]+1)]=1;
        last[x]=i;
        update(1,1,N-1,x,i);
    }
    for(int i=1;i<=N-1;++i)
    {
        if(last[i]&&last[i]!=n)
        vis[query(1,1,N-1,last[i]+1)]=1;
    }
    vis[query(1,1,N-1,1)]=1;
    for(int i=1;i<=N-1;++i)
    {
        if(!vis[i])
        {
            printf("%d\n",i);
            return 0;
        }
    }
}