模拟赛
T1
对h离散化，枚举x，分类讨论某些位置淹没后段的个数的变化情况即可
可恶的毒瘤出题人竟然造了一个高度全0的hack
注意特判此时答案为0
#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;
}
pair<int,int> st[1000005];
int h[1000005];
vector<int> mh[1000005];
int vis[1000005];
signed main()
{//freopen("filename.in", "r", stdin);//freopen("filename.out", "w", stdout);int n=read();int f=0;for(int i=1;i<=n;i++){st[i].first=read();st[i].second=i;if(st[i].first) f=1;}if(!f){cout<<0<<'\n';return 0;}sort(st+1,st+n+1);int cnt=0,las=-1;for(int i=1;i<=n;i++){if(st[i].first!=las) cnt++;h[st[i].second]=cnt;las=st[i].first;}for(int i=1;i<=n;i++){mh[h[i]].push_back(i);}int ans=1;int maxx=1;vis[0]=vis[n+1]=1;for(int i=1;i<=cnt;i++){for(auto ed:mh[i]){if(vis[ed-1]==0&&vis[ed+1]==0) ans++;else if(vis[ed-1]==1&&vis[ed+1]==1) ans--;vis[ed]=1;}
// cout<<ans<<'\n';maxx=max(maxx,ans);}cout<<maxx<<'\n';return 0;
}
T2
数位DP
先考虑L==R的dp
套上数位DP
记忆化 or 递推
注意判前导 0
T3
把从a->b的链提取并重新编号
发现在这条链上，a,b若有人走进子树，两人永远不会相撞
预处理链上的点走进子树还能走多远和链上的前缀和
从相撞时的答案倒推出起点的答案
可用st表做到O(logn)的更新答案
也可O(1)更新答案
T4
恶心数论
n=2可直接构造
最后得出结论：
对x质因数分解
有效质因数个数为m
当且仅当m>=n时，有解
对所有质因数排序
ai=i*x/pi
这里一定有pi>i,因此pi不是i的质因数
复杂度O(sqrt(n))
搜索
记忆化搜索（其实是DP）
如T2
例：CF628D
求[l,r]=[1,r]-[1,l-1]
CF1734F
观察可得对于编号的二进制
每次在前面加一个1，反转一次
于是sk=(p(k)%2)
p(k)表示k二进制下1的个数
题目转化成p(i^(i+n))%2==0的个数
二进制数位DP
注意进位问题
双向搜索
n=40左右使用
复杂度O(2^(n/2))
CF1767E
对相邻两个点的颜色建图连边
得到的图的最小边覆盖即为答案（自环则这个点必选）
众所不周知最小边覆盖=最大独立集
折半搜索经典应用
先dp出0~2^n-1的答案
后面的直接爆搜算答案
小火车
网格图BFS
（图论？）
CF1613E
结合博弈
考虑建出博弈图
拓扑排序
省选 2023 过河卒
思路差不多
根据题目模拟