军训时期抓紧补。

直到上课一周才补完，大学生活真的太忙了/ll

[1001 NJU emulator]

solution

题面：维护一个栈，有八种操作：加入一个 至栈顶；复制栈顶元素至栈顶；删除栈顶元素；交换栈最上端的两个元素；栈顶元素加栈中第 个元素；栈顶元素减栈中第 个元素；栈顶元素乘栈中第 个元素；输出栈顶元素。现给出一个数 ，要求构造操作序列使得输出 。

做法： 的次数是容易的，我们考虑压位，意思就是预处理好 ，然后每次三位三位算即可。但完全过不去。

注意到我们还没使用减法，如果我们处理了 和 ，发现在这种情况下 都是两次操作可以处理的，于是总次数就降到了 ，刚好可以通过。

而处理到 和 次数是一样的，更大的情况预处理就不行了。

所以一定不要相信样例的构造！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//2021.9.9 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    void solve(RG ull n){
        if(!n){
            printf("p1\ndup\nsub 1\n");
            return;
        }
        if(n<=8){
            printf("p1\n");
            if(n>1)printf("add %d\n",int(11-n));
            return;
        }
        if(n<16){
            printf("dup\nsub %d\n",int(n-6));
            return;
        }
        res x=int(n&15);
        if(x<=8){
            solve(n>>4),printf("mul 1\n");
            if(x)printf("add %d\n",10-x);
        }
        else solve((n>>4)+1),printf("mul 1\nsub %d\n",x-6);
    }
    ull n;
    inline void MAIN(){
        res Case=read();
        while(Case--){
            cin>>n;
            printf("p1\n");
            for(res i=1;i<=7;i++)printf("dup\nadd %d\n",i);
            printf("dup\nadd 1\n"),solve(n),printf("end\n");
        }
    }
}

[1002 Just another board game]

solution

题面：给你一个 的棋盘，每个格子有 ，Alice 和 Bob 在玩游戏，初始棋子在 ，Alice 先手，每次可以做以下两个操作之一：一是将棋子移到同一行任意位置（Alice），或将棋子移到同一列任意位置（Bob），（不动也是可以的）；二是直接结束。最终得分为最后棋子所在位置的值。Alice 要最大化，Bob 要最小化。如果 Alice 和 Bob 总共进行 轮之后强制停止。问最终得分。

做法：从两方立场分别贪心来看，总共移动的次数是不超过 次的，直接 常数次即可。时间复杂度 。注意最后一轮是谁在动看的是 是奇还是偶，所以 几次要看 的奇偶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//2021.9.3 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,m,cur,a[N],f[2][N],tmp[N];
    LL k;
    inline int ha(const res &x,const res &y){
        return x*m+y;
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),m=read(),k=Read();
            if(k&1)k=min(k,3ll);
            else k=min(k,2ll);
            cur=0;
            for(res i=0;i<n;i++)for(res j=0;j<m;j++)f[cur][ha(i,j)]=a[ha(i,j)]=read();
            for(k--;~k;k--){
                cur^=1;
                for(res i=0;i<n*m;i++)f[cur][i]=a[i];
                if(k&1)
                    for(res i=0;i<m;i++){
                        tmp[i]=sup;
                        for(res j=0;j<n;j++)tmp[i]=min(tmp[i],f[cur^1][ha(j,i)]);
                    }
                else
                    for(res i=0;i<n;i++){
                        tmp[i]=inf;
                        for(res j=0;j<m;j++)tmp[i]=max(tmp[i],f[cur^1][ha(i,j)]);
                    }
                for(res i=0;i<n;i++)
                    for(res j=0;j<m;j++)
                        if(k&1)f[cur][ha(i,j)]=min(f[cur][ha(i,j)],tmp[j]);
                        else f[cur][ha(i,j)]=max(f[cur][ha(i,j)],tmp[i]);
            }
            printf("%d\n",f[cur][0]);
        }
    }
}

[1003 Dota2 Pro Circuit]

solution

