ZR 集训 Day7 - 模拟赛 · ooliver

2026 暑假 C 班模拟 Day1 之全员 AK | 正睿 OI 合并果子一眼二分，check 直接瞎搞一通。一开始地瞎搞了 1h 的链表，发现自己是糖丸。 C++ #include using namespace std; #define int long long const int N=1e6+5; int c,T,n,k; int a[N]; bool check(int x){ int j=0,now=a[1]; for(int i=2;ik) return 0; return (j>c>>T; while(T--){ cin>>n>>k; for(int i=1;i>a[i]; int l=1,r=1e15,ans; while(l>1; if(check(mid)) l=mid+1,ans=mid; else r=mid-1; } cout `#include using namespace std; #define int long long const int N=1e6+5; int c,T,n,k; int a[N]; bool check(int x){ int j=0,now=a[1]; for(int i=2;in;i++){ if(nowx) now+=a[i],j++; else now=a[i]; } if(nowx&&j+1>k) return 0; return (jk); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>c>>T; while(T--){ cin>>n>>k; for(int i=1;in;i++) cin>>a[i]; int l=1,r=1e15,ans; while(lr){ int mid=(l+r)>>1; if(check(mid)) l=mid+1,ans=mid; else r=mid-1; } coutans"\n"; } return 0; }` 旮旯给木糖糖题，大样例把正解喂给你了，证明也很简单。 C++ #include using namespace std; int T,x; bool solve(int x){ while(!(x&1)) x>>=1; if(x==1) return 1; return 0; } signed main(){ cin>>T; while(T--){ cin>>x; cout `#include using namespace std; int T,x; bool solve(int x){ while(!(x&1)) x>>=1; if(x==1) return 1; return 0; } signed main(){ cin>>T; while(T--){ cin>>x; cout(solve(x)?"Win\n":"Lose\n"); } return 0; }` 晚安。注意到 h 预处理出所有高-高贡献 hc[x][y] 和低-低贡献 lc[x][y]，其中 x,y ∈ [0, 2^10)。对于固定的一个数 p，我们想快速求出 max_q cost(p,q)。设 p 的高位为 ph，低位为 pl。则 cost(p,q) = hc[ph][qh] + lc[pl][ql]。令 f[ph][ql] 表示已存在的数中，当另一个数的高位任意、低位为 ql 时，$lc[pl][ql] $ 的最大值； g[pl][qh] 表示已存在的数中，当另一个数的低位任意、高位为 qh 时，hc[ph][qh] 的最大值。那么 max cost = max_{ql} ( f[ph][ql] + max_{qh} hc[ph][qh] 与 g 相关的组合 ) 实际上通过维护 f 和 g，插入一个数时只需枚举另一维的所有可能值（共 2^10 种）更新答案。为了快速获得 f 和 g 的初始值（对于存在的数），可以用 DP 逐位处理：对于每个固定的高位 id，初始知道哪些低位存在，DP 后得到对于任意低位 x，当配对数的低位为 x 时的最大低位贡献。整体复杂度为 O(2^{h/2} * h + (n+q) * 2^{h/2})，卡卡就过了。代码 C++ #include using namespace std; #define int long long const int V=1>n>>h>>Q; for(int i=0;i>a[i]; for(int i=0;i>b[i]; for(int i=0;i>c[i]; for(int i=1;i>x; int hx=x>>10,lx=x&(V-1); p[hx][lx]=1,q[lx][hx]=1; } for(int id=0;id>i)&1,nxt=j^(1f[cur][j]) f[cur][j]=f[pre][j]; if(f[pre][j]+a[i]+c[i]>f[cur][nxt]) f[cur][nxt]=f[pre][j]+a[i]+c[i]; if(g[pre][j]>g[cur][j]) g[cur][j]=g[pre][j]; if(g[pre][j]+a[u]+c[u]>g[cur][nxt]) g[cur][nxt]=g[pre][j]+a[u]+c[u]; }else{ if(f[pre][j]+a[i]+c[i]>f[cur][nxt]) f[cur][nxt]=f[pre][j]+a[i]+c[i]; if(f[pre][j]+a[i]+b[i]>f[cur][j]) f[cur][j]=f[pre][j]+a[i]+b[i]; if(g[pre][j]+a[u]+c[u]>g[cur][nxt]) g[cur][nxt]=g[pre][j]+a[u]+c[u]; if(g[pre][j]+a[u]+b[u]>g[cur][j]) g[cur][j]=g[pre][j]+a[u]+b[u]; } } } for(int i=0;i>k)&1,bq=(j>>k)&1,u=k+10; s+=(bp|bq)*a[u]+(bp&bq)*b[u]+(bp^bq)*c[u]; t+=(bp|bq)*a[k]+(bp&bq)*b[k]+(bp^bq)*c[k]; } vh[i][j]=s,vl[i][j]=t; if(p[i][j]+q[j][i]>ans) ans=p[i][j]+q[j][i]; } cout>x; int hx=x>>10,lx=x&(V-1); for(int i=0;ip[hx][i]) p[hx][i]=vl[lx][i]; if(vh[hx][i]>q[lx][i]) q[lx][i]=vh[hx][i]; if(p[hx][i]+q[i][hx]>ans) ans=p[hx][i]+q[i][hx]; if(p[i][lx]+q[lx][i]>ans) ans=p[i][lx]+q[lx][i]; } cout>c>>T; while(T--) solve(); return 0; } `#include using namespace std; #define int long long const int V=110; int a[30],b[30],c[30]; int p[V][V],q[V][V],vh[V][V],vl[V][V]; int f[2][V],g[2][V]; void solve(){ int n,h,Q; cin>>n>>h>>Q; for(int i=0;ih;i++) cin>>a[i]; for(int i=0;ih;i++) cin>>b[i]; for(int i=0;ih;i++) cin>>c[i]; for(int i=1;in;i++){ int x; cin>>x; int hx=x>>10,lx=x&(V-1); p[hx][lx]=1,q[lx][hx]=1; } for(int id=0;idV;id++){ for(int i=0;iV;i++){ if(p[id][i]) f[1][i]=0; else f[1][i]=-1e9; if(q[id][i]) g[1][i]=0; else g[1][i]=-1e9; } for(int i=0;i10;i++){ int cur=i&1,pre=cur^1; for(int j=0;jV;j++) f[cur][j]=-1e9,g[cur][j]=-1e9; for(int j=0;jV;j++){ int bit=(j>>i)&1,nxt=j^(1i),u=i+10; if(bit==0){ if(f[pre][j]>f[cur][j]) f[cur][j]=f[pre][j]; if(f[pre][j]+a[i]+c[i]>f[cur][nxt]) f[cur][nxt]=f[pre][j]+a[i]+c[i]; if(g[pre][j]>g[cur][j]) g[cur][j]=g[pre][j]; if(g[pre][j]+a[u]+c[u]>g[cur][nxt]) g[cur][nxt]=g[pre][j]+a[u]+c[u]; }else{ if(f[pre][j]+a[i]+c[i]>f[cur][nxt]) f[cur][nxt]=f[pre][j]+a[i]+c[i]; if(f[pre][j]+a[i]+b[i]>f[cur][j]) f[cur][j]=f[pre][j]+a[i]+b[i]; if(g[pre][j]+a[u]+c[u]>g[cur][nxt]) g[cur][nxt]=g[pre][j]+a[u]+c[u]; if(g[pre][j]+a[u]+b[u]>g[cur][j]) g[cur][j]=g[pre][j]+a[u]+b[u]; } } } for(int i=0;iV;i++) p[id][i]=f[1][i],q[id][i]=g[1][i]; } int ans=-1e9; for(int i=0;iV;i++) for(int j=0;jV;j++){ int s=0,t=0; for(int k=0;k10;k++){ int bp=(i>>k)&1,bq=(j>>k)&1,u=k+10; s+=(bp|bq)*a[u]+(bp&bq)*b[u]+(bp^bq)*c[u]; t+=(bp|bq)*a[k]+(bp&bq)*b[k]+(bp^bq)*c[k]; } vh[i][j]=s,vl[i][j]=t; if(p[i][j]+q[j][i]>ans) ans=p[i][j]+q[j][i]; } coutans' '; while(Q--){ int x; cin>>x; int hx=x>>10,lx=x&(V-1); for(int i=0;iV;i++){ if(vl[lx][i]>p[hx][i]) p[hx][i]=vl[lx][i]; if(vh[hx][i]>q[lx][i]) q[lx][i]=vh[hx][i]; if(p[hx][i]+q[i][hx]>ans) ans=p[hx][i]+q[i][hx]; if(p[i][lx]+q[lx][i]>ans) ans=p[i][lx]+q[lx][i]; } coutans' '; } cout'\n'; for(int i=0;iV;i++) for(int j=0;jV;j++) p[i][j]=q[i][j]=vh[i][j]=vl[i][j]=0; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int c,T; cin>>c>>T; while(T--) solve(); return 0; }` 括号序列题解将 ( 看作 +1，) 看作 -1。记原串的前缀和为： a[i] = \sum_{k=1}^{i} v_k \quad (v_k = \pm 1),\qquad a[0] = 0 原串是合法括号序列，因此对所有 i 有 a[i] \ge 0，且 a[n] = 0。翻转区间 [l, r] 后，对于位置 i：若 i r，字符不变，新前缀和仍为 a[i]。若 l \le i \le r，位置 i 的字符变成了原位置 l + r - i 的字符。因此新前缀和为： a'[i] = a[l-1] + \big( a[r] - a[l+r-i-1] \big) 翻转后串仍是合法括号序列的充要条件是所有 a'[i] \ge 0。对于 i \in [l, r]，要求： a[l-1] + a[r] - a[l+r-i-1] \ge 0 当 i 遍历 [l, r] 时，l+r-i-1 恰好遍历 [l-1, r-1]。因此上式等价于要求 a[l-1] + a[r] 不小于这段区间中 a 的最大值： a[l-1] + a[r] \ge \max_{j = l-1}^{r-1} a[j] 由于 a[r] 本身就出现在该区间内且 a[r] \ge 0，把上界扩展到 r 不改变条件，可得更对称的形式： a[l-1] + a[r] \ge \max_{j = l-1}^{r} a[j] 令 L = l-1，R = r，则原问题转化为：统计所有 $0 \le L 只统计跨过中点 mid 的区间对 (L, R)（即 $L \le mid 对于跨中点的区间，把最大值拆成左右两部分： b[L] = \max_{i=L}^{mid} a[i], \qquad b[R] = \max_{i=mid+1}^{R} a[i] 显然 \max_{i=L}^{R} a[i] = \max(b[L], b[R])，条件变为： a[L] + a[R] \ge \max(b[L], b[R]) 关键观察：b 数组天然具有单调性。当 L 从 mid 向左移动时，覆盖范围扩大，b[L] 只增不减；同理 R 向右移动时 b[R] 只增不减。将左侧所有点 (a[L], b[L]) 和右侧所有点 (a[R], b[R]) 放在一起，按 b 值从小到大处理。处理过程中维护两个集合：已加入的左侧点、已加入的右侧点。当一个点被处理时，另一侧中所有已加入点的 b 值都不超过当前点的 b 值，因此当前点决定了这一批配对中的最大值。当前处理左侧点 L：另一侧已加入的 R 满足 b[R] \le b[L]，故 \max = b[L]。条件化简为： a[R] \ge b[L] - a[L] 查询右侧已加入点中 a 值 \ge 该阈值的个数即可。当前处理右侧点 R：对称地，条件为： a[L] \ge b[R] - a[R] 查询左侧已加入点中 a 值 \ge 该阈值的个数。处理完当前点后，将其加入对应侧的集合。每对 (L, R) 会在 b 值较大的那一方被处理时被统计恰好一次，不重不漏。需要支持的操作：向集合中加入一个 a 值；查询集合中 a 值 \ge x 的元素个数。 a 的值域在 [0, n] 范围内，用树状数组即可在 \mathcal{O}(\log n) 时间内完成每次操作。由于归并过程中每个元素各引起一次加入和若干次查询，单层分治的复杂度为 \mathcal{O}(n \log n)。分治共 \log n 层，总时间复杂度 \mathcal{O}(n \log^2 n)，常数很小。代码： C++ #include using namespace std; #define int long long const int N=2e6+5; int n,mx,cur; string s; int a[N]; struct bit{ int tr[N],ver[N],t; void init(){t=++cur;} void add(int x,int k){ x++; int sz=mx+5; while(x0){ if(ver[x]==t) res+=tr[x]; x-=x&-x; } return res; } }bl,br; pair vl[N],vr[N]; int calc(int l,int mid,int r){ int mxv=a[mid],sl=0,sr=0; for(int i=mid;i>=l;i--) mxv=max(mxv,a[i]),vl[++sl]={a[i],mxv}; mxv=a[mid+1]; for(int i=mid+1;isr||(i0?br.sum(nd-1):0); bl.add(al,1),i++; } else{ int ar=vr[j].first,brv=vr[j].second,nd=brv-ar; if(nd0?bl.sum(nd-1):0); br.add(ar,1),j++; } } return ans; } int solve(int l,int r){ if(l>=r) return 0; int mid=(l+r)>>1; int ans=solve(l,mid)+solve(mid+1,r); ans+=calc(l,mid,r); return ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>s; n=s.size(); for(int i=0;i `#include using namespace std; #define int long long const int N=2e6+5; int n,mx,cur; string s; int a[N]; struct bit{ int tr[N],ver[N],t; void init(){t=++cur;} void add(int x,int k){ x++; int sz=mx+5; while(xsz){ if(ver[x]!=t) ver[x]=t,tr[x]=0; tr[x]+=k; x+=x&-x; } } int sum(int x){ if(x0) return 0; x++; int res=0; while(x>0){ if(ver[x]==t) res+=tr[x]; x-=x&-x; } return res; } }bl,br; pairint,int> vl[N],vr[N]; int calc(int l,int mid,int r){ int mxv=a[mid],sl=0,sr=0; for(int i=mid;i>=l;i--) mxv=max(mxv,a[i]),vl[++sl]={a[i],mxv}; mxv=a[mid+1]; for(int i=mid+1;ir;i++) mxv=max(mxv,a[i]),vr[++sr]={a[i],mxv}; int i=1,j=1,ans=0; bl.init(),br.in…