原来80分,发现并解决了问题……但变成20分了,求解决!
查看原帖
原来80分,发现并解决了问题……但变成20分了,求解决!
565040
Conan15楼主2022/5/22 11:51

因为我是在其它网站上做的(AcWing),所以点进去后不是洛谷的评测界面,但这个网站是公开的,我的代码可以看得到!大家帮忙查个错呗~~

原来的代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 2000010;
vector<int> v[N];
int n, cnt[N], ans[N];
bool cmp(int a, int b) {
	if (cnt[a] == cnt[b]) return a < b;
	return cnt[a] < cnt[b];
}

void work() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) v[i].clear(), ans[i] = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cnt[i]);
		for (int j = 1; j <= cnt[i]; j++) {
			int x; scanf("%d", &x);
			v[x].push_back(i);     //会第x题的人有i
		}
	}
	for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end(), cmp);   //按照会的题目数量排序
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < v[i].size(); j++) {
		    //v[i][j - 1]和v[i][j]有同样会的题i
			if (ans[v[i][j - 1]] == 0) ans[v[i][j - 1]] = v[i][j];
			else if (ans[v[i][j - 1]] != v[i][j]) {
				int res = ans[v[i][j - 1]];
				if (cmp(v[i][j], res)) res = v[i][j];
				printf("YES\n%d %d\n",v[i][j - 1], res);
				return;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
	    if (!ans[i]) continue;
	    //如果ans[i]和i都有一道对方不会的题,那么这就是一组答案
	}
	puts("NO");  return;
}

int main() {
	int t; scanf("%d", &t);
	while (t--) work();
	return 0;
}

过不了自己编的一个测试点:

1
7
3 5 6 7
5 1 2 3 4 5
3 1 3 4
0
0
0
0

输出结果应当是 YES 1 2 但程序输出了NO

于是我调了一下,发现在前面的初步“找讨论对象”的时候第一和第三个人都指向了第二个人。

但是第二个人没有指向任何人!

所以结果就变成了NO

于是我改了一下代码,加入了STLSTLsetset,进行交集操作,代码求查错!谢谢大佬们!这题搞了两周都快吐了……

2022/5/22 11:51
加载中...