今天是 mx 的 NOIP2025 模拟 2。写了前两题。
Luogu P14520 战争游戏
打gen来
第一眼猜答案前半部分是 (0)，后半部分是 (1)，看了看大样例发现猜对了。
然后想想造成这个的原因大概是两人都倾巢对拼，然后哪边多哪边赢。
然后这就是个前缀和吧，写一写。
然后被第二个大样例卡了。
想了想又发现 L 可以先手吃一个 K 的格子，但是 K 也有可能吃回来。
这样的话好像就不能确定了啊，但是别急，我们继续猜俩人顶多互吃一次。
然后这样如果 L 吃了一个还能接着吃，K 就要把这个退回去防止被吃。
如果 L 吃了一个结果 K 能吃回来，那么 L 就不能往前吃。
如果 L 不能吃，那么 L 应该把自己退回来。
然后这样 L 可能会一直退到自己老家 (1) 号格子，然后这时候 K 只能倾巢对拼数量了，这种情况对于 K 也一样。这证明我们猜对了。
于是前缀和写写就行了。赛时因为忘了 K 还能退挂了 8pts，竟然只挂了 8pts。
92pts code
Show me the code
#define rd read() #define mkp make_pair #define ls p<<1 #define rs p<<1|1 #define rep(i,a,b) for( int i=(a); i<=(b); ++i) #define per(i,a,b) for( int i=(a); i>=(b); --i) #include<bits/stdc++.h> using namespace std; typedef long long i64; typedef unsigned long long u64; typedef unsigned int u32; typedef __int128 i128; i64 read(){ i64 x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } void init(){ } int a[200005]; void solve(){ int n;cin>>n; i64 sum=0; for(int i=1;i<=n;i++){ a[i]=rd; sum+=a[i]; } i64 ps=0; int lk=0; for(int i=1;i<n;i++){ ps+=a[i]; i64 p2=ps; if(a[i]>a[i+1]){ i64 t1=a[i]+a[i+1]; if(a[i+2]>=t1){ p2-=a[i]; } else p2+=a[i+1]; } if(p2<=sum-p2&&!lk)cout<<0; else {lk=1;cout<<1;} } cout<<'n'; return ; } int main(){ int T;cin>>T; while(T--){ init();solve(); } return 0; } 100pts code
Show me the code
#define rd read() #define mkp make_pair #define ls p<<1 #define rs p<<1|1 #define rep(i,a,b) for( int i=(a); i<=(b); ++i) #define per(i,a,b) for( int i=(a); i>=(b); --i) #include<bits/stdc++.h> using namespace std; typedef long long i64; typedef unsigned long long u64; typedef unsigned int u32; typedef __int128 i128; i64 read(){ i64 x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } void init(){ } int a[200005]; void solve(){ int n;cin>>n; i64 sum=0; for(int i=1;i<=n;i++){ a[i]=rd; sum+=a[i]; } i64 ps=0; int lk=0; for(int i=1;i<n;i++){ ps+=a[i]; i64 p2=ps; if(a[i]>a[i+1]&&a[i]+a[i+1]>a[i+2]){ p2+=a[i+1]; } if(p2<=sum-p2&&!lk)cout<<0; else {lk=1;cout<<1;} } cout<<'n'; return ; } int main(){ int T;cin>>T; while(T--){ init();solve(); } return 0; } Luogu P14521 加减乘除
长且了，于是建议评绿，于是：
其实赛时想的挺快的，就是钦定用 (1) 开始从根开始走走走，每到一个点加一下，过一个边就能根据相对大小算出能到这个的初值范围。
然后能到这个点的前提是之前也能到，于是处理完范围之后再从初始点开始跑 DFS，过程把区间取个交即可。
如果无根树还可做吗？问题出在可以在某些点横跳攒值。
询问离线即可。最初写了一版还以为询问都很小，结果一打开大样例直接傻眼了，还好写的代码加上离散化就行了。
然后就要从 (-10^{18}) 开始走了。
又要用 __int128，然后大样例大的离谱上了快读。
读题这一块。
code
Show me the code
#define rd read() #define mkp make_pair #define ls p<<1 #define rs p<<1|1 #define rep(i,a,b) for( int i=(a); i<=(b); ++i) #define per(i,a,b) for( int i=(a); i>=(b); --i) #include<bits/stdc++.h> using namespace std; typedef long long i64; typedef unsigned long long u64; typedef unsigned int u32; typedef __int128 i128; i64 read(){ i64 x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } const int N=5e5+1145; struct edge{ int v; i64 l,r; }; pair<i128,i128> rg[N]; vector<edge> e[N]; char op[N]; i64 dt[N]; vector<i64> ql,dis; vector<i64>::iterator rb; void dfs(int u,int fa,i128 d){ if(op[u]=='+'){d+=dt[u];} else d-=dt[u]; for(edge s:e[u]){ int v=s.v; if(v==fa)continue; i64 l=s.l; i64 r=s.r; if(d<l){ i128 rel=(i128)(-1e18)+(l-d); i128 rer=rel+r-l; rg[v].first=rel; rg[v].second=rer; } else if(l<=d&&d<=r){ i128 rel=(i128)-1e18; i128 rer=rel+r-d; rg[v].first=rel; rg[v].second=rer; } else{ rg[v].first=(i128)1e30; rg[v].second=(i128)-1e30; } dfs(v,u,d); } return ; } i64 det[1000999]; void dfs2(int u,int fa,i128 l,i128 r){ l=max(l,rg[u].first); r=min(r,rg[u].second); int llb,rrb; llb=lower_bound(dis.begin(),rb,l)-dis.begin(); rrb=upper_bound(dis.begin(),rb,r)-dis.begin()-1; if(llb<=rrb){det[llb]++;det[rrb+1]--;} for(edge s:e[u]){ int v=s.v; if(v==fa)continue; dfs2(v,u,l,r); } return ; } int main(){ int n,q;cin>>n>>q; for(int i=2;i<=n;i++){ int v;i64 l,r; v=rd;l=rd;r=rd; e[i].push_back(edge{v,l,r}); e[v].push_back(edge{i,l,r}); } for(int i=1;i<=n;i++){ cin>>op[i]>>dt[i]; } for(int i=1;i<=q;i++){ i64 mr=rd; ql.push_back(mr); dis.push_back(mr); } sort(dis.begin(),dis.end()); rb=unique(dis.begin(),dis.end()); rg[1].first=(i64)-1e18; rg[1].second=(i64)1e18; dfs(1,0,-1e18); dfs2(1,0,-1e18,1e18); for(int i=0;i<=q;i++){ det[i]=det[i-1]+det[i]; } for(i64 v:ql){ int wp=lower_bound(dis.begin(),rb,v)-dis.begin(); cout<<det[wp]<<'n'; } return 0; } 再找个时间写写昨晚的猎奇 ABC，还要去背一下 pbds 科技。
