n维偏序
题目背景
1363擅长跑酷 (迫真！
题目描述
今天 \(1363\) 要挑战在 \(n\) 座排成一排的房屋上跑酷。第 \(i\) 座房子的高度是 \(h_i\)。初始时 \(1363\) 站在第一座房子的屋顶。
他有两个跑酷技能。假设他现在站在第 \(i\) 座房屋的屋顶上：
- 若 \(|h_i−h_{i+1}|≤d_1\) ，他可以到达第 \(i+1\) 座房屋的屋顶上。
- 若 \(h_i>h_{i+1}<h_{i+2}\) 且 \(|h_i−h_{i+2}|≤d_2\)，那么他可以到达第 i+2 座房屋的屋顶上。
输入格式
第一行一个数 \(t\) 表示数据组数。对于每组数据：
- 第一行$ 3$ 个整数 \(n,d_1,d_2\)。
- 接下来一行 \(n\) 个整数用空格分开表示 \(h_1,h_2,…,h_n\)。
输出格式
对于每组数据：如果 \(1363\) 可以走到第 \(n\) 座大楼上，输出 Yes，否则输出 No。
样例 #1
样例输入 #1
5
1 5 19
10
14 18 5
13 3 8 16 12 4 17 18 20 13 5 14 13 8
8 3 1
12 11 13 7 9 9 16 17
3 17 5
20 20 6
4 1 12
11 9 13 9
样例输出 #1
Yes
Yes
No
Yes
No
提示
对于所有数据，\(T\ge 1,∑n≤10^5,h_i≤10^5,0≤d_2≤d_1≤10^5\)。
题目分析
（黄题评高了吧
对于每一个点，我们都向前分析它是否可以到达，对于第一个技能，我们可以进行如下的判断：
inline bool check_1(int x){
if(!f[x-1]) return 0; //如果前一个位置都无法到达，那么该位置就不可能通过第一个技能到达
if(abs(h[x]-h[x-1])<=d_1)
return 1;
return 0;
}
相应的，第二个技能的判断如下：
inline bool check_2(int x){
if(!f[x-2]) return 0;
if(vis[x-1]&&abs(h[x]-h[x-2])<=d_2)
return 1;
return 0;
}
对于一个点，判断是否满足上面的任意一个条件即可，最后判断 \(n\) 是否可以到达。
代码如下：
点击查看代码
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define ll long long
using namespace std;
int n,d_1,d_2;
int h[100005];
bool f[100005];
bool vis[100005];
inline ll re(){
register ll k=0,f=1ll;
register char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1ll;
c=getchar();
}
while(isdigit(c)){
k=k*10ll+(c^48ll);
c=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
x=~x+1;
putchar('-');
}
if(x>9) wr(x/10ll);
putchar(x%10ll^48ll);
}
inline bool check_1(int x){
if(!f[x-1]) return 0;
if(abs(h[x]-h[x-1])<=d_1)
return 1;
return 0;
}
inline bool check_2(int x){
if(!f[x-2]) return 0;
if(vis[x-1]&&abs(h[x]-h[x-2])<=d_2)
return 1;
return 0;
}
signed main(){
int t=re();
while(t--){
n=re(),d_1=re(),d_2=re();
for(int i=1;i<=n;++i){
h[i]=re();
f[i]=vis[i]=0;
}
f[1]=1;
for(int i=2;i<=n;++i){
if(h[i-1]>=h[i]&&h[i]<=h[i+1]){
vis[i]=1;
++i;
}
}
for(int i=2;i<=n;++i)
if(check_1(i)||check_2(i))
f[i]=1;
f[n]?puts("Yes"):puts("No");
}
return 0;
}
掌控
题目背景
无
题目描述
公元 2044 年，人类进入了宇宙纪元。L 国有 \(n\) 个星球，分别编号为 \(1\) 到 \(n\) ，每一星球上有一个球长。有些球长十分强大，可以管理或掌控其他星球的球长，具体来说，第 \(i\) 个星球的球长管理 \(k_i+1\) 个星球的球长，分别是\(a_{i1},a_{i2},...,a_{ik_i} (a_{ij}<i)\) ，但若想要掌控一个星球的球长，就没那么容易了，第 \(i\) 个星球的球长掌控第 \(j\) 个星球的球长当且仅当他管理的所有球长都掌控第 \(j\) 个星球的球长，当然，所有球长都掌控他自己。
这些球长要召开 $q$ 次会议，每次会议由 $t_i$ 个球长召开，所有被他们掌控的球长都会参加，你作为宇宙会议室室长，需要知道每次会议有多少个球长参加。
输入格式
第一行一个数 \(n\) ，表示星球的个数；
接下来 \(n\) 行，每一行首先给出一个 \(k_i\) （可能为 \(0\) ），接下来 \(k_i\) 个数，描述第 i 个星球的球长管理的球长。保证没有重复；
接下来一行，给出一个数 \(q\) ，表示询问的个数；
接下来 \(q\) 行，每一行描述一个询问：格式同上文的格式。不保证没有重复（重复的球长当做只出现了一次）
输出格式
输出共 \(q\) 行，第 \(i\) 行输出第 \(i\) 次询问的答案。
样例 #1
样例输入 #1
7
0
1 1
1 1
1 2
2 2 3
0
2 2 6
3
2 2 3
2 3 5
2 4 5
样例输出 #1
3
3
4
提示
对于第一个询问，2、3号球长都掌控1号球长，所以总共有3个球长参会，编号分别为1，2，3；
对于第二个询问，3、5号球长都掌控1号球长，所以总共有3个球长参会，编号分别为1，3，5；
对于第三个询问，4号球长掌控第1、2号球长，所以总共有4个球长参会，编号分别为1，2，4，5；
特别说明：第5号球长没有掌控球长2，因为 \(3∈k_5\),但 \(2\) 不属于 \(k_3\) 。但球长4掌控球长2，因为球长掌控自己。
图片说明： \(u->v\) 表示 \(v\) 管理 \(u\)。
题目分析
仔细分析的话整张图所构成的掌控关系应该形成一棵树，如下图：
显然，dfs序小的会在深度较浅的位置，也就是被掌控。那么，每次询问，就是求掌控节点的并集，这样可以想到利用lca来求解。
对于获取答案，每次将要询问的节点全部放在栈中，答案每次累加栈顶元素和栈顶的下一个元素的lca的深度差并出栈即可。
代码如下：
点击查看代码
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int n,rt;
int dep[200005];
int f[200005][20];
inline ll re(){
register ll k=0,f=1ll;
register char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1ll;
c=getchar();
}
while(isdigit(c)){
k=k*10ll+(c^48ll);
c=getchar();
}
return 1ll*k*f;
}
void wr(ll x){
if(x<0){
x=~x+1;
putchar('-');
}
if(x>9) wr(x/10ll);
putchar(x%10ll^48ll);
}
struct Edge{
int v;
int nex;
}E[2000005];
int head[200005],tote;
inline void add_edge(int u,int v){
++tote;
E[tote].v=v,E[tote].nex=head[u],head[u]=tote;
}
int dfn[200005],idx;
void dfs(int x){
dfn[x]=++idx;
for(int i=head[x];i;i=E[i].nex)
dfs(E[i].v);
}
int s[200005],top;
inline bool cmp(int x,int y){
return dfn[x]<dfn[y];
}
inline int LCA(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;~i;--i)
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
if(u==v) return v;
for(int i=19;~i;--i){
if(f[u][i]!=f[v][i]){
u=f[u][i];
v=f[v][i];
}
}
return f[u][0];
}
signed main(){
// freopen("control.in","r",stdin);
// freopen("control.out","w",stdout);
n=re();
dfn[rt]=1;
for(int i=1;i<=n;++i){
int k,x=rt;
k=re();
if(k){
x=re();
while(--k){
int v=re();
x=LCA(x,v);
}
}
add_edge(x,i);
f[i][0]=x;
dep[i]=dep[x]+1;
for(int j=1;f[i][j-1];++j)
f[i][j]=f[f[i][j-1]][j-1];
}
dfs(rt);
int q=re();
while(q--){
int k=re();
for(int i=1;i<=k;++i) s[++top]=re();
sort(s,s+1+top,cmp);
ll ans=0;
while(top){
ans+=dep[s[top]]-dep[LCA(s[top],s[top-1])];
--top;
}
wr(ans);
putchar('\n');
}
return 0;
}
T3&T4 To be Continued...
标签：总结,掌控,return,int,ll,20221008,球长,测试,include From： https://www.cnblogs.com/WXDreemurr/p/16770128.html