题面：每个人初始有 分，现你有 个分数 ，可以分配给每个人，每个人恰好分配一次，问每个人的最低排名和最高排名。

做法：最高和最低差不多，就提一下最高好了。冷静一下，发现一种比较合理的贪心方式，就是算第 个人时，给他最多的分数，然后从大到小贪心，给最大的人最小的分数，如果还是太大不如给他最大的分数，于是就 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//2021.8.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e3+10;
namespace MAIN{
    int n;
    Pair a[N],ans[N];
    int b[N]
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read();
            for(res i=1;i<=n;i++)a[i]=mp(read(),i);
            sort(a+1,a+n+1);
            for(res i=1;i<=n;i++)b[i]=read();
            for(res i=1;i<=n;i++){
                res x=a[i].fi+b[1];
                res s=1,now=n;
                for(res j=n;j;j--){
                    if(i!=j){
                        if(b[now]+a[j].fi<=x)now--;
                        else s++;
                    }
                }
                ans[a[i].se].fi=s;
                x=a[i].fi+b[n],s=n,now=1;
                for(res j=1;j<=n;j++){
                    if(i!=j){
                        if(b[now]+a[j].fi>x)now++;
                        else s--;
                    }
                }
                ans[a[i].se].se=s;
            }
            for(res i=1;i<=n;i++)printf("%d %d\n",ans[i].fi,ans[i].se);
        }
    }
}

[1004 Into the woods]

solution

题面：每次可以向上下左右等概率地走一步，一共要走 步。定义一条路径的价值为它到原点的曼哈顿距离的最大值。求期望。

做法：我们如果按照期望的定义，即权值乘概率，会发现这题真的不容易做出。

换一种思路，发现可以改写成 ，其中 表示权值。

这要求一条路径要跨出所限制的斜正方形区域，这不好，我们再改写成 。

这样就是要求一条路径不能碰到斜正方形的边界了，可惜这依旧不容易。

二维随机游走有种经典的转化，就是令 ，可以证明这新的二维是独立的，于是就转变了一维问题。即答案变成 。

这就是我们从 开始，每次可以 或 ，但不能触碰边界的方案数。

这也是经典问题，重新转成二维， 变成 ， 变成 ，那就是不能触碰两条直线的方案数。

经典的对称 + 容斥，具体做法可以参考以下（ 是我以前写的 ）：

带范围限制的一维随机游走转为二维随机游走，即转化为

从 开始，向右走转为 ，向左走转为 ，那么 的限制就是 ，也即 ，最终位置为 。

这是一个经典问题，二维向右或向上游走，不接触两条直线，问方案数。

比较好的想法就是容斥，设两条直线分别为 ，我们只讨论终点在直线间的情况，在直线的一侧是容易的。

我们知道 到 的方案数是 。但无疑直接计算会使得触碰直线的情况被算入，于是我们减去这些情况。

考虑将一个触碰直线的情况写成类似 的模式，并将其压缩，即将连续且一致的经过合并成一个，于是上述情况可以改写成 。

我们想分别计算出开头为 与开头为 的方案数，两者类似，先考虑前者。

考虑将终点沿 翻转，假设为 。那么每一条路径到 都必然经过 。同时，将最后一次经过 的点到 的路径再次沿 翻转，这一条路径只能是以 或 结尾的。

但这是结尾，我们需要求的是开头，思考不合法情况有什么，发现是类似 之类的。

我们将 沿 翻转，类似上述地，可以知道这样求出的路径是以 结尾的。这样多减去了 的情况。

可以得出一般性的结论，每一次沿直线 翻转，就等价于将上一次的每一种情况的开头加了 。

于是反复翻转，即可容斥出答案。

而这道题的终点不固定，于是就要枚举终点。

于是答案就是

再冷静一下，这东西很容易就优化掉了。

