比赛页面
T1. P14520 战争游戏
令 \(s[l,r]=a_l+\dots+a_r\)。
我们考虑初始状态下，小 L 占据 \([1,i]\)，小 K 占据 \([i+1,n]\)。
若 \(s[1,i]>s[i+1,n]\)，显然小 L 可以将所有兵力都转移到 \(1\) 处，再一举消灭所有小 K 的兵力。
若 \(s[1,i]\le s[i+1,n]\)，小 L 想战胜小 K 就必须夺取部分小 K 的兵力。而小 L 唯一的机会就是第一次操作，因为在这之后小 K 可以将所有兵力都转移到 \(n\) 处。
此时，小 L 能在第一步夺取成功并能取胜，当且仅当：
- \(a[i]>a[i+1]\)（小 L 能吃过去）
- \(a[i+2]<a[i]+a[i+1]\)（小 K 不能吃回来）
- \(s[1,i+1]>s[i+2,n]\)（夺取后能取胜）
时间复杂度 \(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int t,n,a[N],s[N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];for(int i=1;i<n;i++){if(s[i]>s[n]-s[i]||(a[i]>a[i+1]&&a[i+2]<a[i]+a[i+1]&&s[i+1]>s[n]-s[i+1])) cout<<"1";else cout<<"0";}cout<<"\n";}return 0;
}
T2. P14521 加减乘除
显然从根节点走到某个节点所累加的数值是固定的，我们将区间的左右端点都减去这个数值，就不需要再考虑数值累加了。
原问题转化为：初始拥有一个数值，只能走区间包含该数值的边，能到达多少节点。
将每个节点到根路径上的区间取一个交集，即询问数值被多少节点的区间覆盖。
离散化一下，前缀和即可解决。
时间复杂度 \(O(n\log n+q)\)。
赛时抽了写的树状数组，将就看。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define eb emplace_back
using namespace std;
const int N=5e5+5,Q=1e6+5;
int n,q,a[N],rt,b[2*N+Q],tn,qr[Q];
struct Ed{int to,l,r;};
struct Sg{int l,r;};
vector<Sg> s;
vector<Ed> G[N];
inline void dfs(int u,int c,int l,int r){c+=a[u];if(l<=r){b[++tn]=l,b[++tn]=r+1;s.eb(Sg{l,r+1});}for(Ed i:G[u]){dfs(i.to,c,max(l,i.l-c),min(r,i.r-c));}
}
inline int lb(int x){return x&-x;}
struct BIT{int s[2*N+Q];inline void chp(int x,int v){for(;x<=tn;x+=lb(x)) s[x]+=v;}inline int qry(int x){int a=0;for(;x;x-=lb(x)) a+=s[x];return a;}
}koishi;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=2,f,l,r;i<=n;i++){cin>>f>>l>>r;G[f].eb(Ed{i,l,r});}for(int i=1;i<=n;i++){char c;cin>>c>>a[i];if(c=='-') a[i]=-a[i];}dfs(1,0,-1e18,1e18);for(int i=1;i<=q;i++) cin>>qr[i],b[++tn]=qr[i];sort(b+1,b+1+tn),tn=unique(b+1,b+1+tn)-b-1;for(Sg i:s){i.l=lower_bound(b+1,b+1+tn,i.l)-b;i.r=lower_bound(b+1,b+1+tn,i.r)-b;koishi.chp(i.l,1);koishi.chp(i.r,-1);}for(int i=1;i<=q;i++){qr[i]=lower_bound(b+1,b+1+tn,qr[i])-b;cout<<koishi.qry(qr[i])<<"\n";}return 0;
}
T3. P14522 空之碎物
\(\ominus\)
等题解出了补。