CXXP#2 赛后总结帖

出锅致歉：时间没选好，12点钟，集训同学只能看哪个班先到教室了（？）

原定 T4，官方放错题目了，原题：https://www.acgo.cn/contest/detail/22010?matchRoundId=22010&examId=90123&openLevel=2&teamCode=1935320303573721088&inviteCode=zZXh

@Sherry 申请改题目改数据

题解会给原题的，记比赛 T4 的分。

赛时播报

开赛 60 分钟内，无 AK。
T1 出现了首个 40 分做法
T1 出现了首个 90 分做法
首 AK 帅树（好像是个老师）

T4 只考虑 i ≠ j 的操作

---

赛后总结

本次比赛共 $880$ 人报名，$154$ 人提交，$100$ 人有分。

AK 人数 $2$ 人。

感谢各位选手参加 CXXP#2。

统计信息未排除作弊者，奖项将在作弊检查后发放，请耐心等待。

题号	难度	通过人数	通过率 A	通过率 B	预期情况
$\text{A}$	$\color{9C3DCF}{\text省选}$	$2$	$1.29\%$	$2\%$	远高于预期
$\text{B}$	$\color{13C2C2}{提高}$$\color{53C41A}{(-)}$	$25$	$16.23\%$	$25\%$	略低于预期
$\text{C}$	$\color{F39C11}{普及-}$	$53$	$34.42\%$	$53\%$	低于预期
$\text{D}$	$\color{FFC116}{普及}$	$39$	$25.32\%$	$39\%$	略高于预期
题号	idea 来源	实际出题人	格式修正等	数据来源	题解编写
$\text{A}$	Xyl	Xyl	Xyl & wcqk	Xyl	Xyl
$\text{B}$	sk	sk & Euc	Euc & sk	sk	sk
$\text{C}$	wcqk	wcqk	wcqk	wcqk	yh24chenyiming
$\text{D}$	wcqk	yhzakioi	yhzakioi	yhzakioi	yhzakioi

通过率 A 为全场有提交通过率
通过率 B 为全场有分通过率

CXXP#2 T1 新版题解

很板子的手速题加卡常题。题面在说啥。

对于第一个子任务，暴力做。

对于第二个子任务，相当于 P3834，套用模板可以通过。

对于第三个子任务，只有最后一个操作是询问。用平衡树之类的数据结构维护插入和删除的元素顺序，最后进行中序遍历并暴力求解最后一个操作的答案。

对于 $100\%$ 的数据，注意到操作可以用树套树模板求解，但是无法通过本题大部分的空间限制。由于题目要求动态区间查询且不强制在线，不难想到先维护每个元素的最终位置，再对操作的坐标进行对应，之后使用整体二分求解，添加操作对应整体二分添加值操作，删除对应整体二分的删除值操作。见模板题，整体二分的修改就是一个删除值加一个增加值。

关于做法，Asdfre 大佬场切了这道题，ta 的代码函数名设置为了 cdq()，实际上这个做法应该是整体二分。Asdfre 的做法特判了删除的元素，实际上树状数组数点时可以直接跨过没有操作的元素，在使用平衡树时子树大小不统计已删除节点即可。

其他问题代码里写得很清楚了，可以对照代码理解。本题略微卡常。ACGO 评测机会把某些增加了优化的代码跑得比没有优化的代码慢，不知道啥原理，玄学罢。

