26.11.13 比赛记录
更新于 2026年11月15日约 2 分钟阅读
我宣布 T1>>T2。
T1 翻牌
原来是 ad-hoc,奋战 3h 没切出来。
注意到只有奇数位置的牌移到了偶数位置或者偶数位置的牌移到了奇数位置,才会翻身。初始假设所有牌都在偶数位置,需要挑 张放到奇数位置。这种操作带来的价值为 d[i]=(i&1)?a[i]-b[i]:b[i]-a[i]。降序排序挑前 个即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,a[N],b[N],d[N];
int main(){
cin>>T;
while(T--){
long long ans=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)d[i]=(i&1)?a[i]-b[i]:b[i]-a[i];
for(int i=1;i<=n;i++)ans+=(i&1)?b[i]:a[i];
sort(d+1,d+n+1,greater<int>());
for(int i=1;i<=(n+1)/2;i++)ans+=d[i];
cout<<ans<<'\n';
}
return 0;
}
T2 套盒
先把盒子排序,注意到一种方案,选取盒子的一个后缀作为外盒,一个前缀作为内盒,一定是不劣的。因此二分后缀的长度,把前缀尽可能放进后缀里构造出方案。如果后缀没有被装满就减小后缀长度,否则增加后缀长度。在此过程中取外盒数量的最小值即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,a[N],ans;
bool check(int s){
ans=n;
vector<int>aa,b,c;
for(int i=s;i<=n;i++){
b.push_back(a[i]-1);
c.push_back(a[i]/2);
}
for(int i=0,j=0;i<n-s+1;i++){
while(j<n-s+1&&c[j]<=b[i])
aa.push_back(c[j++]);
aa.push_back(b[i]);
}
int m=(n-s+1)*2;
for(int i=1,j=0;i<s;i++){
while(j<m&&aa[j]<a[i])j++;
if(j>=m)return 0;
ans--,j++;
}
return 1;
}
int solve(){
int l=1,r=n,res=n;
while(l<=r){
int mid=(l+r)/2;
if(check(mid))l=mid+1;
else r=mid-1;
res=min(res,ans);
}
return res;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
cout<<solve()<<'\n';
}
return 0;
}
T3 反冲
有区间操作,这题其实是一道数据结构题。注意到一个性质:任何时刻下,各粒子的相对顺序都和初始顺序相同,因为粒子撞到就湮灭了而不会互相穿过。
考虑使用线段树维护一段编号区间内粒子的信息。需要记录的是:当前区间存活粒子数量,最左端、最右端存活粒子编号,最左端、最右端存活粒子坐标,最左端、最右端存活粒子方向,相向、背向相邻粒子的最小间距。以及反转、位移的懒标记。像一个正常线段树一样去维护这些信息就行。需要注意一些细节,比如懒标记的顺序问题,我这里是先反转,再位移。如果位移 之后反转方向,就相当于先反转方向再位移 。还有坐标统一 以避免浮点数运算。具体见代码:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
const ll inf=4e18;
int n,q,x[N],v[N];
struct node{
/*
cnt:当前区间存活粒子数量
li,ri:最左端、最右端存活粒子的初始编号
lx,rx:最左端、最右端存活粒子的当前坐标(扩大2倍)
ld,rd:最左端、最右端存活粒子的当前方向(+1/-1)
mi1,mi2:(+1,-1)相向、背向相邻粒子的最小间距
inv,add:反转懒标记、位移懒标记
*/
int idx=0,cnt=0,li=0,ri=0,ld=0,rd=0;
ll lx=0,rx=0,mi1=inf,mi2=inf,add=0;
bool inv=0;
node *lc,*rc;
void apply_inv(){
if(!cnt)return;
ld=-ld,rd=-rd;
swap(mi1,mi2);
inv^=1,add=-add;
}
void apply_add(ll d){
if(!d||!cnt)return;
lx+=ld*d,rx+=rd*d;
if(mi1<inf)mi1-=d*2;
if(mi2<inf)mi2+=d*2;
add+=d;
}
void push_down(){
if(!cnt)return;
if(inv){
lc->apply_inv();
rc->apply_inv();
inv=0;
}
if(add){
lc->apply_add(add);
rc->apply_add(add);
add=0;
}
}
void push_up(){
if(!lc->cnt&&!rc->cnt){
cnt=0,mi1=mi2=inf;
return;
}
if(!lc->cnt||!rc->cnt){
node x=lc->cnt?*lc:*rc;
cnt=x.cnt,li=x.li,ri=x.ri;
ld=x.ld,rd=x.rd,lx=x.lx,rx=x.rx;
mi1=x.mi1,mi2=x.mi2;
return;
}
cnt=lc->cnt+rc->cnt;
li=lc->li,ri=rc->ri;
lx=lc->lx,rx=rc->rx;
ld=lc->ld,rd=rc->rd;
mi1=min(lc->mi1,rc->mi1);
mi2=min(lc->mi2,rc->mi2);
if(lc->rd==1&&rc->ld==-1)mi1=min(mi1,rc->lx-lc->rx);
if(lc->rd==-1&&rc->ld==1)mi2=min(mi2,rc->lx-lc->rx);
}
}tr[N<<2];
void build(node *u,int l,int r,int idx){
if(l==r){
u->idx=idx,u->cnt=1;
u->lx=u->rx=x[l];
u->ld=u->rd=v[l];
u->li=u->ri=l;
return;
}
int mid=(l+r)>>1;
u->lc=&tr[idx<<1];
u->rc=&tr[idx<<1|1];
build(u->lc,l,mid,idx<<1);
build(u->rc,mid+1,r,idx<<1|1);
u->push_up();
}
void range_inv(node *u,ll l,ll r){
if(!u->cnt||u->lx>r||u->rx<l)return;
if(l<=u->lx&&u->rx<=r){
u->apply_inv();
return;
}
u->push_down();
range_inv(u->lc,l,r);
range_inv(u->rc,l,r);
u->push_up();
}
pair<int,int> find(node *u){
u->push_down();
if(u->lc->mi1==0)return find(u->lc);
if(u->rc->mi1==0)return find(u->rc);
return {u->lc->ri,u->rc->li};
}
void del(node *u,int l,int r,int tar){
if(l==r){
u->cnt=0;
u->mi1=u->mi2=inf;
return;
}
int mid=(l+r)>>1;
u->push_down();
if(tar<=mid)del(u->lc,l,mid,tar);
else del(u->rc,mid+1,r,tar);
u->push_up();
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>x[i]>>v[i];
x[i]*=2;
}
build(tr+1,1,n,1);
node *rt=&tr[1];
while(q--){
ll l,r,d;
cin>>l>>r>>d;
l*=2,r*=2,d*=2;
range_inv(rt,l,r);
ll rem=d;
while(rt->cnt>=2&&rt->mi1!=inf&&rt->mi1<=2*rem){
rem-=rt->mi1/2;
rt->apply_add(rt->mi1/2);
auto [v1,v2]=find(rt);
del(rt,1,n,v1);
del(rt,1,n,v2);
}
rt->apply_add(rem);
cout<<rt->cnt<<'\n';
}
return 0;
}
T4 换环
GPT 给出的难度评价是:NOI/NOI+/CTS,*3200,qoj 8。可想而知这题很难,我不做了。