A Mocha 上小班啦
题意
求有 n 位且每位数字都不同的最小正整数 1 ≤ n ≤ 20
签到题
B hash
分析：
其实很好想到dp 但是数据范围不允许n方
考虑本题的性质 发现长度超过15 就会超过模数 所以对于第二维枚举 不用从头开始枚举
直接从结尾往前十五位开始枚举就好
E Serval 的俳句
分析：
先找到最短出现5次相同的字符的前缀 然后删去
继续找最短出现7次相同的字符的前缀 继续删去
最后找最短出现5次的相同的字符的前缀
如果找不到 则无解
F 集合之最
做的时候把这个题目想复杂了
注意到 可以构造 A=0,1,2,3,4，，，，k
则 A+A=0,1,2,3,4，，，，，，2k
所以对于奇数方案一定能行
对于偶数方案呢？
特判n=2和n=4都无解
一种巧妙的方案是 A=0,2,3,4，，，，k
把 1 从中去掉 A+A=0,2,3,4,5，，，，2k
G Mocha 上大班啦
分析：
观察之后就会发现 这题压根和期望值没关系
对于每一次操作 无论成功与否 0还是0 1还是1
所以只要判断最初的异或和 1的个数即可
H 旋转水管
分析：
感觉就直接搜索就行了 很多状态都是行不通的
J mex tree
分析：
首先可以考虑将0 作为根节点 因为任何mex=k 都需要包含0
对于每个节点u 其值为val[u]
要求 mex=val[u] 就只能选择其父亲上的连通块
又因为要求最大 所以其上方能选的都选 只要不包含val[u]即可
但是如果u的子树里面出现了val[x] <val[u] 这种情况就不成立
只需要维护一个子树中最小值即可
特别判断根节点 只能取子树中最大的一个
对于mex=n 很明显 整颗树都能选择
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e6+5;
int n,rt;
int a[maxn],sz[maxn],ans[maxn],minn[maxn];
vector<int>Q[maxn];
void dfs(int,int);
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==0)rt=i;
}
for(int i=2,x;i<=n;i++){
scanf("%d",&x);
Q[x].push_back(i);
Q[i].push_back(x);
}
dfs(rt,rt);
for(int i=0;i<Q[rt].size();i++)
ans[0]=max(ans[0],sz[Q[rt][i]]);
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
cout<<n;
return 0;
}
void dfs(int u,int fa){
sz[u]=1;
minn[u]=a[u];
int mm=maxn;
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
if(to==fa)continue;
dfs(to,u);
sz[u]+=sz[to];
mm=min(minn[to],mm);
}
minn[u]=min(minn[u],mm);
if(mm<a[u])ans[a[u]]=0;
else ans[a[u]]=n-sz[u];
}