20221008(大寄)
题目
t1 \(n\)维偏序
递推
乍一看这题就像个\(O(n)\)的递推，甚至根本算不上递推。如果可以到达第\(i-1\)座房屋，或者第\(i-2\)座房屋，并且可以从他们其中之一到达第\(i\)座房屋，就可以进行转移。\(v[i]\)表示能不能到第\(i\)座房屋，则有
然后就没有然后了。。。附上一份丑陋的代码
点击查看代码
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=100005;
int n,d1,d2;
int h[N],dp[N];
inline int miN(int a,int b){
return a<b?a:b;
}
int main(){
int t;
in(t);
while(t--){
in(n),in(d1),in(d2);
fo(i,1,n)in(h[i]);
dp[1]=dp[2]=0x3f3f3f3f;
if(n>=1)dp[1]=0;
if(n>=2)if(abs(h[2]-h[1])<=d1)dp[2]=1;
fo(i,3,n){
dp[i]=0x3f3f3f3f;
if(abs(h[i]-h[i-1])<=d1)dp[i]=miN(dp[i],dp[i-1]+1);
if(h[i-1]<h[i-2]&&h[i-1]<h[i]&&abs(h[i]-h[i-2])<=d2)dp[i]=miN(dp[i],dp[i-2]+1);
}
dp[n]==0x3f3f3f3f?puts("No"):puts("Yes");
}
return 0;
}
t2 掌控
题意分析
每个球长管理一些其他球长，每个球长掌控其本身，一个球长\(i\)能掌控另一个球长\(j\)的条件是他所管理的所有球长都掌控另一个球长\(j\)。每次会议参加的球长包括召开会议的球长和他们掌控的球长。
暴力（40pts）
每次询问时暴力地找出召开会议的球长所掌控的球长，然后统计答案。
特殊情况(20pts)
\(k_{i}\le1\)的特殊情况，即每个球长最多只管理一个球长。那自然，每个球长管理的球长就是被掌控的球长。
LCA(100pts)
建树
题目只提供了每个球长所管理的球长的信息，但其实我们可以根据这些信息构造出保存球长掌控关系信息的一棵树。考虑我们之前的节点已经成功构造出该树,现在要加入一个新的节点\(i\)，他所管理的节点为\(j,k,l\)，而他所能掌控的节点就是\(j,k,l\)都能掌控的节点。因为这棵树所保存的是掌控关系，所以\(j\)和\(k\)共同掌控的节点就是他们的\(lca，\)即最近公共祖先。而\(i\)所能掌控的节点自然就是\(j,k,l\)的\(lca\)了，最后我们只需要将节点\(i\)连向\(j,k,l\)的\(lca\)就完成了对\(i\)所掌控的节点的信息的维护。至于为什么最后构建出来的是一棵树，在了解完加入节点的过程后自然就明白了，即每次加入节点只会在新加入节点与之前加入的节点之间建立\(1\)条边，边数永远比点数少\(1\)。
可能会出现有些点一个其他节点都无法掌控的情况，这时候就需要建立一个超级点\(0\)，让所有一个节点都无法掌控的与\(0\)建立一条边。
查询
对于每个询问，按照建树的思路我们就可以发现，实际上要求的就是所有召开会议的球长的节点编号到根节点的节点个数，不过两两球长之间有可能会有重复的路径，而这个重复的路径就是这两个点的\(lca\)到根节点的节点数，貌似只需要用这两个节点的深度和减去他们\(lca\)的深度即可。但是直接这样做会出现问题，因为每次询问不止两个点，这样你就得每次遍历询问的点两两计算，不然就会多算或者少减，但这样时间复杂度又上去了，那该怎么办呢？我们可以按照一定顺序去两两计算，又能保证每个点被遍历的次数足够小吗？是可以的，我们按照dfs序从大到小地对他们进行两两计算，就可以保证:我们两两计算时的两个点在同一条链上时不重不漏地减去重复的部分。
求lca不要使用树链剖分，容易tle
代码
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
template<typename T>inline void in(T &x){
x=0;int f=0;char c=getchar();
for(;!isdigit(c);c=getchar())f|=(c=='-');
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=f?-x:x;
}
template<typename T>inline void out(T x){
if(x<0)x=~x+1,putchar('-');
if(x>9)out(x/10);
putchar(x%10^48);
}
const int N=200005;
int n;
int k;
struct edge{
int v,nex;
}e[N<<1];
int head[N],tot;
inline void add(int u,int v){e[++tot].v=v,e[tot].nex=head[u],head[u]=tot;}
int dep[N],fa[N][35];
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=30;i>=0;--i){
if(dep[fa[x][i]]<dep[y])continue;
x=fa[x][i];
}
if(x==y)return x;
for(int i=30;i>=0;--i){
if(fa[x][i]==fa[y][i])continue;
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int dfn[N],cnt;
inline void dfs(int x){
dfn[x]=++cnt;
for(int i=head[x];i;i=e[i].nex){
int v=e[i].v;
dfs(v);
}
}
inline bool cmp(int a,int b){return dfn[a]<dfn[b];}
int a[N],ans,top;
int main(){
in(n);
int v,kv;
dep[0]=0;
fo(i,1,n){
kv=0;
in(k);
fo(j,1,k){
in(v);
if(j==1)kv=v;
else kv=lca(kv,v);
}
add(kv,i);
fa[i][0]=kv;
dep[i]=dep[kv]+1;
for(int j=1;fa[i][j-1];++j)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
dfs(0);
int q;
in(q);
while(q--){
int g;
in(g);
fo(i,1,g)in(a[++top]);
sort(a+1,a+top+1,cmp);
ans=0;
while(top)ans+=dep[a[top]]-dep[lca(a[top],a[top-1])],top--;
out(ans),putchar('\n');
}
return 0;
}