【题解】牛客OI周赛14-提高组题解
感谢各位参加本次比赛
T1
数据范围1（5分）：什么都不会的话可以dfs直接搜
数据范围2（15分）：由于地图较小，障碍很多，直接dp即可
数据范围3（15分）：因为需要走最短路径，所以最短路径一定是向右走m步，向上走n步，只需要确定哪些步向右，哪些步向上。组合数公式即可，Ans=
数据范围4（15分）：一个障碍，思路同上一个数据范围，只需要去除不合法的情况，即路径中经过了障碍点的情况数。这个不符合的情况数可以用乘法原理，从起点到障碍点*从障碍点到终点的路径条数算出来。是规模更小的子问题。
数据范围5（15分）：多了一个点，还是同样的思路。不过需要考虑两个点的位置关系，如果不能同时经过，就直接减，否则需要加上同时经过两个障碍点的情况数，也就是容斥原理。
数据范围6（20分）：一样的思路，容斥的时候多加几种情况即可。
（所以输出frog是骗不了分的）
前30分的暴力可以随便乱搞得到，重点讲正解。
很显然是状压题目，预处理出change[i][j]表示在刺激第i个点，经过j秒后对整个神经树的影响。1代表这个点被反转，0代表没有反转。所以算贡献时将 sta |= change 即可
那么就可以枚举时间，每个情况，每个点的影响，得到转移方程：
dp[i+1][j^change[k][i]] = dp[i][j]?true:false
std:
数据范围3（15分）：因为需要走最短路径，所以最短路径一定是向右走m步，向上走n步，只需要确定哪些步向右，哪些步向上。组合数公式即可，Ans=
数据范围4（15分）：一个障碍，思路同上一个数据范围，只需要去除不合法的情况，即路径中经过了障碍点的情况数。这个不符合的情况数可以用乘法原理，从起点到障碍点*从障碍点到终点的路径条数算出来。是规模更小的子问题。
数据范围5（15分）：多了一个点，还是同样的思路。不过需要考虑两个点的位置关系，如果不能同时经过，就直接减，否则需要加上同时经过两个障碍点的情况数，也就是容斥原理。
数据范围6（20分）：一样的思路，容斥的时候多加几种情况即可。
T2
先考虑答案是否一定存在，由于刺激一个点以后，下一秒刺激其父亲节点，等价于单点改变这个点的状态。所以我们可以用2s的时间单点修改状态，答案一定<=2n且>=n，一定不会输出“frog”（所以输出frog是骗不了分的）
前30分的暴力可以随便乱搞得到，重点讲正解。
很显然是状压题目，预处理出change[i][j]表示在刺激第i个点，经过j秒后对整个神经树的影响。1代表这个点被反转，0代表没有反转。所以算贡献时将 sta |= change 即可
那么就可以枚举时间，每个情况，每个点的影响，得到转移方程：
dp[i+1][j^change[k][i]] = dp[i][j]?true:false
std:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,fa[25],maxn;
int need;//最后需要的状态
int s[25][50];//第i个点和它的前j个祖先有哪些点
bool dp[50][1<<17];
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
void print(int x)
{
while(x)
{
cout<<(x&1);
x>>=1;
}
puts("");
}
void init()
{
//把需要的状态压成二进制
for(register int i=1;i<=n;++i)
{
read(fa[0]);
if(fa[0]) need|=1<<(i-1);
}
// print(need);
//处理出每个时刻点i的反转情况
for(register int i=1;i<=n;++i)
{
s[i][1]=1<<(i-1);
int x=fa[i];
for(register int j=2;j<=(n<<1);++j)
{
s[i][j]=s[i][j-1];
if(x) s[i][j]|=(1<<(x-1));
x=fa[x];
}
}
}
void work()
{
dp[0][need]=true;
for(register int i=1;i<=(n<<1);++i)//枚举每个时刻
{
for(register int j=0;j<=maxn;++j)//枚举每个初始情况
{
if(!dp[i-1][j]) continue;
for(register int k=0;k<=n;++k)//枚举每个点
{
int now=j^s[k][i];//now是反转后的情况
// print(now);
dp[i][now]=true;
if(!now)
{
printf("%d\n",i);
exit(0);
}
}
}
}
}
int main()
{
// freopen("20.in","r",stdin);
// freopen("20.out","w",stdout);
read(n);maxn=(1<<n)-1;
for(register int i=2;i<=n;++i) read(fa[i]);
init();
work();
return 0;
} T3
给定一颗或几颗树，询问到x到第k远点的距离，树随机生成，期望树高为logn以下对于各数据范围给出做法
1.n,q≤1,000，暴力求出每个点到x的距离排序即可，注意可能每次dis数组要清空
2.k=1，即求到x最远的点的距离，树形dp，随意选一个根，第一遍dp求出根到各个点的距离dis，再一次dp分别求出各个点先向上走再向下走到叶子的最大距离f，对每个点x取max( dis[rt] - dis[x] , f[x] )即可
3.m=n-1，这个没什么说的，有没有都一样，只是没有的时候要注意初始化
4.注意树高期望为log，那么可以考虑乱搞，将所有询问离线，仍随意选择一个根，先求出dis数组，如果向下递归到v，则会将v所在子树的dis都减去w，其他点加上w（这一步可以变成v所在子树的dis减去2*w，其他点不变，询问时需要加回来一个w），而一个子树的dfs序是连续的，转成序列后就变成了区间修改，求第k大的问题，所以用值域线段树加二分或者平衡树维护，由于期望树高是log，那么每个点期望被修改log次，直接暴力单点修改会修改nlogn次，修改一次的复杂度为logn，那么整个算法的时间复杂度为O(nlog2n+qlogn)
P.S.暴力修改的前提是期望树高为logn，如果不是随机生成的树，那么就要用点分树转成平衡状态了qwq，时间复杂度是O(nlog3n)
std:
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int n,m,T;
int ndsum,root,l,r,p;
ll dis[N],ans[N];
bool vis[N];
struct Node {int k,opt;};
struct Tree
{
int ch[2],size,key;
ll val;
}t[N];
struct Edge
{
int next,to;
ll dis;
}edge[N<<1];int head[N],cnt=1;
vector <Node> q[N];
void add_edge(int from,int to,ll dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
template<class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
inline int add_node(ll val,int nd=-1)
{
if(nd==-1) nd=++ndsum;//带回收的加点
t[nd].size=1;
t[nd].key=rand();
t[nd].val=val;
t[nd].ch[0]=t[nd].ch[1]=0;
return nd;
}
inline void update(int rt) {t[rt].size=t[t[rt].ch[0]].size+t[t[rt].ch[1]].size+1;}
void split(int rt,ll x,int &l,int &r)
{
if(!rt) {l=0;r=0;return;}
if(t[rt].val<=x) {l=rt; split(t[rt].ch[1],x,t[rt].ch[1],r);}
else {r=rt; split(t[rt].ch[0],x,l,t[rt].ch[0]);}
update(rt);
}
int merge(int l,int r)
{
if(!l||!r) return l+r;
if(t[l].key<t[r].key)
{
t[l].ch[1]=merge(t[l].ch[1],r);
update(l);
return l;
}
else
{
t[r].ch[0]=merge(l,t[r].ch[0]);
update(r);
return r;
}
}
int query(int rt,int k)
{
if(k<=t[t[rt].ch[0]].size) return query(t[rt].ch[0],k);
if(k==t[t[rt].ch[0]].size+1) return rt;
return query(t[rt].ch[1],k-t[t[rt].ch[0]].size-1);
}
inline void Add(ll x,int nd=-1)//添加一个元素
{
split(root,x,l,r);
root=merge(merge(l,add_node(x,nd)),r);
}
inline int Erase(ll x)//删除一个元素，并返回其序号
{
split(root,x,p,r);
split(p,x-1,l,p);
int ret=p;
p=merge(t[p].ch[0],t[p].ch[1]);
root=merge(l,merge(p,r));
return ret;
}
void init(int rt,int fa,ll len)//初始化子树得到dis
{
Add(len);
dis[rt]=len;
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
init(v,rt,len+edge[i].dis);
}
}
void T_dfs(int rt,int fa,ll val)//给rt这个子树加上val
{
int nd=Erase(dis[rt]);
dis[rt]+=val;
Add(dis[rt],nd);
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
T_dfs(v,rt,val);
}
}
void dfs(int rt,int fa,ll len)//递归处理每一个点
{
vis[rt]=1;
if(!q[rt].empty())//计算rt上的问题
{
for(vector<Node>::iterator it=q[rt].begin();it!=q[rt].end();++it)
{
if((it->k)<ndsum) ans[it->opt]=t[query(root,ndsum-(it->k)+1)].val+len;
else ans[it->opt]=-1;
}
}
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
T_dfs(v,rt,-edge[i].dis*2);//减掉两倍
dfs(v,rt,len+edge[i].dis);
T_dfs(v,rt,edge[i].dis*2);//回溯
}
}
int main()
{
srand((unsigned)time(NULL));
read(n);read(m);read(T);
for(int i=1;i<=m;++i)
{
int x,y; ll z;
read(x);read(y);read(z);
add_edge(x,y,z);
add_edge(y,x,z);
}
for(int i=1;i<=T;++i)
{
int x,k;
read(x);read(k);
q[x].push_back((Node){k,i});
}
for(int i=1;i<=n;++i)
if(!vis[i])
{
ndsum=root=0;
init(i,0,0LL);
dfs(i,0,0LL);
}
for(int i=1;i<=T;++i) printf("%lld\n",ans[i]);
return 0;
} 
而且一般说的也很宽泛 不是特指后端
改成项目亮点观感会更好