首页 › 题库 › C/C++编程考级 › 2 并查集

C/C++编程八级 题库

共 12 道题 · 按题型筛选,点「查看答案」核对解析
章节 2 并查集 清除
1 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

开关问题

有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)

时间限制:1000

内存限制:65536

输入

输入第一行有一个数K,表示以下有K组测试数据。 每组测试数据的格式如下: 第一行 一个数N(0 < N < 29) 第二行 N个0或者1的数,表示开始时N个开关状态。 第三行 N个0或者1的数,表示操作结束后N个开关的状态。 接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。

输出

如果有可行方法,输出总数,否则输出“Oh,it's impossible~!!” 不包括引号

样例输入

2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0

样例输出

4
Oh,it's impossible~!!

提示

第一组数据的说明:一共以下四种方法: 操作开关1 操作开关2 操作开关3 操作开关1、2、3 (不记顺序)

答案与解析
参考答案
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 35;
bool a[MAXN][MAXN];

inline int read() {
  int x;
  scanf("%d", &x);
  return x;
}

int gauss(int n) {
  int rank = 0;
  for (int d = 0; d < n; ++d) { /* d for diagonal */
    int i;
    /* try to find first line whose d'th element = 1 */
    for (i = d; i < n; ++i)
      if (a[i][d] == 1)
        break;

    /* not found */
    if (i == n)
      continue;

    /* found */

    /* Step 1: make the d'th element of rank'th line to be 1, by swapping i'th
     * line and rank'th line, including the rightmost column */
    for (int j = 0; j <= n; ++j)
      swap(a[rank][j], a[i][j]);
    /* Step 2: eliminating the following line if the d'th element = 1, including
     * the rightmost column */
    for (i = rank + 1; i < n; ++i)
      if (a[i][d])
        for (int j = 0; j <= n; ++j)
          a[i][j] ^= a[rank][j];

    ++rank;
  }

  /* up to now, the rank+'th line should be all 0 */
  /* if the rightmost column is 1, bad equation, return -1 */
  for (int i = rank; i < n; ++i)
    if (a[i][n])
      return -1;

  /* otherwise, return the rank */
  return rank;
}

int main() {
  int K = read();
  for (int k = 0; k < K; ++k) {
    memset(a, 0, sizeof(a));
    int N = read();
    for (int i = 0; i < N; ++i)
      a[i][N] ^= read();
    for (int i = 0; i < N; ++i)
      a[i][N] ^= read();
    for (int x = 0; x < N; ++x)
      a[x][x] = 1;
    for (;;) {
      int x = read() - 1, y = read() - 1;
      if (x == -1)
        break;
      a[y][x] = 1;
    }
    int rank = gauss(N);
    if (rank == -1)
      printf("Oh,it's impossible~!!\n");
    else
      printf("%d\n", 1 << (N - rank));
  }
  system("pause");
  return 0;
}
题目详情
2 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

冰阔落I

老王喜欢喝冰阔落。

初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。

有m 次操作,每次操作包含两个整数x与y。

若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。

最后,老王想知道哪些杯子有冰阔落。

时间限制:10000

内存限制:65536

输入

有多组测试数据,少于5 组。 每组测试数据,第一行两个整数 n, m (n, m<=50000)。接下来 m 行,每行两个整数 x, y (1<=x, y<=n)。

输出

每组测试数据,前m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数,表示有阔落的杯子数量。 第 m+2 行有若干个整数,从小到大输出这些杯子的编号。

样例输入

3 2

1 2

2 1

4 2

1 2

4 3

样例输出

No

Yes

2

1 3

No

No

2

1 4

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000 + 5], cnt;
int root(int x) {
  if (a[x] == x)
    return x;
  return root(a[x]);
}
void find(int l, int r) {
  int ll = root(l), rr = root(r);
  if (ll == rr) {
    printf("Yes\n");
    // cout<<"Yes"<<endl;
  } else {
    a[rr] = ll;
    cnt--;
    // cout<<"No"<<endl;
    printf("No\n");
  }
}
int main() {
  int m, n, l, r;
  while (scanf("%d %d", &n, &m) != EOF) {
    cnt = n;
    for (int i = 1; i <= n; i++) {
      a[i] = i;
    }
    for (int i = 1; i <= m; i++) {
      scanf("%d %d", &l, &r);
      // cin>>l>>r;
      find(l, r);
    }
    printf("%d\n", cnt);
    // cout<<cnt<<endl;
    for (int i = 1; i <= n; i++)
      if (a[i] == i)
        printf("%d ", i); // cout<<i<<" ";
    // cout<<endl;
    printf("\n");
  }
  return 0;
}
题目详情
3 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