#include<bits/stdc++.h>
using namespace std;
int root,cnt,x,y,k,n,m,len,pos,p,ans[300005],tree[300005],maxn,a[300005],od,newid[300005],idcnt,idx,tot,qcnt;
struct order{
    int x,y,k,op,id;
}q[300005],q1[300005],q2[300005];
void add(int x,int y){for(;x<=tot;x+=x&(-x))tree[x]+=y;}
int sum(int x){
    int ans=0;
    for(;x;x-=x&(-x))ans+=tree[x];
    return ans;
}
struct node{int ls,rs,pri,sz,rk,val,ext=1;}t[300005];
void update(int u){t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+t[u].ext;}
int newnode(int c,int val){t[++cnt]={0,0,rand(),1,c,val,1};return cnt;}
void split(int u,int x,int &L,int &R){
    if(!u){L=R=0;return;}
    if(t[t[u].ls].sz+t[u].ext<=x)L=u,split(t[u].rs,x-t[t[u].ls].sz-t[u].ext,t[u].rs,R);
    else R=u,split(t[u].ls,x,L,t[u].ls);
    update(u);
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(t[x].pri>t[y].pri){t[x].rs=merge(t[x].rs,y),update(x);return x;}
    else{t[y].ls=merge(x,t[y].ls),update(y);return y;}
}
void del(int u,int x){
    t[u].sz--;
    if(t[t[u].ls].sz+t[u].ext==x){if(t[u].ext)t[u].ext=0;else del(t[u].ls,x);}
    else if(t[t[u].ls].sz+t[u].ext<x)del(t[u].rs,x-t[t[u].ls].sz-t[u].ext);
    else del(t[u].ls,x);
    update(u);
}
int find(int u,int x){
    if(t[t[u].ls].sz+t[u].ext==x)return t[u].ext?u:find(t[u].ls,x);
    else if(t[t[u].ls].sz+t[u].ext<x)return find(t[u].rs,x-t[t[u].ls].sz-t[u].ext);
    return find(t[u].ls,x);
}
void inorder(int u){
    if(!u)return;
    inorder(t[u].ls),newid[t[u].rk]=++tot,inorder(t[u].rs);
}
void solve(int l,int r,int ql,int qr){
    if(l>r||ql>qr)return;
    int cnt1=0,cnt2=0,mid=l+r>>1;
    if(l==r){
        for(int i=ql;i<=qr;++i)
            if(q[i].op==1)
                ans[q[i].id]=l;
        return;
    }
    bool b1=0,b2=0;
    for(int i=ql;i<=qr;++i){
        if(q[i].op==1){
            int t=sum(q[i].y)-sum(q[i].x-1);
            if(q[i].k<=t)
                q1[++cnt1]=q[i],b1=1;
            else q[i].k-=t,q2[++cnt2]=q[i],b2=1;
        }
        else{
            if(q[i].y<=mid)
                add(q[i].x,q[i].k),q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }
    }
    for(int i=1;i<=cnt1;++i)
        if(q1[i].op!=1)
            add(q1[i].x,-q1[i].k);
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    if(b1)solve(l,mid,ql,ql+cnt1-1);
    if(b2)solve(mid+1,r,ql+cnt1,qr);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    srand(0);
    n=read(),m=read();
    for(int i=1;i<=n;++i)q[++idx]={i,read(),1,2,0},root=merge(root,newnode(++idcnt,q[idx].y)),maxn=max(maxn,q[idx].y);
    for(int i=1;i<=m;++i){
        od=read(),x=read();
        if(od==1)y=read(),q[++idx]={find(root,x),find(root,y),read(),1,++qcnt};
        else if(od==2){
            y=read();
            maxn=max(maxn,y);
            int L,R,P=newnode(++idcnt,y);
            ++idx,q[idx]={P,y,1,2,0};
            split(root,x,L,R);
            root=merge(merge(L,P),R);
        }
        else {int tmp=find(root,x);++idx,q[idx]={tmp,t[tmp].val,-1,0,0},del(root,x);}
    }
    inorder(root);
    for(int i=1;i<=idx;++i){
        q[i].x=newid[q[i].x];
        if(q[i].op==1)q[i].y=newid[q[i].y];
    }
    solve(1,maxn,1,idx);
    for(int i=1;i<=qcnt;++i)write(ans[i]),putchar_unlocked('\n');
    return 0;
}

感谢大和赤骥智力支援卡对题解作者智力的一切支持。

T1 岁月成碑 旧版题解

题意是求带插入/删除元素的区间第 $k$ 小值。
10pts Solution
有 $10$ 的数据量很小，暴力模拟即可。时间复杂度 $O(MNlog N)$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[300005],b[300005],op,x,y,z;
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
	n=read(),m=read();
	for(register int i=1;i<=n;++i)a[i]=read();
	while(m--){
		op=read();
		if(op==1){
			x=read(),y=read(),z=read();
			for(register int i=x;i<=y;++i)b[i]=a[i];
			sort(b+x,b+y+1);
			write(b[x+z-1]),putchar('\n');
		}
		else if(op==2){
			x=read(),y=read();
			a[++n]=y;
			for(register int i=n;i>x+1;--i)a[i]^=a[i-1]^=a[i]^=a[i-1];
		}
		else {
			x=read();
			a[x]=0,--n;
			for(register int i=x;i<=n;++i)a[i]^=a[i+1]^=a[i]^=a[i+1];
		}
	}
	return 0;
}

