0906题解

kcs007 超级无敌管理员 LV 8 SU ~ 2025-9-7 13:36:24

T0选数

专门出的一个搜索题。

我们考虑 $dfs(i,x,y,now)$ 。

此处 $i$ 表示该考虑第 $i$ 个质数的归属了，当前分别是 $x,y$ ，当前一共有 $now$ 个不同的质因子。

那么下一次 $dfs$ 肯定是 $dfs(i+1,x\times p[i]^t,y,now+1)$ ，或者是 $dfs(i+1,x,y\times p[i]^t,now+1)$ ，或者是 $dfs(i+1,x,y,now)$ 。

需要注意的是，这个过程中很容易乘爆 $long\ long$ ，要么用 $int128$ ，要么用除法来保证不会乘爆，比如if (a*b<=n)可以改写乘if (a<=n/b)。

剪枝的话很容易想到，就是假设后面都用第 $i,i+1,...,$ 种质数，加上当前的 $now$ 都凑不够目前的 $best$ ，那就直接不用搜了。

#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
using namespace std;
int p[maxn+5],prime[maxn],tot;
ll n;
ll best=0,num=0,ok;
int zd=0;
map<pair<ll,ll>,int> vis;
void dfs(ll i,ll x,ll y,ll now)
{
	ll tx=x,ty=y,tt=0,ii=i;
	while (tx*prime[ii]<=n) {tx*=prime[ii++]; tt++;}
	ii=i;
	while (ty*prime[ii]<=n) {ty*=prime[ii++]; tt++;}
//	cout<<i<<" "<<x<<" "<<y<<endl;
	zd=max(zd+0ll,i);
	if (x<0 || y<0) exit(1);
	if (tt+now<best) return;
	if (now>=best)
	{
		if (now>best) best=now,num=1,ok=i;
		else num++,ok=max(i,ok);
	}
	ll t1=x,t2=y;
	while (true)
	{
		t1*=prime[i]; t2*=prime[i];
		if (t1>n && t2>n) break;
		if (t1>n) t1=n+1; if (t2>n) t2=n+1;
		if (t1<=n) dfs(i+1,t1,y,now+1);
		if (x!=1 && t2<=n) dfs(i+1,x,t2,now+1);
	}
	if (prime[i+1]*min(x,y)<=n) dfs(i+1,x,y,now);
	return;
}
void init()
{
	for (int i=2;i<=maxn;i++)
	if (!p[i])
	{
		prime[++tot]=i;
		for (int j=i+i;j<=maxn;j+=i) p[j]=1;
	}
}
int main()
{
	init();
	cin>>n;
	dfs(1,1,1,0);
	cout<<best<<" "<<num<<endl;
//	cout<<prime[ok]<<endl;
}

T1传送带

我们考虑它到底是从哪边出去的，其实跟左边的 $>$ 以及右边的 $<$ 有关，假设左边有 $4$ 个 $>$ ，右边有 $6$ 个 $<$ ，那么他显然从左边出去，并且路径一定是走到第一个 $>$ ，向右走到第一个 $<$ ，然后向左走到第二个 $>$ ，如此进行。

那么答案就是个前缀和，我们二分或者用其他办法找到对应的位置，前缀和一下即可。

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
ll   Sl[N],Sr[N],IDl[N],IDr[N];
char s[N];

int findpre(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sr[M]<x) L=M;
		else R=M; 
	}
	return R;
}

int findsuf(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sl[n]-Sl[M-1]<x) R=M;
		else L=M; 
	}
	return L;
}

int main()
{
	T=1;
	while(T--)
	{
    	        scanf("%d%s",&n,s);
		for(int i=1;i<=n;i++) 
		{
	  	  Sr[i]=Sr[i-1]+(s[i-1]=='>');
	  	  Sl[i]=Sl[i-1]+(s[i-1]=='<');
 		  IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); 	
 		  IDl[i]=IDl[i-1]+i*(s[i-1]=='<'); 	
		}		
		for(int i=1;i<=n;i++)
		{
			if(s[i-1]=='>')
			{
				if(Sr[i]>Sl[n]-Sl[i])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i]));
					printf("%lld ",2*((IDl[n]-IDl[i])-(IDr[i]-IDr[p-1]))+i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i])-Sr[i]+1);
					printf("%lld ",2*((IDl[p]-IDl[i])-(IDr[i]-IDr[0]))+i);
				}
			}
			else
			{
				if(Sr[i]>=Sl[n]-Sl[i-1])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i-1])+1);
					printf("%lld ",2*((IDl[n]-IDl[i-1])-(IDr[i]-IDr[p-1]))-i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i-1])-Sr[i]);
					printf("%lld ",2*((IDl[p]-IDl[i-1])-(IDr[i]-IDr[0]))-i);
				}
			}
		}
		printf("\n");
	}
	
	return 0;
}