冰阔落 I

老王喜欢喝冰阔落。

初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。

有m 次操作,每次操作包含两个整数x与y。

若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。

最后,老王想知道哪些杯子有冰阔落。

 

时间限制:10000

内存限制:65536

输入

有多组测试数据,少于 5 组。 每组测试数据,第一行两个整数 n, m (n, m<=50000)。接下来 m 行,每行两个整数 x, y (1<=x, y<=n)。

输出

每组测试数据,前 m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数,表示有阔落的杯子数量。 第 m+2 行有若干个整数,从小到大输出这些杯子的编号。

样例输入

3 2
1 2
2 1
4 2
1 2
4 3

样例输出

No
Yes
2
1 3 
No
No
2
1 4
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000+5],cnt;
int root(int x)
{
    if(a[x]==x) return x;
    return root(a[x]);
}
void find(int l,int r)
{
    int ll=root(l),rr=root(r);
    if(ll==rr)
    {
        printf("Yes\n");
        //cout<<"Yes"<<endl;
    }
    else
    {
        a[rr] =ll;
        cnt--;
        //cout<<"No"<<endl;
        printf("No\n");
    }
}
int main()
{
    int m,n,l,r;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        cnt=n;
        for(int i=1;i<=n;i++)
        {
            a[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&l,&r);
            //cin>>l>>r;
            find(l,r);
        }
        printf("%d\n",cnt);
        //cout<<cnt<<endl;
        for(int i=1;i<=n;i++)
            if(a[i]==i) printf("%d ",i);//cout<<i<<" ";
        //cout<<endl;
        printf("\n");
    }
    return 0;

}


题目详情
4 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

最短路径问题

平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。

若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

时间限制:1000

内存限制:131072

输入

共n+m+3行,其中: 第一行为整数n。 第2行到第n+1行(共n行) ,每行两个整数x和y,描述了一个点的坐标。 第n+2行为一个整数m,表示图中连线的个数。 此后的m 行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。 最后一行:两个整数s和t,分别表示源点和目标点。

输出

仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度。

样例输入

5 

0 0 

2 0 

2 2 

0 2 

3 1 

5 

1 2 

1 3 

1 4 

2 5 

3 5 

1 5

样例输出

3.41

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, m, sx, ex, x, y;
double range[101][101], dot[101][3];
double findrange(int sx, int ex) {
  int a = (dot[ex][1] - dot[sx][1]);
  int b = (dot[ex][2] - dot[sx][2]);
  return sqrt(a * a + b * b);
}
int main() {
  memset(range, 127, sizeof(range));
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 2; j++) {
      cin >> dot[i][j];
    }
    range[i][i] = 0;
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> sx >> ex;
    range[sx][ex] = range[ex][sx] = findrange(sx, ex); // 无向图
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (k != i && k != j && i != j) {
          range[i][j] = min(range[i][j], range[i][k] + range[k][j]);
        }
      }
    }
  } // 弗洛伊德算法核心:三重循环遍历;外层循环是k可以理解为,中间点是k是遍历所有i和j
  cin >> x >> y;
  printf("%.2lf", range[x][y]);
  return 0;
}


//参考答案2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 123
#define E 1e-6
using namespace std;
int x[N],y[N];
double g[N][N];
double calculate(int x1,int y1,int x2,int y2)
{
    return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
int main()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    cin>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            g[i][j]=INF;
            g[j][i]=INF;
        }
        g[i][i]=0;
    }
 
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        double temp=calculate(x[u],y[u],x[v],y[v]);
        g[u][v]=temp;
        g[v][u]=temp;
    }
 
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(g[i][j]>g[i][k]+g[k][j])
                    g[i][j]=g[i][k]+g[k][j];
    int u,v;
    cin>>u>>v;
    printf("%.2lf",g[u][v]);
 
    return 0;
}
题目详情
5 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

社交网络

随着社交平台的兴起,人们之间的沟通变得越来越密切。通过Facebook的分享功能,只要你是对方的好友,你就可以转发对方的状态,并且你的名字将出现在“转发链”上。经过若干次转发以后,很可能A分享了一条好友C的状态,而C的这条状态实际上是分享B的,但A与B可能并不是好友,即A通过C间接分享了B的状态。