30pts Solution
当 $1\leq N,Q\leq 500$ 时，运行暴力程序。
否则，由于对于另外 $20$ 的数据， $op_i=1$, 因此这部分测试点直接使用主席树/整体二分模板完成即可。
代码在这里不予给出，请查找资料。
50pts Solution
对于以上所述 $1\leq N,Q\leq 500$ 和 $op_i=1$ 的测试点，使用 30pts 的解法。对于 $op_i\in{2,3}$, $op_Q=1$ 的测试点，只有最后一个操作是询问，前面我们只需要维护序列的插入和删除操作。我们可以维护一个有序表，最后进行一次暴力解决最后一个询问。由于维护有序表只需要 $O(Nlog_2N)$ 的时间复杂度，因此如替罪羊树这样的 BST 应该也可以通过。注意， 如果使用 BST 维护有序表，最后进行一次中序遍历得到最终序列。代码不予给出，请查找资料。
90pts/AC Solution
注意到，对于此问题，在线查询很不可做，考虑离线。如何用树套树解决此问题？
树套树维护的是一个整体序列，不支持插入/删除操作。用一种入门级的方法，只需要将数组将要插入的位置多空开一格，初始设为 INF, 不影响区间第 $k$ 小值的计算。我们可以用有序表离线维护每个查询/插入/删除操作的端点位置，当插入新元素时在有序表里插入这个元素位置，当删除元素时只用将它标记为删除，后续二分时忽略这个元素即可。不能真删是因为如果真删那么离线完处理询问时将无法处理包含已删除元素的询问。离线处理完每个操作的下标后如果是 BST 就要进行一次中序遍历，包含已被删除的元素，最后将每个操作的初始位置修改为新位置。由于树套树支持修改操作，在添加时只用把已有的 INF 位置修改为新数，删除时把该位置修改为 INF 即可。
代码不予给出，请对照后面 AC 代码和网上资料改出树套树代码学习。
因为树套树空间复杂度大、常数大，无法通过本题最后一个测试点。考虑整体二分。
由于进行了两次离线，出题人将该技巧称为“整体二分二次离线”或者“整体二分后置二次离线”。理论上该算法可以解决整体二分中操作对全局其它操作有影响的问题，特别是带插入/删除的整体二分经典问题。作者在代码中使用 FHQ-Treap 维护有序表。代码中所有操作的初始位置代表了所操作位置在 FHQ-Treap 中对应的节点编号，插入时开一个新节点，并到 root 根节点的树上，把插入操作的位置设为新节点的编号。删除时查找 BST 上第 $x$ 个元素的编号。询问操作同理，将左端点和右端点转化为 FHQ-Treap 上的编号。
完成第一次离线后，中序遍历 FHQ-Treap, 计算出每个节点对应的新位置，最后使用整体二分。整体二分不用初始化 INF, 因为整体二分是一种仅与操作有关的算法，没有给出的操作可以直接忽略， 可以理解为支持回答某些元素空缺的询问。整体二分和 FHQ-Treap 的常数较小，可以通过所有测试点。
由于本题时间限制，给定正解为跳表/FHQ-Treap/Splay + 整体二分，其它算法理论上无法通过。
以下是未优化代码，注意二分查找时不能查找到已删除元素：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int root,cnt,x,y,k,n,m,len,pos,p,ans[300005],tree[300005],maxn,a[300005],od,newid[300005],idcnt,idx,tot,qcnt;
struct order{
    int x,y,k,op,id;
}q[300005],q1[300005],q2[300005];
void add(int x,int y){for(;x<=tot;x+=x&(-x))tree[x]+=y;}
int sum(int x){
    int ans=0;
    for(;x;x-=x&(-x))ans+=tree[x];
    return ans;
}
struct node{int ls,rs,pri,sz,rk,val,ext=1;}t[300005];
void update(int u){t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+t[u].ext;}
int newnode(int c,int val){t[++cnt]={0,0,rand(),1,c,val,1};return cnt;}
void split(int u,int x,int &L,int &R){
    if(!u){L=R=0;return;}
    if(t[t[u].ls].sz+t[u].ext<=x)L=u,split(t[u].rs,x-t[t[u].ls].sz-t[u].ext,t[u].rs,R);
    else R=u,split(t[u].ls,x,L,t[u].ls);
    update(u);
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(t[x].pri>t[y].pri){t[x].rs=merge(t[x].rs,y),update(x);return x;}
    else{t[y].ls=merge(x,t[y].ls),update(y);return y;}
}
void del(int u,int x){
    t[u].sz--;
    if(t[t[u].ls].sz+t[u].ext==x){if(t[u].ext)t[u].ext=0;else del(t[u].ls,x);}
    else if(t[t[u].ls].sz+t[u].ext<x)del(t[u].rs,x-t[t[u].ls].sz-t[u].ext);
    else del(t[u].ls,x);
    update(u);
}
int find(int u,int x){
    if(t[t[u].ls].sz+t[u].ext==x)return t[u].ext?u:find(t[u].ls,x);
    else if(t[t[u].ls].sz+t[u].ext<x)return find(t[u].rs,x-t[t[u].ls].sz-t[u].ext);
    return find(t[u].ls,x);
}
void inorder(int u){
    if(!u)return;
    inorder(t[u].ls),newid[t[u].rk]=++tot,inorder(t[u].rs);
}
void solve(int l,int r,int ql,int qr){
    if(l>r||ql>qr)return;
    int cnt1=0,cnt2=0,mid=l+r>>1;
    if(l==r){
        for(int i=ql;i<=qr;++i)
            if(q[i].op==1)
                ans[q[i].id]=l;
        return;
    }
    bool b1=0,b2=0;
    for(int i=ql;i<=qr;++i){
        if(q[i].op==1){
            int t=sum(q[i].y)-sum(q[i].x-1);
            if(q[i].k<=t)
                q1[++cnt1]=q[i],b1=1;
            else q[i].k-=t,q2[++cnt2]=q[i],b2=1;
        }
        else{
            if(q[i].y<=mid)
                add(q[i].x,q[i].k),q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }
    }
    for(int i=1;i<=cnt1;++i)
        if(q1[i].op!=1)
            add(q1[i].x,-q1[i].k);
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    if(b1)solve(l,mid,ql,ql+cnt1-1);
    if(b2)solve(mid+1,r,ql+cnt1,qr);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    srand(0);
    n=read(),m=read();
    for(int i=1;i<=n;++i)q[++idx]={i,read(),1,2,0},root=merge(root,newnode(++idcnt,q[idx].y)),maxn=max(maxn,q[idx].y);
    for(int i=1;i<=m;++i){
        od=read(),x=read();
        if(od==1)y=read(),q[++idx]={find(root,x),find(root,y),read(),1,++qcnt};
        else if(od==2){
            y=read();
            maxn=max(maxn,y);
            int L,R,P=newnode(++idcnt,y);
            ++idx,q[idx]={P,y,1,2,0};
            split(root,x,L,R);
            root=merge(merge(L,P),R);
        }
        else {int tmp=find(root,x);++idx,q[idx]={tmp,t[tmp].val,-1,0,0},del(root,x);}
    }
    inorder(root);
    for(int i=1;i<=idx;++i){
        q[i].x=newid[q[i].x];
        if(q[i].op==1)q[i].y=newid[q[i].y];
    }
    solve(1,maxn,1,idx);
    for(int i=1;i<=qcnt;++i)write(ans[i]),putchar_unlocked('\n');
    return 0;
}

