PAT A1139 First Contact

• 原题如下：
• 题目大意
• 方法
• 错误总结
• 技巧
• AC代码
• 结语

原题如下：

PAT A1139 First Contact(30分）

题目大意

A想和B交朋友，只能通过和A同性的好朋友和其好朋友且和B是同性的好朋友联系才行，找到这两个好朋友。

方法

这道题，我自己想用BFS来写，结果写错了，调不下去了去看柳神代码orz,
柳神传送门 A1139
同性的朋友标记好，然后是朋友也标记好。
然后分别找出A的同性好友和B的同性好友是朋友的两个好友，
注意：A的同性好友不能是B，同理，B的同性好友不能是A。

错误总结

在标记ans时我没有初始化！
当有多个case时，若第一个case对了，后面的case不对，则考虑初始化问题，大概率是初始化问题！！！

技巧

今天又是在柳神的帮助下学到东西的一天呀，这次学到的是unorder_map和stoi

//一个底层用hash表实现的不按键值排序的map
unorder_map<int,bool> flag;

string str;
int str_int=stoi(str);
//将string型转化为int型，只在int范围内有用

AC代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cctype>
#include<cstring>
//#include<stdlib>
#include<algorithm>
#include<ctime>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include <unordered_map>
using namespace std;

const int maxn = 10000;
vector<int> frid[maxn];
bool flag[maxn*maxn] = { false };
struct node {
	int a, b;
};
vector<node> ans;
bool cmp(node& a, node& b) {
	if (a.a != b.a) {
		return a.a < b.a;
	}
	else {
		return a.b < b.b;
	}
}
int main() {
#ifdef testing
	freopen("input.txt", "r", stdin);
#endif
	int n, m;
	cin >> n >> m;
#ifdef test
	cout << n << ' ' << m << endl;
#endif

	for (int i = 0; i < m; i++) {
		string s1, s2;
		cin >> s1 >> s2;
#ifdef test
		cout << s1 << ' ' << s2 << endl;
#endif
		if (s1.length() == s2.length()) {
			frid[abs(stoi(s1))].push_back(abs(stoi(s2)));
			frid[abs(stoi(s2))].push_back(abs(stoi(s1)));	
		}
		flag[abs(stoi(s1)) * 10000 + abs(stoi(s2))] = flag[abs(stoi(s2)) * 10000 + abs(stoi(s1))] = true;
	}
	int k;
	cin >> k;
#ifdef test
	cout << k << endl;
#endif
	
	for (int i = 0; i < k; i++) {
		ans.clear();
		int c, d;
		cin >> c >> d;
#ifdef test
		cout << c << ' ' << d << endl;
#endif
		for (int p = 0; p < frid[abs(c)].size(); p++) {
			for (int q = 0; q < frid[abs(d)].size(); q++) {
				if (frid[abs(c)][p] == abs(d) || frid[abs(d)][q] == abs(c))continue;
				if (flag[frid[abs(c)][p] * 10000 + frid[abs(d)][q]]==true) {
					ans.push_back(node{ frid[abs(c)][p] ,frid[abs(d)][q] });
				}
			}
		}
		//cout << '-' << endl;
		sort(ans.begin(), ans.end(), cmp);
		printf("%d\n", ans.size());
		for (int j = 0; j < ans.size(); j++) {
			printf("%04d %04d\n", ans[j].a, ans[j].b);
		}
	}
	return 0;
}

结语

进步进步进步！！！