当前位置：首页 > news >正文

复健 day1：vp CF2205

news 2026/6/5 13:18:24

起因是，这周末要打 thupc 了，我不想太拖累队友，决定找找手感。

考虑到我是一个退役时长两年半的选手，于是先 vp 一个 div2 作为开场。

但是现在的 div2 怎么这么难！！！

A. Simons and Making It Beautiful

显然把最大值交换到第一个即可。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
int T,n,m,a[maxn];
int main(){T=read();while(T--){n=read();int pos=-1;for(int i=1;i<=n;i++)a[i]=read(),pos=(a[i]==n?i:pos);swap(a[1],a[pos]);for(int i=1;i<=n;i++)printf("%d ",a[i]);puts("");}return 0;
}

B. Simons and Cakes for Success

把 \(n\) 的所有质因子去重。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
int T,n,m;
int main(){T=read();while(T--){n=read();int res=1;for(int i=2;i*i<=n;i++)if(n%i==0){res*=i;while(n%i==0)n/=i;}if(n>1)res*=n;printf("%d\n",res);}return 0;
}

C. Simons and Posting Blogs

我的想法是，将每个序列反转，然后每次贪心选字典序最小的。

选完后，将其余序列的重复的数去除，然后继续循环。目前经历神秘 RE。

upd：值域数组没开够。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
#define vi vector<int>
int T,n,m,ok[maxn],vis[maxn],Vis[maxn];vi a[maxn];
inline void refresh(vi &x){
//	puts("refresh");vi res;res.clear();for(int i=0;i<x.size();i++)if(!vis[x[i]])res.push_back(x[i]);swap(x,res);
//	puts("refresh over");
}
inline bool cmp(vi x,vi y){int len=min(x.size(),y.size());for(int i=0;i<len;i++)if(x[i]<y[i])return false;else if(x[i]>y[i])return true;if(x.size()>len)return true;else return false;
}
int main(){T=read();while(T--){n=read();for(int i=1;i<=n;i++){int len=read();a[i].clear();ok[i]=1;a[i].resize(len);vi tmp;for(int j=1;j<=len;j++)a[i][len-j]=read();for(int j=1,x;j<=len;j++){x=a[i][j-1];if(Vis[x])continue;Vis[x]=1;tmp.push_back(x);vis[x]=0;}swap(tmp,a[i]);for(auto x:a[i])Vis[x]=0;}for(int i=1;i<=n;i++){
//			printf("i=%d\n",i);int Mxid=-1;for(int j=1;j<=n;j++)if(ok[j]&&(Mxid==-1||cmp(a[Mxid],a[j])))Mxid=j;ok[Mxid]=0;for(int j=0;j<a[Mxid].size();j++)printf("%d ",a[Mxid][j]),vis[a[Mxid][j]]=1;for(int j=1;j<=n;j++)if(ok[j])refresh(a[j]);}puts("");}return 0;
}

D. Simons and Beating Peaks

显然题意要求单谷，那么考虑最大值，要么放到最左边要么放到最右边。

放完最大值后，剩下一个区间，再考虑其最大值，发现过程有递归性。

于是设 \(dp_{l,r}\) 表示将区间 \([l,r]\) 变为单谷的答案，设 \(k\) 为最大值的位置，则有

\[dp_{l,r}=1+\max(dp_{l,k-1},dp_{k+1,r}) \]

每个区间对应笛卡尔树上的一个点，直接搜索即可。

由于我忘记怎么建笛卡尔树了，于是时间复杂度 \(O(n\log n)\)，瓶颈是倍增。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
int n,m,T,a[maxn],Mx[maxn][21],lg[maxn],inv[maxn];
inline int calc(int l,int r){int k=lg[r-l+1];return inv[max(Mx[l][k],Mx[r-(1<<k)+1][k])];
}
inline int dp(int l,int r){if(l>r)return 0;int id=calc(l,r);return 1+max(dp(l,id-1),dp(id+1,r));
}
int main(){T=read();while(T--){n=read();lg[0]=-1;for(int i=1;i<=n;i++)a[i]=read(),inv[a[i]]=i;for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1,Mx[i][0]=a[i];for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)Mx[i][j]=max(Mx[i][j-1],Mx[i+(1<<j-1)][j-1]);printf("%d\n",n-dp(1,n));}return 0;
}

E. Simons and Dividing the Rhythm

题意可以转化为，一个指针，每次选择一个位置，然后一步一步往后挪一直到上一次选的位置。

考虑去重，发现，如果新走的这一段存在 border，那么就可以被先走 border，然后跟之前同步，最后走前面这一段。

因此从后往前 dp，对每个后缀做 kmp，以此判断是否可以转移即可。

时间复杂度 \(O(n^2)\)。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
#define inf 1e9
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
const int N=8005;
int n,m,T,a[N],nxt[N],dp[N];
inline void solve(){n=read();dp[n+1]=1;for(int i=1;i<=n;i++)a[i]=read(),dp[i]=0;for(int i=n;i>=1;i--){dp[i]=dp[i+1];for(int j=i;j<=n;j++)nxt[j]=i-1;for(int j=i+1;j<=n;j++){int pos=nxt[j-1];while(pos!=i-1&&a[pos+1]!=a[j])pos=nxt[pos];if(a[pos+1]==a[j])nxt[j]=pos+1;else dp[i]=(dp[i]+dp[j+1])%mod;}}printf("%d\n",dp[1]);
}
int main(){T=read();while(T--)solve();return 0;
}