以下是已优化代码，可能可读性不如未优化版本。

#include<bits/stdc++.h>
using namespace std;
int root,cnt,x,y,k,n,m,len,pos,p,ans[300005],tree[300005],maxn,a[300005],od,newid[300005],idcnt,idx,tot,qcnt,sp[300005],spcnt;
struct order{
    int x,y,k,op,id;
}q[300005],q1[300005],q2[300005];
void add(int x,int y){for(;x<=tot;x+=x&(-x)){if(!tree[x])sp[++spcnt]=x;tree[x]+=y;}}
int sum(int x){
    int ans=0;
    for(;x;x-=x&(-x))ans+=tree[x];
    return ans;
}
struct node{int ls,rs,pri,sz,rk,val,ext=1;}t[300005];
void update(int u){t[u].sz=t[t[u].ls].sz+t[t[u].rs].sz+t[u].ext;}
int newnode(int c,int val){t[++cnt]={0,0,rand(),1,c,val,1};return cnt;}
void split(int u,int x,int &L,int &R){
    if(!u){L=R=0;return;}
    if(t[t[u].ls].sz+t[u].ext<=x)L=u,split(t[u].rs,x-t[t[u].ls].sz-t[u].ext,t[u].rs,R);
    else R=u,split(t[u].ls,x,L,t[u].ls);
    update(u);
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(t[x].pri>t[y].pri){t[x].rs=merge(t[x].rs,y),update(x);return x;}
    else{t[y].ls=merge(x,t[y].ls),update(y);return y;}
}
void del(int u,int x){
    t[u].sz--;
    if(t[t[u].ls].sz+t[u].ext==x){if(t[u].ext)t[u].ext=0;else del(t[u].ls,x);}
    else if(t[t[u].ls].sz+t[u].ext<x)del(t[u].rs,x-t[t[u].ls].sz-t[u].ext);
    else del(t[u].ls,x);
    update(u);
}
int find(int u,int x){
    if(t[t[u].ls].sz+t[u].ext==x)return t[u].ext?u:find(t[u].ls,x);
    else if(t[t[u].ls].sz+t[u].ext<x)return find(t[u].rs,x-t[t[u].ls].sz-t[u].ext);
    return find(t[u].ls,x);
}
void inorder(int u){
    if(!u)return;
    inorder(t[u].ls),newid[t[u].rk]=++tot,inorder(t[u].rs);
}
void solve(int l,int r,int ql,int qr,int pos){
    if(l>r||ql>qr)return;
    int cnt1=0,cnt2=0,mid=l+r>>1;
    if(l==r){
        for(int i=ql;i<=qr;++i)
            if(q[i].op==1)
                ans[q[i].id]=l;
        return;
    }
    int b1=0,b2=0;
    for(int i=ql;i<=qr;++i){
        if(q[i].op==1){
            int t=sum(q[i].y)-sum(q[i].x-1);
            if(q[i].k<=t)
                q1[++cnt1]=q[i],b1=cnt1;
            else q[i].k-=t,q2[++cnt2]=q[i],b2=cnt2;
        }
        else{
            if(q[i].y<=mid){if(i<=pos)add(q[i].x,q[i].k);q1[++cnt1]=q[i];}
            else q2[++cnt2]=q[i];
        }
    }
    while(spcnt)tree[sp[spcnt--]]=0;
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    if(b1)solve(l,mid,ql,ql+cnt1-1,ql+b1-1);
    if(b2)solve(mid+1,r,ql+cnt1,qr,ql+b2+cnt1-1);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    srand(0);
    n=read(),m=read();
    for(int i=1;i<=n;++i)q[++idx]={i,read(),1,2,0},root=merge(root,newnode(++idcnt,q[idx].y)),maxn=max(maxn,q[idx].y);
    for(int i=1;i<=m;++i){
        od=read(),x=read();
        if(od==1)y=read(),q[++idx]={find(root,x),find(root,y),read(),1,++qcnt};
        else if(od==2){
            y=read();
            maxn=max(maxn,y);
            int L,R,P=newnode(++idcnt,y);
            ++idx,q[idx]={P,y,1,2,0};
            split(root,x,L,R);
            root=merge(merge(L,P),R);
        }
        else {int tmp=find(root,x);++idx,q[idx]={tmp,t[tmp].val,-1,0,0},del(root,x);}
    }
    inorder(root);
    for(int i=1;i<=idx;++i){
        q[i].x=newid[q[i].x];
        if(q[i].op==1)q[i].y=newid[q[i].y];
    }
    solve(1,maxn,1,idx,idx);
    for(int i=1;i<=qcnt;++i)write(ans[i]),putchar_unlocked('\n');
    return 0;
}