T2报数

暴力分：

我们枚举每一个 $x$ ，然后去检查答案是否合法即可。

100分：

只有两种可能，你要么是下降过程中遇到 $x$ ，要么是上升过程中遇到 $x$ 。

如果是下降过程中遇到 $x$ ，那么 $k$ 得满足： $(n+x-2)\% (k-2)=0$ 。

如果是上升过程中遇到 $x$ ，那么 $k$ 得满足： $(n-x)\%(k-2)=0$ 。

暴力把所有可能的 $k$ 存起来，然后验证一遍即可。

#include <bits/stdc++.h>
#define ll long long
#define maxn 500005
#define mod 998244353
using namespace std;
int n,x;
set<int> vis;
void check(int n)
{
	for (int i=1;i*i<=n;i++)
	if (n%i==0)
	{
		vis.insert((i+2)/2);
		vis.insert((n/i+2)/2);
	}
	return;
}

int fuck(int x,int n)
{
	int aa=n%(2*x-2);
	if (aa>=1 && aa<=x) return aa;
	if (aa==0) return 2;
	return 2*x-aa;	
}

void work()
{
	cin>>n>>x;
	vis.clear();
	check(n+x-2);
	check(n-x);
	vis.erase(1);
	int ret=0;
	for (int i:vis) if (i>=x) 
	{
//		cout<<i<<" "<<fuck(i,n)<<endl;
		if (fuck(i,n)==x) 
		{
			ret++;
		}
	}
	cout<<ret<<endl;
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while (T--) work();
}

T3 子序列

20分：随便暴力一下就可以。

50分：预处理一下对于第 $i$ 个位置，找下一个字符 $j$ 到哪里了，就可以 $O(n)$ 的check。

一个简单的100分拿法：

每次随机一个序列，然后去检查一遍，正确率非常高的，如果查了很多次都没找到就当做是全都可以。由于数据造的水可以满分（但并非正解）。

100分：

或者也可以选择，我们每次从当前位置出发，找到最近的一个 $r$ ，使得这一段里面包含了 $1,...,k$ 中的所有字符，如果能找到 $\geq n$ 段，则合法，否则每次跳这一段的尾巴，跳到最后一段的时候补上一个没出现过的字符即可。

正确性很容易证明。

#include <bits/stdc++.h>
#define ll long long
#define maxn 200005
#define mod 998244353
using namespace std;
string s;
int dp[maxn][27];
int nxt[maxn][27];
int pre[27];
int n,k,m; 
void work()
{
	cin>>n>>k>>m;
	cin>>s; s="a"+s;
	memset(pre,-1,sizeof(pre));
	for (int i=m;i>=0;i--)
	{
		for (int j=0;j<k;j++) nxt[i][j]=pre[j];
		pre[s[i]-'a']=i;
	}
	for (int i=m;i>=0;i--)
	{
		for (int j=0;j<n;j++) dp[i][j]=0;
		dp[i][n]=1; //�Ѿ�nλ����1
		for (int j=0;j<n;j++)
		{
			int flag=0;
			for (int t=0;t<k;t++)
			if (nxt[i][t]==-1 || dp[nxt[i][t]][j+1]==0)
			{
				flag=1; break;
			}
			if (!flag) dp[i][j]=1;
		} 
	}
	if (dp[0][0]==1) {cout<<"YES"<<endl; return;}
	cout<<"NO"<<endl;
	int now=0;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<k;j++)
		if (nxt[now][j]==-1)
		{
			for (int k=i;k<n;k++) cout<<(char)(j+'a'); cout<<endl;
			return;
		}
		for (int j=0;j<k;j++)
		if (dp[nxt[now][j]][i+1]==0)
		{
			cout<<(char)(j+'a');
			now=nxt[now][j];
			break;
		}
	}
	cout<<endl;
}

int main()
{
	int T=1;
	while (T--) work();
}

T4 划分序列

非常经典且简单的套路 $DP$ 。

我们考虑二分这个最大值，把求最优解问题转换成可行性问题。

