CXXP#2 赛后总结帖

userId_undefined
wcqk
禁言
出题人

2026-08-06 14:16:43

发布于：浙江

1481阅读
0回复
0点赞

出锅致歉：时间没选好，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 的操作

赛后总结

本次比赛共 880880 人报名，154154 人提交，100100 人有分。

AK 人数 22 人。

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

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

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

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

CXXP#2 T1 新版题解

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

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

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

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

对于 100%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 岁月成碑 旧版题解

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

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

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

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

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

T4 上帝造题2原题

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

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

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

每个元素最多被访问两次（左扩展一次、右扩展一次），总复杂度 O(n)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;
	}
}
userId_undefined
去预览
0/2000

全部评论 36

  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖
    置顶

    题目顺序止战之殇

    1周前 来自 浙江

    9
  • userId_undefined
    MLE_Automaton
    CSP-S一等奖

    请问T4中，如果选择i=j，a_i会被替换为0还是2a_i？

    2026-08-03 来自 天津

    25
  • userId_undefined
    wcqk
    禁言
    出题人

    此贴禁水

    2026-08-05 来自 浙江

    16
    • userId_undefined
      AK.LiuYH☠
      回复
      wcqk

      我错了，别拉黑我啊

      1周前 来自 浙江

      8
    • userId_undefined
      AK.LiuYH☠
      回复
      wcqk

      我能问一个问题吗，夏老师吃小孩（见头像）是谁啊

      1周前 来自 浙江

      6
    • userId_undefined
      炁༒旸
      回复
      AK.LiuYH☠

      是夏老师的心腹大患

      1周前 来自 上海

      5
  • userId_undefined
    学
    时空双修者荣耀黄金勇敢小狗快乐小狗

    T1诗人

    2026-08-04 来自 浙江

    12
    • userId_undefined
      学
      回复
      学

      为什么ACGO端T1显示500ms，64MB?

      2026-08-04 来自 浙江

      8
    • userId_undefined
      学
      回复
      学

      @wcqk

      2026-08-04 来自 浙江

      7
    • userId_undefined
      wcqk
      回复
      学

      是的，500ms，64MB?

      2026-08-04 来自 浙江

      6
  • userId_undefined
    咕咕咕
    8月全勤卷王出道萌新时空双修者荣耀黄金

    问一下T1那里，当操作1的k为0时怎么定义这个操作

    2026-08-04 来自 江西

    9
  • userId_undefined
    暴力出奇迹，结果TLE
    小有名气8月全勤卷王7月全勤卷王时空双修者快乐小狗荣耀黄金

    所以T4T4用的是官方比赛的T4T4还是新的那个。
    @wcqk

    2026-08-03 来自 上海

    6
  • userId_undefined
    cjj
    小有名气时间刺客时空双修者永恒钻石CSP-J一等奖快乐小狗

    最后一题，ZDZL OJ和ACGO的题目不一样@ZDZL

    2026-08-03 来自 广东

    6
    • userId_undefined
      wcqk
      回复
      cjj

      是吗

      2026-08-03 来自 浙江

      5
    • userId_undefined
      cjj
      回复
      wcqk

      是的，ZDZL OJ第四题是判断能否让所有数通过操作都相等而且No的‘o’是小写

      2026-08-03 来自 广东

      6
    • userId_undefined
      wcqk
      回复
      cjj

      那就不管。就不一样吧

      2026-08-03 来自 浙江

      6
  • userId_undefined
    TQjc
    荣耀黄金

    如果T1AK的是老师，那我现在AK还来的急吗

    1周前 来自 湖北

    3
    • userId_undefined
      wcqk
      回复
      TQjc

      不是我们的老湿。是参赛者。

      1周前 来自 浙江

      2
  • userId_undefined
    cjdst
    禁言
    小有名气尊贵铂金CSP-S一等奖

    感觉认真做 T1 的赤道大变了

    1周前 来自 浙江

    2
    • userId_undefined
      wcqk
      回复
      cjdst

      是的 T1 = 大汾题

      1周前 来自 浙江

      1
    • userId_undefined
      Xylophone
      回复
      cjdst

      吃不够的为什么不来找我要

      1周前 来自 广东

      1
    • userId_undefined
      Eucatastrophe‌
      回复
      cjdst

      注意到≈IOI Day1，不知道有没有出越南小伙

      4天前 来自 浙江

      0
  • userId_undefined
    TQjc
    荣耀黄金

    原来难度是倒着的嘛

    1周前 来自 湖北

    2
  • userId_undefined
    137****8558
    倔强青铜时间刺客空间掌握者

    上面那些链接是一个吗

    1周前 来自 黑龙江

    2
    • userId_undefined
      wcqk
      回复
      137****8558

      ？请你组织好你的语言

      1周前 来自 浙江

      2
    • userId_undefined
      TQjc
      回复
      wcqk

      言语的你好织组你请？

      4天前 来自 湖北

      1
  • userId_undefined
    Xylophone
    传道者

    为什么 wcqk 和 cjdst 全禁言了

    2天前 来自 广东

    1
  • userId_undefined
    J
    进制转换师快排信徒→排序之神维度操控者素数猎手ASCII炼金师俄罗斯套娃大师

    nb

    1周前 来自 广东

    1
  • userId_undefined
    杨一诺
    分支·分支解题者倔强青铜I/O·IO入门者循环·循环打卡人

    1

    1周前 来自 安徽

    1
  • userId_undefined
    137****8558
    倔强青铜时间刺客空间掌握者

    cool

    1周前 来自 黑龙江

    1
  • userId_undefined
    静逐浪（互关）

    为什么最近好多人都被禁言了？

    9小时前 来自 上海

    0
  • userId_undefined
    张菜~喵
    空间掌握者I/O·IO入门者

    哇

    10小时前 来自 重庆

    0
  • userId_undefined
    lxy
    时间刺客空间掌握者7月全勤卷王I/O·IO入门者分支·分支解题者维度操控者

    666

    11小时前 来自 浙江

    0
  • userId_undefined
    _Xcap
    贪心·贪心尝试者时间刺客循环·循环打卡人

    dl

    11小时前 来自 浙江

    0
  • userId_undefined
    ๓₯㎕神㎕₯๓
    空间掌握者出道萌新

    1

    3天前 来自 广东

    0

热门讨论