T2 皓仔的太空人计划 题解

• 难度：绿
• 思路：按题目要求广搜即可

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,bx,by,ex,ey,b[105][105][55],vis[55],t[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
char c[105][105];
struct node
{
    int x,y;
};
vector<node>s;
struct statue
{
    int x,y,dis,bl;
    int sup;
};
int find(int x,int y)
{
    int p=0;
    for(node i:s)
    {
        if(i.x==x && i.y==y)return p;
        p++;
    }
    return -1;
}
signed main()
{
    cin>>n>>m;
    assert(n<=100 && m<=100);
    int x=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
            if(c[i][j]=='@')bx=i,by=j;
            if(c[i][j]=='X')ex=i,ey=j;
            if(c[i][j]=='E'){s.push_back({i,j});k++;}
            assert(c[i][j]=='@' || c[i][j]=='X' || c[i][j]=='O' || c[i][j]=='E' || c[i][j]=='.');
        }
    }
    queue<statue>q;
    q.push({bx,by,0,0,0LL});
    b[bx][by][0]=1;
    while(!q.empty())
    {
        int x=q.front().x,y=q.front().y,dis=q.front().dis,bl=q.front().bl,sup=q.front().sup;
        if(!vis[x+y-2])vis[x+y-2]=1;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+t[i][0],ny=y+t[i][1],ndis=dis+1;
            if(nx<=0 || ny<=0 || nx>n || ny>m || c[nx][ny]=='O')continue;
            if(c[nx][ny]=='X')
            {
                if(bl+10<=50)
                {
                    cout<<ndis;
                    return 0;
                }
            }
            else if(c[nx][ny]=='.')
            {
                int nbl=bl+10;
                if(nbl<50 && !b[nx][ny][nbl])
                {
                    b[nx][ny][nbl]=1;
                    q.push({nx,ny,ndis,nbl,sup});
                }
            }
            else if(c[nx][ny]=='E')
            {
                int nbl=max(0LL,bl-15),nid=find(nx,ny);
                int tmp=(sup>>nid)&1;
                if(!tmp && !b[nx][ny][nbl])
                {
                    b[nx][ny][nbl]=1;
                    q.push({nx,ny,ndis,nbl,sup+(1LL<<nid)});
                }
                else if(!b[nx][ny][nbl])
                {
                    b[nx][ny][nbl]=1;
                    q.push({nx,ny,ndis,bl+10,sup});
                }
            }
        }
    }
    cout<<-1;
    return 0;
}

