【做題記錄】csp2025刷題計劃-單調棧/單調隊列
A. Cashback
設某一個子串的大小為 \(k\)。
- \(k<c\)，要刪掉 \(0\) 個最小值，等價于 \(k\) 個長為 \(1\) 的區間。
- \(k=c\)，就是這個區間之和減掉這個區間最小值。
- \(c<k<2c\)，等價于 \(1\) 個長為 \(k\) 的區間和 \(k-c\) 個長為 \(1\) 的區間。
- \(k\ge 2c\)，顯然不如前幾種情況優。可以歸納證明。
于是問題變為將原數組分為若干長為 \(1\) 和長為 \(k\) 的區間的問題。用單調隊列預處理以每個位置結尾的長為 \(c\) 的區間的最小值，DP 即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,duil[maxn];
ll a[maxn],sum[maxn];
ll f[maxn],g[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,hd=1,tl=0;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
while(hd<=tl&&a[duil[tl]]>a[i]){
tl--;
}
duil[++tl]=i;
while(hd<=tl&&i-duil[hd]>=m){
hd++;
}
g[i]=a[duil[hd]];
}
// for(int i=1;i<=n;i++){
// cout<<g[i]<<" ";
// }
// puts("");
for(int i=1;i<=n;i++){
f[i]=f[i-1]+a[i];
if(i>=m){
f[i]=min(f[i],f[i-m]+sum[i]-sum[i-m]-g[i]);
}
}
cout<<f[n];
return 0;
}
}
int main(){return asbt::main();}
B. Cutlet
首先有一個 \(O(n^2)\) 的 DP：設 \(f_{i,j}\) 表示前 \(i\) 分鐘，當前朝上的面煎了 \(j\) 分鐘的最小翻面次數。于是有方程：
\[f_{i,j}=\min(f_{i-1,j},f_{i-1,i-j}+1)
\]
其中第二種轉移是翻面的，即僅當 \(\exist k,i\in[l_k,r_k]\) 時可以轉移。
那么如果 \(i\) 不在可以翻面的區間里，直接移過來就行了。于是只考慮可翻面的區間。設 \(f_{i,j}\) 表示前 \(r_i\) 分鐘，朝上的面煎了 \(j\) 分鐘的最小翻面次數。
考慮當在同一區間內如果翻面次數 \(\ge 2\)，那一不如只翻 \(1\) 次或 \(2\) 次。于是只需考慮這兩個轉移。
-
翻 \(1\) 次
枚舉當前朝下的面在這個區間內煎的時間 \(k\)。當前朝下的面顯然總共煎了 \(r_i-j\) 分鐘，那么在這個區間開始前它就煎了 \(r_i-j-k\) 分鐘。而這個區間前這一面正好就是朝上的。于是 \(f_{i,j}=\min(f_{i-1,r_i-j-k})\)。
-
翻 \(2\) 次
枚舉當前朝上的面在這個區間內煎的時間 \(k\)。在這個區間前這一面也是朝上的，煎了 \(j-k\) 分鐘。于是 \(f_{i,j}=min(f_{i-1,j-k})\)。
用單調隊列優化這兩個轉移即可。時間復雜度 \(O(nk)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,duil[maxn];
int f[105][maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// cout<<cplx::usdmem();
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
memset(f[0],0x3f,sizeof f[0]);
f[0][0]=0;
for(int i=1,l,r,hd,tl;i<=m;i++){
for(int j=0;j<=n;j++){
f[i][j]=f[i-1][j];
}
cin>>l>>r;
hd=1,tl=0;
for(int j=0;j<=min(r,n);j++){
while(hd<=tl&&f[i-1][duil[tl]]>f[i-1][j]){
tl--;
}
duil[++tl]=j;
while(hd<=tl&&duil[hd]<j-(r-l)){
hd++;
}
f[i][j]=min(f[i][j],f[i-1][duil[hd]]+2);
}
hd=1,tl=0;
for(int j=r;~j;j--){
while(hd<=tl&&f[i-1][duil[tl]]>f[i-1][r-j]){
tl--;
}
duil[++tl]=r-j;
while(hd<=tl&&duil[hd]<l-j){
hd++;
}
f[i][j]=min(f[i][j],f[i-1][duil[hd]]+1);
}
}
// for(int i=0;i<=m;i++){
// for(int j=0;j<=n;j++){
// cout<<f[i][j]<<" ";
// }
// puts("");
// }
printf(f[m][n]>=inf?"Hungry":"Full\n%d",f[m][n]);
return 0;
}
}
int main(){return asbt::main();}
/*
10 1
0 20
*/
C. Kuzya and Homework
要求結果為整數，我們將所有 \(a_i\) 分解質因數，對于每個質數分別考慮。
考慮對于一個左端點 \(l\)，能滿足要求的右端點一定在從 \(l\) 開始的一段連續區間中。于是我們得對于每個 \(l\) 求出 \(ans_l\) 表示那個最遠的右端點。
對于一個質數 \(p\)，假設 \(a_i\) 中有 \(k\) 個 \(p\)，如果 \(b_i\) 為乘號就在 \(i\) 這里記一個 \(k\)，否則記一個 \(-k\)。然后再做一個前綴和 \(pre\)。那么對于 \(l\)，我們要求的就是最大的 \(r\)，滿足 \(\forall k\in[l,r],pre_k-pre_{l-1}\ge 0\)。可以倒著掃，維護一個單調棧，每次在單調棧上二分。但是這樣的時間復雜度是無法承受的。我們考慮如果 \(a_i\) 中沒有 \(p\)，那么 \(i\) 這個位置的答案就是等于 \(i+1\) 的答案的。于是我們只用存儲那些包括了 \(p\) 的位置。于是就成了若干次區間的取 \(\min\)。再用并查集掃一遍即可。
先將所有質數都篩出來，時間復雜度可以承受。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define lwrb lower_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,inf=0x3f3f3f3f;
int n,prn,a[maxn];
int prm[maxn],pre[maxn];
int zh1[maxn],zh2[maxn];
int fa[maxn],ans[maxn];
bool npr[maxn];
string b;
vector<pii> wei[maxn],cun[maxn];
il void init(int x){
for(int i=2;i<=x;i++){
if(!npr[i]){
prm[++prn]=i;
}
for(int j=i*i;j<=x;j+=i){
npr[j]=1;
}
}
}
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>b;
b=" "+b;
init(1e3);
for(int i=1,tmp;i<=n;i++){
tmp=a[i];
for(int j=1,cnt;j<=prn&&prm[j]<=tmp/prm[j];j++){
if(tmp%prm[j]==0){
cnt=0;
while(tmp%prm[j]==0){
tmp/=prm[j],cnt++;
}
wei[prm[j]].pb(mp(i,b[i]=='*'?cnt:-cnt));
}
}
if(tmp>1){
wei[tmp].pb(mp(i,b[i]=='*'?1:-1));
}
}
for(int i=1,top;i<=1e6;i++){
if(wei[i].empty()){
continue;
}
pre[0]=wei[i][0].sec;
for(int j=1;j<wei[i].size();j++){
pre[j]=pre[j-1]+wei[i][j].sec;
}
top=1;
zh1[1]=-inf,zh2[1]=n+1;
for(int j=wei[i].size()-1,k;~j;j--){
while(top&&zh1[top]>pre[j]){
top--;
}
zh1[++top]=pre[j],zh2[top]=wei[i][j].fir;
k=lwrb(zh1+1,zh1+top+1,pre[j]-wei[i][j].sec)-zh1-1;
cun[zh2[k]-1].pb(mp(j?wei[i][j-1].fir+1:1,wei[i][j].fir));
}
}
for(int i=1;i<=n+1;i++){
fa[i]=i,ans[i]=n;
}
for(int i=0;i<=n;i++){
for(pii j:cun[i]){
for(int k=find(j.fir);k<=j.sec;k=find(k+1)){
ans[k]=i;
fa[find(k)]=find(k+1);
}
}
}
// for(int i=1;i<=n;i++){
// cout<<ans[i]<<" ";
// }
// puts("");
ll Ans=0;
for(int i=1;i<=n;i++){
Ans+=ans[i]-i+1;
}
cout<<Ans;
return 0;
}
}
int main(){return asbt::main();}
D. Non-equal Neighbours
設 \(f_{i,j}\) 表示考慮 \(1\) 到 \(i\)，\(b_i=j\) 的方案數。于是方程：
\[f_{i,j}=\sum_{k=1}^{a_{i-1}}f_{i-1,k}-f_{i-1,j}
\]
其中 \(j\in[1,a_i]\)。
顯然可以滾動數組，然后可以用線段樹優化。進行區間乘和區間加即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
const int mod=998244353;
int n,rt,tot,a[maxn],sum[maxn<<6];
int ls[maxn<<6],rs[maxn<<6];
int tgj[maxn<<6],tgc[maxn<<6];
il int New(){
tgc[++tot]=1;
return tot;
}
il void pushup(int id){
sum[id]=(sum[ls[id]]+sum[rs[id]])%mod;
}
il void pushtgj(int id,int l,int r,int v){
sum[id]=(sum[id]+(r-l+1)*1ll*v)%mod;
(tgj[id]+=v)%=mod;
}
il void pushtgc(int id,int v){
sum[id]=sum[id]*1ll*v%mod;
tgj[id]=tgj[id]*1ll*v%mod;
tgc[id]=tgc[id]*1ll*v%mod;
}
il void pushdown(int id,int l,int r){
if(tgc[id]!=1){
if(!ls[id]){
ls[id]=New();
}
if(!rs[id]){
rs[id]=New();
}
pushtgc(ls[id],tgc[id]);
pushtgc(rs[id],tgc[id]);
tgc[id]=1;
}
if(tgj[id]){
if(!ls[id]){
ls[id]=New();
}
if(!rs[id]){
rs[id]=New();
}
int mid=(l+r)>>1;
pushtgj(ls[id],l,mid,tgj[id]);
pushtgj(rs[id],mid+1,r,tgj[id]);
tgj[id]=0;
}
}
il void add(int &id,int L,int R,int l,int r,int v){
if(!id){
id=New();
}
if(L>=l&&R<=r){
pushtgj(id,L,R,v);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
add(ls[id],L,mid,l,r,v);
}
if(r>mid){
add(rs[id],mid+1,R,l,r,v);
}
pushup(id);
}
il void mul(int &id,int L,int R,int l,int r,int v){
if(l>r){
return ;
}
if(!id){
id=New();
}
if(L>=l&&R<=r){
pushtgc(id,v);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
mul(ls[id],L,mid,l,r,v);
}
if(r>mid){
mul(rs[id],mid+1,R,l,r,v);
}
pushup(id);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
add(rt,1,1e9,1,a[1],1);
// cout<<sum[rt]<<"\n";
for(int i=2,tmp;i<=n;i++){
tmp=sum[rt];
mul(rt,1,1e9,1,a[i],mod-1);
add(rt,1,1e9,1,a[i],tmp);
mul(rt,1,1e9,a[i]+1,1e9,0);
// cout<<sum[rt]<<"\n";
}
cout<<sum[rt];
return 0;
}
}
int main(){return asbt::main();}
/*
10
10 10 7 9 8 3 3 10 7 3
*/
E. 「CZOI-R1」消除威脅
首先全都去取絕對值，對答案沒有影響。
對于某個相同的 \(a\) 值 \(x\)，我們想要快速地求出 \(a_l=a_r=x\) 的具有威脅的區間 \([l,r]\) 的個數。從左向右掃 \(a\) 數組，維護一個單調遞減的單調棧，對于每個位置 \(i\) 記錄 \(cnt_i\) 表示以 \(i\) 為左端點，有多少個 \(r>i\) 滿足 \([i,r]\) 是具有威脅的。這樣做會算重，辦法是當當前值等于棧頂時不壓棧。
對于 \(cnt_i\)，如果 \(a_i=0\)，那么貢獻就是 \(cnt_i+1\choose 2\)。否則我們可以將一部分變成負的。顯然變一半是最優的，貢獻為 \({\lfloor\frac{cnt_i+1}{2}\rfloor\choose{2}}+{\lceil\frac{cnt_i+1}{2}\rceil\choose{2}}\)。\(O(n)\) 統計即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
il int read(){
char ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
#undef getchar
}
using IO::read;
const int maxn=5e5+5;
int n,a[maxn];
int zhan[maxn],cnt[maxn];
il ll calc(int x){
return x*1ll*(x-1)>>1;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
// cout<<a[i]<<" ";
}
// puts("");
int top=0;
for(int i=1;i<=n;i++){
while(top&&a[zhan[top]]<a[i]){
top--;
}
if(top&&a[zhan[top]]==a[i]){
cnt[zhan[top]]++;
}
else{
zhan[++top]=i;
}
}
ll ans=0;
for(int i=1;i<=n;i++){
cnt[i]++;
if(!a[i]){
ans+=calc(cnt[i]);
}
else{
ans+=calc(cnt[i]>>1)+calc((cnt[i]+1)>>1);
}
}
// puts("");
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號