【比賽記錄】2025CSP-S模擬賽9
A. 皮胚 (match)
可行性 dp。設(shè) \(f_{i,j}\) 表示 \(s\) 的第 \(i\) 位能否匹配到 \(t\) 的第 \(j\) 位。分討轉(zhuǎn)移即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e3+5;
int T;
bool f[maxn][maxn];
string s,t;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>s>>t;
int ls=s.size(),lt=t.size();
s=" "+s,t=" "+t;
if(t[1]=='.'||s[1]==t[1]){
memset(f,0,sizeof f);
f[1][1]=1;
}
else{
cout<<0<<"\n";
continue;
}
for(int i=1;i<=ls;i++){
for(int j=1;j<=lt;j++){
if(!f[i][j]){
continue;
}
if(t[j]=='*'&&s[i+1]==s[i]){
f[i+1][j]=1;
}
if(t[j+1]=='.'){
f[i+1][j+1]=1;
}
else if(t[j+1]=='*'){
f[i][j+1]=1;
if(s[i+1]==s[i]){
f[i+1][j+1]=1;
}
}
else if(s[i+1]==t[j+1]){
f[i+1][j+1]=1;
}
}
}
int ans=0;
for(int i=1;i<=ls;i++){
ans+=f[i][lt];
}
cout<<ans<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
B. 核冰 (merge)
考慮一個(gè)貪心暴力，從小到大枚舉每一個(gè)數(shù)，如果一個(gè)數(shù)合并后還有剩余（即出現(xiàn)次數(shù)大于等于 \(3\))，那么就不斷合并。
考慮用線段樹去優(yōu)化。用線段樹維護(hù)合并到最后每個(gè)數(shù)出現(xiàn)的次數(shù) \(cnt\)。考慮插入一個(gè)數(shù) \(x\)，可能會(huì)引起一系列的合并，即從 \(x\) 開始的連續(xù)一段 \(cnt=2\) 的數(shù)都可以合并進(jìn)位上去。遇到 \(cnt<2\) 的數(shù)時(shí)停止。線段樹二分即可。
考慮刪除一個(gè)數(shù) \(x\)，類似地，需要連續(xù)地借位。這時(shí)需要滿足的有兩個(gè)條件，分別是當(dāng)前數(shù)出現(xiàn)次數(shù)為 \(1\)，以及當(dāng)前數(shù)進(jìn)行過進(jìn)位。于是再開一棵線段樹維護(hù)每個(gè)數(shù)的進(jìn)位次數(shù)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e5+25,N=5e5+20;
int n,m,a[maxn],pos[maxn];
il void gpos(int id,int l,int r){
if(l==r){
pos[l]=id;
return ;
}
int mid=(l+r)>>1;
gpos(lid,l,mid);
gpos(rid,mid+1,r);
}
struct{
int mx[maxn<<2],mn[maxn<<2],tag[maxn<<2];
il void pushup(int id){
mx[id]=max(mx[lid],mx[rid]);
mn[id]=min(mn[lid],mn[rid]);
}
il void pushtag(int id,int v){
mx[id]+=v,mn[id]+=v,tag[id]+=v;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void add(int id,int L,int R,int l,int r,int v){
if(l>r){
return ;
}
if(L>=l&&R<=r){
pushtag(id,v);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid,l,r,v);
}
if(r>mid){
add(rid,mid+1,R,l,r,v);
}
pushup(id);
}
il int ef1(int id,int L,int R,int l,int r){
if(R<l||L>r){
return -1;
}
if(mn[id]>=2){
return -1;
}
if(L==R){
return L;
}
pushdown(id);
int mid=(L+R)>>1;
int res=ef1(lid,L,mid,l,r);
if(res==-1){
res=ef1(rid,mid+1,R,l,r);
}
return res;
}
il int ef2(int id,int L,int R,int l,int r){
if(R<l||L>r){
return -1;
}
if(mx[id]<=1){
return -1;
}
if(L==R){
return L;
}
pushdown(id);
int mid=(L+R)>>1;
int res=ef2(lid,L,mid,l,r);
if(res==-1){
res=ef2(rid,mid+1,R,l,r);
}
return res;
}
}S1;
struct{
int mn[maxn<<2],tag[maxn<<2];
il void pushup(int id){
mn[id]=min(mn[lid],mn[rid]);
}
il void pushtag(int id,int v){
mn[id]+=v,tag[id]+=v;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void add(int id,int L,int R,int l,int r,int v){
if(l>r){
return ;
}
if(L>=l&&R<=r){
pushtag(id,v);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid,l,r,v);
}
if(r>mid){
add(rid,mid+1,R,l,r,v);
}
pushup(id);
}
il int ef(int id,int L,int R,int l,int r){
// cout<<id<<" "<<L<<" "<<R<<" "<<l<<" "<<r<<"\n";
if(mn[id]>=1){
return -1;
}
if(R<l||L>r){
return -1;
}
if(L==R){
return L;
}
pushdown(id);
int mid=(L+R)>>1;
int res=ef(lid,L,mid,l,r);
if(res==-1){
res=ef(rid,mid+1,R,l,r);
}
return res;
}
}S2;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
gpos(1,1,N);
cin>>n>>m;
int ans=0;
function<void(int)> insert=[&](int x){
int p=S1.ef1(1,1,N,x,N);
// cout<<p<<"\n";
if(!S1.mx[pos[p]]){
ans++;
}
S1.add(1,1,N,x,p-1,-1);
S1.add(1,1,N,p,p,1);
S2.add(1,1,N,x,p-1,1);
};
function<void(int)> del=[&](int x){
int p=S1.ef2(1,1,N,x,N),q=S2.ef(1,1,N,x,N);
// cout<<p<<" "<<q<<"\n";
if(p==-1||~q&&p>q){
p=q;
}
if(S1.mx[pos[p]]==1){
ans--;
}
S1.add(1,1,N,x,p-1,1);
S1.add(1,1,N,p,p,-1);
S2.add(1,1,N,x,p-1,-1);
};
for(int i=1;i<=n;i++){
cin>>a[i];
insert(a[i]);
}
// cout<<ans<<"\n";
while(m--){
int opt;
cin>>opt;
if(opt==1){
int p,v;
cin>>p>>v;
del(a[p]);
a[p]=v;
insert(a[p]);
}
else{
cout<<ans<<"\n";
}
}
return 0;
}
}
int main(){return asbt::main();}
C. 方珍 (mex)
顯然瓶頸在于如何快速求出第 \(k\) 大的 \(\operatorname{mex}\)。考慮二分。設(shè)當(dāng)前答案為 \(x\)，那么可以雙指針求出 \(\operatorname{mex}<x\) 的區(qū)間數(shù)量。于是獲得了 \(O(n^2\log n)\) 的算法。
考慮一個(gè)神秘優(yōu)化。首先將 \(w\) 降序排序，動(dòng)態(tài)地維護(hù)答案。設(shè)當(dāng)前答案為 \(ans\)，那么我們就不斷嘗試 \(ans+1-w\) 是否合法即可。由于 \(w\) 降序，\(ans\) 最多增加 \(O(n)\) 次。因此時(shí)間復(fù)雜度為 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e4+5;
int n,k[maxn],w[maxn],m[maxn],a[maxn],p[maxn],ton[maxn];
ull rs[maxn];
il int rd(int i){
rs[i]^=rs[i]<<13;
rs[i]^=rs[i]>>7;
rs[i]^=rs[i]<<17;
return rs[i]%m[i];
}
il int check(int x){
// cout<<x<<"\n";
for(int i=0;i<=n;i++){
ton[i]=0;
}
int res=0,cnt=0;
for(int l=1,r=1;r<=n;r++){
if(a[r]<x){
cnt+=ton[a[r]]==0;
ton[a[r]]++;
}
while(cnt>=x){
while(a[l]>=x){
l++;
}
ton[a[l]]--;
cnt-=ton[a[l]]==0;
l++;
}
res+=r-l+1;
}
return res;
}
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>>k[i]>>w[i]>>m[i]>>rs[i];
p[i]=i;
}
// puts("666");
sort(p+1,p+n+1,[](const int &x,const int &y){return w[x]>w[y];});
int ans=w[p[1]];
for(int i=1;i<=n;i++){
// cout<<i<<":\n";
int x=p[i];
if(ans>=m[x]+w[x]){
continue;
}
for(int j=1;j<=n;j++){
a[j]=rd(x);
}
while(check(ans+1-w[x])<k[x]){
ans++;
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
D. 術(shù)劣 (sequence)
有這樣一個(gè)神奇的推論：等差序列 \(a\) 打亂后公差 \(d=\gcd(|a_2-a_1|,|a_3-a_2|,\dots,|a_n-a_{n-1}|)\)。對(duì)此搞笑椅子 AI 給出了嚴(yán)謹(jǐn)?shù)淖C明過程。[1]
由此，我們可以進(jìn)一步推知：
-
對(duì)于任意序列 \(a\)，\(\max\{a\}-\min\{a\}\ge (n-1)d\)。
-
當(dāng)且僅當(dāng) \(a\) 排序后是等差序列時(shí)，上式取等。
于是對(duì)于題目中 \(a\) 序列的一個(gè)區(qū)間 \([l,r]\)，我們就可以通過判斷 \(\max[l,r]-\min[l,r]=(r-l)d\) 是否成立即可。移項(xiàng)，得 \(\max[l,r]-\min[l,r]+ld=rd\)。由是我們可以考慮線段樹經(jīng)典套路：移動(dòng)右端點(diǎn) \(r\)，在每個(gè)位置 \(x\) 維護(hù) \([x,r]\) 的信息。這里我們維護(hù)的就是 \(\max[x,r]-\min[x,r]+xd\)。
考慮 \(r\) 右移時(shí)應(yīng)該怎么在線段樹上修改。其中 \(\max\) 和 \(\min\) 可以用單調(diào)棧簡(jiǎn)單地完成。對(duì)于 \(d\) 的改變，顯然從 \(1\) 到 \(r-1\) 的 \(d\) 是不降的，且連續(xù)顏色段是 \(O(\log)\) 級(jí)別的。于是我們用并查集將連續(xù)段合并起來，在需要修改時(shí)直接暴力修改。這樣時(shí)間正確的原因是，顯然 \(d\) 最多也就改變 \(O(\log)\) 次。時(shí)間復(fù)雜度 \(O(n\log^2)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int n,a[maxn],st1[maxn],tp1,st2[maxn],tp2;
struct node{
int mn,num;
node(int mn=0,int num=0):mn(mn),num(num){}
il node operator+(const node &x)const{
if(mn==x.mn){
return node(mn,num+x.num);
}
else if(mn<x.mn){
return *this;
}
else{
return x;
}
}
}tr[maxn<<2];
int tag[maxn<<2];
#define lid id<<1
#define rid id<<1|1
#define mn(id) tr[id].mn
#define num(id) tr[id].num
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void pushtag(int id,int v){
tag[id]+=v,mn(id)+=v;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r){
if(l==r){
tr[id]=node(0,1);
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void add(int id,int L,int R,int l,int r,int v){
if(L>=l&&R<=r){
pushtag(id,v);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid,l,r,v);
}
if(r>mid){
add(rid,mid+1,R,l,r,v);
}
pushup(id);
}
il node query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return tr[id];
}
pushdown(id);
int mid=(L+R)>>1;
if(r<=mid){
return query(lid,L,mid,l,r);
}
if(l>mid){
return query(rid,mid+1,R,l,r);
}
return query(lid,L,mid,l,r)+query(rid,mid+1,R,l,r);
}
int fa[maxn],lp[maxn],d[maxn];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
//il void debug(int id,int l,int r){
// cerr<<id<<" "<<l<<" "<<r<<" "<<mn(id)<<" "<<num(id)<<"\n";
// if(l==r){
// return ;
// }
// int mid=(l+r)>>1;
// debug(lid,l,mid);
// debug(rid,mid+1,r);
//}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
// freopen("D.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
fa[i]=lp[i]=i;
}
build(1,1,n);
// debug(1,1,n);
int ans=1;
for(int r=1;r<=n;r++){
// cerr<<r<<":\n";
while(tp1&&a[st1[tp1]]>=a[r]){
add(1,1,n,st1[tp1-1]+1,st1[tp1],a[st1[tp1]]-a[r]);
tp1--;
}
st1[++tp1]=r;
while(tp2&&a[st2[tp2]]<=a[r]){
add(1,1,n,st2[tp2-1]+1,st2[tp2],a[r]-a[st2[tp2]]);
tp2--;
}
st2[++tp2]=r;
if(r==1){
cout<<1<<" ";
continue;
}
int cur=abs(a[r]-a[r-1]);
d[r-1]=cur;
// cerr<<cur<<" "<<r<<"\n";
//// puts("666");
// debug(1,1,n);
// cerr<<"---------------------------------\n";
add(1,1,n,r-1,r-1,cur*(r-1));
// debug(1,1,n);
// puts("777");
for(int i=r-2,j=r-1;i;i--){
i=find(i);
cur=gcd(cur,d[i]);
if(cur!=d[i]){
for(int k=lp[i];k<j;k++){
add(1,1,n,k,k,k*(cur-d[i]));
}
d[i]=cur;
}
if(d[i]==d[find(j)]){
int x=find(i),y=find(j);
fa[x]=y;
lp[y]=min(lp[x],lp[y]);
}
i=j=lp[find(i)];
}
// cout<<ans<<"\n";
ans++;
for(int i=r-1,j=r;i;i--){
i=find(i);
node res=query(1,1,n,lp[i],j-1);
if(res.mn==r*d[i]){
ans+=res.num;
}
i=j=lp[find(i)];
}
// cout<<ans<<"\n";
cout<<ans<<" ";
}
return 0;
}
}
signed main(){return asbt::main();}
設(shè)等差數(shù)列為 \(a,a+d,a+2d,\dots,a+(n-1)d\)。那么對(duì)于亂序后的兩個(gè)相鄰的數(shù) \(a+pd\) 和 \(a+qd\)，二者之差即為 \(|p-q|d\)。若存在 \(k\in\mathbb{Z}\) 且 \(k>1\)，使得所有的 \(kd\) 整除 \(|p-q|d\)，即 \(k\mid p-q\)，那么所有的 \(p\) 和 \(q\) 都將存在于 \(k\) 的某一個(gè)剩余系中，又 \(p,q\in[0,n-1]\) 且兩兩不等，那 \(p,q\) 就不夠了。因此這樣的 \(k\) 是不存在的。 ??
浙公網(wǎng)安備 33010602011771號(hào)