「CF 1490A」Dense Array

Link.

显然不满足的 adjacent elements 之间一直加 $\min\times2,\min\times4,\cdots,\min\times2^{k}$，满足 $\min\times2^{k}\le\max$ 即可。

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,a[60],ans;
bool judge(double one,double ano)
{
    return max(one,ano)/min(one,ano)<=2.0;
}
int jump(int one,int ano)
{
    int cone=min(one,ano),cano=max(one,ano),res=0;
    while(cone<=cano)
    {
        if((cone<<1)>=cano)    break;
        else
        {
            cone<<=1;
            res++;
        }
    }
    return res;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)    scanf("%d",&a[i]);
        for(int i=2;i<=n;++i)    ans+=judge(a[i],a[i-1])?0:jump(a[i],a[i-1]);
        printf("%d\n",ans);
    }
    return 0;
}

「CF 1490B」Balanced Remainders

Link.

把原序列的 $c_{0\sim2}$ 统计出来然后贪心（具体怎么贪看代码，不好描述）模拟。

#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,a[30010],c[3],ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            ++c[a[i]%3];
        }
        while((c[0]^c[1])||(c[0]^c[2]))
        {
            ans++;
            if(c[0]==*max_element(c,c+3))
            {
                --c[0];
                ++c[1];
            }
            else if(c[1]==*max_element(c,c+3))
            {
                --c[1];
                ++c[2];
            }
            else
            {
                --c[2];
                ++c[0];
            }
        }
        printf("%d\n",ans);
        for(int i=0;i<3;++i)    c[i]=0;
        ans=0;
    }
    return 0;
}

「CF 1490C」Sum of Cubes

Link.

枚举一个 $a$，然后判断 $n-a^{3}$ 是否为完全立方数即可，这个可以二分，注意二分的范围不要乱搞，容易溢出。

#include<cmath>
#include<cstdio>
using namespace std;
int t,flag;
long long n;
long long cud(long long x)
{
    return x*x*x;
}
bool check(long long x)
{
    long long l=1,r=pow(x,1.0/3.0)+5;
    while(l<=r)
    {
        long long mid=(l+r)>>1;
        if(cud(mid)>x)    r=mid-1;
        else if(cud(mid)<x)    l=mid+1;
        else    return true;
    }
    return false;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag=0;
        scanf("%lld",&n);
        for(int i=1;cud(i)<n;++i)
        {
            if(check(n-cud(i)))
            {
                flag=1;
                break;
            }
        }
        if(flag)    printf("YES\n");
        else    printf("NO\n");
    }
    return 0;
}

「CF 1490D」Permutation Transformation

Link.

递归建树，照题意模拟即可。

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int> e[110];
int t,n,a[110],dep[110];
int build(int l,int r)
{
    if(l>r)    return -1;
    int root=0,pos=0;
    for(int i=l;i<=r;++i)
    {
        if(a[i]>root)
        {
            root=a[i];
            pos=i;
        }
    }
    if(l^r)
    {
        int one=build(l,pos-1),ano=build(pos+1,r);
        if(~one)    e[root].push_back(one);
        if(~ano)    e[root].push_back(ano);
        return root;
    }
    else    return root;
}
void dfs(int x)
{
    for(int i=0;i<e[x].size();++i)
    {
        int y=e[x][i];
        dep[y]=dep[x]+1;
        dfs(y);
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)    scanf("%d",&a[i]);
        dfs(build(1,n));
        for(int i=1;i<=n;++i)    printf("%d ",dep[a[i]]);
        printf("\n");
        for(int i=1;i<=n;++i)
        {
            dep[i]=0;
            e[i].clear();
        }
    }
    return 0;
}

「CF 1490E」Accidental Victory

Link.

贪心，记录个 id 后排序（看代码吧）。

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int> ans;
pair<long long,int> a[200010];
int t,n;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i].first);
            a[i].second=i;
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;++i)    a[i].first+=a[i-1].first;
        ans.push_back(a[n].second);
        for(int i=n-1;i>=1;--i)
        {
            if(a[i].first>=a[i+1].first-a[i].first)    ans.push_back(a[i].second);
            else    break;
        }
        sort(ans.begin(),ans.end());
        printf("%d\n",(int)ans.size());
        for(int i=0;i<ans.size();++i)    printf("%d ",ans[i]);
        printf("\n");
        ans.clear();
        for(int i=1;i<=n;++i)    a[i]=make_pair(0,0);
    }
    return 0;
}

「CF 1490F」Equalize the Array

Link.

统计出现次数和出现次数的出现次数，然后根号模拟取 $\min$。

#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=1e9;
map<int,int> one,ano;
int t,n,a[200010],ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            ++one[a[i]];
        }
        for(map<int,int>::iterator now=one.begin();now!=one.end();++now)    ++ano[now->second];
        ans=INF;
        int l=0,r=n,c=one.size();
        for(map<int,int>::iterator now=ano.begin();now!=ano.end();++now)
        {
            ans=min(ans,l+r-c*now->first);
            l+=now->first*now->second;
            r-=now->first*now->second;
            c-=now->second;
        }
        printf("%d\n",ans);
        one.clear();
        ano.clear();
    }
    return 0;
}

「CF 1490G」Old Floppy Drive

Link.

denote for $S$ of the sum of all elements，for $pre$ of the prefix sum of the origin sequence。

首先判断原 $pre$ 里面有没有 $x$，这个搞个 std::map 就有了。

when $S\le0\and\max\{pre_{i}\}<x$ the answer doesn't exist.

if $S\ge0\and\not\exists i,s.t.pre_{i}=x$：此时先把 $x:=x\bmod S$，然后就查 std::map。

但是你会发现这样做写起来非常麻烦，可能需要手写平衡树。

于是你发现读错了题，是 $\ge x$ 不是 $=x$ （日你 horse）。

然后负数直接不存进 $pre$ 然后开两个 std::vector 二分就好了。

#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long INF=1e18;
vector<long long> onepre;
vector<int> anopre;
long long x,S,mx,len;
int t,n,m;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        mx=-INF;
        S=0;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&x);
            S+=x;
            if(onepre.empty()||S>*(prev(onepre.end())))
            {
                onepre.push_back(S);
                anopre.push_back(i-1);
            }
            mx=max(S,mx);
        }
//        printf("-------------------------\n");
//        printf("onemp area:\n");
//        for(auto now:onemp)
//        {
//            printf("    preval=%lld ; preval appearing position=",now.first);
//            for(auto won:now.second)    printf("%d ",won);
//            printf("\n");
//        }
//        printf("\nanomp area:\n");
//        for(auto now:anomp)
//        {
//            printf("[preval=%lld boolean=%d]\n",now.first,now.second);
//        }
//        printf("-------------------------\n");
        while(m--)
        {
//            int minuser=0;
            scanf("%lld",&x);
            if(lower_bound(onepre.begin(),onepre.end(),x)!=onepre.end())    printf("%d ",anopre[lower_bound(onepre.begin(),onepre.end(),x)-onepre.begin()]);
            else if(S<=0)    printf("-1 ");
            else
            {
//                minuser=((x%S)==0);
                len=(mx<x)?((x-mx+S-1)/S):0;
//                printf("(%lld %lld %lld %lld)",x,S,x%S,x/S);
                printf("%lld ",(lower_bound(onepre.begin(),onepre.end(),x%S)==onepre.end())?(-1):(len*n+anopre[lower_bound(onepre.begin(),onepre.end(),x-len*S)-onepre.begin()])/*((((x%S)==0)?(0):(anopre[lower_bound(onepre.begin(),onepre.end(),x%S)-onepre.begin()]))+(int)(x/S)*len-minuser)*/);
            }
        }
        printf("\n");
        onepre.clear();
        anopre.clear();
    }
    return 0;
}

Description

Link.

大模拟是不可能给你概括题意的。

Solution

（据说鸭棋题解用这个标题很吉利）（这里是被点名批评的 长度 19k 的打法）（先说好代码里 Chinglish 满地，尽量不要吐槽吧……）

首先我们不需要仔细阅读每一种棋的判定方法及其走法，写的时候照抄即可。

理一下大体逻辑。首先开一个全局的棋盘 vector<vector<string> > evemap;，一个 over 表示棋局是否结束。

然后是棋手的结构体：