给定你N个人之间的好友关系,好友关系一定是双向的。只要两个人是好友,他们就可以互相转发对方的状态,无论这条状态是他自己的,还是他转发了其他人的。现在请你统计,对于每两个人,他们是否有可能间接转发对方的状态。

时间限制:1000

内存限制:262144

输入

第一行1个整数N(1<=N<=300)。 接下来N行每行N个整数,表示一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人是好友,0则表示不是好友。 保证矩阵的主对角线上都是1,并且矩阵关于主对角线对称。

输出

一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人可能间接转发对方的状态,0则表示不可能。

样例输入

5
11000
11100
01100
00011
00011

样例输出

11100
11100
11100
00011
00011

提示

在输入数据中,1与2是好友,2与3是好友,4与5是好友。 因此1、2、3有可能互相转发状态;4、5有可能互相转发状态。这两组人之间则不可能。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, fa[310];
char a[310][310];
int find(int x) {
  if (x == fa[x]) {
    return x;
  }
  return find(fa[x]);
}
void merge(int x, int y) {
  if (find(x) == find(y)) {
    return;
  }
  fa[find(x)] = find(y);
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] == 49 && i != j) {
        merge(i, j);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (find(i) == find(j)) {
        cout << 1;
      } else {
        cout << 0;
      }
    }
    cout << '\n';
  }
}
题目详情
6 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

最短路径问题

平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。

  若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

时间限制:1000

内存限制:131072

输入

共n+m+3行,其中: 第一行为整数n。 第2行到第n+1行(共n行) ,每行两个整数x和y,描述了一个点的坐标。 第n+2行为一个整数m,表示图中连线的个数。 此后的m 行,每行描述一条连线,由两个整数i和j组成,表示第i个点和第j个点之间有连线。 最后一行:两个整数s和t,分别表示源点和目标点。

输出

仅一行,一个实数(保留两位小数),表示从s到t的最短路径长度。

样例输入

5 
0 0 
2 0 
2 2 
0 2 
3 1 
5 
1 2 
1 3 
1 4 
2 5 
3 5 
1 5

样例输出

3.41
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, m, sx, ex, x, y;
double range[101][101], dot[101][3];
double findrange(int sx, int ex) {
  int a = (dot[ex][1] - dot[sx][1]);
  int b = (dot[ex][2] - dot[sx][2]);
  return sqrt(a * a + b * b);
}
int main() {
  memset(range, 127, sizeof(range));
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 2; j++) {
      cin >> dot[i][j];
    }
    range[i][i] = 0;
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> sx >> ex;
    range[sx][ex] = range[ex][sx] = findrange(sx, ex); // 无向图
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (k != i && k != j && i != j) {
          range[i][j] = min(range[i][j], range[i][k] + range[k][j]);
        }
      }
    }
  } // 弗洛伊德算法核心:三重循环遍历;外层循环是k可以理解为,中间点是k是遍历所有i和j
  cin >> x >> y;
  printf("%.2lf", range[x][y]);
  return 0;
}


//参考答案2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 123
#define E 1e-6
using namespace std;
int x[N],y[N];
double g[N][N];
double calculate(int x1,int y1,int x2,int y2)
{
    return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
int main()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    cin>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            g[i][j]=INF;
            g[j][i]=INF;
        }
        g[i][i]=0;
    }
 
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        double temp=calculate(x[u],y[u],x[v],y[v]);
        g[u][v]=temp;
        g[v][u]=temp;
    }
 
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(g[i][j]>g[i][k]+g[k][j])
                    g[i][j]=g[i][k]+g[k][j];
    int u,v;
    cin>>u>>v;
    printf("%.2lf",g[u][v]);
 
    return 0;
}
题目详情
7 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

控制公司

有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司12%的股票。据说,如果至少满足了以下条件之一,公司A就可以控制公司B了:

l  公司A = 公司B。

l  公司A拥有大于50%的公司B的股票。

l  公司A控制K(K >= 1)个公司,记为C1, ..., CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ .... + xK > 50%。(ps:A可以控制自己,即Ci可以为A)

你将被给予一系列的三对数(i,j,p),表明公司i拥有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。

写一个程序读入三对数(i,j,p),并且找出所有的数对(h,s),使得公司h控制公司s。

 

时间限制:1000

内存限制:65536

