主頁 > 軟體設計 > 【LDUOJ】寒假專題訓練——并查集、種類并查集、帶權并查集（參考題解）

【LDUOJ】寒假專題訓練——并查集、種類并查集、帶權并查集（參考題解）

2021-01-14 13:11:50 軟體設計

寫在前面： 希望大家把這篇題解作為參考題解，而不要去比著代碼抄襲、作弊，做一些沒有意義的事情，真正把并查集的原理搞懂才是此次訓練的真正目的，

并查集專題訓練題解

  • A. 親戚
    • 題目大意：
    • 題目思路：
    • Code:
  • B.無所不在的宗教
    • 題目大意：
    • 題目思路：
    • Code:
  • C.星際爭霸
    • 題目大意：
    • 題目思路：
    • Code：
  • D. 宇宙食物鏈
    • 題目大意：
    • 題目思路：
    • Code:
  • E. 超市
    • 題目大意：
    • 題目思路：
    • Code：
  • F. 奇偶博弈
    • 題目大意：
    • 題目思路：
    • Code:
  • G.天使與惡魔
    • 題目大意：
    • 題目思路：
    • Code:
  • 附言

A. 親戚

題目大意：

給出一些親戚的組合，親戚關系具有傳遞性，將一些關系結合后，進行 p p p次詢問，每次詢問 x , y x,y x,y是否為親戚

題目思路：

可以說是并查集的模板題

因為關系具有傳遞性，那么可以將這些人看作成一個個的點，親戚關系作為一條一條的邊，

那么對于每次詢問，就轉換為：判斷兩個點是否在同一個根樹下，