二分完之后，就变成： $dp_{i}$ 表示我刚刚在 $i$ 选了一个 $B$ ，之前合法，当前 $B$ 的之和最小是多少了。

转移显然是$dp_i=\min_\limits{j<i,sum_{j,i-1}\leq LIM}(dp_j)+A_i$

单调队列优化 $DP$ 即可。

#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
ll dp[maxn];
ll zx[maxn<<2],tmp;
ll n,a[maxn],L[maxn];
ll head,tail,Q1[maxn],Q2[maxn]; //Q1��id��Q2��ֵ 
int check(ll lim)
{
	ll sum=0; int l=n+1;
	for (int r=n;r>=1;r--) //����r��˵��L[r]�����ܰ���������λ�� 
	{
		while (l>1 && sum+a[l-1]<=lim)
		{
			l--;
			sum+=a[l];
		}
		L[r]=l-1;
		sum-=a[r];
	}
	
	dp[0]=0;
	//dp[i]=min(dp[i-1],...,dp[L[i-1]])+a[i]
	//L����
	ll best=1ll<<60;
	head=tail=1; Q1[1]=0; Q2[1]=0;
	for (int i=1;i<=n;i++)
	{
		while (Q1[head]<L[i-1]) head++;
		dp[i]=Q2[head]+a[i];
		while (head<=tail && Q2[tail]>=dp[i]) tail--;
		tail++;
		Q1[tail]=i; Q2[tail]=dp[i];	
		if (L[n]<=i) best=min(best,dp[i]);
	}
	return best<=lim;
}

void work()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	tmp=a[1]; for (int i=1;i<=n;i++) tmp=max(tmp,a[i]);
	ll now=tmp-1;
	for (ll step=1ll<<50;step>=1;step=step>>1)
	if (check(now+step)==0)
	{
		now+=step;
	}
	cout<<now+1<<endl;
	return;
}

int main()
{
	int T=1;
	while (T--) work();
}

T5 算数求值

嘿嘿，我们模拟一下，把这个式子化简成 $ans=x\times A+B$ ，然后枚举 $x$ 即可。

遇到加法，直接给 $B$ 加那么多。

遇到减法，直接给 $B$ 减那么多。

遇到乘法，直接给 $A,B$ 一起乘那么多。

#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
using namespace std;
ll N,x,add;
string s;
int main()
{
	x=1; add=0;
	ll tp=1,val=0;
	cin>>N>>s; s=s+'+'; 
	for (int i=1;i<s.size();i++)
	{
		if (s[i]=='+' || s[i]=='-' || s[i]=='*')
		{
			if (tp==1) 	add=(add+val)%mod;
			else if (tp==2) add=(add+mod-val)%mod;
			else if (tp==3) x=x*val%mod,add=add*val%mod;
			if (s[i]=='+') tp=1; if (s[i]=='-') tp=2; if (s[i]=='*') tp=3;
			val=0;
		}
		else
			val=(val*10+(s[i]-'0'))%mod;
	}
	ll best=-1,id=-1;
	for (ll i=1;i<=N;i++)
	{
		ll ret=(x*i+add)%mod;
		if (ret>best) best=ret,id=i;
	}
	cout<<id<<" "<<best<<endl;
}

T6 括号序列

部分分实在是不好出。

正解是这样的：我们考虑直接按栈来模拟它，把匹配的括号都删掉。