输入

第一行: N,表明接下来三对数的数量。 第二行到第N+1行:每行三个整数作为一个三对数(i,j,p),如上文所述。 I,J≤100,N,P≤100

输出

输出零个或更多个的控制其他公司的公司。每行包括两个整数表明序号为第一个整数的公司控制了序号为第二个整数的公司。将输出的每行以第一个数字升序排列(并且第二个数字也升序排列来避免并列)。请不要输出控制自己的公司。

样例输入

3
1 2 80
2 3 80
3 1 20

样例输出

1 2
1 3
2 3
答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
unsigned long long int n,gf[1000][1000],mp[1000][1000];
void jf(int x,int y)//x公司加上i公司股票
{
	for(int i=1;i<=100;i++)
	{
		if(gf[x][i]+gf[y][i]>100) gf[x][i]=100;//判断 
		else gf[x][i]+=gf[y][i];
	}
	return ;
}
void find(int x)//递归 
{
	for(int i=1;i<=100;i++)
	{
		if(gf[x][i]>=50&&mp[x][i]==0&&x!=i)
		{
			mp[x][i]=1;//标记 x公司可以控制i公司 
			jf(x,i);
			find(x);//加上以后再找一遍 
			return ;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		gf[a][b]=c;
	 } 
	int t=1;
	while(t<=100)//枚举每一个公司 
	{
		find(t);
		t++;
	}
	for(int i=1;i<=100;i++)
	{
		for(int j=1;j<=100;j++)
		{
			if(mp[i][j]==1) cout<<i<<" "<<j<<endl; 
		}
	}
}


题目详情
8 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

发现它,抓住它

一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:

1. D [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为

2. A [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为

注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。

时间限制:1000

内存限制:65536

输入

第一行是测试数据的数量T(1<=T<=20)。 每组测试数据的第一行包括两个数N和M,分别表示案件的数量和信息的数量,其后M行表示按时间顺序收到的M条信息。

输出

对于每条需要回答的信息,你需要输出一行答案。如果是同一个团伙所为,回答"In the same gang.",如果不是,回答"In different gangs.",如果不确定,回答”Not sure yet."。

样例输入

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

样例输出

Not sure yet.
In different gangs.
In the same gang.
答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
template<class T>
struct DisjointSet{
	int *parent;
	T *data;
	map<T,int> m;
	int capacity;
	int size;
	DisjointSet(int max=1000){
		capacity=max;
		size=0;
		parent=new int[max+1];
		data=new T[max+1];
	}
	~DisjointSet(){
		delete [] parent;
		delete [] data;
	}
	bool insert(T x){
		if(size==capacity) return false;
		size++;
		data[size]=x;
		parent[size]=-1;
		m[x]=size;
		return true;
	}
	int getIndex(T x){
		for(int i=1;i<=size;i++)
		  if(data[i]==x)
		    return i;
		return -1; 
	}
	int find(T x){
		typename map<T,int>::iterator it;
		it=m.find(x);
		if(it==m.end()) return -1;
		int i,rt;
		i=rt=it->second;
		while(parent[rt]>0)
		  rt=parent[rt];
		return rt;
	}
	void unionSet(T x,T y){
		int rx,ry;
		rx=find(x);
		ry=find(y);
		if(rx==-1||ry==-1) return ;
		if(rx==ry) return ;
		if(parent[rx]<parent[ry]){
			parent[rx]+=parent[ry];
			parent[ry]=rx;
		}
		else{
			parent[ry]+=parent[rx];
			parent[rx]=ry;
		}
		find(x);
		find(y);
	}
};
int main(){
	int t;
	cin>>t;
	while(t--){
		DisjointSet<int> s;
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) s.insert(i);
		for(int i=1;i<=m;i++){
			int a,b;
			char c;
			cin>>c>>a>>b;
			if(c=='D')
			  s.unionSet(a,b);
			else{
				if(s.find(a)!=s.find(b)) cout<<"Not sure yet.";
				else if(s.parent[a]==s.parent[b]) cout<<"In the same gang.";
				else cout<<"In different gangs.";
				cout<<endl;
			}
		}
	}
	return 0;
}


题目详情
9 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

冰阔落 I(2024.3八级)

老王喜欢喝冰阔落。

初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。

有m 次操作,每次操作包含两个整数x与y。

若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。

最后,老王想知道哪些杯子有冰阔落。

时间限制:10000

内存限制:65536

输入

有多组测试数据,少于 5 组。 每组测试数据,第一行两个整数 n, m (n, m<=50000)。接下来 m 行,每行两个整数 x, y (1<=x, y<=n)。

输出

每组测试数据,前 m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数,表示有阔落的杯子数量。 第 m+2 行有若干个整数,从小到大输出这些杯子的编号。


样例输入

3 2
1 2
2 1
4 2
1 2
4 3

样例输出

No
Yes
2
1 3 
No
No
2
1 4
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000+5],cnt;
int root(int x)
{
    if(a[x]==x) return x;
    return root(a[x]);
}
void find(int l,int r)
{
    int ll=root(l),rr=root(r);
    if(ll==rr)
    {
        printf("Yes\n");
        //cout<<"Yes"<<endl;
    }
    else
    {
        a[rr] =ll;
        cnt--;
        //cout<<"No"<<endl;
        printf("No\n");
    }
}
int main()
{
    int m,n,l,r;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        cnt=n;
        for(int i=1;i<=n;i++)
        {
            a[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&l,&r);
            //cin>>l>>r;
            find(l,r);
        }
        printf("%d\n",cnt);
        //cout<<cnt<<endl;
        for(int i=1;i<=n;i++)
            if(a[i]==i) printf("%d ",i);//cout<<i<<" ";
        //cout<<endl;
        printf("\n");
    }
    return 0;

}
题目详情
10 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

