ZR 集训 Day 7 – 模拟赛

ooliver 发布于 11 小时前 88 次阅读 OI

AI 摘要

看似全员AK，实则暗藏玄机！链表合并果子瞎搞1h变糖丸，大样例直接吐出正解；h≤20就拆成高低10位，括号序列分治双指针一秒统计。

2026 暑假 C 班模拟 Day1 之全员 AK | 正睿 OI

合并果子

一眼二分，check 直接瞎搞一通。

一开始地瞎搞了 1h 的链表，发现自己是糖丸。

C++
#include<bits/stdc++.h>
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;i<=n;i++){
        if(now<x) now+=a[i],j++;
        else now=a[i];
    }
    if(now<x&&j+1>k) return 0;
    return (j<=k);
}

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;i<=n;i++) cin>>a[i];
        int l=1,r=1e15,ans;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

旮旯给木

糖糖题，大样例把正解喂给你了，证明也很简单。

C++
#include<bits/stdc++.h>
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 <= 20，把每个数拆成高 10 位和低 10 位。
$cost(p,q)$ 可以拆成只与高位相关的部分和只与低位相关的部分之和：
$ cost(p,q) = high(p高, q高) + low(p低, q低)$

预处理出所有高-高贡献 $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<bits/stdc++.h>
using namespace std;

#define int long long
const int V=1<<10;
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;i<h;i++) cin>>a[i];
	for(int i=0;i<h;i++) cin>>b[i];
	for(int i=0;i<h;i++) cin>>c[i];
	for(int i=1;i<=n;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;id<V;id++){
		for(int i=0;i<V;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;i<10;i++){
			int cur=i&1,pre=cur^1;
			for(int j=0;j<V;j++) f[cur][j]=-1e9,g[cur][j]=-1e9;
			for(int j=0;j<V;j++){
				int bit=(j>>i)&1,nxt=j^(1<<i),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;i<V;i++) p[id][i]=f[1][i],q[id][i]=g[1][i];
	}
	int ans=-1e9;
	for(int i=0;i<V;i++) for(int j=0;j<V;j++){
		int s=0,t=0;
		for(int k=0;k<10;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];
	}
	cout<<ans<<' ';
	while(Q--){
		int x;
		cin>>x;
		int hx=x>>10,lx=x&(V-1);
		for(int i=0;i<V;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];
		}
		cout<<ans<<' ';
	}
	cout<<'\n';
	for(int i=0;i<V;i++) for(int j=0;j<V;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 < l$ 或 $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 < R \le n$，满足 $\displaystyle a[L] + a[R] \ge \max_{i=L}^{R} a[i]$。

只统计跨过中点 $mid$ 的区间对 $(L, R)$（即 $L \le mid < R$），然后在左右半边递归。这样每对 $(L, R)$ 会在 $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<bits/stdc++.h>
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(x<=sz){
			if(ver[x]!=t) ver[x]=t,tr[x]=0;
			tr[x]+=k;
			x+=x&-x;
		}
	}
	int sum(int x){
		if(x<0) return 0;
		x++;
		int res=0;
		while(x>0){
			if(ver[x]==t) res+=tr[x];
			x-=x&-x;
		}
		return res;
	}
}bl,br;

pair<int,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;i<=r;i++) mxv=max(mxv,a[i]),vr[++sr]={a[i],mxv};
	int i=1,j=1,ans=0;
	bl.init(),br.init();
	while(i<=sl||j<=sr){
		if(j>sr||(i<=sl&&vl[i].second<=vr[j].second)){
			int al=vl[i].first,blv=vl[i].second,nd=blv-al;
			if(nd<=mx) ans+=br.sum(mx)-(nd>0?br.sum(nd-1):0);
			bl.add(al,1),i++;
		}
		else{
			int ar=vr[j].first,brv=vr[j].second,nd=brv-ar;
			if(nd<=mx) ans+=bl.sum(mx)-(nd>0?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<n;i++) a[i+1]=a[i]+(s[i]=='('?1:-1);
	for(int i=0;i<=n;i++) mx=max(mx,a[i]);
	cout<<solve(0,n)<<"\n";
	return 0;
}