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

2025国庆Day7

news 2025/10/8 16:05:48

模拟赛

T1

将所有ai=bi的数取出来

这些数的mex即为答案

然后对于每个i,判定ai，bi是否等于答案

相当于固定某些位置

答案就是2^cnt

cnt是没被固定的位置的数量

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;	
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
const int MOD=1e9+7;
int a[100005],b[100005];
unordered_map<int,int> sum;
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++){b[i]=read();if(a[i]==b[i]) sum[b[i]]++;} int minn=0;while(sum[minn]) minn++;cout<<minn<<' ';int ans=1;for(int i=1;i<=n;i++){if(a[i]!=minn&&b[i]!=minn) ans=ans*2%MOD;}cout<<ans<<'\n';return 0;
}

T2

容易发现一维dp有后效性

dpi,j表示考虑1~i，选了j个的最大字典序

简单转移

（代码滚动数组滚掉一维）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;	
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
string maxx,A,B,C;
int l[25],n,gop[55],cnt;
string dp[55][3];
void dfs(int x){if(x==n){string s="";for(int i=1;i<=n;i++){if(!l[i]) s+=A[i-1];}for(int i=1;i<=n;i++){if(!l[i]) s+=B[i-1];}for(int i=1;i<=n;i++){if(!l[i]) s+=C[i-1];}if(s>maxx) maxx=s;return ;}x++;dfs(x);l[x]=1;dfs(x);l[x]=0;
}
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);cin>>A>>B>>C;	maxx=A+B+C;A=" "+A;B=" "+B;C=" "+C;n=A.size();if(n<=20){dfs(0);	cout<<maxx<<'\n';return 0;}for(int i=1;i<=n;i++){for(int j=i;j;j--){string ss1=dp[j][0]+dp[j][1]+dp[j][2];string ss2=dp[j-1][0]+A[i]+dp[j-1][1]+B[i]+dp[j-1][2]+C[i];if(ss2>ss1){dp[j][0]=dp[j-1][0]+A[i];dp[j][1]=dp[j-1][1]+B[i];dp[j][2]=dp[j-1][2]+C[i];}}}for(int i=1;i<=n;i++){string ss=dp[i][0]+dp[i][1]+dp[i][2];if(ss>maxx) maxx=ss;}cout<<maxx<<'\n';return 0;
}