1. 首頁 > 生活百科 > >

n維偏序 方法記錄

生活百科


n維偏序 方法記錄

文章插圖
n維偏序 方法記錄

文章插圖
n維偏序 方法記錄

文章插圖
題解首先我們要對一個地點能否到達建立認知：一個地點能到達不僅僅是能從它的上一個點或上上個點跳到，而是能從第一個點開始跳一路跳到 。就好比說，咱吃了6個包子吃飽了，但咱不能只付第6個包子的錢 。
方法一：并查集遍歷整個序列，若一個點能由上一個點或上上個點跳到，則把出發點和目標點丟入同一個并查集 。最后檢查第一個點和最后一個點是否在同一個集合里 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=100005;int t;int fa[N];int h[N];template <typename T>inline void re(T &x) { x=0; int f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-f; for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48); x*=f; return;}template <typename T>void wr(T x) { if(x<0) putchar('-'),x=-x; if(x>9) wr(x/10); putchar(x%10^'0'); return;}int my_abs(int a,int b){ if(a>=b) return a-b; else return b-a;}int get(int x){ if(fa[x]!=x) fa[x]=get(fa[x]); return fa[x];}void merge(int r1,int r2){ fa[r2]=r1;}int main(){ freopen("n.in","r",stdin); freopen("n.out","w",stdout); re(t); while(t--) {int n,d1,d2;memset(h,0,sizeof(h));re(n);re(d1);re(d2);for(int i=1;i<=n;i++){re(h[i]);fa[i]=i;}for(int i=1;i<=n;i++){if(i>=2&&my_abs(h[i],h[i-1])<=d1){int r1=get(i);int r2=get(i-1);if(r1!=r2) merge(r1,r2);}if(i>=3&&h[i-2]>h[i-1]&&h[i-1]<h[i]&&my_abs(h[i],h[i-2])<=d2){int r1=get(i);int r2=get(i-2);if(r1!=r2) merge(r1,r2);}}if(get(1)==get(n)) puts("Yes");else puts("No"); } return 0;}方法二：標記法給每個能被跳到的點打上標記，而每一個能被跳到的點不僅要滿足存在上個點或上上個點能跳到這個點，還要滿足起跳點也能被跳到 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int a[100001];bool pd[100001];template <typename T>inline void re(T &x) { x=0; int f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-f; for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48); x*=f; return;}int main(){ freopen("n.in","r",stdin); freopen("n.out","w",stdout); int t,n,d1,d2; re(t); for(int x=1;x<=t;x++) {n=0,d1=0,d2=0;re(n);re(d1);re(d2);memset(pd,0,sizeof(pd));pd[1]=1;re(a[1]);for(int i=2;i<=n;i++){re(a[i]);if(abs(a[i]-a[i-1])<=d1&&pd[i-1]){pd[i]=1;continue;}if(abs(a[i]-a[i-2])<=d2&&pd[i-2]&&a[i]>a[i-1]&&a[i-1]<a[i-2]){pd[i]=1;continue;}}if(pd[n]) printf("Yes\n");else printf("No\n"); } return 0;}【n維偏序 方法記錄】

    推薦閱讀