📅 发布时间：2026/6/20 21:06:54

前言：

好久没写改题记录了。（真的有很久吗？）

趁着今晚有空，赶紧写一写。

T1：括号问号（bracket）

思路：

原本在和学妹“愉快地”卡最优解，结果好像把评测机玩的有点生气死了，直接从 $83 ~ ms$ 跑成了 $94 ~ ms$ 。

看着括号匹配问题显然一眼 $dp$ 。

我们令 " ( " 对应的值为 $1$ ，" ) " 对应的值为 $-1$ 。

设 $dp_{i,j}$ 表示前 $i$ 个，前缀和为 $j$ 的方案数。

状态转移很显然。只是要注意 " ? " 既可作 " ( " ，又可作 " ) "。

代码：

$code$

#include<iostream>
using namespace std;
const int N=5005,mod=998244353;
unsigned int dp[2][N],ans;
int n;
bool st;
char ch[N];
int main(){freopen("bracket.in","r",stdin);freopen("bracket.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>(ch+1);dp[0][0]=1ll;for(int i=1;i<=n;i++){st^=1;for(int j=0;j<=i;j++) dp[st][j]=dp[st^1][j];if(ch[i]=='(') for(int j=1;j<=i;j++) dp[st][j]=(dp[st][j]+dp[st^1][j-1])%mod;else if(ch[i]==')') for(int j=0;j<=i;j++) dp[st][j]=(dp[st][j]+dp[st^1][j+1])%mod;else{for(int j=0;j<=i;j++){if(!j) dp[st][j]=(dp[st][j]+dp[st^1][j+1])%mod;else dp[st][j]=(dp[st][j]+dp[st^1][j+1]+dp[st^1][j-1])%mod;}}}cout<<dp[st][0]<<'\n';return 0;
} /*
4
(?)?50
???)??)?(?)(?(??)????(?)?))?)((?()??(??))(()()((?(*/

T2：狗卡（dog）

思路：

小狗什么的最可爱啦~~

当然，某卡除外！

首先根据题目的数据范围可以确定的是，每一个武将都可以完全升级完。

对于每一个武将来说，$ta$ 的收益等于 $m-time$（该武将出现的时间）

显然我们优先升级当前升级所需时间较短的武将更优。

但是因为我们不能越过低级武将去升级高级武将。所以我们可以将一大堆同一武将的不同等级捆在一起，按照他们的平均值进行排序，最后从小到大处理就好了。

但是具体怎么搞呢？

依据小学数学可知，当往一个序列里放入一个比平均值还要小时，这个序列的平均值会减小。

那么我们可以先将每一位武将单独捆作一捆。

如果当前捆的平均值小于等于后一捆的平均值，那我们就把当前捆与后一捆合并。

最后排个序就大功告成啦~~

代码：

$code$

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int N=6e5+5;
int n,m,k,x,cnt,tim,ans,q[N];
struct flower{int sum,num,id;bool operator < (const flower &css)const{return sum*css.num<css.sum*num; }
}d[N<<1];
vector<int> a[N];
vector<flower> v[N];
inline void work(int sum,int num,int id){flower x=v[id].back();v[id].pop_back();x.sum+=sum;x.num+=num;if(!v[id].empty()&&x.sum*v[id].back().num<=x.num*v[id].back().sum) work(x.sum,x.num,id);else v[id].push_back(x);
}
signed main(){freopen("dog.in","r",stdin);freopen("dog.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++){cin>>k;for(int j=1;j<=k;j++){cin>>x;a[i].push_back(x);flower t={x,1,i};//这捆武将的和，个数，武将编号 if(j==1){v[i].push_back(t);continue;}if(x<=v[i].back().sum/v[i].back().num) work(x,1,i);//合并 else v[i].push_back(t);}for(auto b:v[i]) d[++cnt]=b;}sort(d+1,d+1+cnt);//排序 for(int i=1;i<=cnt;i++){flower t=d[i];for(int j=q[t.id];j<=q[t.id]+t.num-1;j++){//把这一捆升级了 tim+=a[t.id][j];ans+=m-tim;}q[t.id]+=t.num;//该武将升到几级了 }cout<<ans<<'\n';return 0;
}

T3：均衡区间（interval）

我做主（疑似放假怒追小说的后遗症），T3严格简单于T2。

朕先送诸爱卿原（黑）（毫无意义，纯交着玩）

思路：

这里只拿左端点举例，右端点同理哈

首先肯定要枚举一下哪个点作为左端点。

一个点可以作为左端点的条件是它的右面既有比它大的数，又有比它小的数。

那么我们首先要做的就是统计这个点的右面出现的第一个大于/小于这个点的数的位置

然后我们可以很惊奇地发现：这玩意假了

为啥呢？

因为第一个大于左端点的数的下一个数可能会更大，这一段显然也不是能使左端点合法的右端点，所以我们要去掉它们。

怎么去呢？

我们可以再统计一下从这个点开始的递增/减区间的长度

这部分就是不合法的部分，把它们减去就好了。

代码：

$code$

#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+5;
int n,id,a[N];
int rmax[N],rmin[N],ranum[N],rbnum[N],r[N];
int lmax[N],lmin[N],lanum[N],lbnum[N],l[N];
deque<int> qmax,qmin;
int main(){freopen("interval.in","r",stdin);freopen("interval.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>id;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){while(!qmax.empty()&&a[qmax.front()]<=a[i]) rmax[qmax.front()]=i,qmax.pop_front();while(!qmin.empty()&&a[qmin.front()]>=a[i]) rmin[qmin.front()]=i,qmin.pop_front();qmax.push_front(i);qmin.push_front(i);}//统计这个点的右面出现的第一个大于/小于这个点的数的位置 while(!qmax.empty()) qmax.pop_front();while(!qmin.empty()) qmin.pop_front();for(int i=n;i>=1;i--){while(!qmax.empty()&&a[qmax.front()]<=a[i]) lmax[qmax.front()]=i,qmax.pop_front();while(!qmin.empty()&&a[qmin.front()]>=a[i]) lmin[qmin.front()]=i,qmin.pop_front();qmax.push_front(i);qmin.push_front(i);}for(int i=1;i<=n;i++){if(!rmin[i]) rmin[i]=n+1;if(!rmax[i]) rmax[i]=n+1;if(!lmin[i]) lmin[i]=0;if(!lmax[i]) lmax[i]=0;}ranum[n+1]=rbnum[n+1]=-1;for(int i=n;i>=1;i--){ranum[i]=ranum[rmax[i]]+1;rbnum[i]=rbnum[rmin[i]]+1;if(!ranum[i]||!rbnum[i]||id==2){r[i]=0;continue;}int r1=rmax[i],r2=rmin[i],ans=0;if(r1<r2){while(r1<r2) r1=rmax[r1];ans=n-r2+1-(ranum[r1]+rbnum[r2]+2);}else{while(r2<r1) r2=rmin[r2];ans=n-r1+1-(ranum[r1]+rbnum[r2]+2);}r[i]=ans;}for(int i=1;i<=n;i++) cout<<r[i]<<' ';cout<<'\n';lanum[0]=lbnum[0]=-1;for(int i=1;i<=n;i++){lanum[i]=lanum[lmax[i]]+1;lbnum[i]=lbnum[lmin[i]]+1;if(!lanum[i]||!lbnum[i]||id==2){l[i]=0;continue;}int l1=lmax[i],l2=lmin[i],ans=0;if(l1>l2){while(l1>l2) l1=lmax[l1];ans=l2-(lanum[l1]+lbnum[l2]+2);}else{while(l2>l1) l2=lmin[l2];ans=l1-(lanum[l1]+lbnum[l2]+2);}l[i]=ans;}for(int i=1;i<=n;i++) cout<<l[i]<<' ';return 0;
}