T3 上帝造题1

第一眼，这个题不会太简单。

但是看了一眼样例，发现全是 $Yes$ 。

所以感觉题目的答案有可能也全是 $Yes$。

让我们来想想如何实现所有数一样，发现，当我们看 $n=1$ 的时候样例输出了 $Yes$，
那时候必须 $i=j$（其实已经全都一样了），显然突破口在这里，当 $i=j$ 的时候 $a_i = a_i + a_j = 2 * a_i, a_j = |a_i - a_j| = 0$ 所以
$a_i = a_j = 0$ 只要执行 $n$ 次所有数都会变为 $0$，这样全输出 $Yes$ 就行了。

T4 上帝造题2原题

条件 $\max>\text{sum}$ 与区间内去掉最大值后，剩余元素的和为负数其实等价。

枚举每个位置作为区间最大值，向左右扩展到第一个比它大的数为止（这是它作为最大值的最大范围）。

在这个范围内向左或向右累加（不含自身），一旦累加和变成负数，就找到了符合条件的区间。

每个元素最多被访问两次（左扩展一次、右扩展一次），总复杂度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		long long a[200010];
		for(int i=1;i<=n;i++) cin>>a[i];
		
		bool flag=false;
		
		for(int i=1;i<=n&&!flag;i++){
			long long sum=a[i];
			for(int j=i-1;j>=1&&a[j]<=a[i];j--){
				sum+=a[j];
				if(sum<a[i]){
					flag=true;
					break;
				}
			}
		}
		
		for(int i=1;i<=n&&!flag;i++){
			long long sum=a[i];
			for(int j=i+1;j<=n&&a[j]<=a[i];j++){
				sum+=a[j];
				if(sum<a[i]){
					flag=true;
					break;
				}
			}
		}
		
		if(flag) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}