struct chess
{
    string color;
    string getcolor(int x,int y);
    string getchess(int x,int y);
    bool outside(int x,int y);
    bool exist(int x,int y);
    bool thereok(int x,int y);
    bool occaptain(int sx,int sy,int tx,int ty);
    bool ocguard(int sx,int sy,int tx,int ty);
    bool ocelephant(int sx,int sy,int tx,int ty);
    bool ochorse(int sx,int sy,int tx,int ty);
    bool occar(int sx,int sy,int tx,int ty);
    bool ocduck(int sx,int sy,int tx,int ty);
    bool ocsoldier(int sx,int sy,int tx,int ty);
    string checkgoi();
    bool checkove();
    void moving(int sx,int sy,int tx,int ty);
    string final(string s);
    vector<string> movecaptain(int sx,int sy,int tx,int ty);
    vector<string> moveguard(int sx,int sy,int tx,int ty);
    vector<string> moveelephant(int sx,int sy,int tx,int ty);
    vector<string> movehorse(int sx,int sy,int tx,int ty);
    vector<string> movecar(int sx,int sy,int tx,int ty);
    vector<string> moveduck(int sx,int sy,int tx,int ty);
    vector<string> movesoldier(int sx,int sy,int tx,int ty);
    vector<string> execute(int sx,int sy,int tx,int ty); 
}redplay,blueplay;

string color 表示棋手的颜色。

这里先来解释一下各个函数的含义：

• oc-chess 和 move-chess 形式：

  • bool oc-chess(sx,sy,tx,ty)：这个表示 chess 棋从 $(s_{x},s_{y})$ 走到 $(t_{x},t_{y})$ 是否合法。
  • vector<string> move-chess(sx,sy,tx,ty)：这个标识 chess 棋从 $(s_{x},s_{y})$ 走到 $(t_{x},t_{y})$ 最终返回的东西。

• 其他的一些杂函数：

  • string getcolor(x,y)：棋盘位置 $(x,y)$ 的棋的颜色，如果没有则返回 empty。
  • string getchess(x,y)：棋盘位置 $(x,y)$ 的棋的棋子类型，如果没有则返回 empty。
  • bool outside(int x,int y)：$(x,y)$ 是否出界。
  • bool exist(int x,int y)：$(x,y)$ 是否存在任意一方的棋子。
  • bool thereok(int x,int y)：$(x,y)$ 是否不存在同色棋子且没有出界。
  • string checkgoi()：检查是否有将军。（通过遍历棋盘实现）
  • bool checkove()：是否有任意一方的将军被吃。
  • void moving(int sx,int sy,int tx,int ty)：把 $(s_{x},s_{y})$ 的棋子移到 $(t_{x},t_{y})$。
  • string final(string s)：我棋盘存储棋子的形式是 color-chess，这个函数的作用就是转为题目的形式 color chess。
  • void execute(sx,sy,tx,ty)：处理一次询问。

结构差不多就这里，接下来说一下具体实现。

• 首先用个 void mapinitial() 初始化棋盘。
• 然后都询问，处理询问，调用 execute()。
• 输出。

好的我承认这个实现方法特别烂。