冷静一下， 是调和级数，所以总复杂度就是 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//2021.9.11 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    int n;
    int inv[N];
    int sum[N];
    inline void MAIN(){
        inv[0]=inv[1]=1;
        res Case=read();
        while(Case--){
            n=read(),kcz=read();
            for(res i=2;i<=n;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
            res fac=1;
            sum[0]=1;
            for(res i=1;i<=n;i++)fac=mul(fac,mul(inv[i],n-i+1)),sum[i]=Add(sum[i-1],fac);
            res ans=0;
#define s(l,r) (l>0?Add(sum[r],kcz-sum[l-1]):sum[r])
            for(res i=1;i<n;i++){
                res l=(n-i+1)>>1,r=(n+i)>>1,ret=0;
                for(res j=1,k=i+1;k<=r;j^=1,k+=i+1)j?add(ret,kcz-s(l-k,r-k)):add(ret,s(l-k,r-k));
                ret=Add(ret,ret),add(ret,Add(sum[r],kcz-sum[l-1])),add(ans,mul(ret,ret));
            }
            ans=Add(n,mul(kcz-ans,qpow(qpow(4,n)))),printf("%d\n",ans);
        }
    }
}

[1005 Did I miss the lethal?]

solution

题面：每张牌能造成 的伤害，但是会弃掉 张牌，问最坏情况下的最大伤害。

做法：以弃的牌的数量不同分类，分为 类。考虑 表示还剩下 张 类牌…，当前还要弃 张牌。当前不用弃牌就直接选最大的牌贪心做，可以证明在固定一种牌型中选当前最大的一定是最优的，否则弃牌肯定也会弃最大的，即让 尽量小。按着这个转移即可，时间复杂度 ，将 map 换成 即可降一个 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//2021.9.7 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=200+10;
namespace MAIN{
    int n;
    int v[4][N],vx[4];
    int f[6765300][5];
    int sz[5],bas[5],r[5];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),vx[0]=vx[1]=vx[2]=vx[3]=0;
            for(res i=1;i<=n;i++){
                res D=read(),a=read()-1;
                v[a][++vx[a]]=D;
            }
            for(res i=0;i<=3;i++)sort(v[i]+1,v[i]+vx[i]+1),sz[i]=vx[i]+1;
            bas[0]=1;
            for(res i=1;i<=4;i++)bas[i]=bas[i-1]*sz[i-1];
            for(res x=1;x<bas[4];x++){
                for(res i=0;i<4;i++)r[i]=x/bas[i]%sz[i];
                f[x][0]=0;
                for(res i=0;i<4;i++)if(r[i])f[x][0]=max(f[x][0],f[x-bas[i]][i+1]+v[i][r[i]]);
                for(res j=1;j<=4;j++){
                    f[x][j]=sup;
                    for(res i=0;i<4;i++)if(r[i])f[x][j]=min(f[x][j],f[x-bas[i]][j-1]);
                }
            }
            res ans=0;
            for(res i=0;i<=4;i++)ans=max(ans,f[bas[4]-1][i]);
            printf("%d\n",ans);
        }
    }
}

[1006 Guess the weight]

solution

题面： 张牌，分别消耗 点法力水晶。现有两种操作，一是将 张耗费为 的牌添加入手牌中，二是随机抽一张牌，问你看到这张牌后下一张牌耗费比它大的概率与比它小的概率取 ，然后求和。（不太好翻译，建议自己看题）

做法：当我们对数 求出比它大的和比它小的数的个数时，剩下所需的就是找到一个分界点，左边所有数取比它大的，右边取小，两边分别求一个和即可。

首先能发现这个分界点可以二分。那么我们只需要维护上述信息，发现线段树是完全可以胜任的。维护值域，需要维护的信息有每个数的出现次数，比这个数大的个数，以及小的个数。修改操作就是两个区间修改和一个单点修改，分界点直接二分，那么总时间复杂度就是 。

可惜这个过不了，冷静一下发现这个分界点是中位数，所以可以直接在线段树上二分，就是 了。

