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\left[x\right]\left[y\right]$ 和低-低贡献 $lc\left[x\right]\left[y\right]$，其中 $x,y\mathrm{\in }[0,2^{10})$。 对于固定的一个数 p，我们想快速求出 $ma{x}_{q}cost(p,q)$。 设 $p$ 的高位为 $ph$，低位为 $pl$。则 $cost(p,q)=hc\left[ph\right]\left[qh\right]+lc\left[pl\right]\left[ql\right]$。 令 $f\left[ph\right]\left[ql\right]$ 表示已存在的数中，当另一个数的高位任意、低位为 $ql$ 时，$lc[pl][ql] $ 的最大值； $g\left[pl\right]\left[qh\right]$ 表示已存在的数中，当另一个数的低位任意、高位为 $qh$ 时，$hc\left[ph\right]\left[qh\right]$ 的最大值。 那么 $maxcost=ma{x}_{ql}$ ( $f\left[ph\right]\left[ql\right]+ma{x}_{qh}hc\left[ph\right]\left[qh\right]$ 与 $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\left[i\right]=\sum _{k=1}^i{v}_k(v_k=\pm 1),a\left[0\right]=0$$

原串是合法括号序列，因此对所有 $i$ 有 $a\left[i\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}0$，且 $a\left[n\right]=0$。

翻转区间 $[l,r]$ 后，对于位置 $i$：

• 若 $ir$，字符不变，新前缀和仍为 $a\left[i\right]$。

• 若 $l\text{[PARSE ERROR: Undefined("Command("le")")]}i\text{[PARSE ERROR: Undefined("Command("le")")]}r$，位置 $i$ 的字符变成了原位置 $l+r-i$ 的字符。因此新前缀和为：

$$a^{\prime }\left[i\right]=a[l-1]+\text{[PARSE ERROR: Undefined("Command("big")")]}\left(a\right[r]-a[l+r-i-1\left]\text{[PARSE ERROR: Undefined("Command("big")")]}\right)$$

翻转后串仍是合法括号序列的充要条件是所有 $a^{\prime }\left[i\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}0$。对于 $i\in [l,r]$，要求：

$$a[l-1]+a\left[r\right]-a[l+r-i-1]\text{[PARSE ERROR: Undefined("Command("ge")")]}0$$

当 $i$ 遍历 $[l,r]$ 时，$l+r-i-1$ 恰好遍历 $[l-1,r-1]$。因此上式等价于要求 $a[l-1]+a\left[r\right]$ 不小于这段区间中 $a$ 的最大值：

$$a[l-1]+a\left[r\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}{\underset{j=l-1}{\max }}^{r-1}a\left[j\right]$$

由于 $a\left[r\right]$ 本身就出现在该区间内且 $a\left[r\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}0$，把上界扩展到 $r$ 不改变条件，可得更对称的形式：

$$a[l-1]+a\left[r\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}{\underset{j=l-1}{\max }}^{r}a\left[j\right]$$

令 $L=l-1$，$R=r$，则原问题转化为：

统计所有 $0 \le L 只统计跨过中点 $mid$ 的区间对 $(L,R)$（即 $L \le mid 对于跨中点的区间，把最大值拆成左右两部分：

$$b\left[L\right]={\underset{i=L}{\max }}^{mid}a\left[i\right],b\left[R\right]={\underset{i=mid+1}{\max }}^{R}a\left[i\right]$$

显然 ${\underset{i=L}{\max }}^{R}a\left[i\right]=\max \left(b\right[L],b[R\left]\right)$，条件变为：

$$a\left[L\right]+a\left[R\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}\max \left(b\right[L],b[R\left]\right)$$

关键观察：$b$ 数组天然具有单调性。当 $L$ 从 $mid$ 向左移动时，覆盖范围扩大，$b\left[L\right]$ 只增不减；同理 $R$ 向右移动时 $b\left[R\right]$ 只增不减。

将左侧所有点 $\left(a\right[L],b[L\left]\right)$ 和右侧所有点 $\left(a\right[R],b[R\left]\right)$ 放在一起，按 $b$ 值从小到大处理。

处理过程中维护两个集合：已加入的左侧点、已加入的右侧点。当一个点被处理时，另一侧中所有已加入点的 $b$ 值都不超过当前点的 $b$ 值，因此当前点决定了这一批配对中的最大值。

• 当前处理左侧点 $L$：另一侧已加入的 $R$ 满足 $b\left[R\right]\text{[PARSE ERROR: Undefined("Command("le")")]}b\left[L\right]$，故 $\max =b\left[L\right]$。条件化简为： $$a\left[R\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}b\left[L\right]-a\left[L\right]$$ 查询右侧已加入点中 $a$ 值 $\text{[PARSE ERROR: Undefined("Command("ge")")]}$ 该阈值的个数即可。

• 当前处理右侧点 $R$：对称地，条件为： $$a\left[L\right]\text{[PARSE ERROR: Undefined("Command("ge")")]}b\left[R\right]-a\left[R\right]$$ 查询左侧已加入点中 $a$ 值 $\text{[PARSE ERROR: Undefined("Command("ge")")]}$ 该阈值的个数。

处理完当前点后，将其加入对应侧的集合。

每对 $(L,R)$ 会在 $b$ 值较大的那一方被处理时被统计恰好一次，不重不漏。

需要支持的操作：

• 向集合中加入一个 $a$ 值；

• 查询集合中 $a$ 值 $\text{[PARSE ERROR: Undefined("Command("ge")")]}x$ 的元素个数。

$a$ 的值域在 $[0,n]$ 范围内，用树状数组即可在 $\text{[PARSE ERROR: Undefined("Command("mathcal")")]}O\left(\log n\right)$ 时间内完成每次操作。由于归并过程中每个元素各引起一次加入和若干次查询，单层分治的复杂度为 $\text{[PARSE ERROR: Undefined("Command("mathcal")")]}O\left(n\log n\right)$。

分治共 $\log n$ 层，总时间复杂度 $\text{[PARSE ERROR: Undefined("Command("mathcal")")]}O\left(n{\log }^{2}n\right)$，常数很小。

代码：

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.init();
	while(isl||jsr){
		if(j>sr||(isl&&vl[i].secondvr[j].second)){
			int al=vl[i].first,blv=vl[i].second,nd=blv-al;
			if(ndmx) 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(ndmx) 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;in;i++) a[i+1]=a[i]+(s[i]=='('?1:-1);
	for(int i=0;in;i++) mx=max(mx,a[i]);
	coutsolve(0,n)"\n";
	return 0;
}`