这样，栈里一定只剩下了一段)，接了一段(。

假设)有 $a$ 个，(有 $b$ 个。

那么，我们首先肯定是贪心的把左边的)改成(，右边的(改成)来完成内部的配对，如果最后还各剩一个，花费 $2$ 的代价让他们匹配。

例如)))))(((((，我们首先花 $4$ 的代价把他们改成(()))((())，然后花 $2$ 的代价完成中间)(的配对。

#include <bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define mod 998244353
using namespace std;
string s;
int tot=0;
char stk[maxn];
int main()
{
	cin>>s;
	for (char c:s)
	{
		if (c=='(') stk[++tot]='(';
		else
		{
			if (tot>=1 && stk[tot]=='(') tot--;
			else stk[++tot]=')';
		}
	}
	int a=0,b=0,ret=0;
	for (int i=1;i<=tot;i++) if (stk[i]=='(') a++; else b++;
	ret=a/2+b/2;
	if (a&1) ret+=2;
	cout<<ret<<endl;
}

# T0选数
专门出的一个搜索题。

我们考虑$dfs(i,x,y,now)$。

此处$i$表示该考虑第$i$个质数的归属了，当前分别是$x,y$，当前一共有$now$个不同的质因子。

那么下一次$dfs$肯定是$dfs(i+1,x\times p[i]^t,y,now+1)$，或者是$dfs(i+1,x,y\times p[i]^t,now+1)$，或者是$dfs(i+1,x,y,now)$。

需要注意的是，这个过程中很容易乘爆$long\ long$，要么用$int128$，要么用除法来保证不会乘爆，比如`if (a*b<=n)`可以改写乘`if (a<=n/b)`。

剪枝的话很容易想到，就是假设后面都用第$i,i+1,...,$种质数，加上当前的$now$都凑不够目前的$best$，那就直接不用搜了。
```c++
#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
using namespace std;
int p[maxn+5],prime[maxn],tot;
ll n;
ll best=0,num=0,ok;
int zd=0;
map<pair<ll,ll>,int> vis;
void dfs(ll i,ll x,ll y,ll now)
{
	ll tx=x,ty=y,tt=0,ii=i;
	while (tx*prime[ii]<=n) {tx*=prime[ii++]; tt++;}
	ii=i;
	while (ty*prime[ii]<=n) {ty*=prime[ii++]; tt++;}
//	cout<<i<<" "<<x<<" "<<y<<endl;
	zd=max(zd+0ll,i);
	if (x<0 || y<0) exit(1);
	if (tt+now<best) return;
	if (now>=best)
	{
		if (now>best) best=now,num=1,ok=i;
		else num++,ok=max(i,ok);
	}
	ll t1=x,t2=y;
	while (true)
	{
		t1*=prime[i]; t2*=prime[i];
		if (t1>n && t2>n) break;
		if (t1>n) t1=n+1; if (t2>n) t2=n+1;
		if (t1<=n) dfs(i+1,t1,y,now+1);
		if (x!=1 && t2<=n) dfs(i+1,x,t2,now+1);
	}
	if (prime[i+1]*min(x,y)<=n) dfs(i+1,x,y,now);
	return;
}
void init()
{
	for (int i=2;i<=maxn;i++)
	if (!p[i])
	{
		prime[++tot]=i;
		for (int j=i+i;j<=maxn;j+=i) p[j]=1;
	}
}
int main()
{
	init();
	cin>>n;
	dfs(1,1,1,0);
	cout<<best<<" "<<num<<endl;
//	cout<<prime[ok]<<endl;
}
```

# T1传送带
我们考虑它到底是从哪边出去的，其实跟左边的$>$以及右边的$<$有关，假设左边有$4$个$>$，右边有$6$个$<$，那么他显然从左边出去，并且路径一定是走到第一个$>$，向右走到第一个$<$，然后向左走到第二个$>$，如此进行。

那么答案就是个前缀和，我们二分或者用其他办法找到对应的位置，前缀和一下即可。
```c++
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
ll   Sl[N],Sr[N],IDl[N],IDr[N];
char s[N];

int findpre(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sr[M]<x) L=M;
		else R=M; 
	}
	return R;
}

int findsuf(int x)
{
	int L=0,R=n+1,M;
	while(L+1!=R)
	{
		M=(L+R)>>1;
		if(Sl[n]-Sl[M-1]<x) R=M;
		else L=M; 
	}
	return L;
}

int main()
{
	T=1;
	while(T--)
	{
    	        scanf("%d%s",&n,s);
		for(int i=1;i<=n;i++) 
		{
	  	  Sr[i]=Sr[i-1]+(s[i-1]=='>');
	  	  Sl[i]=Sl[i-1]+(s[i-1]=='<');
 		  IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); 	
 		  IDl[i]=IDl[i-1]+i*(s[i-1]=='<'); 	
		}		
		for(int i=1;i<=n;i++)
		{
			if(s[i-1]=='>')
			{
				if(Sr[i]>Sl[n]-Sl[i])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i]));
					printf("%lld ",2*((IDl[n]-IDl[i])-(IDr[i]-IDr[p-1]))+i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i])-Sr[i]+1);
					printf("%lld ",2*((IDl[p]-IDl[i])-(IDr[i]-IDr[0]))+i);
				}
			}
			else
			{
				if(Sr[i]>=Sl[n]-Sl[i-1])
				{
					int p=findpre(Sr[i]-(Sl[n]-Sl[i-1])+1);
					printf("%lld ",2*((IDl[n]-IDl[i-1])-(IDr[i]-IDr[p-1]))-i+(n+1));
				}
				else
				{
					int p=findsuf((Sl[n]-Sl[i-1])-Sr[i]);
					printf("%lld ",2*((IDl[p]-IDl[i-1])-(IDr[i]-IDr[0]))-i);
				}
			}
		}
		printf("\n");
	}
	
	return 0;
}
```

# T2报数
暴力分：

我们枚举每一个$x$，然后去检查答案是否合法即可。

100分：

只有两种可能，你要么是下降过程中遇到$x$，要么是上升过程中遇到$x$。

如果是下降过程中遇到$x$，那么$k$得满足：$(n+x-2)\% (k-2)=0$。

如果是上升过程中遇到$x$，那么$k$得满足：$(n-x)\%(k-2)=0$。

暴力把所有可能的$k$存起来，然后验证一遍即可。

```c++
#include <bits/stdc++.h>
#define ll long long
#define maxn 500005
#define mod 998244353
using namespace std;
int n,x;
set<int> vis;
void check(int n)
{
	for (int i=1;i*i<=n;i++)
	if (n%i==0)
	{
		vis.insert((i+2)/2);
		vis.insert((n/i+2)/2);
	}
	return;
}

int fuck(int x,int n)
{
	int aa=n%(2*x-2);
	if (aa>=1 && aa<=x) return aa;
	if (aa==0) return 2;
	return 2*x-aa;	
}

void work()
{
	cin>>n>>x;
	vis.clear();
	check(n+x-2);
	check(n-x);
	vis.erase(1);
	int ret=0;
	for (int i:vis) if (i>=x) 
	{
//		cout<<i<<" "<<fuck(i,n)<<endl;
		if (fuck(i,n)==x) 
		{
			ret++;
		}
	}
	cout<<ret<<endl;
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while (T--) work();
}
```
# T3 子序列
20分：随便暴力一下就可以。

50分：预处理一下对于第$i$个位置，找下一个字符$j$到哪里了，就可以$O(n)$的check。

一个简单的100分拿法：

每次随机一个序列，然后去检查一遍，正确率非常高的，如果查了很多次都没找到就当做是全都可以。由于数据造的水可以满分（但并非正解）。

100分：

或者也可以选择，我们每次从当前位置出发，找到最近的一个$r$，使得这一段里面包含了$1,...,k$中的所有字符，如果能找到$\geq n$段，则合法，否则每次跳这一段的尾巴，跳到最后一段的时候补上一个没出现过的字符即可。

正确性很容易证明。


```c++
#include <bits/stdc++.h>
#define ll long long
#define maxn 200005
#define mod 998244353
using namespace std;
string s;
int dp[maxn][27];
int nxt[maxn][27];
int pre[27];
int n,k,m; 
void work()
{
	cin>>n>>k>>m;
	cin>>s; s="a"+s;
	memset(pre,-1,sizeof(pre));
	for (int i=m;i>=0;i--)
	{
		for (int j=0;j<k;j++) nxt[i][j]=pre[j];
		pre[s[i]-'a']=i;
	}
	for (int i=m;i>=0;i--)
	{
		for (int j=0;j<n;j++) dp[i][j]=0;
		dp[i][n]=1; //�Ѿ�nλ����1
		for (int j=0;j<n;j++)
		{
			int flag=0;
			for (int t=0;t<k;t++)
			if (nxt[i][t]==-1 || dp[nxt[i][t]][j+1]==0)
			{
				flag=1; break;
			}
			if (!flag) dp[i][j]=1;
		} 
	}
	if (dp[0][0]==1) {cout<<"YES"<<endl; return;}
	cout<<"NO"<<endl;
	int now=0;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<k;j++)
		if (nxt[now][j]==-1)
		{
			for (int k=i;k<n;k++) cout<<(char)(j+'a'); cout<<endl;
			return;
		}
		for (int j=0;j<k;j++)
		if (dp[nxt[now][j]][i+1]==0)
		{
			cout<<(char)(j+'a');
			now=nxt[now][j];
			break;
		}
	}
	cout<<endl;
}

int main()
{
	int T=1;
	while (T--) work();
}
```
# T4 划分序列

非常经典且简单的套路$DP$。

我们考虑二分这个最大值，把求最优解问题转换成可行性问题。

二分完之后，就变成：$dp_{i}$表示我刚刚在$i$选了一个$B$，之前合法，当前$B$的之和最小是多少了。

转移显然是$dp_i=\min_\limits{j<i,sum_{j,i-1}\leq LIM}(dp_j)+A_i$

单调队列优化$DP$即可。
```c++
#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
ll dp[maxn];
ll zx[maxn<<2],tmp;
ll n,a[maxn],L[maxn];
ll head,tail,Q1[maxn],Q2[maxn]; //Q1��id��Q2��ֵ 
int check(ll lim)
{
	ll sum=0; int l=n+1;
	for (int r=n;r>=1;r--) //����r��˵��L[r]�����ܰ���������λ�� 
	{
		while (l>1 && sum+a[l-1]<=lim)
		{
			l--;
			sum+=a[l];
		}
		L[r]=l-1;
		sum-=a[r];
	}
	
	dp[0]=0;
	//dp[i]=min(dp[i-1],...,dp[L[i-1]])+a[i]
	//L����
	ll best=1ll<<60;
	head=tail=1; Q1[1]=0; Q2[1]=0;
	for (int i=1;i<=n;i++)
	{
		while (Q1[head]<L[i-1]) head++;
		dp[i]=Q2[head]+a[i];
		while (head<=tail && Q2[tail]>=dp[i]) tail--;
		tail++;
		Q1[tail]=i; Q2[tail]=dp[i];	
		if (L[n]<=i) best=min(best,dp[i]);
	}
	return best<=lim;
}

void work()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	tmp=a[1]; for (int i=1;i<=n;i++) tmp=max(tmp,a[i]);
	ll now=tmp-1;
	for (ll step=1ll<<50;step>=1;step=step>>1)
	if (check(now+step)==0)
	{
		now+=step;
	}
	cout<<now+1<<endl;
	return;
}

int main()
{
	int T=1;
	while (T--) work();
}
```

# T5 算数求值
嘿嘿，我们模拟一下，把这个式子化简成$ans=x\times A+B$，然后枚举$x$即可。

遇到加法，直接给$B$加那么多。

遇到减法，直接给$B$减那么多。

遇到乘法，直接给$A,B$一起乘那么多。

```c++
#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 998244353
using namespace std;
ll N,x,add;
string s;
int main()
{
	x=1; add=0;
	ll tp=1,val=0;
	cin>>N>>s; s=s+'+'; 
	for (int i=1;i<s.size();i++)
	{
		if (s[i]=='+' || s[i]=='-' || s[i]=='*')
		{
			if (tp==1) 	add=(add+val)%mod;
			else if (tp==2) add=(add+mod-val)%mod;
			else if (tp==3) x=x*val%mod,add=add*val%mod;
			if (s[i]=='+') tp=1; if (s[i]=='-') tp=2; if (s[i]=='*') tp=3;
			val=0;
		}
		else
			val=(val*10+(s[i]-'0'))%mod;
	}
	ll best=-1,id=-1;
	for (ll i=1;i<=N;i++)
	{
		ll ret=(x*i+add)%mod;
		if (ret>best) best=ret,id=i;
	}
	cout<<id<<" "<<best<<endl;
}
```

# T6 括号序列
部分分实在是不好出。

正解是这样的：我们考虑直接按栈来模拟它，把匹配的括号都删掉。

这样，栈里一定只剩下了一段`)`，接了一段`(`。

假设`)`有$a$个，`(`有$b$个。

那么，我们首先肯定是贪心的把左边的`)`改成`(`，右边的`(`改成`)`来完成内部的配对，如果最后还各剩一个，花费$2$的代价让他们匹配。

例如`)))))(((((`，我们首先花$4$的代价把他们改成`(()))((())`，然后花$2$的代价完成中间`)(`的配对。
```c++
#include <bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define mod 998244353
using namespace std;
string s;
int tot=0;
char stk[maxn];
int main()
{
	cin>>s;
	for (char c:s)
	{
		if (c=='(') stk[++tot]='(';
		else
		{
			if (tot>=1 && stk[tot]=='(') tot--;
			else stk[++tot]=')';
		}
	}
	int a=0,b=0,ret=0;
	for (int i=1;i<=tot;i++) if (stk[i]=='(') a++; else b++;
	ret=a/2+b/2;
	if (a&1) ret+=2;
	cout<<ret<<endl;
}
```

我们会审查剪贴板内容，并对发布不合适内容的同学进行相应的处理