实现时我偷懒直接用了 pair ，所以常数比较大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//2021.9.4 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n,q;
    int sz[N<<2];
    Pair tr[N<<2],laz[N<<2],sum[N<<2];
    inline Pair operator + (const RG Pair &A,const RG Pair &B){
        return mp(A.fi+B.fi,A.se+B.se);
    }
    inline Pair operator * (const RG Pair &A,const res &v){
        return mp(A.fi*v,A.se*v);
    }
    int v[N];
    inline void pushup(const res &rt){
        tr[rt]=tr[rt<<1]+tr[rt<<1|1];
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
        sz[rt]=sz[rt<<1]+sz[rt<<1|1];
    }
    void build(res rt,res l,res r){
        laz[rt]=mp(0,0);
        if(l==r){tr[rt]=mp(v[l-1],n-v[l]),sz[rt]=v[l]-v[l-1],sum[rt]=mp(1ll*v[l-1]*sz[rt],1ll*(n-v[l])*sz[rt]);return;}
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    inline void change(const res &rt,const RG Pair &val){
        tr[rt]=tr[rt]+val,sum[rt]=sum[rt]+(val*sz[rt]),laz[rt]=laz[rt]+val;
    }
    inline void pushdown(const res &rt){
        change(rt<<1,laz[rt]),change(rt<<1|1,laz[rt]),laz[rt]=mp(0,0);
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const RG Pair &v){
        if(L<=l&&r<=R){change(rt,v);return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R,v);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,v);
        pushup(rt);
    }
    Pair query(res rt,res l,res r,const res &L,const res &R){
    	if(L>R)return mp(0ll,0ll);
        if(L<=l&&r<=R)return sum[rt];
        pushdown(rt);
        res mid=(l+r)>>1;
        RG Pair ret=mp(0,0);
        if(L<=mid)ret=query(rt<<1,l,mid,L,R);
        if(R>mid)ret=ret+query(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
        return ret;
    }
    int query_sz(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return sz[rt];
        pushdown(rt);
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query_sz(rt<<1,l,mid,L,R);
        if(R>mid)ret+=query_sz(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
        return ret;
    }
    void modify(res rt,res l,res r,const res &p,const res &v){
        if(l==r){sz[rt]+=v,sum[rt]=tr[rt]*sz[rt];return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(p<=mid)modify(rt<<1,l,mid,p,v);
        else modify(rt<<1|1,mid+1,r,p,v);
        pushup(rt);
    }
    int div;
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),q=read();
            for(res i=1;i<=N-10;i++)v[i]=0;
            for(res i=1;i<=n;i++)v[read()]++;
            for(res i=1;i<=N-10;i++)v[i]+=v[i-1];
            build(1,1,N-10);
            while(q--){
                res opt=read();
                if(opt==1){
                    res x=read(),w=read();
                    if(w>1)modify(1,1,N-10,1,w-1,mp(0,x));
                    if(w<N-10)modify(1,1,N-10,w+1,N-10,mp(x,0));
                    modify(1,1,N-10,w,x);
                    n+=x;
                }
                else {
					res div=0,l=1,r=N-10,rt=1,k=(n+1)>>1;
					for(;l!=r;){
						res mid=(l+r)>>1;
						if(sz[rt<<1]>=k)rt<<=1,r=mid;
						else k-=sz[rt<<1],rt=rt<<1|1,l=mid+1;
					}
					div=l;
                    RG LL nume=max(query(1,1,N-10,1,div).se+query(1,1,N-10,div+1,N-10).fi,query(1,1,N-10,1,div-1).se+query(1,1,N-10,div,N-10).fi);
                    RG LL deno=1ll*n*(n-1);
                    RG LL gcd=__gcd(nume,deno);
                    print(nume/gcd),sr[++C]='/',print(deno/gcd),sr[++C]='\n';
                }
            }
        }
    }
}

[1007 Boring data structure problem]

solution

题面：第 个加入数组的元素是 ，现有四个操作：一是左边进入一个新元素，二是右边进入一个新元素，三是将元素 丢出数组，四是查询最中间的数。

