【比賽記錄】2025CSP-S模擬賽20
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 20 | 20 | - | - | 40 | 20/21 |
比賽是??，我更是??。
A. 簽
可以發現每次操作會減少 \(3\) 個逆序對，同時如果只考慮奇數位或偶數位那么會減少 \(1\) 個逆序對。因此有解的充要條件是奇數逆序對與偶數逆序對之和等于總逆序對的三分之一。具體證明不會
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int T,n,a[maxn];
struct{
int tr[maxn];
il int lowbit(int x){
return x&-x;
}
il void init(){
memset(tr,0,sizeof(tr));
}
il void add(int p,int v){
for(;p<=n;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
}F;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
bool flag=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]%2!=i%2){
flag=1;
}
}
if(flag){
cout<<"No\n";
continue;
}
ll c1=0,c2=0,c=0;
F.init();
for(int i=1;i<=n;i+=2){
c1+=F.query(n)-F.query(a[i]);
F.add(a[i],1);
}
F.init();
for(int i=2;i<=n;i+=2){
c2+=F.query(n)-F.query(a[i]);
F.add(a[i],1);
}
F.init();
for(int i=1;i<=n;i++){
c+=F.query(n)-F.query(a[i]);
F.add(a[i],1);
}
cout<<((c1+c2)*3==c?"Yes":"No")<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
B. 數據結構基礎練習題
首先將操作離線下來，將修改操作差分，在 \(l\) 處加，在 \(r+1\) 處減。
我們對序列 \(a\) 的下標做掃描線，維護每個時刻當前位置的值。于是對于每個詢問，我們將下標小于它的和同一下標、時間更小的修改全部插入進去即可。
問題于是轉化為區間加操作和區間查詢第 \(k\) 小。考慮分塊，維護每一塊中排序后的序列，這樣就可以算出區間中小于某個數的數的數量，再套個二分即可。
理論最佳快長應該是 \(631\)，然額比 \(300\) 的塊長多跑了 4000ms。
Code
#include<bits/stdc++.h>
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=7e4+5;
int n,m,ca,cb,ans[maxn];
bool vis[maxn];
struct node{
int t,p,k,l,r;
node(int t=0,int p=0,int k=0,int l=0,int r=0):t(t),p(p),k(k),l(l),r(r){}
il bool operator<(const node &x)const{
return p<x.p||p==x.p&&t<x.t;
}
}a[maxn<<1],b[maxn];
struct{
int B=300,bn,L[240],R[240],bel[maxn];
int p[240][305],q[240][305],tag[240];
il void reset(int x){
int len=R[x]-L[x]+1;
for(int i=1;i<=len;i++){
q[x][i]=p[x][i];
}
sort(q[x]+1,q[x]+len+1);
}
il void build(){
L[0]=R[0]=-1;
while(R[bn]!=m){
bn++;
L[bn]=R[bn-1]+1;
R[bn]=min(R[bn-1]+B,m);
for(int i=L[bn];i<=R[bn];i++){
bel[i]=bn;
}
}
}
il void add(int l,int r,int v){
int pl=bel[l],pr=bel[r];
if(pl==pr){
for(int i=l;i<=r;i++){
p[pl][i-L[pl]+1]+=v;
}
reset(pl);
return ;
}
for(int i=l;i<=R[pl];i++){
p[pl][i-L[pl]+1]+=v;
}
for(int i=L[pr];i<=r;i++){
p[pr][i-L[pr]+1]+=v;
}
reset(pl),reset(pr);
for(int i=pl+1;i<pr;i++){
tag[i]+=v;
}
}
il int query(int l,int r,int x){
int pl=bel[l],pr=bel[r],res=0;
if(pl==pr){
for(int i=l;i<=r;i++){
if(p[pl][i-L[pl]+1]+tag[pl]<x){
res++;
}
}
return res;
}
for(int i=l;i<=R[pl];i++){
if(p[pl][i-L[pl]+1]+tag[pl]<x){
res++;
}
}
for(int i=L[pr];i<=r;i++){
if(p[pr][i-L[pr]+1]+tag[pr]<x){
res++;
}
}
for(int i=pl+1,len;i<pr;i++){
len=R[i]-L[i]+1;
res+=lwrb(q[i]+1,q[i]+len+1,x-tag[i])-q[i]-1;
}
return res;
}
il int kth(int l,int r,int k){
int ll=-7e7,rr=7e7;
while(ll<rr){
int mid=(ll+rr+1)>>1;
if(query(l,r,mid)<k){
ll=mid;
}
else{
rr=mid-1;
}
}
return ll;
}
}BL;
int main(){
// system("fc ds3.ans my.out");
// freopen("ds4.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,opt,p,l,r,k;i<=m;i++){
cin>>opt;
if(!opt){
cin>>l>>r>>k;
a[++ca]=node(i,l,k);
a[++ca]=node(i,r+1,-k);
}
else{
cin>>p>>l>>r>>k;
b[++cb]=node(i,p,k,l,r);
vis[i]=1;
}
}
sort(a+1,a+ca+1),sort(b+1,b+cb+1);
BL.build();
for(int i=1,j=1;i<=cb;i++){
// cerr<<"6666\n";
while(j<=ca&&a[j]<b[i]){
BL.add(a[j].t,m,a[j].k);
j++;
}
ans[b[i].t]=BL.kth(b[i].l,b[i].r,b[i].k);
}
for(int i=1;i<=m;i++){
if(vis[i]){
cout<<ans[i]<<"\n";
}
}
return 0;
}
}
int main(){return asbt::main();}
C. 制糊串
一個直接的想法是設 \(f_{i,0/1,j}\) 表示在 \(i\) 位置填 \(A/B\) 能否使答案為 \(j\)。可以發現 \(f_{i,0/1}\) 對應的 \(01\) 串中只有一段連續的 \(1\)，或者頂多中間被挖去了一個位置。這可以用歸納法證明。
于是可以用一個三元組 \((l,r,p)\) 來表示一個 \(01\) 串，即左、右端點為 \(l\)、\(r\)，被挖去的那個位置為 \(p\)。于是時間復雜度線性。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int T,n,m;
string s;
struct node{
int l,r,p;
node(int l=0,int r=0,int p=-1):l(l),r(r),p(p){}
il bool ctain(const int &x)const{
return x>=l&&x<=r&&x!=p;
}
il node operator<<(const int &x)const{
return node(l+x,r+x,~p?p+x:p);
}
il node operator|(const node &x)const{
int L=min(l,x.l),R=max(r,x.r);
if(~p&&!x.ctain(p)){
return node(L,R,p);
}
if(~x.p&&!ctain(x.p)){
return node(L,R,x.p);
}
if(x.l==r+2){
return node(L,R,r+1);
}
if(l==x.r+2){
return node(L,R,x.r+1);
}
return node(L,R);
}
}f[maxn][2];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m>>s;
s=" "+s;
for(int i=1;i<n;i++){
if(s[i]!=s[i+1]){
m--;
}
}
if(s[1]=='A'){
f[1][0]=node(0,0),f[1][1]=node(1,1);
}
else{
f[1][0]=node(1,1),f[1][1]=node(0,0);
}
for(int i=2;i<=n;i++){
if(s[i]=='A'){
f[i][0]=f[i-1][0]|f[i-1][1]<<1;
f[i][1]=f[i-1][0]<<2|f[i-1][1]<<1;
}
else{
f[i][0]=f[i-1][0]<<1|f[i-1][1]<<2;
f[i][1]=f[i-1][0]<<1|f[i-1][1];
}
}
// for(int i=1;i<=n;i++){
// cout<<f[i][0].l<<" "<<f[i][0].r<<" "<<f[i][0].p<<"\n";
// cout<<f[i][1].l<<" "<<f[i][1].r<<" "<<f[i][1].p<<"\n";
// }
cout<<(f[n][0].ctain(m)||f[n][1].ctain(m)?"YES":"NO")<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
D. 牛仔
發現牛仔序列這個限制較為困難。考慮正難則反，用不考慮這個限制的答案減去不符合這個限制的答案。顯然前者為 \((n-m+1)\times k^{n-m}\)。然后就需要分類討論了。
1.\(A\) 為牛仔序列
這個東西比較顯然，沒有不符合限制的序列。
2.\(A\) 中有數重復出現
較為明顯的是，跨過 \(A\) 的子序列不可能是 \(1\) 到 \(K\) 的排列。因此只用考慮 \(A\) 之前與 \(A\) 之后。設 \(f_{i,j}\) 表示長為 \(i\) 的序列、結尾最長的互不相同的序列長為 \(j\) 的方案數。轉移有兩種：
-
往后面加一個新的數，即 \(f_{i,j}\times(K-j)\to f_{i+1,j+1}\)
-
往后加一個已有的數，從而縮短結尾序列的長度，即 \(f_{i,j}\to f_{i+1,p}\)，其中 \(p\le j\)。
顯然第二個轉移可以后綴和優化。往前 DP 一遍往后 DP 一遍，統計答案即可。
3.\(A\) 中沒有重復的數
可以發現 \(A_K^m\) 種序列是等價的，考慮計算長為 \(n\) 的非牛仔序列中長為 \(m\) 的不重復子序列的數量，除以 \(A_K^m\) 即為牛度。DP 思路是類似的，需要另外設一個 \(g_{i,j}\) 表示牛度，轉移依然類似，只需要在 \(j\ge m\) 時加上 \(f\) 的貢獻即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=25005,mod=1e9+7;
int n,kk,m,a[maxn],tong[405];
int f[maxn][405],g[maxn][405];
int sf[maxn][405],sg[maxn][405];
int fac[maxn],inv[maxn];
il int qpow(int x,int y=mod-2){
int res=1;
for(;y;y>>=1,x=x*1ll*x%mod){
if(y&1){
res=res*1ll*x%mod;
}
}
return res;
}
il bool chk1(){
for(int l=1,r=kk;r<=m;l++,r++){
for(int i=1;i<=kk;i++){
tong[i]=0;
}
for(int i=l;i<=r;i++){
if(tong[a[i]]++==1){
goto togo;
}
}
return 1;
togo:;
}
return 0;
}
il bool chk2(){
for(int i=1;i<=kk;i++){
tong[i]=0;
}
for(int i=1;i<=m;i++){
if(tong[a[i]]++==1){
return 1;
}
}
return 0;
}
il void DP(int f[maxn][405],int sf[maxn][405]){
for(int i=0;i<=n;i++){
for(int j=kk-1;j;j--){
sf[i][j]=(sf[i][j+1]+f[i][j])%mod;
}
for(int j=1;j<kk;j++){
(f[i+1][j+1]+=(kk-j)*1ll*f[i][j]%mod)%=mod;
(f[i+1][j]+=sf[i][j])%=mod;
}
}
}
il void init(int x=25000){
fac[0]=1;
for(int i=1;i<=x;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[x]=qpow(fac[x]);
for(int i=x;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>kk>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
}
int ans=qpow(kk,n-m)*1ll*(n-m+1)%mod;
if(chk1()){
cout<<ans;
return 0;
}
if(chk2()){
// puts("666");
for(int i=1;i<=kk;i++){
tong[i]=0;
}
for(int i=1;i<=m;i++){
if(tong[a[i]]++==1){
f[0][i-1]=1;
break;
}
}
DP(f,sf);
for(int i=1;i<=kk;i++){
tong[i]=0;
}
for(int i=m;i;i--){
if(tong[a[i]]++==1){
g[0][m-i]=1;
break;
}
}
DP(g,sg);
for(int i=0,j=n-m;~j;i++,j--){
(ans+=mod-sf[i][1]*1ll*sg[j][1]%mod)%=mod;
}
cout<<ans;
return 0;
}
init();
f[0][0]=sf[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<kk;j++){
f[i][j]=(f[i-1][j-1]*1ll*(kk-j+1)+sf[i-1][j])%mod;
g[i][j]=(g[i-1][j-1]*1ll*(kk-j+1)+sg[i-1][j])%mod;
if(j>=m){
(g[i][j]+=f[i][j])%=mod;
}
}
for(int j=kk-1;j;j--){
sf[i][j]=(sf[i][j+1]+f[i][j])%mod;
sg[i][j]=(sg[i][j+1]+g[i][j])%mod;
}
}
ans-=sg[n][1]*1ll*fac[kk-m]%mod*inv[kk]%mod;
cout<<(ans+mod)%mod;
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號