赛时rank 11，T1 100pts，T2 17pts，T3 0pts，T4 0pts，T5 10pts
这场模拟赛就是糖，告诉我题目难度不按升序排列就是除了T1我都不会呗。
玩水 (water)
签成了，还签了个首切？
定义一个形如\(\begin{matrix} A*\\*\ \end{matrix}\)的为一个角，角的位置为A的位置。
有解的时候就是两个角相邻或者一个角在另一个角的左上方。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define InF(x) freopen(x".in","r",stdin)
#define OutF(x) freopen(x".out","w",stdout)
#define ErrF(x) freopen(x".err","w",stderr)
#define AnsF(x) freopen(x".ans","w",stdout)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = InF("in"),*OutFile = OutF("out");
// FILE *ErrFile = ErrF("err");
#else
FILE *Infile = InF("water"),*OutFile = OutF("water");
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e3 + 10;
int n,m;
int flag[N][N],pd[N][N];
char a[N][N];
inline int get(int x1,int y1,int x2,int y2){
return flag[x2][y2] - flag[x2][y1-1] - flag[x1-1][y2] + flag[x1-1][y1-1];
}
inline void solve(){
cin>>n>>m;
rep(i,0,n+1,1) rep(j,0,m+1,1) a[i][j] = ' ';
rep(i,0,n+1,1) rep(j,0,m+1,1) flag[i][j] = pd[i][j] = 0;
rep(i,1,n,1) cin>>(a[i]+1);
rep(i,1,n,1) rep(j,1,m,1){
if(a[i+1][j] == a[i][j+1]) flag[i][j] = pd[i][j] = 1;
}
rep(i,1,n,1) rep(j,1,m,1){
flag[i][j] += flag[i-1][j] + flag[i][j-1] - flag[i-1][j-1];
}
rep(i,1,n,1) rep(j,1,m,1)
if(pd[i][j] && (flag[i-1][j-1] >= 1||pd[i-1][j]||pd[i][j-1])){
return cout<<"1\n",void();
}
cout<<"0\n";
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
int T;cin>>T;while(T--) solve();
}
AVL 树
唐氏贪心构造题。
先放一个显然的结论：高度为\(i\)的平衡树最少的节点的递推式为\(f_{i} = f_{i-1}+f_{i-2}+1,f_{1} = 1,f_{0} = 0\)
这个可以通过打表或手膜得出来，证明的话手膜一下就明白了。
如果你不愿意手膜怎么办
证明 ：
思考一下就会发现，其实就是一个根节点(+1)，左边挂一个深度为\(i-1\)的AVL(\(f_{i-1}\))，右边挂一个深度为\(i-2\)的AVL(\(f_{i-2}\))。
所以节点数就是\(f_{i} = f_{i-1}+f_{i-1}+1\)
发现无论怎样，尽可能保留左儿子一定更优，所以优先递归左儿子。
考虑对于每一个节点，如何判断它是否可以保留。
回溯它的所有父亲，对于该节点是左孩子的情况，我们通过深度与AVL的定义，计算出保留它，至少需要右子树中有几个点，直到根，我们便算出了保留这个点需要整棵树至少多大。如果当前剩下的k足够，那就可以选。
但是此时可能会有一个错误，就是左儿子选了太多，右儿子不够选了怎么办?
预估一下AVL的深度。
定义\(dis_x\):以\(x\)为根的子树的极限可能深度；\(nw_x\)：已选子树中的最大深度；mx\(x\)：如果留下rt，需要至少往下延伸到第几层。
在查询时，利用这些数组找到可能的最大深度，进而判定是否留下；当确定一个点被选时，向上更新它的父亲的最大深度信息。
时间复杂度\(O(n\log n)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define InF(x) freopen(x".in","r",stdin)
#define OutF(x) freopen(x".out","w",stdout)
#define ErrF(x) freopen(x".err","w",stderr)
#define AnsF(x) freopen(x".ans","w",stdout)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = InF("in"),*OutFile = OutF("out");
// FILE *ErrFile = ErrF("err");
#else
FILE *Infile = InF("avl"),*OutFile = OutF("avl");
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int long long
const int N = 5e5 + 10;
int n,k,rt,son[N][2],dep[N],fa[N],dist[N],nw[N],mx[N],f[N];
bitset<N> ok;
#define eb emplace_back
#define lc(x) son[x][0]
#define rc(x) son[x][1]
void dfs1(int x){
dist[x] = dep[x] = dep[fa[x]] + 1;
if(lc(x)) dfs1(lc(x)),dist[x] = max(dist[x],dist[lc(x)]);
if(rc(x)) dfs1(rc(x)),dist[x] = max(dist[x],dist[rc(x)]);
}
inline void update(int x){
nw[x] = max(nw[x],dep[x]);
int now = x,f = fa[x];
while(f){
nw[f] = max(nw[f],dep[x]);//已经选择的子树中的最大深度
if(now == lc(f) && rc(f)) mx[rc(f)] = max(mx[rc(f)],nw[f] - 1);//至少要多少
now = f,f = fa[f];
}
}
inline int query(int x){
int now = x,F = fa[x],res = 0;
while(F){
if(now == lc(F)) res += f[max({nw[F]-1,dep[x]-1,mx[rc(F)]})-dep[F]];//取出最少深度
now = F,F = fa[F];
}
return res;
}
void dfs2(int x){
if(!x) return;
if(query(x) <= k-1){
ok.set(x);
k--;
update(x);
}
if(lc(x) && dist[lc(x)] >= mx[x]){//左子树优先
mx[lc(x)] = max(mx[lc(x)],mx[x]);
if(rc(x)) mx[rc(x)] = max(mx[rc(x)],mx[x]-1);
}
else if(rc(x)){//如果左子树不够就换右子树
mx[rc(x)] = max(mx[rc(x)],mx[x]);
if(lc(x)) mx[lc(x)] = max(mx[lc(x)],mx[x]-1);
}
dfs2(lc(x));dfs2(rc(x));
}
inline void solve(){
cin>>n>>k;
rep(i,1,n,1){
cin>>fa[i];int f = fa[i];
if(f == -1) rt = i,fa[i] = 0;
else{
if(i < f) lc(f) = i;
else rc(f) = i;
}
}
f[1] = 1;
rep(i,2,30,1) f[i] = f[i - 1] + f[i - 2] + 1;
dfs1(rt);dfs2(rt);
rep(i,1,n,1) cout<<ok[i];
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
暴雨
\(\checkmark\)
标签：11,int,rep,long,mx,using,csp,模拟,define From： https://www.cnblogs.com/hzoi-Cu/p/18466193