做法：只要用个 list 就可以维护所有信息了，具体细节直接看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//2021.9.2 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e7+10;
namespace MAIN{
    char opt[3];
    int nxt[N],las[N],m;
    int he,ta,ls,rs;
    int vis[N];
    int ans;
    inline void MAIN(){
        res Case=1;
        while(Case--){
            res q=read();
            while(q--){
                scanf("%s",opt+1);
                if(opt[1]=='L'){
                    m++;
                    if(!he)he=ta=ans=m,las[m]=nxt[m]=ls=rs=vis[m]=0;
                    else {
                        las[he]=m,nxt[m]=he,he=m,las[m]=0,vis[m]=1;
                        if(ls==rs)ls++;
                        else rs++,vis[ans]=2,ans=las[ans],vis[ans]=0;
                    }
                }
                else if(opt[1]=='R'){
                    m++;
                    if(!he)he=ta=ans=m,las[m]=nxt[m]=ls=rs=vis[m]=0;
                    else {
                        nxt[ta]=m,las[m]=ta,ta=m,nxt[m]=0,vis[m]=2;
                        if(ls==rs)ls++,vis[ans]=1,ans=nxt[ans],vis[ans]=0;
                        else rs++;
                    }
                }
                else if(opt[1]=='G'){
                    res x=read();
                    if(x==he)he=nxt[he];
                    if(x==ta)ta=las[ta];
                    if(!vis[x]){
                        res l=las[x],r=nxt[x];
                        if(ls==rs)las[r]=l,nxt[l]=r,vis[r]=0,ans=r,rs--;
                        else las[r]=l,nxt[l]=r,vis[l]=0,ans=l,ls--;
                    }
                    else if(vis[x]==1){
                        res l=las[x],r=nxt[x];
                        if(ls==rs)las[r]=l,nxt[l]=r,vis[ans]=1,ans=nxt[ans],rs--,vis[ans]=0;
                        else las[r]=l,nxt[l]=r,ls--;
                    }
                    else {
                        res l=las[x],r=nxt[x];
                        if(ls==rs)las[r]=l,nxt[l]=r,rs--;
                        else las[r]=l,nxt[l]=r,vis[ans]=2,ans=las[ans],vis[ans]=0,ls--;
                    }
                }
                else printf("%d\n",ans);
            }
        }
    }
}

[1008 Integers Have Friends 2.0]

solution

题面：找出一个最长的子序列，使得每个数模 都相等， 由你选取。

做法：注意到一件事，当模 比模 的质因数一定更劣，于是我们就只用考虑模 的质因数了。

两个数在最后的答案中的概率是 ，而它们的差的质因数不多，大概最多 个，所以我们随机 次，每次暴力地拿它们的所有质因数算一遍答案即可，时间复杂度 。考场上廷廷直接拿 分解了，太暴力了属于是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//2021.9.3 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e6+10;
namespace MAIN{
    int n;
    LL a[N];
    int prim[N],vis[N],tot;
    inline void MAIN(){
        for(res i=2;i<=N-10;i++){
            if(!vis[i])prim[++tot]=i;
            for(res j=1;j<=tot&&prim[j]*i<=N-10;j++){
                vis[prim[j]*i]=1;
                if(i%prim[j]==0)break;
            }
        }
        res Case=read();
        while(Case--){
            n=read();
            res sum=0;
            for(res i=1;i<=n;i++)a[i]=Read(),sum+=a[i]&1;
            res ans=max(sum,n-sum);
            for(res K=1;K<=40;K++){
                res x=rng()%n+1,y=rng()%n+1;
                while(x==y)x=rng()%n+1,y=rng()%n+1;
                RG LL _=abs(a[x]-a[y]);
                for(res j=1;j<=tot;j++){
                    if(_%prim[j]==0){
                        RG LL __=a[x]%prim[j];
                        sum=0;
                        for(res i=1;i<=n;i++)sum+=a[i]%prim[j]==__;
                        ans=max(ans,sum);
                        while(_%prim[j]==0)_/=prim[j];
                    }
                    if(_!=1){
                        RG LL __=a[x]%_;
                        sum=0;
                        for(res i=1;i<=n;i++)sum+=a[i]%prim[j]==__;
                        ans=max(ans,sum);
                    }
                }
            }
            printf("%d\n",ans);
        }
    }
}