/*
function(vector<string>)(with prefix 'move') result:
    "invcom": invalid command
    "color-chess": the chess(opposite) which is eaten
    "beaten": have the Jiangjun been complete
    "over": have the game been over
vector[0][1][2][3]
*/
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int h=10,w=9;
int over;
//string evemap[20][20];
vector<vector<string> > evemap;
void printmap()
{
    for(int i=0;i<h;++i)
    {
        for(int j=0;j<w;++j)    printf("%14s",evemap[i][j].c_str()),printf("[%d %d]",i,j);
        printf("\n");
    }
}
struct chess
{
    string color;
    string getcolor(int x,int y)
    /*
        result:
            "empty": empty place
            "red": red chess
            "blue": blue chess
    */
    {
        string res,s=evemap[x][y];
        if(s=="empty")    return "empty";
        else
        {
            for(int i=0;i<s.length();++i)
            {
                if(s[i]=='-')    break;
                res+=s[i];
            }
            return res;
        }
    }
    string getchess(int x,int y)
    /*
        result:
            each string has the same meaning as 'evemap'
    */
    {
        string res,s=evemap[x][y];
        if(s=="empty")    return "empty";
        else
        {
            int st=0;
            for(int i=0;i<s.length();++i)
            {
                if(st)    res+=s[i];
                else if(s[i]=='-')    st=1;
            }
            return res;
        }
    }
    bool outside(int x,int y)
    {
        if(x<0||x>=h||y<0||y>=w)    return 1;
        else    return 0;
    }
    bool exist(int x,int y)
    {
        if(getchess(x,y)=="empty")    return 0;
        else    return 1;
    }
    bool thereok(int x,int y)
    /*
        result:
            1: this place is walkable
            0: this place is occupied or (x,y) is out of range
        means:
            1. isn't out of range
            2. (x,y) has no same color chess or is empty
    */
    {
        if(outside(x,y))    return 0;
        else if(evemap[x][y]!="empty"&&getcolor(x,y)==color)    return 0;
        else    return 1;
    }
    bool occaptain(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                if(thereok(sx+i,sy)&&tx==(sx+i)&&ty==sy)    return 1;
                else if(thereok(sx,sy+i)&&tx==sx&&ty==(sy+i))    return 1;
            }
        }
        return 0;
    }
    bool ocguard(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                if(thereok(sx+i,sy+i)&&tx==(sx+i)&&ty==(sy+i))    return 1;
                if(thereok(sx+i,sy-i)&&tx==(sx+i)&&ty==(sy-i))    return 1;
            }
        }
        return 0;
    }
    bool ocelephant(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                for(int j=-1;j<=1;++j)
                {
                    if(j)
                    {
                        if(thereok(sx+i,sy+j))
                        {
                            if(thereok(sx+(i<<1),sy+(j<<1))&&tx==(sx+(i<<1))&&ty==(sy+(j<<1)))    return 1;
                        }
                    }
                }
            }
        }
        return 0;
    }
    bool ochorse(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                for(int j=-1;j<=1;++j)
                {
                    if(j)
                    {
//                        printf("[{%d %d} {%d %d} {%d %d %d}]\n",sx,sy+j,sx+i,sy+(j<<1),outside(sx,sy+j),exist(sx,sy+j),!outside(sx,sy+j)&&!exist(sx,sy+j));
                        if(!outside(sx+i,sy)&&!exist(sx+i,sy))
                        {
                            if(thereok(sx+(i<<1),sy+j)&&tx==(sx+(i<<1))&&ty==(sy+j))    return 1;
                        }
                        if(!outside(sx,sy+j)&&!exist(sx,sy+j))
                        {
                            if(thereok(sx+i,sy+(j<<1))&&tx==(sx+i)&&ty==(sy+(j<<1)))    return 1;
                        }
                    }
                }
            }
        }
        return 0;
    }
    bool occar(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        if(sx==tx)
        {
            int delta;
            if(sy<ty)    delta=1;
            else    delta=-1;
            for(int j=sy;j^ty;j+=delta)
            {
                if((j^sy)&&exist(sx,j))    return 0;
            }
            return 1;
        }
        else if(sy==ty)
        {
            int delta;
            if(sx<tx)    delta=1;
            else    delta=-1;
            for(int i=sx;i^tx;i+=delta)
            {
//                printf("[{%d %d}]\n",i,sy);
                if((i^sx)&&exist(i,sy))    return 0;
            }
            return 1;
        }
        else    return 0;
    }
    bool ocduck(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                for(int j=-1;j<=1;++j)
                {
                    if(j)
                    {
                        if(!outside(sx+(i<<1),sy+j)&&!exist(sx+(i<<1),sy+j)&&!outside(sx+i,sy)&&!exist(sx+i,sy))
                        {
//                            printf("[{%d %d} {%d %d} {%d %d} {%d %d} {%d %d} {%d %d}]\n",sx,sy,tx,ty,sx+i,sy,sx+(i<<1),sy+j,sx+((i<<1)+i),sy+(j<<1),thereok(sx+((i<<1)+i),sy+(j<<1)),tx==(sx+((i<<1)+i)&&ty==(sy+(j<<1))));
                            if(thereok(sx+((i<<1)+i),sy+(j<<1))&&tx==(sx+((i<<1)+i))&&ty==(sy+(j<<1)))    return 1;
                        }
                        if(!outside(sx+i,sy+(j<<1))&&!exist(sx+i,sy+(j<<1))&&!outside(sx,sy+j)&&!exist(sx,sy+j))
                        {
                            if(thereok(sx+(i<<1),sy+((j<<1)+j))&&tx==(sx+(i<<1))&&ty==(sy+((j<<1)+j)))    return 1;
                        }
                    }
                }
            }
        }
        return 0;
    }
    bool ocsoldier(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                if(thereok(sx+i,sy)&&tx==(sx+i)&&ty==sy)    return 1;
                if(thereok(sx,sy+i)&&tx==sx&&ty==(sy+i))    return 1;
                if(thereok(sx+i,sy+i)&&tx==(sx+i)&&ty==(sy+i))    return 1;
                if(thereok(sx+i,sy-i)&&tx==(sx+i)&&ty==(sy-i))    return 1;
            }
        }
        return 0;
    }
    string checkgoi()
    /*
        result:
            "not": Jiangjun didn't happened
            "red": the RED general has been Jiangjuned
            "blue": the BLUE general has been Jiangjuned
    */
    {
        if(over)    return "not";
        for(int i=0;i<h;++i)
        {
            for(int j=0;j<w;++j)
            {
                string curcol=getcolor(i,j),curche=getchess(i,j),revcol;
                if(curcol=="red")    revcol="blue";
                else if(curcol=="blue")    revcol="red";
                else    revcol="empty";
                if(curche!="empty")
                {
                    if(curche=="captain")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                if(!outside(i+k,j))
                                {
                                    string nxtcol=getcolor(i+k,j),nxtche=getchess(i+k,j);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i,j+k))
                                {
                                    string nxtcol=getcolor(i,j+k),nxtche=getchess(i,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                            }
                        }
                    }
                    else if(curche=="guard")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                if(!outside(i+k,j+k))
                                {
                                    string nxtcol=getcolor(i+k,j+k),nxtche=getchess(i+k,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i+k,j-k))
                                {
                                    string nxtcol=getcolor(i+k,j-k),nxtche=getchess(i+k,j-k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                            }
                        }
                    }
                    else if(curche=="elephant")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                for(int l=-1;l<=1;++l)
                                {
                                    if(l)
                                    {
                                        if(!outside(i+(k<<1),j+(l<<1))&&!exist(i+k,j+l))
                                        {
                                            string nxtcol=getcolor(i+(k<<1),j+(l<<1)),nxtche=getchess(i+(k<<1),j+(l<<1));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol; 
                                        }
                                    }
                                }
                            }
                        }
                    }
                    else if(curche=="horse")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                for(int l=-1;l<=1;++l)
                                {
                                    if(l)
                                    {
                                        if(!outside(i+(k<<1),j+l)&&!exist(i+k,j))
                                        {
                                            string nxtcol=getcolor(i+(k<<1),j+l),nxtche=getchess(i+(k<<1),j+l);
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                        if(!outside(i+k,j+(l<<1))&&!exist(i,j+l))
                                        {
                                            string nxtcol=getcolor(i+k,j+(l<<1)),nxtche=getchess(i+k,j+(l<<1));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                    }
                                }
                            }
                        }
                    }
                    else if(curche=="car")
                    {
                        for(int k=i;k<h;++k)
                        {
                            if(!outside(k,j))
                            {
                                string nxtcol=getcolor(k,j),nxtche=getchess(k,j);
                                if(nxtche!="empty")
                                {
                                    if(nxtche=="captain")    return nxtcol;
                                    break;
                                }
                            }
                        }
                        for(int l=j;l<w;++l)
                        {
                            if(!outside(i,l))
                            {
                                string nxtcol=getcolor(i,l),nxtche=getchess(i,l);
                                if(nxtche!="empty")
                                {
                                    if(nxtche=="captain")    return nxtcol;
                                    break;
                                }
                            }
                        }
                    }
                    else if(curche=="duck")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                for(int l=-1;l<=1;++l)
                                {
                                    if(l)
                                    {
                                        if(!outside(i+((k<<1)+k),j+(l<<1))&&!exist(i+(k<<1),j+l)&&!exist(i+k,j))
                                        {
                                            string nxtcol=getcolor(i+((k<<1)+k),j+(l<<1)),nxtche=getchess(i+((k<<1)+k),j+(l<<1));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                        if(!outside(i+(k<<1),j+((l<<1)+l))&&!exist(i+k,j+(l<<1))&&!exist(i,j+l))
                                        {
                                            string nxtcol=getcolor(i+(k<<1),j+((l<<1)+l)),nxtche=getchess(i+(k<<1),j+((l<<1)+l));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                    }
                                }
                            }
                        }
                    }
                    else if(curche=="soldier")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                if(!outside(i+k,j))
                                {
                                    string nxtcol=getcolor(i+k,j),nxtche=getchess(i+k,j);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i,j+k))
                                {
                                    string nxtcol=getcolor(i,j+k),nxtche=getchess(i,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i+k,j+k))
                                {
                                    string nxtcol=getcolor(i+k,j+k),nxtche=getchess(i+k,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i+k,j-k))
                                {
                                    string nxtcol=getcolor(i+k,j-k),nxtche=getchess(i+k,j-k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                            }
                        }
                    }
                }
            }
        }
        return "not";
    }
    bool checkove()
    /*
        result:
            0: the game isn't over
            1: the game is still alive
    */
    {
        bool red=0,blue=0;
        for(int i=0;i<h;++i)
        {
            for(int j=0;j<w;++j)
            {
                if(getchess(i,j)=="captain")
                {
//                    printf("[%d %d]\n",i,j);
                    if(getcolor(i,j)=="red")    red=1;
                    else    blue=1;
                }
            }
        }
        return !red||!blue;
    }
    void moving(int sx,int sy,int tx,int ty)
    {
        evemap[tx][ty]=evemap[sx][sy];
        evemap[sx][sy]="empty";
    }
    string final(string s)
    {
        if(s=="empty")    return "empty";
        else
        {
            for(int i=0;i<s.length();++i)
            {
                if(s[i]=='-')
                {
                    s[i]=' ';
                    break;
                }
            }
            return s;
        }
    }
    vector<string> movecaptain(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
//        printf("%s %s\n",getcolor(sx,sy).c_str(),color.c_str());
        if(over||!occaptain(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> moveguard(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocguard(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> moveelephant(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocelephant(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> movehorse(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ochorse(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> movecar(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!occar(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> moveduck(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocduck(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> movesoldier(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocsoldier(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> execute(int sx,int sy,int tx,int ty)
    {
        if(getchess(sx,sy)=="captain")    return movecaptain(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="guard")    return moveguard(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="elephant")    return moveelephant(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="horse")    return movehorse(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="car")    return movecar(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="duck")    return moveduck(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="soldier")    return movesoldier(sx,sy,tx,ty);
        else    return vector<string>({"Invalid command"});
    }
}redplay,blueplay;
void mapinitial()
{
    evemap.resize(20);
    static vector<string> zero({"red-car","red-horse","red-elephant","red-guard","red-captain","red-guard","red-elephant","red-horse","red-car"});
    static vector<string> one({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> two({"red-duck","empty","empty","empty","empty","empty","empty","empty","red-duck"});
    static vector<string> three({"red-soldier","empty","red-soldier","empty","red-soldier","empty","red-soldier","empty","red-soldier"});
    static vector<string> four({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> five({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> six({"blue-soldier","empty","blue-soldier","empty","blue-soldier","empty","blue-soldier","empty","blue-soldier"});
    static vector<string> seven({"blue-duck","empty","empty","empty","empty","empty","empty","empty","blue-duck"});
    static vector<string> eight({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> nine({"blue-car","blue-horse","blue-elephant","blue-guard","blue-captain","blue-guard","blue-elephant","blue-horse","blue-car"});
    evemap[0]=zero;
    evemap[1]=one;
    evemap[2]=two;
    evemap[3]=three;
    evemap[4]=four;
    evemap[5]=five;
    evemap[6]=six;
    evemap[7]=seven;
    evemap[8]=eight;
    evemap[9]=nine;
    for(int i=0;i<evemap.size();++i)    evemap[i].resize(20);
}
int main()
{
//     freopen("duck.in","r",stdin);
//    freopen("own.out","w",stdout);
    mapinitial();
    redplay.color="red";
    blueplay.color="blue";
    int q,now=1;
    scanf("%d",&q);
//    printmap();
    for(int i=1;i<=q;++i)
    {
        int sx,sy,tx,ty;
        scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
//        printf("{%d %d %d %d}\n",sx,sy,tx,ty);
        vector<string> ret;
        if(now&1)    ret=redplay.execute(sx,sy,tx,ty);
        else    ret=blueplay.execute(sx,sy,tx,ty);
        if(ret[0]=="Invalid command")    printf("Invalid command\n");
        else
        {
            printf("%s;%s;%s;%s\n",ret[0].c_str(),ret[1].c_str(),ret[2].c_str(),ret[3].c_str());
            if(ret[3]=="yes")    over=1;
            now++;
        }
//         if(i>=q-1)
//         printmap();
    }
    return 0;
}

这种东西怎么写啊。。。

Day 1（好像也没有 Day 2

到了 NK 后发现正好可以进门，于是就什么也没有检查的进去了。

进门前问了一下 LYC 之前问过的一个问题，他说没有头绪，然后就没怎么说话了。

在去考场的途中和大 LJS 瞎扯了一下 CF 的 bitmasks 瘤子题。

小 ljs 在考场外面等的时候问我 KMP 怎么打。（伏笔 x1

我告诉他没有关系，碰见全部哈希（伏笔 x2。

快要进门的时候发现 WXK、TR、高一正在互相进行仪式。

然后就没有什么了。

进了考场之后打开 Dev，把快读之类的东西打了打，果然还是不习惯辣么大个的 Enter。

右边的右边是 WXK，坐下时互相说了句：“好巧啊”，然后互相迷惑地做了一下 orz 动作。

左边的左边是 TLY，直接 yyds。

然后，然后就发题了嘛，打开看见文件夹里一个 string 我就知道事情不对。

此时尧姐的 flag 倒了：“今年考字符串、计数我把这个键盘夹着草稿纸吃了。”

打开 PDF，先用了整整半个小时通读了一下，感觉 T1、T2 简单题，T3、T4 只能骗。

于是乎细读了一下 T1，发现是个 DFS 模拟水题。（当时没有往拓扑想，不过反正都是对的）

然后花了半个小时的样子过完了所有大样例，还很 sb 地认为不会报 int。不过保险起见还是在代码开头和考场的草稿纸（指记事本 text.txt，事实上考场上的草稿纸质量太劣我没用）都写了一句 Beware of your LONG LONG 以提醒自己最后十五分钟再重新考虑会不会爆。

然后看 T2，想了大概五分钟出了一个翻过来枚举就是 $\Theta(n\ln n)$ 大众 84pts 的垃圾做法。

此时想起了 YHN 学长在暑假的时候讲的话：“在考场上有一个暴力就先打一个，可以在正解死亡时应急以及对拍。”

然后就开始打这个 伪·$\Theta(n^{2})$。然后打出了一个 180+ 行的垃圾。

T3 带 SPJ，此时教练的 flag 倒了：“NOIP 不会考带 SPJ 的东西，以后不要考了。”

T3 又是个构造，此时教练的 flag 又倒了：“NOIP 不会考构造，以后不要考了。”

到了后面就根本不想打正解了，只想着调自己的暴力。结果就是调到后面越调越慌，连改思路的想法都没有。

最后就改了个 T1 的 long long，什么也没有干。

于是，NOIP2020 成了至暗时刻。

出来考场后，我问 LYC T2 的复杂度，他说：“$\Theta(Tn\sqrt{n})$”。我当时就以为块 YC 打了个分块。

中午大家一起到某个不知名的地方吃了一个疑似火锅的东西。

桌子上小 ljs 跟我一样 T2 陷在 $\Theta(n^2)$ 潮流中，其他人都打了 84。

然后说着说着 LYC 发现自己 T1 读错了题（后来被证实是出题人语文差，自己也没考虑这些，于是读错题 没 有 关 系），蒙着发现自己也读错了。

然后就觉得，要完，这下没了（本来就没了好吧）。

本来大家都十分快乐的对着自己的答案，然后尧姐冒了一句：“大家不要对了，伤感情。”

于是 LYC 对着这个 T12 没对出错 T34 骗分稳健的人喊了一句：“对了半天没对出错，有优越感了是吧。”

十分奇妙的，本来大家都对吃没有什么兴趣，LYC 和 LJS 这两个饭量小的早就不吃了，结果 TR 点的虾滑来之后一个二个都站了起来。

感觉就这样了吧，NOIP2020 是灰色但打醒的。

Sol.

A 排水系统

找出所有的起点 DFS 即可，可以手动实现一个分数类。

/* Beware of your __INT128 */

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

namespace MySpace {
typedef long long LL;

const __int128 MAXN = 1e5 + 5, MAXS = 10 + 5, MAXE = 1e5 + 5;

__int128 rint () {
    __int128 x = 0, f = 1; char c = getchar ();
    for ( ; c < '0' || c > '9'; c = getchar () )    f = ( c == '-' ? -1 : f );
    for ( ; c >= '0' && c <= '9'; c = getchar () )    x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
    return x * f;
}

template<typename _T>
void wint ( _T x ) {
    if ( x < 0 )    putchar ( '-' ), x = ~ x + 1;
    if ( x > 9 )    wint ( x / 10 );
    putchar ( x % 10 + '0' );
}

__int128 calcGCD ( const __int128 a, const __int128 b ) ;
__int128 calcLCM ( const __int128 a, const __int128 b ) ;

struct GraphSet {
    __int128 to, nx;
    GraphSet ( __int128 T = 0, __int128 N = 0 ) { to = T, nx = N; }
} as[MAXN * 5 * 4];

struct Frac {
    __int128 one, ano;
    Frac ( __int128 O = 0, __int128 A = 0 ) { one = O, ano = A; }
} nds[MAXN];

__int128 n, stn, edn, bgn[MAXN], cnte, ind[MAXN], outd[MAXN], sts[MAXN], eds[MAXN], stnd, ednd, vis[MAXN];

void makeEdge ( const __int128 u, const __int128 v ) { as[++ cnte] = GraphSet ( v, bgn[u] ), bgn[u] = cnte; }
__int128 calcGCD ( const __int128 a, const __int128 b ) { return ! b ? a : calcGCD ( b, a % b ); }
__int128 calcLCM ( const __int128 a, const __int128 b ) { return ( ! a || ! b ) ? 0 : ( __int128 )a / calcGCD ( a, b ) * b; }
void getSimp ( Frac& fr ) { __int128 ret = calcGCD ( fr.one, fr.ano ); if ( ! ret )    fr = Frac (); else fr.one /= ret, fr.ano /= ret; }

void dfs ( const __int128 u ) {
    for ( __int128 i = bgn[u]; i; i = as[i].nx ) {
        __int128 v = as[i].to;
        Frac ad = Frac ( nds[u].one, nds[u].ano * outd[u] );
        getSimp ( ad );
        __int128 ret = calcLCM ( ad.ano, nds[v].ano );
        if ( ! ret )    nds[v] = ad, dfs ( v );
        else {
            __int128 ads = ret / ad.ano, us = ret / nds[v].ano;
            ad.one *= ads, ad.ano *= ads;
            nds[v].one *= us, nds[v].ano *= us;
            nds[v].one += ad.one;
            getSimp ( nds[v] );
            dfs ( v );
        }
    }
    if ( bgn[u] )    nds[u] = Frac ();
}

void Main () {
    n = rint (), stn = rint ();
    for ( __int128 i = 1; i <= n; ++ i ) {
        __int128 eg = rint ();
        for ( __int128 j = 1; j <= eg; ++ j ) {
            __int128 to = rint ();
            makeEdge ( i, to );
            ind[to] ++, outd[i] ++;
        }
    }
    for ( __int128 i = 1; i <= n; ++ i ) {
        if ( ! ind[i] )    sts[++ stnd] = i;
        if ( ! outd[i] )    eds[++ ednd] = i;
    }
    for ( __int128 i = 1; i <= stnd; ++ i )    nds[sts[i]].one = nds[sts[i]].ano = 1;
    sort ( eds + 1, eds + 1 + ednd );
    for ( __int128 i = 1; i <= stnd; ++ i )    dfs ( i );
    for ( __int128 i = 1; i <= ednd; ++ i )    wint ( nds[eds[i]].one ), putchar ( ' ' ), wint ( nds[eds[i]].ano ), putchar ( '\n' );
}
}

int main () {
//    freopen ( "water.in", "r", stdin );
//    freopen ( "water.out", "w", stdout );
    MySpace :: Main ();
    return 0;
}

B 字符串匹配

这里是 $\Theta(Tn\ln n+26Tn)$，我 yy 出来的一个 $\Theta(n\ln n+Tn)$ 的做法由于太过繁杂不想想了。

首先枚举 $AB$ 即循环节，然后挨个往后面跳记个数就好了。

#include <cstdio>
#include <cstring>

namespace mySpace {
typedef long long LL;

const int KEY = 1331;
const int MAXN = ( 1 << 20 ) + 5;

int mul ( const LL a, const LL b, const int p ) { return a * b % p; }
int add ( const int a, const int b, const int p ) { return ( a + b ) < p ? ( a + b ) : ( a + b - p ); }
int sub ( const int a, const int b, const int p ) { return ( a - b ) < 0 ? ( a - b + p ) : ( a - b ); }
struct Value {
    static const int onemod = 19260817, anomod = 998244353;
    int p, q;
    Value () : p ( 0 ), q ( 0 ) {}
    Value ( const int x ) : p ( x ), q ( x ) {}
    Value ( const int a, const int b ) : p ( a ), q ( b ) {}
    Value operator * ( const Value &other ) const { return Value ( mul ( p, other.p, onemod ), mul ( q, other.q, anomod ) ); }
    Value operator + ( const Value &other ) const { return Value ( add ( p, other.p, onemod ), add ( q, other.q, anomod ) ); }
    Value operator - ( const Value &other ) const { return Value ( sub ( p, other.p, onemod ), sub ( q, other.q, anomod ) ); }
    bool operator == ( const Value &other ) const { return p == other.p && q == other.q; }
    bool operator != ( const Value &other ) const { return ! ( Value ( p, q ) == other ); }
} pwr[MAXN], has[MAXN];

int n, mps[MAXN], buc[MAXN][26], suf[MAXN];
char str[MAXN];

void initial () {
    scanf ( "%s", str + 1 ), n = strlen ( str + 1 );
    for ( int i = 1; i <= n; ++ i )    mps[i] = str[i] - 'a';
    bool tmp[26] = {}; int cur = 0;
    for ( int i = 1; i <= n; ++ i ) {
        has[i] = has[i - 1] * KEY + mps[i];
        memcpy ( buc[i], buc[i - 1], sizeof ( int ) * 26 );
        tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1;
        for ( int j = cur; j < 26; ++ j )    buc[i][j] ++;
    }
    memset ( tmp, 0, sizeof ( tmp ) ), cur = 0;
    for ( int i = n; i; -- i )    tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1, suf[i] = cur;
}

Value calcHS ( const int l, const int r ) { return has[r] - has[l - 1] * pwr[r - l + 1]; }
void solve () {
    initial (); LL ans = 0;
    for ( int len = 2; len < n; ++ len ) {
        Value tmp = calcHS ( 1, len );
        for ( int nxt = len; nxt < n; nxt += len ) {
            if ( calcHS ( nxt - len + 1, nxt ) != tmp )    break;
            ans += buc[len - 1][suf[nxt + 1]];
        }
    }
    printf ( "%lld\n", ans );
}

void main () {
    pwr[0] = 1;
    for ( int i = 1; i <= MAXN - 5; ++ i )    pwr[i] = pwr[i - 1] * KEY;
    int TC; scanf ( "%d", &TC );
    while ( TC -- > 0 )    solve ();
}
}

int main () {
//    freopen ( "string.in", "r", stdin );
//    freopen ( "string.out", "w", stdout );
    mySpace :: main ();
    return 0;
}

C 移球游戏

首先肯定这是 $n$ 个栈。先看 $n=2$ 的部分分。

这种情况只有黑白两色。

设 $1$ 柱有 $b$ （总共）个黑棋，有 $w$ 个白棋，把 $2$ 柱上 $b$ 个棋子放到 $3$ 柱上，然后重复：

• 把 $1$ 柱顶部所有黑棋放到 $2$ 柱上。
• 然后把 $1$ 柱上所有白棋放到 $3$ 柱。

直到 $1$ 柱为空。

然后把 $3$ 柱上面本属于 $1$ 柱的白棋放回去，又把 $2$ 柱上面的 $b$ 个黑棋放到 $1$ 柱去。

于是乎现在 $1$ 柱的情况大概是这样的：

假设原本是这样的：

$$ \begin{aligned} &\texttt{W W B W W B W W B B B} \\ &\texttt{W B W B B B W B W B W} \end{aligned} $$

那么现在移完后是这样：

$$ \begin{aligned} &\texttt{W W W W W W B B B B B} \\ &\texttt{W B W B B B} \\ &\texttt{W B W B W} \end{aligned} $$

然后我们把此时 $2$ 柱上的棋子全部放到 $3$ 柱上去，然后就划分一下就完了。

后面的事情就简单了，当 $n>2$ 的时候打个分治，一半一半划分染色，然后按着按着整理。

（代码和 CQ 队长 jiangly 对拍过，不过莫名奇妙就变成了基因比照，于是代码就基本变成了 jiangly 的）

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

namespace mySpace {
const int MAXN = 50 + 5, MAXM = 400 + 5, MAXK = 820000 + 5;

int rint () {
    int x = 0, f = 1; char c = getchar ();
    for ( ; c < '0' || c > '9'; c = getchar () )    f = c == '-' ? -1 : f;
    for ( ; c >= '0' && c <= '9'; c = getchar () )    x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
    return x * f;
}

template<typename _T>
void wint ( _T x ) {
    if ( x < 0 )    putchar ( '-' ), x = ~ x + 1;
    if ( x > 9 )    wint ( x / 10 );
    putchar ( x % 10 ^ '0' );
}

struct Stack {
private:
    int stk[MAXM], _top;
public:
    Stack () { memset ( stk, 0, sizeof ( stk ) ), _top = 0; }
    void push ( const int val ) { stk[_top ++] = val; }
    void pop () { if ( _top )    _top --; }
    int at ( const int pos ) { return stk[pos]; }
    int top () { return stk[_top - 1]; }
    int size () { return _top; }
    bool empty () { return _top < 0; }
    void debug ( char c = ' ' ) {
        putchar ( '[' );
        for ( int i = 0; i < _top; ++ i )    printf ( "%d ", stk[i] );
        printf ( "]%c", c ) ;
    }
} clr[MAXN];

struct Answer {
    int one, ano;
    Answer ( int O = 0, int A = 0 ) { one = O, ano = A; }
} ans[MAXK];

int n, m, cnt;

void trans ( const int one, const int ano ) {
    clr[ano].push ( clr[one].top () );
    clr[one].pop ();
    ans[cnt ++] = Answer ( one, ano );
}

void solve ( const int l, const int r, const vector<int>& col ) {
    if ( r - l == 1 )    return;
    int mid = ( l + r ) >> 1;
    int lst = col[0];
    vector<int> onevec, anovec;
    for ( int i = 1; i < r - l; ++ i ) {
        int one = lst, ano = col[i], cnt = 0;
        for ( int j = 0; j < m; ++ j ) {
            if ( clr[one].at ( j ) < mid )    ++ cnt;
        }
        for ( int j = 0; j < cnt; ++ j )    trans ( ano, n );
        for ( int j = m - 1; ~ j; -- j ) {
            if ( clr[one].at ( j ) < mid )    trans ( one, ano );
            else    trans ( one, n );
        }
        for ( int j = 0; j < m - cnt; ++ j )    trans ( n, one );
        for ( int j = 0; j < cnt; ++ j )    trans ( ano, one );
        for ( int j = 0; j < m - cnt; ++ j )    trans ( ano, n );
        for ( int j = 0; j < cnt; ++ j )    trans ( one, ano );
        for ( int j = m - 1; ~ j; -- j ) {
            if ( clr[ano].size () < m && ( clr[n].at ( j ) < mid || clr[one].size () == m ) )    trans ( n, ano );
            else    trans ( n, one );
        }
        bool was = 0;
        for ( int j = 0; j < m; ++ j ) {
            if ( clr[ano].at ( j ) >= mid )    was = 1;
        }
        if ( was )    anovec.push_back ( one ), lst = ano;
        else    onevec.push_back ( ano ), lst = one;
    }
    if ( clr[lst].at ( 0 ) < mid )    onevec.push_back ( lst );
    else    anovec.push_back ( lst );
    solve ( l, mid, onevec ), solve ( mid, r, anovec );
}

void main () {
    n = rint (), m = rint ();
    for ( int i = 0; i < n; ++ i ) {
        for ( int j = 0; j < m; ++ j )    clr[i].push ( rint () - 1 );
    }
    vector<int> col;
    for ( int i = 0; i < n; ++ i )    col.push_back ( i );
    solve ( 0, n, col );
    wint ( cnt ), putchar ( '\n' );
    for ( int i = 0; i < cnt; ++ i ) {
        wint ( ans[i].one + 1 ), putchar ( ' ' );
        wint ( ans[i].ano + 1 ), putchar ( '\n' );
    }
}
}

int main () {
//    freopen ( "ball.in", "r", stdin );
//    freopen ( "ball.out", "w", stdout );
    mySpace :: main ();
    return 0;
}

Problem. 1 Junior - Thinking

Desc. & Link.

注意到值域乘范围刚好能过。

然后就存两个桶即可。。。（数组开小飞了半天才调出来。。。）

Problem. 2 Junior / Senior - Thinking

Desc. & Link.

考虑一次反转后对整个序列造成的影响。

每次操作相当于把整个序列分成了 $2^{n-q}$ 个块，我们只需要考虑块内和块外。

考虑一个块对其他块的情况。

嗯。

没有影响，完。

那么我们只需要考虑如何快速计算出每个块内的变化即可。

像归并排序一样考虑问题，把序列分成 $n$ 层（把二叉树画出来）。

要反转区间 $[l,r]$ 就要翻转 $[l,m],[m+1,r],m=\lfloor\frac{l+r}{2}\rfloor$，以此类推。

然后就预处理出每一层顺序对逆序对即可。

Problem. 3 Junior / Senior - Thinking

首先否决往大了想。

我们首先可以通过背包算出所有能够组成的值。

然后不会了。

Problem. 1 - Junior Julian

模拟模拟模拟摸死 CTR 的母。

考场代码：

#include<cstdio>
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
int Q;
int chkyearG(int mon) // 1:run 0:ping
{
    if(((mon%4==0)&&(mon%100!=0))||(mon%400==0))    return 1;
    else    return 0;
}
int chkyearJ(int mon) // 1:run 0:ping
{
    if(mon%4==0)    return 1;
    else    return 0;
}
int chkmontG(int mon,int yea) // 31: big,30: small,28/29: 2
{
    if(yea<0)    yea=-yea,yea--;
    if(mon==1||mon==3||mon==5||mon==7||mon==8||mon==10||mon==12)    return 31;
    else if(mon!=2)    return 30;
    else
    {
        if(chkyearG(yea))    return 29;
        else    return 28;
    }
}
int chkmontJ(int mon,int yea) // 31: big,30: small,28/29: 2
{
    if(yea<0)    yea=-yea,yea--;
    if(mon==1||mon==3||mon==5||mon==7||mon==8||mon==10||mon==12)    return 31;
    else if(mon!=2)    return 30;
    else
    {
        if(chkyearJ(yea))    return 29;
        else    return 28;
    }
}
void Main()
{
    read(Q);
    while(Q--)
    {
        int r;
        read(r);
        int days=1,months=1,years=-4713;
        int flag=0; // 0:Julian,1:Gregorian
        while(true)
        {
            if(years==0)    years=1;
            if(days==1&&months==10&&years==1582)
            {
                if(r<=3)
                {
                    days+=r;
                    break;
                }
                else if(r>3&&r<20)
                {
                    days+=3;
                    r-=3;
                    days=15;
                    days+=r;
                    break;
                }
                else
                {
                    flag=1;
                    days=1;
                    r-=21;
                    months++;
                }
            }
            if(days+r<=(flag?chkmontG(months,years):chkmontJ(months,years)))
            {
                days+=r;
                break;
            }
            days=1;
            r-=(flag?chkmontG(months,years):chkmontJ(months,years));
            months++;
            if(months==13)    months=1,years++;
        }
        if(years>0)    printf("%d %d %d\n",days,months,years);
        else    printf("%d %d %d BC\n",days,months,-years);
    }
}
}
int main()
{
//    freopen("D:/csp-s(windows)/julian/julian3.in","r",stdin);
//    freopen("D:/my.out","w",stdout);
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
    solveIt::Main();
    return 0;
}
/*
There are 365 days in a ping year.
There are 366 days in a run year.
There are 4714 ping years in -4713(BC) to 1582
There are 1582 run years in -4713(BC) to 1582
There are 2299622 days in -4713(BC) to 1582
There are 3571 ping years BC
There are 1142 yun years BC
There are 1721387 days in BC
*/

下来重写：

#include <cstdio>

typedef long long LL;

template<typename _T>
void read( _T &x ){
    x = 0; char c = getchar( ); _T f = 1;
    while( c < '0' || c > '9' ){ if( c == '-' )    f = -1; c = getchar( ); }
    while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar(); }
    x *= f;
}

template<typename _T>
void write( _T x ){
    if( x < 0 ){ putchar( '-' ); x = -x; }
    if( x > 9 )    write( x / 10 );
    putchar( x % 10 + '0' );
}

int MonthDays( int x ){
    if( x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12 )    return 31;
    else if( x == 2 )    return 28;
    else    return 30;
}

bool checkRJ( int x ){ return ! ( x % 4 ); }
bool checkRG( int x ){ return ( ( ! ( x % 4 ) ) && ( x % 100 ) ) || ( ! ( x % 400 ) ); }

int Q;

void GetData( LL& dBC, LL& dAJ, LL& dAG, LL& dFK ){
    for( int i = 4712; ~ i; -- i )  dBC += 365 + checkRJ( i );
    dAJ = dBC; dAG = dBC;
    for( int i = 1; i <= 1581; ++ i )    dAJ += 365 + checkRJ( i );
    for( int i = 1; i <= 1582; ++ i )    dAG += 365 + checkRG( i );
    dFK = dAJ + 365;
    for( int i = 1; i <= 9; ++ i )  dAJ += MonthDays( i );
    dAJ += 4;
}

int fuckCTR( int x, int y ){
    if( y < 0 )    ++ y;
    if( x != 2 )    return MonthDays( x );
    if( y <= 1582 ) return MonthDays( x ) + checkRJ( y );
    else    return MonthDays( x ) + checkRG( y );
}

int main( ){
    LL dBC = 0, dAJ = 0, dAG = 0, dFK = 0;
    /*
     * several key time frame:
     * 4713.1.1
     * 1582.10.5~14 ( don't exist )
     * 1582.10.4 Julian Calendar has been fucked
     * 1582.10.15 Gregorian Calendar has been implemented
     * dBC - 1.1.1 (Julian Day)
     * dAJ - 1582.10.15 (Julian Day)
     * dFK - 1583.1.1 (Imagine that the fucking 10 days exist)
     * dAG - 1583.1.1 (the fucking 10 days don't exist(the fucking problem's description))
    */
    GetData( dBC, dAJ, dAG, dFK );
    read( Q ); while( Q -- > 0 ){
        LL R; read( R );
        if( R < dBC ){
            int years = 4713 - R / ( 365 * 4 + 1 ) * 4; R %= ( 365 * 4 + 1 );
            if( R >= 366 ){
            R -= 366; years --;
            if( R >= 365 ){ R -= 365; years --; }
            if( R >= 365 ){ R -= 365; years --; }
            }
            int months = 1;
            while( R - fuckCTR( months, -years ) >= 0 ){ R -= fuckCTR( months, -years ); months ++; }
            int days = R + 1;
            printf( "%d %d %d BC\n", days, months, years );
            continue;
        }
        if( R >= dAJ )    R += 10;
        if( R >= dBC && R < dFK ){
            R -= dBC;
            int years = R / ( 365 * 4 + 1 ) * 4 + 1; R %= ( 365 * 4 + 1 );
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            int months = 1;
            while( R - fuckCTR( months, years ) >= 0 ){ R -= fuckCTR( months, years ); months ++; }
            int days = R + 1;
            printf( "%d %d %d\n", days, months, years );
            continue;
        }
        if( R >= dFK ){
            R -= dBC; R += dAG - dFK;
            int years = R / ( 365 * 400 + 24 * 4 + 1 ) * 400 + 1; R %= ( 365 * 400 + 24 * 4 + 1 );
            if( R >= 365 * 100 + 24 ){ R -= 365 * 100 + 24; years += 100; }
            if( R >= 365 * 100 + 24 ){ R -= 365 * 100 + 24; years += 100; }
            if( R >= 365 * 100 + 24 ){ R -= 365 * 100 + 24; years += 100; }
            years += R / ( 365 * 4 + 1 ) * 4; R %= ( 365 * 4 + 1 );
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            int months = 1;
            while( R - fuckCTR( months, years ) >= 0 ){ R -= fuckCTR( months, years ); months ++; }
            int days = R + 1;
            printf( "%d %d %d\n", days, months, years );
        }
    }
    return 0;
}

码风飞跃的变化

Problem. 2 - Junior Zoo

把所有数或起来，然后计算需要买哪些饲料，然后统计 $1\texttt{ to }k$ 有哪些位没有被买，记为 $C$ 然后答案就是 $2^{C}-n$。

考场代码：

#include<cstdio>
#include<vector>
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
const int MAXN=1e6+5;
int n,m,c,k,a[MAXN],vis[MAXN],fuc[MAXN];
struct ask
{
    int w,s;
    ask(int W=0,int S=0){w=W;s=S;}
}as[MAXN];
void Main()
{
    read(n),read(m),read(c),read(k);
    for(int i=1;i<=n;++i)    read(a[i]),fuc[a[i]]=1;
    for(int i=1;i<=m;++i)    read(as[i].w),read(as[i].s);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
//            printf("FU ");for(int i=1;i<=c;++i)    printf("%d ",vis[i]); puts("");
            if((a[i]>>as[j].w)&1)    vis[as[j].s]=1;//,printf("%d %d %d\n",a[i],as[j].w,as[j].s);
        }
    }
//    for(int i=1;i<=c;++i)    write(vis[i]),putchar(' '),write(i),putchar('\n');
    int up=(1<<k),ans=0;
    for(int s=0;s<up;++s)
    {
        if(fuc[s])    continue;
        bool flag=0,book=0;
        for(int i=1;i<=m;++i)
        {
            if((s>>as[i].w)&1)
            {
                flag=1;
                if(!vis[as[i].s])    book=1;
            }
            if(book)    break;
        }
        if(!flag)    ans++;
        else if(!book)    ans++;
    }
    write(ans);
}
}
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    solveIt::Main();
    return 0;
}

下来改的：

#include<cstdio>
#include<algorithm>
using namespace std;
namespace solveIt
{
typedef unsigned long long ULL;
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void readull(ULL &x)
{
    x=0;
    char c=getchar();
    ULL f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
void writeull(ULL x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    writeull(x/10);
    putchar(x%10+'0');
}
const int MAXN=1e6+5;
int n,m,c,k,len;
ULL a[MAXN],all,pri[MAXN];
bool fuc[70],buc[MAXN];
struct ask
{
    int w,s;
    ask(int W=0,int S=0){w=W;s=S;}
}as[MAXN];
void Main()
{
    read(n),read(m),read(c),read(k);
    for(int i=1;i<=n;++i)
    {
        readull(a[i]);
        all|=a[i];
    }
    for(int i=1;i<=m;++i)
    {
        read(as[i].w);
        read(as[i].s);
        pri[i]=as[i].s;
    }
    sort(pri+1,pri+1+m);
    len=unique(pri+1,pri+1+m)-pri-1;
    for(int i=1;i<=m;++i)    as[i].s=lower_bound(pri+1,pri+1+len,as[i].s)-pri;
    for(int i=1;i<=m;++i)
    {
        if((all>>as[i].w)&1)    buc[as[i].s]=1;
    }
    for(int i=1;i<=m;++i)
    {
        if(!buc[as[i].s])    fuc[as[i].w]=1;
    }
    int tot=0;
    for(int i=0;i<k;++i)
    {
        if(!fuc[i])    ++tot;
    }
    if(tot==64)
    {
        if(n==0)    puts("18446744073709551616");
        else
        {
            ULL ans=0,two=1;
            for(int i=1;i<=63;++i)    two<<=1;
            ans+=two;
            ans-=n;
            ans+=two;
            writeull(ans);
        }
    }
    else    writeull((1ull<<tot)-n);
}
}
int main()
{
    // freopen("zoo.in","r",stdin);
    // freopen("zoo.out","w",stdout);
    solveIt::Main();
    return 0;
}

Problem. 3 - Senior Call

这儿

考场代码： （Loneliness）

下来改的：

#include <queue>
#include <cstdio>
#define mod ( 998244353 )

using namespace std;
typedef long long LL;

const int MAXN = 1e6 + 5;

template<typename _T>
void read( _T &x ){
    x = 0; char c = getchar(); _T f = 1;
    while( c < '0' || c > '9' ){ if( c == '-' )    f = -1; c = getchar(); }
    while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar(); }
    x *= f;
}

template<typename _T>
void write( _T x ){
    if( x < 0 ){ putchar( '-' ); x = -x; }
    if( x > 9 )    write( x / 10 );
    putchar( x % 10 + '0' );
}

struct starS{
    int to, nxt;
    starS( int T = 0, int N = 0 ){ to = T; nxt = N; }
} as[MAXN * 2];

struct operateS{
    int Tp, pos;
    LL add, mul, sum;
    operateS( int T = 0, int P = 0, LL A = 0, LL M = 0, LL S = 0 ){ Tp = T; pos = P; add = A; mul = M; sum = S; }
} opS[MAXN];

int N, M, Q;
int totE, totT;
int A[MAXN], topS[MAXN], degS[MAXN], firS[MAXN], queS[MAXN];

void pushEdge( int u, int v ){ as[++ totE] = starS( v, firS[u] ); firS[u] = totE; }

void TopSort( ){
    queue<int> align;
    for( int i = 1; i <= M; ++ i ){
        if( ! degS[i] )    align.push( i );
    }
    while( ! align.empty( ) ){
        int u = align.front( ); align.pop( );
        topS[++ totT] = u;
        for( int i = firS[u]; i; i = as[i].nxt ){
            int v = as[i].to; degS[v] --;
            if( ! degS[v] ) align.push( v );
        }
    }
}

int main( ){
    read( N );
    for( int i = 1; i <= N; ++ i )  read( A[i] );
    read( M );
    for( int i = 1; i <= M; ++ i ){
        read( opS[i].Tp );
        if( opS[i].Tp == 1 ){
            read( opS[i].pos ); read( opS[i].add );
            opS[i].mul = 1;
        }
        else if( opS[i].Tp == 2 ) {
            read( opS[i].mul );
            opS[i].add = opS[i].mul;
        }
        else{
            read( opS[i].pos );
            opS[i].mul = 1;
            for( int j = 1, to; j <= opS[i].pos; ++ j ){ read( to ); pushEdge( i, to ); degS[to] ++; }
        }
    }
    TopSort( );
    for( int i = M; i; -- i ){
        int u = topS[i];
        for( int j = firS[u]; j; j = as[j].nxt ){
            int v = as[j].to;
            opS[u].mul = ( LL )opS[u].mul * opS[v].mul % mod;
        }
    }
    read( Q ); int now = 1;
    for( int i = 1; i <= Q; ++ i )  read( queS[i] );
    for( int i = Q; i; -- i ){ opS[queS[i]].sum = ( ( LL )opS[queS[i]].sum + now ) % mod; now = ( LL )now * opS[queS[i]].mul % mod; }
    for( int i = 1; i <= M; ++ i ){
        int u = topS[i], now = 1;
        for( int j = firS[u]; j; j = as[j].nxt ){
            int v = as[j].to;
            opS[v].sum = ( ( LL )opS[u].sum * now % mod + opS[v].sum ) % mod;
            now = ( LL )now * opS[v].mul % mod;
        }
    }
    for( int i = 1; i <= N; ++ i )  A[i] = ( LL )A[i] * now % mod;
        for( int i = 1; i <= M; ++ i ){
        if( opS[i].Tp == 1 )    A[opS[i].pos] = ( A[opS[i].pos] + ( LL )opS[i].add * opS[i].sum % mod ) % mod;
    }
    for( int i = 1; i <= N; ++ i )  write( A[i] ), putchar( ' ' );
    return 0;
}

Problem. 4 - Senior Snakes

先讲个 $\texttt{70pts}$ 的做法。没脑子吃，然后回来判断。所有大样例有些多一的代码改一下就有。

正解应该就是利用序列单调性把 $\texttt{70pts}$ 的暴力的线段树改成其他的东西。

目前还没做出来，可以欣赏一下我考场的 186 行 SGST（含义见代码）。

考场代码：

（upd：这份代码下面是 $\texttt{70pts}$ 的代码：）

#include<cstdio>
#include<algorithm>
using namespace std;
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
struct node
{
    int val,pos;
    node(int V=0,int P=0)
    {
        val=V;
        pos=P;
    }
    bool operator<(const node&ano)const
    {
        if(val==ano.val)    return pos<ano.pos;
        else    return val<ano.val;
    }
};
const int MAXN=1e6+6;
int n,a[MAXN];
struct TREE
{
node mnx[MAXN*4],mxx[MAXN*4];
void upd(int x)
{
    mnx[x]=min(mnx[x<<1],mnx[x<<1|1]);
    mxx[x]=max(mxx[x<<1],mxx[x<<1|1]);
}
void build(int x,int l,int r)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        upd(x);
    }
    else
    {
        mnx[x]=node(a[l],l);
        mxx[x]=node(a[l],l);
    }
}
void ins(int x,int l,int r,int pos,int val)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        if(mid>=pos)    ins(x<<1,l,mid,pos,val);
        else    ins(x<<1|1,mid+1,r,pos,val);
        upd(x);
    }
    else
    {
        mnx[x].val+=val;
        mxx[x].val+=val;
    }
}
node findmin(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)    return 1e9;
    if(l>=fr&&r<=ba)    return mnx[x];
    else
    {
        int mid=(l+r)>>1;
        return min(findmin(x<<1,l,mid,fr,ba),findmin(x<<1|1,mid+1,r,fr,ba));
    }
}
node findmax(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)    return 0;
    if(l>=fr&&r<=ba)    return mxx[x];
    else
    {
        int mid=(l+r)>>1;
        return max(findmax(x<<1,l,mid,fr,ba),findmax(x<<1|1,mid+1,r,fr,ba));
    }
}
} tmx,tmn;
void Main()
{
    int t;
    read(t);
    int flag=1;
    while(t--)
    {
        read(n);
        if(flag==1)
        {
            for(int i=1;i<=n;++i)    read(a[i]);
            flag=0;
        }
        else
        {
            for(int i=1,p,v;i<=n;++i)
            {
                read(p);
                read(v);
                int tmxv=tmx.findmax(1,1,n,p,p).val;
                int tmnv=tmn.findmin(1,1,n,p,p).val;
                tmx.ins(1,1,n,p,-tmxv);
                tmx.ins(1,1,n,p,v);
                tmn.ins(1,1,n,p,-tmnv);
                tmn.ins(1,1,n,p,v);
            }
            for(int i=1;i<=n;++i)    a[i]=tmx.findmax(1,1,n,i,i).val;
//            for(int i=1;i<=n;++i)    write(a[i]),putchar(' '); puts("");
        }
        tmx.build(1,1,n);
        tmn.build(1,1,n);
        int ans=n;
        while(true)
        {
            node nowmax=tmx.findmax(1,1,n,1,n);
            tmx.ins(1,1,n,nowmax.pos,-nowmax.val);
            node secmax=tmx.findmax(1,1,n,1,n);
            tmx.ins(1,1,n,nowmax.pos,nowmax.val);
            
            node nowmin=tmn.findmin(1,1,n,1,n);
            tmn.ins(1,1,n,nowmin.pos,-nowmin.val+1e9);
            node secmin=tmn.findmin(1,1,n,1,n);
            tmn.ins(1,1,n,nowmin.pos,nowmin.val-1e9);
//            printf("nmx=(%d %d),nmn=(%d %d),smx=(%d %d),smn(%d %d)\n",nowmax.pos,nowmax.val,
//                nowmin.pos,nowmin.val,secmax.pos,secmax.val,secmin.pos,secmin.val);
            if(((nowmax.val-nowmin.val<secmin.val)
                &&((nowmax.val-nowmin.val>secmax.val)
                    ||(nowmax.val-nowmin.val==secmax.val&&nowmax.pos>secmax.pos)))
                ||(((nowmax.val-nowmin.val==secmin.val)&&(nowmax.pos<secmin.val))
                    &&((nowmax.val-nowmin.val>secmax.val)
                        ||((nowmax.val-nowmin.val==secmax.val)&&(nowmax.pos>secmax.pos))))
                ||(nowmax.val-nowmin.val>secmin.val)
                ||((nowmax.val-nowmin.val==secmin.val)&&(nowmax.pos>secmin.pos)))
            {
                tmn.ins(1,1,n,nowmax.pos,-nowmin.val);
                tmn.ins(1,1,n,nowmin.pos,-nowmin.val+1e9);
                tmx.ins(1,1,n,nowmax.pos,-nowmin.val);
                tmx.ins(1,1,n,nowmin.pos,-nowmin.val);
                ans--;
            }
            else    break;
        }
        write(ans);
        putchar('\n');
    }
}
}
int main()
{
//    freopen("D:/csp-s(windows)/snakes/snakes3.in","r",stdin);
    freopen("snakes.in","r",stdin);
    freopen("snakes.out","w",stdout);
    solveIt::Main();
    return 0;
}
/*
SGST - Strong-Guy Segment Tree
*/

$\texttt{70pts}$

#include<cstdio>
#include<algorithm>
using namespace std;
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')  f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct node
{
    int val,pos;
    node(int V=0,int P=0)
    {
        val=V;
        pos=P;
    }
    bool operator<(const node&ano)const
    {
        if(val==ano.val)    return pos<ano.pos;
        else    return val<ano.val;
    }
};
const int MAXN=1e6+6;
int n,ans,a[MAXN];
struct TREE
{
node mnx[MAXN*4],mxx[MAXN*4];
int siz,tp;
TREE()
{
    siz=0;
}
void upd(int x)
{
    mnx[x]=min(mnx[x<<1],mnx[x<<1|1]);
    mxx[x]=max(mxx[x<<1],mxx[x<<1|1]);
}
void build(int x,int l,int r)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        upd(x);
    }
    else
    {
        mnx[x]=node(a[l],l);
        mxx[x]=node(a[l],l);
    }
}
void ins(int x,int l,int r,int pos,int val)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        if(mid>=pos)    ins(x<<1,l,mid,pos,val);
        else    ins(x<<1|1,mid+1,r,pos,val);
        upd(x);
    }
    else
    {
        mnx[x].val+=val;
        mxx[x].val+=val;
    }
}
node findmin(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)  return 1e9;
    if(l>=fr&&r<=ba)    return mnx[x];
    else
    {
        int mid=(l+r)>>1;
        return min(findmin(x<<1,l,mid,fr,ba),findmin(x<<1|1,mid+1,r,fr,ba));
    }
}
node findmax(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)  return 0;
    if(l>=fr&&r<=ba)    return mxx[x];
    else
    {
        int mid=(l+r)>>1;
        return max(findmax(x<<1,l,mid,fr,ba),findmax(x<<1|1,mid+1,r,fr,ba));
    }
}
void del(node one)
{
    if(tp==1)    ins(1,1,n,one.pos,-one.val);
    else    ins(1,1,n,one.pos,-one.val+1e9);
    siz--;
}
void buildemp(int f,int n)
{
    build(1,1,n);
    siz=n;
    tp=f;
}
};
struct treetoheap
{
TREE tmx,tmn;
node findmax(int l,int r)
{
    return tmx.findmax(1,1,n,l,r);
}
node findmin(int l,int r)
{
    return tmn.findmin(1,1,n,l,r);
}
void ins(node one)
{
    tmx.siz++;
    tmn.siz++;
    tmx.ins(1,1,n,one.pos,one.val);
    if(tmn.findmin(1,1,n,one.pos,one.pos).val==(int)1e9)    tmn.ins(1,1,n,one.pos,one.val-1e9);
    else    tmn.ins(1,1,n,one.pos,one.val);
}
void del(node one)
{
    tmx.del(one);
    tmn.del(one);
}
void buildemp(int n)
{
    tmx.buildemp(1,n);
    tmn.buildemp(0,n);
}
int siz()
{
    return tmx.siz;
}
} wer;
bool dfs()
{
    if(wer.siz()==2)    return 1;
    int f=0;
    while(wer.siz()>=3)
    {
        int siz=wer.siz();
        node nowmin=wer.findmin(1,n),nowmax=wer.findmax(1,n);
        wer.del(nowmin);
        wer.del(nowmax);
        node secmin=wer.findmin(1,n);
        wer.ins(node(nowmax.val-nowmin.val,nowmax.pos));
//        puts("\n/********************************************/");
//        printf("(%d %d %d)\n",secmin.val,secmin.pos,wer.siz());
//        for(int i=1;i<=n;++i)    printf("%d ",wer.findmax(i,i).val);puts("");
//        puts("/********************************************/\n");
        if(nowmax.val-nowmin.val<secmin.val)
        {
            if(!dfs())
            {
                ans=siz-1;
                return 1;
            }
            else if(f)
            {
                ans=siz;
                return 1;
            }
            else
            {
                ans=siz;
                return 0;
            }
        }
        ++f;
    }
    ans=1;
    return 1;
}
void Main()
{
    int t;
    read(t);
    int flag=1;
    while(t--)
    {
        if(flag==1)
        {
            read(n);
            for(int i=1;i<=n;++i)   read(a[i]);
            flag=0;
        }
        else
        {
            int tmp;
            read(tmp);
            for(int i=1,p,v;i<=tmp;++i)
            {
                read(p);
                read(v);
                a[p]=v;
            }
        }
        if(n==3)
        {
            if(a[1]+a[2]<=a[3])    puts("1");
            else    puts("3");
            continue;
        }
        wer.buildemp(n);
        ans=n;
        bool WASTED=dfs();
        write(ans);
        putchar('\n');
        WASTED=!WASTED;
    }
}
}
int main()
{
//    freopen("snakes/snakes4.in","r",stdin);
//    freopen("snakes/fuck.out","w",stdout);
//    freopen("snakes.in","r",stdin);
//    freopen("snakes.out","w",stdout);
    solveIt::Main();
    return 0;
}
/*
SGST - Strong-Guy Segment Tree
*/