开关问题(2023.12)

有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)

时间限制:1000

内存限制:65536

输入

输入第一行有一个数K,表示以下有K组测试数据。 每组测试数据的格式如下: 第一行 一个数N(0 < N < 29) 第二行 N个0或者1的数,表示开始时N个开关状态。 第三行 N个0或者1的数,表示操作结束后N个开关的状态。 接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。

输出

如果有可行方法,输出总数,否则输出“Oh,it's impossible~!!” 不包括引号


样例输入

2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0

样例输出

4
Oh,it's impossible~!!

提示

第一组数据的说明:一共以下四种方法: 操作开关1 操作开关2 操作开关3 操作开关1、2、3 (不记顺序)

答案与解析
参考答案
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 35;
bool a[MAXN][MAXN];

inline int read() {
  int x;
  scanf("%d", &x);
  return x;
}

int gauss(int n) {
  int rank = 0;
  for (int d = 0; d < n; ++d) { /* d for diagonal */
    int i;
    /* try to find first line whose d'th element = 1 */
    for (i = d; i < n; ++i)
      if (a[i][d] == 1)
        break;

    /* not found */
    if (i == n)
      continue;

    /* found */

    /* Step 1: make the d'th element of rank'th line to be 1, by swapping i'th
     * line and rank'th line, including the rightmost column */
    for (int j = 0; j <= n; ++j)
      swap(a[rank][j], a[i][j]);
    /* Step 2: eliminating the following line if the d'th element = 1, including
     * the rightmost column */
    for (i = rank + 1; i < n; ++i)
      if (a[i][d])
        for (int j = 0; j <= n; ++j)
          a[i][j] ^= a[rank][j];

    ++rank;
  }

  /* up to now, the rank+'th line should be all 0 */
  /* if the rightmost column is 1, bad equation, return -1 */
  for (int i = rank; i < n; ++i)
    if (a[i][n])
      return -1;

  /* otherwise, return the rank */
  return rank;
}

int main() {
  int K = read();
  for (int k = 0; k < K; ++k) {
    memset(a, 0, sizeof(a));
    int N = read();
    for (int i = 0; i < N; ++i)
      a[i][N] ^= read();
    for (int i = 0; i < N; ++i)
      a[i][N] ^= read();
    for (int x = 0; x < N; ++x)
      a[x][x] = 1;
    for (;;) {
      int x = read() - 1, y = read() - 1;
      if (x == -1)
        break;
      a[y][x] = 1;
    }
    int rank = gauss(N);
    if (rank == -1)
      printf("Oh,it's impossible~!!\n");
    else
      printf("%d\n", 1 << (N - rank));
  }
  system("pause");
  return 0;
}
题目详情
11 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

社交网络(2023.12)

随着社交平台的兴起,人们之间的沟通变得越来越密切。通过Facebook的分享功能,只要你是对方的好友,你就可以转发对方的状态,并且你的名字将出现在“转发链”上。经过若干次转发以后,很可能A分享了一条好友C的状态,而C的这条状态实际上是分享B的,但A与B可能并不是好友,即A通过C间接分享了B的状态。