[1009 Little prince and the garden of roses]

solution

题面： 的方格，每个方格的初始颜色为 。现让你给方格的第二维颜色染色，使得两个颜色相同的方格不在同一行和同一列。问最少颜色数和染色方案。

做法：对于某一种颜色 ，构造一张二分图，若 ，则连一条从 到 的边。而最少颜色数就是最大度数。

这是容易证明的，考虑类似匈牙利的过程，若当前无颜色可用了，可逼迫当前染色边染成该颜色，然后将另一条有该颜色的边退流，容易构造出方案。容易证明这样的复杂度是 的，类似匈牙利。

所以不能跟榜啊。

代码不是很想写了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//2021.9.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=600+10;
namespace MAIN{
    int n;
    int ans[N][N],vis[N][N];
    vector<Pair> G[N*N];
    int du[N];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read();
            for(res i=1;i<=n*n;i++)vector<Pair>().swap(G[i]);
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)ans[i][j]=-1,G[read()].pb(mp(i,j));
            res mx=0;
            for(res i=1;i<=n*n;i++){
                for(res j=1;j<=n<<1;j++)du[j]=0;
                for(auto x:G[i])du[x.fi]++,du[x.se+n]++;
                res d=0;
                for(res j=1;j<=n<<1;j++)d=max(d,du[j]);
                mx=max(mx,--d);
                for(res j=1;j<=n<<1;j++)for(res k=0;k<=d;k++)vis[j][k]=0;
                for(auto _:G[i]){
                    res x=_.fi,y=_.se+n,c1=0,c2=0;
                    for(res k=0;k<=d;k++){
                        if(!vis[x][k])c1=k;
                        if(!vis[y][k])c2=k;
                    }
                    while(y){
                        if(ans[x][y-n]>=0)vis[y][ans[x][y-n]]=0;
                        ans[x][y-n]=c1,vis[x][c1]=y,swap(vis[y][c1],x);
                        if(!x)break;
                        if(ans[x][y-n]>=0)vis[x][ans[x][y-n]]=0;
                        ans[x][y-n]=c2,vis[y][c2]=x,swap(vis[x][c2],y);
                    }
                }
            }
            res tot=0;
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)tot+=ans[i][j]>0;
            printf("%d %d\n",mx,tot);
            for(res i=1;i<=n;i++)for(res j=1;j<=n;j++)ans[i][j]>0?printf("%d %d %d\n",i,j,ans[i][j]):1;
        }
    }
}

[1010 Unfair contest]

solution

题面：有两个人在跳水比赛，他们的最终成绩为去掉最大的 个和去掉最小的 个剩下来的数的和，现在 个裁判已经打好了分，轮到你打分，你希望第一个人能赢，但希望你自己打的分之差最小，问最小的差。

做法：冷静一下，最大的 个和最小的 个肯定要拿掉，那么剩下来就 种可能，讨论一下即可，时间复杂度 。

