模拟赛
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;
}
T3
首先n+m-1有40
发现无障碍一定是放斜对角线
考虑正解:
发现相当于通过连接点和障碍分开矩形
建两个点,往边界连边
将障碍联通块进行一些合并
每个联通块向左下和右上对应联通块连边
每条路径就是一种答案
注意边界有屏障需要特判
简单dp即可
T4
若点权大于边权,肯定要走啊
考虑树形dp
记录二元组(x,y) 表示花费X代价,最终可能增加Y的收益
将所有点按X排序
每次将u及其子树内的点排序后捆绑,直到u这个点的收入>0
合并方式(a,b),(c,d)->(max(a,c-d),b+d)
写一个可合并堆
最后发现能走的地方是代价的一段前缀
二分答案即可
好题选讲
https://www.luogu.com.cn/problem/P7823
dpi,j表示考虑1~i时刻,一个数在j,另一个数在ki
转移即可
线段树优化
https://www.luogu.com.cn/problem/P11233
思想一样
还有一堆题
没空讲
关键词
得分
全局
决心&勇气