给定你N个人之间的好友关系,好友关系一定是双向的。只要两个人是好友,他们就可以互相转发对方的状态,无论这条状态是他自己的,还是他转发了其他人的。现在请你统计,对于每两个人,他们是否有可能间接转发对方的状态。

时间限制:1000

内存限制:262144

输入

第一行1个整数N(1<=N<=300)。 接下来N行每行N个整数,表示一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人是好友,0则表示不是好友。 保证矩阵的主对角线上都是1,并且矩阵关于主对角线对称。

输出

一个N*N的01矩阵,若矩阵的第i行第j列是1,表示这两个人可能间接转发对方的状态,0则表示不可能。


样例输入

5
11000
11100
01100
00011
00011

样例输出

11100
11100
11100
00011
00011

提示

在输入数据中,1与2是好友,2与3是好友,4与5是好友。 因此1、2、3有可能互相转发状态;4、5有可能互相转发状态。这两组人之间则不可能。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, fa[310];
char a[310][310];
int find(int x) {
  if (x == fa[x]) {
    return x;
  }
  return find(fa[x]);
}
void merge(int x, int y) {
  if (find(x) == find(y)) {
    return;
  }
  fa[find(x)] = find(y);
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] == 49 && i != j) {
        merge(i, j);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (find(i) == find(j)) {
        cout << 1;
      } else {
        cout << 0;
      }
    }
    cout << '\n';
  }
}
题目详情
12 简答题 偏难 C/C++编程考级 ·C/C++编程八级 · 2 并查集

逆散列问题

给定长度为 N 的散列表,处理整数最常用的散列映射是 H(x) = x%N。如果我们决定用线性探测解决冲突问题,则给定一个顺序输入的整数序列后,我们可以很容易得到这些整数在散列表中的分布。例如我们将 1、2、3 顺序插入长度为 3 的散列表HT[]后,将得到HT[0]=3,HT[1]=1,HT[2]=2的结果。

但是现在要求解决的是“逆散列问题”,即给定整数在散列表中的分布,问这些整数是按什么顺序插入的?

时间限制:5000

内存限制:65536

输入

输入的第一行是正整数 N(≤ 1000),为散列表的长度。第二行给出了 N 个整数,其间用空格分隔,每个整数在序列中的位置(第一个数位置为0)即是其在散列表中的位置,其中负数表示表中该位置没有元素。题目保证表中的非负整数是各不相同的。

输出

按照插入的顺序输出这些整数,其间用空格分隔,行首尾不能有多余的空格。注意:对应同一种分布结果,插入顺序有可能不唯一。例如按照顺序 3、2、1 插入长度为 3 的散列表,我们会得到跟 1、2、3 顺序插入一样的结果。在此规定:当前的插入有多种选择时,必须选择最小的数字,这样就保证了最终输出结果的唯一性。

样例输入

11
33 1 13 12 34 38 27 22 32 -1 21

样例输出

1 13 12 21 33 34 38 27 22 32
答案与解析
参考答案
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int m;
int main()
{
	cin >> m;
	vector<int>v(m);
	vector<int>temp;
	for (int i = 0; i < m; i++)
	{
		cin >> v[i];
		if (v[i] != -1)
			temp.push_back(v[i]);
	}
	sort(temp.begin(), temp.end());
	int length = temp.size();
	vector<bool>finding_value(length, 0);
	vector<bool>hashtable(m, 0);
	int num = 0, index = 0;
	//length 为插入数据长度
	while (num != length)
	{
		for (int i = 0; i < length; i++)
		{
			if (!finding_value[i]) //如果这个值没有找到位置
			{
				int posi = temp[i] % m;
				//temp[i]的线性探测初始位置
				if (v[posi] == temp[i])
				{
					printf("%d ", temp[i]);
					finding_value[i] = 1;
					hashtable[posi] = 1;
					num++;
					break;
				}
				else
				{
					for (int t = 0; t < m; t++)
					{
						int new_posi = (posi + t) % m;
						if (hashtable[new_posi])
							continue;
						if (!hashtable[new_posi] && v[new_posi] != temp[i])
							break;
						finding_value[i] = hashtable[new_posi] = 1;
						printf("%d ", temp[i]);
						num++;
						break;
					}
				}
			}
		}
	}
}
题目详情