坑： 或 的情况要注意一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//2021.8.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,s,t,h;
    int a[N],b[N];
    struct P{
        LL sum;
        int l,r;
        P() {}
        P(RG LL sum,res l,res r):sum(sum),l(l),r(r) {}
    }A[3],B[3];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read()-1,s=read(),t=read(),h=read();
            for(res i=1;i<=n;i++)a[i]=read();
            for(res i=1;i<=n;i++)b[i]=read();
            sort(a+1,a+n+1),sort(b+1,b+n+1);
            RG LL sa=0;
            for(res i=t+1;i<=n-s;i++)sa+=a[i];
            res as=a[n-s+1],at=a[t];
            RG LL sb=0;
            for(res i=t+1;i<=n-s;i++)sb+=b[i];
            res bs=b[n-s+1],bt=b[t];
            if(s)A[0]=P(sa+as,as,h);
            else A[0]=P(-1,0,0);
            if(t)A[1]=P(sa+at,1,at);
            else A[1]=P(-1,0,0);
            if(s&&t)A[2]=P(sa,at,as);
            else if(s)A[2]=P(sa,1,as);
            else if(t)A[2]=P(sa,at,h);
            else A[2]=P(sa,1,h);
            if(s)B[0]=P(sb+bs,bs,h);
            else B[0]=P(INF,0,0);
            if(t)B[1]=P(sb+bt,1,bt);
            else B[1]=P(INF,0,0);
            if(s&&t)B[2]=P(sb,bt,bs);
            else if(s)B[2]=P(sb,1,bs);
            else if(t)B[2]=P(sb,bt,h);
            else B[2]=P(sb,1,h);
            res ans=inf;
            for(res i=0;i<2;i++)for(res j=0;j<2;j++){
                if(A[i].sum<=B[j].sum)continue;
                res l0=A[i].l,r1=B[j].r;
                ans=min(ans,l0-r1);
            }
            for(res i=0;i<2;i++){
                if(A[2].sum>B[i].sum){
                    ans=min(ans,A[2].l-B[i].r);
                }
                else {
                    RG LL x=B[i].sum-A[2].sum+1;
                    if(A[2].l<=x&&x<=A[2].r)ans=min(ans,int(x-B[i].r));
                    else if(A[2].l>x)ans=min(ans,int(A[2].l-B[i].r));
                }
            }
            for(res i=0;i<2;i++){
                if(A[i].sum<=B[2].sum);
                else {
                    RG LL x=A[i].sum-B[2].sum-1;
                    if(B[2].l<=x&&x<=B[2].r)ans=min(ans,int(A[i].l-x));
                    else if(B[2].r<x)ans=min(ans,int(A[i].l-B[2].r));
                }
            }
            RG LL x=B[2].sum-A[2].sum+1;
            res l=A[2].l-B[2].r,r=A[2].r-B[2].l;
            if(l<=x&&x<=r)ans=min(ans,int(x));
            else if(l>x)ans=min(ans,int(l));
            if(ans==inf)puts("IMPOSSIBLE");
            else printf("%d\n",ans);
        }
    }
}

[1011 ZYB’s kingdom]

solution

题面：一棵树，每个点有一个值 和权值，初始权值为 。修改操作是选出给定的 个点，使得所有不经过它们的最短路径的端点权值互相加上对方的 。询问单点权值。

做法：先理解下题意，等价于每次去掉那 个点，然后每个连通块加上自己连通块的 之和即可（ 虽然不用加上自己，但这都是小细节，可以随意处理 ）。

考虑一种暴力的做法。用 序维护子树修改。每次修改按深度遍历这 个点，然后遍历这个 的儿子，如果儿子的子树里没有这 个点，那么就是直接修改子树；否则将那个点的区间去掉，剩下的几段区间照样修改。发现这个复杂度非常不对，因为遍历儿子是可以卡到 的（ 例如菊花 ）。而发现如果儿子子树里有这 个点，反而遍历的复杂度是正确的，这还是因为总点数是 。

于是我们考虑一种新的做法，即维护一棵类似虚树的结构，将这 个点直接按祖孙关系连边，那么每次可以选择遍历这棵虚树，来处理儿子子树有这 个点的情况。而儿子子树没有这 个点的情况，可以考虑打个标记，即表示当前这个点的子树都修改，那么只要在有这 个点的儿子子树做特殊处理即可。而每次询问则是暴力跳父亲，有标记就修改。