用并查集就非常好的判斷了，只會 f i n d ( ) find() find()函式即可，

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int Find(int x){
	return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main(){
	read(n);read(m);read(p);
	for(int i=1;i<=n;i++) pre[i] = i;
	for(int i=1;i<=m;i++){
		int x,y;read(x);read(y);
		int dx = Find(x),dy = Find(y);
		if(dx != dy) pre[dx] = dy;
	}
	
	for(int i=1;i<=p;i++){
		int x,y;read(x);read(y);
		if(Find(x) == Find(y)) puts("YES");
		else puts("NO");
	}
	return 0;

}

B.無所不在的宗教

題目大意：

每個學生都有自己的宗教信仰，已知 m m m對學生有相同的信仰，詢問共有幾個宗教？

題目思路：

將題意轉換理解一下

a , b a,b a,b信仰相同， b , c b,c b,c信仰相同，那么 a , c a,c a,c信仰肯定也是相同的，也就是說 a , b , c a,b,c a,b,c是同一個宗教，所以把人看成點，相同關系看為邊，那么就是求這個圖中有多少個連通塊，同一個連通塊內信仰相同，

連通塊：連通塊內任何兩點都可達

聯通塊的問題，可以用并查集去求解：因為(路徑壓縮)并查集的本質是將所有的點壓縮到一個根下，那么假設有一個根 r t rt rt，那么所有的組先是 r t rt rt的節點，都是該連通塊內的點，所以只需要判斷有幾個根即可

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int Find(int x){
	return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main(){
	int cas = 0;
	while(~scanf("%lld%lld",&n,&m)){
		if(n == 0 && m==0) break;
		for(int i=1;i<=n;i++) pre[i] = i;
		for(int i=1;i<=m;i++){
			int x,y;read(x);read(y);
			int dx = Find(x),dy = Find(y);
			if(dx != dy) pre[dx] = dy;
		}
		int ans = 0;
		for(int i=1;i<=n;i++)
			if(pre[i] == i) 
				ans++;
		printf("Case %d: %d\n",++cas,ans);
	}
	return 0;

}
`----------------------------------難度加大分割線------------------------------------------`

C.星際爭霸

題目大意：

給出 T T T條指令，初始時，所有戰艦所在的行均不相同，進行兩種操作：

  • M i j M\ i\ j M i j 將 i i i 所在的行 連接到 j j j所在行的后面
  • C i j C\ i\ j C i j 如果 i i i, j j j在同一行輸出它們兩個相距幾個戰艦，否則輸出-1

題目思路：

帶權并查集

因為普通并查集已經維護不了相距幾個戰艦的操作，所以此時需要把路徑壓縮時的邊附加一個權值

所以此時需要新開一個陣列 r k [ i ] rk[i] rk[i]， r k [ i ] rk[i] rk[i]代表i節點對于當前所處的連通塊根節點的排名，例如: 3 ? > 2 ? > 1 3->2->1 3?>2?>1，那么 1 1 1在該連通塊內排名第 1 1 1， 2 2 2排名第 2 2 2

如果此時需要將第 x x x個連通塊與第 y y y個連通塊進行合并，并以 y y y為根，那么y連通塊內所有點對于根的排名是不需要改變的，但是 x x x連通塊內的排名是需要改變的，但是又不能全改(時間不允許)，所以現在假設:

x x x聯通塊的根為 d x dx dx， y y y連通塊的根為 d y dy dy，

已知 r k [ x ] rk[x] rk[x]與 r k [ d x ] rk[dx] rk[dx]的大小關系， r k [ d x ] rk[dx] rk[dx]與 r k [ d y ] rk[dy] rk[dy]大小的關系,合并之后 d x dx dx的排名肯定為y連通塊內數量 + 1 +1 +1

那么x與dy的關系肯定也可以推出來的：
d x ? x = a , d y ? d x = b dx - x = a , dy - dx = b dx?x=a,dy?dx=b,那么 d y ? x = a + b dy - x = a+b dy?x=a+b，所以 x x x與 d y dy dy的關系也就知道了合并就好了，

Code：

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn],sz[maxn];
int rt[maxn],rk[maxn];
int Find(int x){
	if(pre[x] == x) return x;
	int t = pre[x];
	pre[x] = Find(pre[x]);
	rk[x] += rk[t];
	return pre[x];
}
int main(){
	read(n);
	for(int i=1;i<=500000;i++) pre[i] = i,sz[i] = 1;
	for(int i=1;i<=n;i++){
		char op[5];
		int x,y;
		scanf("%s%d%d",op,&x,&y);
		if(op[0] == 'M'){
			int dx = Find(x),dy = Find(y);
			pre[dx] = dy;
			rk[dx] = sz[dy];
			sz[dy]  += sz[dx];
		}else{
			int dx = Find(x),dy = Find(y);
			if(dx != dy) printf("-1\n");
			else printf("%d\n",abs(rk[x]-rk[y])-1);
		}
	}
	return 0;

}

D. 宇宙食物鏈

題目大意：

有一些動物，存在兩種關系:

  • X X X吃 Y Y Y， X X X也可以吃掉 Y Y Y的同類
  • X X X與 Y Y Y是同類， X X X可以吃 Y Y Y的獵物， Y Y Y可以吃 X X X的獵物，

然后給出一些食物關系(按順序)，你需要按順序判斷每次給出關系是否合法，不合法就拋棄并計數，否則就將加入到食物鏈中

題目思路：

這題也可以帶權并查集求解，但是上面題目帶權了之后，這個題目就不想再寫同樣的型別，

這里附帶種類并查集的做法：

對于一個動物來說，有三種集合：

  • 自己的同類
  • 自己的獵物
  • 自己的天敵(吃自己的)

對于一個動物，就可以用 i i i, i + n i+n i+n, i + 2 ? n i+2*n i+2?n去表示，

所以對于同類關系$(a,b)$的判斷：

1.首先判斷是否沖突，也就是說是否存在 a a a吃 b b b 或者 b b b吃 a a a 的現象

2.由于種類并查集所以只需要知道 a a a的獵物 和 b b b的天敵是否屬于同一集合，或者 b b b的獵物 和 a a a的天敵是否屬于同一集合，這樣可以用并查集輕松解決，

3.之后合并同類關系，合并 ( a , b ) , ( a + n , b + n ) , ( a + 2 ? n , b + 2 ? n ) (a,b),(a+n,b+n),(a+2*n,b+2*n) (a,b),(a+n,b+n),(a+2?n,b+2?n)即可，因為 a a a與 b b b是同類，也就說明 a a a與 b b b可以同時為天敵 或者 獵物

對于吃關系$(a,b)$的判斷：指a吃b

1.首先判斷是否沖突，也就是說是否存在 a a a, b b b同類 或者 b b b吃 a a a 的現象

2.之后合并吃關系，合并非常簡單自己看代碼推一下吧，

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int Find(int x){
	return  x == pre[x] ? x: pre[x] = Find(pre[x]);
}
int main(){

	read(n);read(m);
	for(int i=1;i<=3*n;i++) pre[i] = i;
	int ans = 0;
	for(int i=1;i<=m;i++){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(x>n || y > n){
			ans++;
			continue;
		}
		if(op == 2 && x == y){
			ans++;
			continue;
		}
		if(op == 1){///維護同類
			int ax = Find(x),ay = Find(y),bx = Find(x+n),by = Find(y+n),cx = Find(x+2*n),cy = Find(y+2*n);
			if(by == cx || bx == cy) ans++;
			else pre[ax] = ay,pre[bx] = by,pre[cx] = cy;
		}else{
			///x吃y
			int ax = Find(x),ay = Find(y),bx = Find(x+n),by = Find(y+n),cx = Find(x+2*n),cy = Find(y+2*n);
			if(by == cx || ax == ay) ans++;
			else pre[ay] = cx,pre[ax] = by,pre[bx] = cy;
		}
	}
	di(ans);
	return 0;

}

E. 超市

題目大意：

給出一些商品的價值與截止時間，問最多能賣多少錢

題目思路：

貪心的考慮，在沒到截至時間的情況下，肯定貪心的去賣價值大的

所以此時要按價值從大到小排序，表示能賣就賣，

如何知道“能賣”呢？

在該商品的截止時間之前，看是否存在一個空閑時間即可，但不可以隨便找一個空閑時間，防止 后面有截止時間小的，此時還要找最大的空閑時間，

所以題目轉換為了，每次找到一個小于當前時間的最大的時間，如果能找到就說明“能賣” 并 占用，否則不可，

這種問題模型有多種解法，二分維護最小值也可以，這里的并查集是最高效的解法:
初始令所有的 p r e i pre_i prei?都指向 i ? 1 i-1 i?1,然后就變成了一個鏈表，但是由于并查集可以路徑壓縮，所以可以省去中間已經占用的點，

復雜度 O ( N ) O(N) O(N)

Code：

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int vis[maxn];
int Find(int x){
	if(!vis[x]) return x;
	return pre[x] = Find(pre[x]); 
}
struct node{
	int w,id;
	bool friend operator<(node a,node b){return a.w > b.w;}
}q[maxn];
int main(){
	while(~scanf("%lld",&n)){
		for(int i=1;i<=10000;i++) pre[i] = i-1,vis[i] = 0;
		ll ans = 0;
		for(int i=1;i<=n;i++){
			read(q[i].w);
			read(q[i].id);
		}
		sort(q+1,q+1+n);
		for(int i=1;i<=n;i++){
			int op = Find(q[i].id);
			if(op){
				ans += q[i].w;
				vis[op] = 1;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;

}

F. 奇偶博弈

題目大意：

給出 N N N限制： l i , r i l_i,r_i li?,ri?區間 [ l i , r i ] [l_i,r_i] [li?,ri?]的和為偶數或者奇數

輸出最大 x x x，滿足 1 ? x 1 - x 1?x之間的限制合法

題目思路：

限制合法也就是說，不可以出現沖突

首先將題目給出的進行轉換: 令 f ( x ) f(x) f(x)為區間 [ 1 , x ] [1,x] [1,x]的和

那么區間 [ l i , r i ] [l_i,r_i] [li?,ri?]和是偶數 等價于 ( f ( r i ) ? f ( l i ? 1 ) ) % 2 = = 0 (f(r_i) - f(l_i-1))\%2 == 0 (f(ri?)?f(li??1))%2==0

也就說 f ( r i ) f(r_i) f(ri?) 與 f ( l i ? 1 ) f(l_i-1) f(li??1)對 2 2 2取余相同，同理是奇數則不同

所以每個點建兩個點，奇數點 x x x和偶數點 y + n y+n y+n，對于給出如果和為奇數，那么：就可以連邊： ( x , y + n ) ( y , x + n ) (x,y+n)(y,x+n) (x,y+n)(y,x+n)，反之同理

如何判斷沖突呢？當且僅當 x x x與 x + n x+n x+n在同一個集合內就出現沖突了

當然這個題肯定是可以帶權并查集寫的，只不過種類并查集好理解而已，(有能力的可以推一下帶權并查集)

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int vis[maxn];
int Find(int x){
	return pre[x] == x?x:pre[x] = Find(pre[x]);
}
struct node{
	int x,y;
	char op[10];
}q[maxn];
vector<int>v;
int getid(int x){
	return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}
int main(){
	read(n);read(m);

	for(int i=1;i<=m;i++){
		scanf("%d%d%s",&q[i].x,&q[i].y,q[i].op);
		v.push_back(q[i].x-1);
		v.push_back(q[i].y);
	}
	sort(v.begin(),v.end());
	v.erase((unique(v.begin(),v.end())),v.end());
	int sz = v.size();
	for(int i=1;i<=2*sz;i++) pre[i] = i;
	for(int i=1;i<=m;i++){
		int idx = getid(q[i].x-1),idy = getid(q[i].y);
		if(q[i].op[0] == 'e'){
			int dx = Find(idx),dy = Find(idy);
			pre[dx] = dy;
			dx = Find(idx+sz),dy = Find(idy+sz);
			pre[dx] = dy;

		}else{
			int dx = Find(idx),dy = Find(idy+sz);
			pre[dx] = dy;
			dx = Find(idx+sz),dy = Find(idy);
			pre[dx] = dy;
		}
		if(Find(idx) == Find(idx+sz) || Find(idy) == Find(idy+sz)){
			printf("%d\n",i-1);
			return 0;
		}
	}
	printf("%lld\n",m);
	return 0;

}

G.天使與惡魔

題目大意：

有 m m m個天使， p p p個惡魔，天使永遠說真話，惡魔永遠說假話，
下面給出n條語言：

  • x , y , y e s x,y,yes x,y,yes 代表 x x x說 y y y是天使
  • x , y , n o x,y,no x,y,no代表 x x x說 y y y不是天使

問是否存在唯一一種方案使得有 m m m個天使， p p p個惡魔？

如果存在吧啦吧啦，不存在巴啦啦~

題目思路：

帶權并查集 + dp路徑還原

有能力就做一下，這里講的不深入，如果想學習可以 Q Q QQ QQ私信我

利用帶權并查集推出每個節點與所在聯通塊根的關系，那么就把每個連通塊內分成了兩類，同類和異類

然后利用分組背包，將每個連通塊看成一個組，同類一樣物品，異類一樣物品，每組只能選一個，沒組必須選，看方案數是否唯一即可

最后根據背包 d p dp dp的性質和上面的要求進行路徑還原即可，

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
//#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn],rk[maxn];///rk_i帶權并查集
int vis[maxn];
int Find(int x){
	if(pre[x] == x) return x;
	int t = pre[x];
	pre[x] = Find(pre[x]);
	rk[x] = rk[x]^rk[t];
	return pre[x];
}
int w[maxn][2];
int save[maxn];
int dp[1005][305],visp[maxn];
int main(){
	while(~scanf("%lld%lld%lld",&n,&m,&p)){
		if(n == 0 && m == 0 && p == 0) break;
		for(int i=1;i<=m+p;i++) pre[i] = i,rk[i] = 0;
		for(int i=1;i<=m+p;i++) w[i][0] = w[i][1] = 0,vis[i] = 0;
		
		for(int i=1;i<=n;i++){
			char op[5];int x,y;
			scanf("%d%d%s",&x,&y,op);
			if(op[0] == 'n'){
				int dx = Find(x),dy = Find(y);
				if(dx != dy){
					pre[dx] = dy;
					rk[dx] = !(rk[x] ^ rk[y]);
				}
			}else{
				int dx = Find(x),dy = Find(y);
				if(dx != dy){
					pre[dx] = dy;
					rk[dx] = (rk[x] ^ rk[y]);
				}
			}
		}

		int cnt = 0;
		for(int i=1;i<=m+p;i++){
			int dx = Find(i);
			w[dx][rk[i]]++;
			if(!vis[dx]) vis[dx] = 1,save[++cnt] = dx;
		}

		memset(dp,0,sizeof(dp));
		dp[0][0] = 1;
		for(int i=1;i<=cnt;i++) visp[i] = 0;
		for(int i=1;i<=cnt;i++){
			int dx = save[i];
			for(int k=m;k>=w[dx][0];k--)
				dp[i][k] += dp[i-1][k-w[dx][0]];
			for(int k=m;k>=w[dx][1];k--)
				dp[i][k] += dp[i-1][k-w[dx][1]];
		}
		memset(visp,0,sizeof(visp));
		if(dp[cnt][m] == 1){
			ll y = m;
			for(int i=cnt;i>=1;i--){
				if(y>=w[save[i]][0] && dp[i-1][y-w[save[i]][0]] == 1){
					 visp[save[i]] = 0;
					 y -= w[save[i]][0];
				}else if(y>=w[save[i]][1] && dp[i-1][y-w[save[i]][1]] == 1){
					 visp[save[i]] = 1;
					 y -= w[save[i]][1];
				}
			}
			for(int i=1;i<=m+p;i++){
				int dx = Find(i);
				if(!visp[dx] && !rk[i]) printf("%d\n",i);
				if(visp[dx] && rk[i]) printf("%d\n",i);
			}
			printf("end\n");
		}else puts("no");
	}
	return 0;

}
/***
10
2
1 2 even
1 3 odd
***/

附言

光光能有什么壞心思呢，寫這么久希望大家有所提高罷了，

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/248642.html

標籤：其他

上一篇：Redis高性能原因決議——Redis內部的阻塞式操作及應對方法

下一篇：JBOSS安全配置與應用

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 面試突擊第一季，第二季，第三季

    第一季必考 https://www.bilibili.com/video/BV1FE411y79Y?from=search&seid=15921726601957489746 第二季分布式 https://www.bilibili.com/video/BV13f4y127ee/?spm_id_fro ......

    uj5u.com 2020-09-10 05:35:24 more
  • 第三單元作業總結

    1.前言 這應該是本學期最后一次寫作業總結了吧。總體來說，對作業的節奏也差不多掌握了，作業做起來的效率也更高了。雖然和之前的作業一樣，作業中都要用到新的知識，但是相比之前，更加懂得了如何利用工具以及資料。雖然之間卡過殼，但總體而言，這幾次作業還算完成的比較好。 2.作業程序總結 相比前兩個單元，此單 ......

    uj5u.com 2020-09-10 05:35:41 more
  • 北航OO（2020）第四單元博客作業暨課程總結博客

    北航OO（2020）第四單元博客作業暨課程總結博客 本單元作業的架構設計 在本單元中，由于UML圖具有比較清晰的樹形結構，因此我對其中需要進行查詢操作的元素進行了包裝，在樹的父節點中存盤所有孩子的參考。考慮到性能問題，我采用了快取機制，一次查詢后盡可能快取已經遍歷過的資訊，以減少遍歷次數。 本單元我 ......

    uj5u.com 2020-09-10 05:35:48 more
  • BUAA_OO_第四單元

    一、UML決議器設計 ? 先看下題目：第四單元實作一個基于JDK 8帶有效性檢查的UML(Unified Modeling Language)類圖，順序圖，狀態圖分析器 MyUmlInteraction，實際上我們要建立一個有向圖模型，UML中的物件（元素）可能與同級元素連接，也可與低級元素相連形成 ......

    uj5u.com 2020-09-10 05:35:54 more
  • 6.1邏輯運算子

    邏輯運算子 1. && 短路與 運算式1 && 運算式2 01.運算式1為true并且運算式2也為true 整體回傳為true 02.運算式1為false，將不會執行運算式2 整體回傳為false 03.只要有一個運算式為false 整體回傳為false 2. || 短路或 運算式1 || 運算式2 ......

    uj5u.com 2020-09-10 05:35:56 more
  • BUAAOO 第四單元 & 課程總結

    1. 第四單元：StarUml檔案決議 本單元采用了圖模型決議UML。 UML檔案可以抽象為圖、子圖、邊的邏輯結構。 在實作中，圖的節點包括類、介面、屬性，子圖包括狀態圖、順序圖等。 采用了三次遍歷UML元素的方法建圖，第一遍遍歷建點，第二、三次遍歷設定屬性、連邊，實作圖物件的初始化。這里借鑒了一些 ......

    uj5u.com 2020-09-10 05:36:06 more
  • 談談我對C# 多型的理解

    面向物件三要素：封裝、繼承、多型。 封裝和繼承，這兩個比較好理解，但要理解多型的話，可就稍微有點難度了。今天，我們就來講講多型的理解。 我們應該經常會看到面試題目：請談談對多型的理解。 其實呢，多型非常簡單，就一句話：呼叫同一種方法產生了不同的結果。 具體實作方式有三種。 一、多載 多載很簡單。 p ......

    uj5u.com 2020-09-10 05:36:09 more
  • Python 資料驅動工具：DDT

    背景 python 的unittest 沒有自帶資料驅動功能。 所以如果使用unittest，同時又想使用資料驅動，那么就可以使用DDT來完成。 DDT是 “Data-Driven Tests”的縮寫。 資料：http://ddt.readthedocs.io/en/latest/ 使用方法 dd. ......

    uj5u.com 2020-09-10 05:36:13 more
  • Python里面的xlrd模塊詳解

    那我就一下面積個問題對xlrd模塊進行學習一下： 1.什么是xlrd模塊？ 2.為什么使用xlrd模塊？ 3.怎樣使用xlrd模塊？ 1.什么是xlrd模塊？ ?python操作excel主要用到xlrd和xlwt這兩個庫，即xlrd是讀excel，xlwt是寫excel的庫。 今天就先來說一下xl ......

    uj5u.com 2020-09-10 05:36:28 more
  • 當我們創建HashMap時，底層到底做了什么？

    jdk1.7中的底層實作程序（底層基于陣列+鏈表） 在我們new HashMap()時，底層創建了默認長度為16的一維陣列Entry[ ] table。當我們呼叫map.put(key1,value1)方法向HashMap里添加資料的時候： 首先，呼叫key1所在類的hashCode()計算key1 ......

    uj5u.com 2020-09-10 05:36:38 more
最新发布
  • 【中介者設計模式詳解】C/Java/JS/Go/Python/TS不同語言實作

    * 中介者模式是一種行為型設計模式，它可以用來減少類之間的直接依賴關系，
    * 將物件之間的通信封裝到一個中介者物件中，從而使得各個物件之間的關系更加松散。
    * 在中介者模式中，物件之間不再直接相互互動，而是通過中介者來中轉訊息。 ......

    uj5u.com 2023-04-20 08:20:47 more
  • 露天煤礦現場調研和交流案例分享

    他們集團的資訊化公司及研究院在一個礦區正在做智能礦山的統一平臺的 試點，專案投資大概1億，包括了礦山的各方面的內容，顯示得我們這次交流有點多余。他們2年前開始做智能礦山的規劃，有很多煤礦行業專家的加持，他們的描述是非常完美，但是去年底應該上線的平臺，現在還沒有看到影子。他們確實有很多場景需求，但是被... ......

    uj5u.com 2023-04-20 08:20:25 more
  • 《社區人員管理》實戰案例設計&個人案例分享

    設計是一個讓人夢想成真程序，開始編碼、測驗、除錯之前進行需求分析和架構設計，才能保證關鍵方面都做正確 ......

    uj5u.com 2023-04-20 08:20:17 more
  • 軟體架構生態化-多角色交付的探索實踐

    作為一個技術架構師，不僅僅要緊跟行業技術趨勢，還要結合研發團隊現狀及痛點，探索新的交付方案。在日常中，你是否遇到如下問題 “ 業務需求排期長研發是瓶頸；非研發角色感受不到研發技改提效的變化；引入ISV 團隊又擔心質量和安全，培訓周期長“等等，基于此我們探索了一種新的技術體系及交付方案來解決如上問題。 ......

    uj5u.com 2023-04-20 08:20:10 more
  • 【中介者設計模式詳解】C/Java/JS/Go/Python/TS不同語言實作

    * 中介者模式是一種行為型設計模式，它可以用來減少類之間的直接依賴關系，
    * 將物件之間的通信封裝到一個中介者物件中，從而使得各個物件之間的關系更加松散。
    * 在中介者模式中，物件之間不再直接相互互動，而是通過中介者來中轉訊息。 ......

    uj5u.com 2023-04-20 08:19:44 more
  • 露天煤礦現場調研和交流案例分享

    他們集團的資訊化公司及研究院在一個礦區正在做智能礦山的統一平臺的 試點，專案投資大概1億，包括了礦山的各方面的內容，顯示得我們這次交流有點多余。他們2年前開始做智能礦山的規劃，有很多煤礦行業專家的加持，他們的描述是非常完美，但是去年底應該上線的平臺，現在還沒有看到影子。他們確實有很多場景需求，但是被... ......

    uj5u.com 2023-04-20 08:19:07 more
  • 《社區人員管理》實戰案例設計&個人案例分享

    設計是一個讓人夢想成真程序，開始編碼、測驗、除錯之前進行需求分析和架構設計，才能保證關鍵方面都做正確 ......

    uj5u.com 2023-04-20 08:18:57 more
  • 軟體架構生態化-多角色交付的探索實踐

    作為一個技術架構師，不僅僅要緊跟行業技術趨勢，還要結合研發團隊現狀及痛點，探索新的交付方案。在日常中，你是否遇到如下問題 “ 業務需求排期長研發是瓶頸；非研發角色感受不到研發技改提效的變化；引入ISV 團隊又擔心質量和安全，培訓周期長“等等，基于此我們探索了一種新的技術體系及交付方案來解決如上問題。 ......

    uj5u.com 2023-04-20 08:18:49 more
  • 05單件模式

    #經典的單件模式 public class Singleton { private static Singleton uniqueInstance; //一個靜態變數持有Singleton類的唯一實體。 // 其他有用的實體變數寫在這里 //構造器宣告為私有，只有Singleton可以實體化這個類! ......

    uj5u.com 2023-04-19 08:42:51 more
  • 【架構與設計】常見微服務分層架構的區別和落地實踐

    軟體工程的方方面面都遵循一個最基本的道理：沒有銀彈，架構分層模型更是如此，每一種都有各自優缺點，所以請根據不同的業務場景，并遵循簡單、可演進這兩個重要的架構原則選擇合適的架構分層模型即可。 ......

    uj5u.com 2023-04-19 08:42:41 more

Copyright © 2010-2020 有解無憂