【比賽記錄】2025CSP-S模擬賽12
倒序放題嗎，有點意思????????????????
A. 環游(tour)
注意到我們最多可以跳 \(O(\log V)\) 次。考慮對于每一次的容量，求出若干連續的區間，于是我們要在每一層選一個區間來使這些區間的并為全集。
對除了最上面那一層之外的層進行狀壓 DP，維護 \(f_S\) 表示在 \(S\) 這些層選了區間后能走到的最大前綴，\(g_S\) 表示最大后綴。然后枚舉每個子集，看它的補集和它自己能不能構成合法答案即可。
代碼實現是 \(O(V\log V\log n)\) 的，實現的好可以做到 \(O((V+n)\log V)\)。
Code
#include<bits/stdc++.h>
#define il inline
#define lwrb lower_bound
#define uprb upper_bound
using namespace std;
namespace asbt{
const int maxn=2e5+5,maxm=(1<<20)+5;
int n,V,m,U,a[maxn],ll[22][maxn],rr[22][maxn],cnt[22],f[maxm],g[maxm],ans[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>V;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(;;V>>=1,m++){
int l=1,r=1;
while(l<=n){
while(r<n&&a[r+1]-a[r]<=V){
r++;
}
cnt[m]++;
ll[m][cnt[m]]=l;
rr[m][cnt[m]]=r;
l=++r;
}
ll[m][cnt[m]+1]=rr[m][cnt[m]+1]=n+1;
if(!V){
break;
}
}
U=(1<<m)-1;
for(int i=0;i<=U;i++){
g[i]=n+1;
}
for(int S=0;S<=U;S++){
for(int i=1;i<=m;i++){
if(S>>(i-1)&1){
continue;
}
int p=uprb(ll[i]+1,ll[i]+cnt[i]+1,f[S])-ll[i]-1;
if(f[S]==rr[i][p]){
p++;
}
f[S|1<<(i-1)]=max(f[S|1<<(i-1)],rr[i][p]);
}
}
for(int S=0;S<=U;S++){
for(int i=1;i<=m;i++){
if(S>>(i-1)&1){
continue;
}
int p=lwrb(rr[i]+1,rr[i]+cnt[i]+1,g[S])-rr[i];
if(g[S]==ll[i][p]){
p--;
}
g[S|1<<(i-1)]=min(g[S|1<<(i-1)],ll[i][p]);
}
}
for(int i=0,j;i<=U;i++){
j=U^i;
if(f[i]>=g[j]){
for(int k=1;k<=n;k++){
cout<<"Possible\n";
}
return 0;
}
int p=uprb(ll[0]+1,ll[0]+cnt[0]+1,f[i])-ll[0]-1;
if(f[i]==rr[0][p]){
p++;
}
if(g[j]<=rr[0][p]+1){
ans[p]=1;
}
}
// puts("666");
for(int i=1;i<=cnt[0];i++){
for(int j=ll[0][i];j<=rr[0][i];j++){
cout<<(ans[i]?"Possible":"Impossible")<<"\n";
}
}
return 0;
}
}
int main(){return asbt::main();}
B. 數塔(pyramid)
二分答案，將大于等于 \(mid\) 的記為 \(1\)，小于 \(mid\) 的記為 \(0\)。于是只需判斷頂端是 \(1\) 還是 \(0\)。
簡單手玩后發現，兩個相鄰的相同的數上面就都是這個數了。并且對于中間的一段 1010101 串，左 / 右最近的 11 或 00 會不斷地向中間擴散，離得最近的會改變中間的答案。于是判斷最近的是 11 還是 00 就行了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int T,n,a[maxn];
bool b[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<n<<1;i++){
cin>>a[i];
}
int l=1,r=2*n-1;
while(l<r){
int mid=(l+r+1)>>1;
for(int i=1;i<n<<1;i++){
b[i]=a[i]>=mid;
}
int resl=n+1,resr=n+1;
for(int i=n-1;i;i--){
if(b[i]==b[i+1]){
resl=n-i+1;
break;
}
}
for(int i=n+1;i<n<<1;i++){
if(b[i]==b[i-1]){
resr=i-n+1;
break;
}
}
if(min(resl,resr)&1){
b[n]^=1;
}
if(b[n]){
l=mid;
}
else{
r=mid-1;
}
}
cout<<l<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
C. 二擇(choice)
注意到一個 \(\beta_1\) 的點集和一個 \(\beta_2\) 的邊集加起來正好有 \(3\times n\) 個點。于是我們先隨便求一個極大的 \(\beta_2\) 的邊集，不難發現剩下的點就是一個 \(\beta_1\) 的點集。這兩個中肯定有一個符合條件。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e+5+5;
int T,n,m;
bool vsd[maxn],vsb[maxn];
struct{
int u,v;
}e[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v;
vsb[i]=0;
}
for(int i=1;i<=n*3;i++){
vsd[i]=0;
}
int cnt=0;
for(int i=1;i<=m;i++){
if(!vsd[e[i].u]&&!vsd[e[i].v]){
vsd[e[i].u]=vsd[e[i].v]=vsb[i]=1;
cnt++;
}
}
if(cnt>=n){
cout<<"Beta2\n";
cnt=0;
for(int i=1;i<=m;i++){
if(vsb[i]){
cnt++;
cout<<i<<" ";
if(cnt==n){
break;
}
}
}
cout<<"\n";
}
else{
cout<<"Beta1\n";
cnt=0;
for(int i=1;i<=n*3;i++){
if(!vsd[i]){
cnt++;
cout<<i<<" ";
if(cnt==n){
break;
}
}
}
cout<<"\n";
}
}
return 0;
}
}
int main(){return asbt::main();}
D. 平衡(balance)
打表可以發現當 \(n\) 為偶數時無解而當 \(n\) 為奇數時一個合法構造為形如 1 4 5 8 9 ... 2 3 6 7 10 ... 的形式，即差分后數組為 3 1 3 1 ...。
具體的證明：因為 \(\operatorname{sum}[1,n]=\operatorname{sum}[2,n+1]\)，所以 \(a_1\) 和 \(a_{n+1}\) 一定相差 \(1\)。又因為 \(\operatorname{sum}[1,n]=\operatorname{sum}[3,n+2]\)，所以 \(a_{n-1}-a_1\) 一定和 \(a_{n+2}-a_2\) 異號。故這樣的構造是合法的。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int T,n,a[maxn],b[maxn<<1],c[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
if(n<=5){
for(int i=1;i<=n<<1;i++){
// cin>>a[i];
a[i]=i;
}
do{
for(int i=1;i<=n<<1;i++){
b[i]=b[i-1]+a[i];
}
for(int i=1;i<=n<<1;i++){
b[i+n*2]=b[i]+b[n*2];
}
// for(int i=1;i<=n<<2;i++){
// cout<<b[i]<<" ";
// }
// cout<<"\n";
for(int i=1;i<=n<<1;i++){
c[i]=b[i+n]-b[i];
// cout<<c[i]<<" ";
}
// cout<<"\n";
sort(c+1,c+n*2+1);
// cout<<c[n*2]-c[1]<<"\n";
if(c[n*2]-c[1]<=1){
cout<<"YES\n";
for(int i=1;i<=n*2;i++){
cout<<a[i]<<" ";
}
cout<<"\n";
goto togo;
}
}while(next_permutation(a+1,a+n*2+1));
cout<<"NO\n";
togo:;
}
else{
if(n%2==0){
cout<<"NO\n";
continue;
}
int cnt=0;
for(int i=1;i<=2*n;i+=2){
a[++cnt]=i;
}
for(int i=2;i<=2*n;i+=2){
a[++cnt]=i;
}
for(int i=2;i<=n;i+=2){
swap(a[i],a[i+n]);
}
cout<<"YES\n";
for(int i=1;i<=n*2;i++){
cout<<a[i]<<" ";
}
cout<<"\n";
}
}
return 0;
}
}
signed main(){return asbt::main();}
/*
1 4 5 8 9 12 13 2 3 6 7 10 11 14
*/
浙公網安備 33010602011771號