这样的复杂度还是错的，毕竟是暴力跳父亲。不过没啥关系，一般的暴力跳父亲都可以重链剖分一次，来优化这个复杂度。这题也毫不例外，于是暴力直接修改的点只有重儿子和那些特殊点，那么暴力跳就只用跳到重链链顶。时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//2021.9.15 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n,q,m;
    vector<int> G[N];
    int c[N],F[N][21];
    int dfn[N],idx,pos[N],top[N],sz[N],son[N],dep[N],low[N];
    void dfs(res x,res fax){
        sz[x]=1,son[x]=0,F[x][0]=fax;
        for(res i=1;i<=20;i++)F[x][i]=F[F[x][i-1]][i-1];
        for(auto tox:G[x]){
            if(tox==fax)continue;
            dfs(tox,x),sz[x]+=sz[tox];
            if(sz[tox]>sz[son[x]])son[x]=tox;
        }
    }
    void dfs(res x,res fax,res topx,res depx){
        top[pos[dfn[x]=++idx]=x]=topx,dep[x]=depx;
        if(son[x])dfs(son[x],x,topx,depx+1);
        for(auto tox:G[x]){
            if(tox==fax||tox==son[x])continue;
            dfs(tox,x,tox,depx+1);
        }
        low[x]=idx;
    }
    inline int get(res x,const res &f){
        for(res i=20;~i;i--)if(dep[F[x][i]]>dep[f])x=F[x][i];
        return x;
    }
    LL sum[N],tr[N];
    inline void modify(const res &x,const RG LL &y){
        for(res i=x;i<=n;i+=lowbit(i))tr[i]+=y;
    }
    inline LL getsub(const res &x){
        return sum[low[x]]-sum[dfn[x]-1];
    }
    inline void modify(const res &l,const res &r,const RG LL &v){
        modify(l,v),modify(r+1,-v);
    }
    Pair a[N];
    int st[N],Top;
    struct E{
        int next,to;
        E() {}
        E(res next,res to):next(next),to(to) {}
    }edge[N];
    int head[N],cnt;
    inline void addedge(const res &u,const res &v){
        edge[++cnt]=E(head[u],v),head[u]=cnt;
    }
    int tag[N];
    void dfs(res x){
        if(x)tag[x]++;
        RG bool fl=0;
        for(res i=head[x];~i;){
            res tox=edge[i].to,ch=get(tox,x),j=i;
            RG LL s=getsub(ch);
            for(;~j;j=edge[j].next){
                res Tox=edge[j].to;
                if(dfn[ch]<=dfn[Tox]&&dfn[Tox]<=low[ch])s-=getsub(Tox);
                else break;
            }
            modify(dfn[ch],low[ch],s);
            for(res k=i;k!=j;k=edge[k].next){
                res Tox=edge[k].to;
                modify(dfn[Tox],low[Tox],-s);
            }
            if(ch==son[x])fl=1;
            else modify(dfn[ch],low[ch],-getsub(ch));
            i=j;
        }
        if(!fl&&son[x])modify(dfn[son[x]],low[son[x]],getsub(son[x]));
        for(res i=head[x];~i;i=edge[i].next)dfs(edge[i].to);
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),q=read();
            for(res i=1;i<=n;i++)vector<int>().swap(G[i]);
            for(res i=1;i<n;i++){
                res u=read(),v=read();
                G[u].pb(v),G[v].pb(u);
            }
            for(res i=1;i<=n;i++)c[i]=read();
            idx=m=0,son[0]=1,dfn[0]=1,low[0]=n,dfs(1,0),dfs(1,0,1,1);
            for(res i=1;i<=n;i++)sum[i]=sum[i-1]+c[pos[i]];
            for(res i=0;i<=n;i++)tag[i]=0,tr[i]=0;
            while(q--){
                res opt=read(),k=read();
                if(opt==1){
                    m++;
                    for(res i=1;i<=k;i++){
                        res x=read();
                        modify(dfn[x],dfn[x],c[x]),a[i]=mp(dfn[x],low[x]);
                    }
                    sort(a+1,a+k+1),Top=cnt=0;
                    for(res i=0;i<=k;i++)head[pos[a[i].fi]]=-1;
                    for(res i=1;i<=k;i++){
                        while(Top&&a[st[Top]].se<a[i].se)Top--;
                        addedge(pos[a[st[Top]].fi],pos[a[i].fi]),st[++Top]=i;
                    }
                    dfs(0);
                }
                else {
                    RG LL ret=0;
                    for(res i=dfn[k];i;i-=lowbit(i))ret+=tr[i];
                    ret-=1ll*m*c[k];
                    while(k)ret+=getsub(top[k])*tag[F[top[k]][0]],k=F[top[k]][0];
                    print(ret),sr[++C]='\n';
                }
            }
        }
    }
}