【比賽記錄】2025CSP-S模擬賽4
A. 序列問題
首先有一個 DP，設 \(f_i\) 表示前 \(i\) 個位置，當前子序列長度為 \(a_i\)，結尾也為 \(a_i\) 的最大價值。那么我們有:
\[f_i=\max_{j<i\land a_j<a_i\land i-j\ge a_i-a_j}\{f_j+1\}
\]
考慮這三個限制條件，滿足了后兩個就一定滿足第一個。第三個限制可以變形為 \(i-a_i\ge j-a_j\)。于是將原序列按 \(a\) 值排序，再 \(O(n\log n)\) 跑一個 \(i-a_i\) 最長不下降子序列即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define uprb upper_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e5+5;
int n,f[maxn];
struct node{
int a,p;
il bool operator<(const node &x)const{
return a<x.a||a==x.a&&p>x.p;
}
}b[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>b[i].a;
b[i].p=i;
}
sort(b+1,b+n+1);
int cnt=0;
for(int i=1;i<=n;i++){
// cout<<b[i].p-b[i].a<<" ";
if(b[i].a>b[i].p){
continue;
}
if(!cnt||b[i].p-b[i].a>=f[cnt]){
f[++cnt]=b[i].p-b[i].a;
}
else{
*uprb(f+1,f+cnt+1,b[i].p-b[i].a)=b[i].p-b[i].a;
}
}
// puts("");
cout<<cnt;
return 0;
}
}
int main(){return asbt::main();}
B. 錢倉
顯然需要斷環為鏈。
考慮一個鏈怎么處理，倒著掃，每次貪心地用當前的錢去填充最遠的位置。斷環為鏈后，顯然我們有 \(n\) 個起點可供選擇。那么在倒著掃的過程中記錄一個后綴和，差分計算即可。
但是會有問題，就是當前這一段長為 \(n\) 的鏈中的錢有可能給到后面去了，也就是說這段鏈中不能還有 \(0\) 沒被填充。判斷一下更新答案即可。用隊列維護 \(0\) 的位置，時間復雜度是線性的。
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;
const ll inf=1e18;
int n,a[maxn<<1],q[maxn<<1];
ll f[maxn<<1];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
freopen("barn.in","r",stdin);
freopen("barn.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
int hd=1,tl=0;
ll ans=inf;
for(int i=n<<1;i;i--){
f[i]=f[i+1];
while(a[i]&&hd<=tl){
f[i]+=(q[hd]-i)*(q[hd]-i);
a[i]--,hd++;
}
if(!a[i]){
q[++tl]=i;
}
if(i<=n&&(hd>tl||q[tl]>=i+n)){
ans=min(ans,f[i]-f[i+n]);
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
Upd on 3.30：存在這么一個性質，當當前的長為 \(n\) 的鏈中沒有未被填充的 \(0\)，那么此時隊列一定為空。
證明：因為當前這一段長為 \(n\) 的鏈的和一定為 \(n\)，又是往后給的，那么給完后沒有 \(0\) 和就一定依然為 \(n\)。換句話說，這一段中的錢都給了這一段了。而我們又是優先給最遠的，因此這一段區間后面 一定也沒有 \(0\)。也就是隊列為空。
因此，我們更新答案就只用判斷隊列為空就好了。
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;
const ll inf=1e18;
int n,a[maxn<<1],q[maxn<<1];
ll f[maxn<<1];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
freopen("barn.in","r",stdin);
freopen("barn.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
int hd=1,tl=0;
ll ans=inf;
for(int i=n<<1;i;i--){
f[i]=f[i+1];
while(a[i]&&hd<=tl){
f[i]+=(q[hd]-i)*(q[hd]-i);
a[i]--,hd++;
}
if(!a[i]){
q[++tl]=i;
}
if(i<=n&&hd>tl){
ans=min(ans,f[i]-f[i+n]);
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
C. 自然數
首先 \(O(n)\) 暴力算出 \(\operatorname{mex}(1,i)\) 的值。考慮從左往右掃 \(l\) 指針，用線段樹維護 \(\sum_{r=l}^{n}\operatorname{mex}(l,r)\)。
考慮 \(l\) 右移一位時，設 \(a_l\) 下一個出現的位置為 \(nxt_l\)，則我們要將 \([l,nxt_l)\) 中所有大于 \(a_l\) 的 \(\operatorname{mex}\) 值改為 \(a_l\)。注意到確定了 \(l\) 后，隨著 \(r\) 的單增，\(\operatorname{mex}(l,r)\) 的值是單調不降的，于是我們去做線段樹二分，再區間推平就行了。時間復雜度 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
#define int 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=2e5+5;
int n,a[maxn],b[maxn],bu[maxn];
int nxt[maxn],pos[maxn];
int sum[maxn<<2],tag[maxn<<2],mxz[maxn<<2];
il void pushup(int id){
sum[id]=sum[lid]+sum[rid];
mxz[id]=max(mxz[lid],mxz[rid]);
}
il void pushtag(int id,int l,int r,int x){
tag[id]=mxz[id]=x;
sum[id]=x*(r-l+1);
}
il void pushdown(int id,int l,int r){
if(~tag[id]){
int mid=(l+r)>>1;
pushtag(lid,l,mid,tag[id]);
pushtag(rid,mid+1,r,tag[id]);
tag[id]=-1;
}
}
il void build(int id,int l,int r){
tag[id]=-1;
if(l==r){
sum[id]=mxz[id]=b[l];
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void upd(int id,int L,int R,int l,int r,int x){
if(L>=l&&R<=r){
pushtag(id,L,R,x);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,x);
}
if(r>mid){
upd(rid,mid+1,R,l,r,x);
}
pushup(id);
}
il int qsum(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return sum[id];
}
pushdown(id,L,R);
int mid=(L+R)>>1,res=0;
if(l<=mid){
res+=qsum(lid,L,mid,l,r);
}
if(r>mid){
res+=qsum(rid,mid+1,R,l,r);
}
return res;
}
il int qpos(int id,int L,int R,int l,int r,int x){
if(mxz[id]<=x){
return -1;
}
if(L==R){
return L;
}
pushdown(id,L,R);
int mid=(L+R)>>1,res=-1;
if(l<=mid){
res=qpos(lid,L,mid,l,r,x);
}
if(r>mid&&res==-1){
res=qpos(rid,mid+1,R,l,r,x);
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1,res=0;i<=n;i++){
if(a[i]<=n){
bu[a[i]]++;
}
while(bu[res]){
res++;
}
b[i]=res;
}
for(int i=n;i;i--){
if(a[i]>n){
continue;
}
nxt[i]=pos[a[i]];
pos[a[i]]=i;
}
for(int i=1;i<=n;i++){
if(!nxt[i]){
nxt[i]=n+1;
}
}
build(1,1,n);
int ans=0;
for(int i=1;i<=n;i++){
ans+=qsum(1,1,n,i,n);
int tmp=qpos(1,1,n,i,nxt[i]-1,a[i]);
if(~tmp){
upd(1,1,n,tmp,nxt[i]-1,a[i]);
}
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
/*
3
0 1 3
5
*/
D. 環路
將圖存成鄰接矩陣 \(bas\)，那么我們的答案其實就是 \(bas+bas^2+bas^3+\dots+bas^{k-1}\) 的主對角線的和。而對于這個式子的計算是可以用一個分治非常輕松地解決的。具體地，如果當前項數為偶數，那么直接砍半；是奇數，就將末項去掉后砍半，然后再加上。時間復雜度 \(O(n^3\log^2k)\)。在計算過程中同時算末項，就是 \(O(n^3\log k)\) 了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
int n,m,mod;
string s;
struct juz{
int mat[105][105];
juz(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
mat[i][j]=0;
}
}
}
il int*operator[](int x){
return mat[x];
}
il juz operator*(juz x)const{
juz res;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
(res[i][j]+=mat[i][k]*1ll*x[k][j]%mod)%=mod;
}
}
}
return res;
}
il juz operator+(juz x)const{
juz res;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
res[i][j]=(mat[i][j]+x[i][j])%mod;
}
}
return res;
}
}bas;
il pair<juz,juz> solve(int k){
if(k==1){
return mp(bas,bas);
}
auto res=solve(k>>1);
res.fir=res.fir+res.fir*res.sec;
res.sec=res.sec*res.sec;
if(k&1){
res.sec=res.sec*bas;
res.fir=res.fir+res.sec;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>s;
for(int j=0;j<n;j++){
bas[i][j]=s[j]=='Y';
}
}
cin>>m>>mod;
juz res=solve(m-1).fir;
int ans=0;
for(int i=0;i<n;i++){
(ans+=res[i][i])%=mod;
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號