讲解 && 提示：

这题最好是使用集合，因为集合具有有序性（c++中），在查找是否有违禁品的时候，可以二分查找，这个效率就比较高，否则用别的查找方式会超时。而且不能用map，因为这可能出现一个key对应多个value的情况！至于可不可以multimap去处理，我也明天再研究，和下一题的关联容器总结一起研究！

我的AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

const int maxn = 1e6 + 5;
set<int> s[maxn];
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	while (n--)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		s[a].insert(b);
		s[b].insert(a);
	}
	while (m--)
	{
		int k, book = 0, a;
		scanf("%d", &k);
		set<int> Set;
		while (k--)
		{
			scanf("%d", &a);
			Set.insert(a);
		}
		for (set<int>::iterator it1 = Set.begin(); Set.end() != it1; ++it1)
		{
			int j = *it1;
			for (set<int>::iterator it2 = s[j].begin(); s[j].end() != it2; ++it2)
				if (Set.find(*it2) != Set.end())
				{
					book = 1;
					printf("No\n");
					break;
				}
			if (book)
				break;
		}
		if (!book)
			printf("Yes\n");
	}
	return 0;
}

昨日最后那个点没AC的代码：咱们来一起分析一下

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;
struct Student 
{
	string id;
	int sc;
	string name;
}s[maxn];
struct School
{
	int rank = 1;
	string SchName;
	int Count = 0;
	double Score = 0.0;
}res[maxn];
int GetScore(Student stu)
{
	if ('B' == stu.id[0] || 'b' == stu.id[0])
		return stu.sc / 1.5;
	else if ('A' == stu.id[0] || 'a' == stu.id[0])
		return stu.sc;
	else if ('T' == stu.id[0] || 't' == stu.id[0])
		return stu.sc * 1.5;
}
bool cmp1(Student s1, Student s2)
{ return s1.name < s2.name; }
bool cmp2(School s1, School s2) 
{ 
	if (s1.Score != s2.Score)
		return s1.Score > s2.Score;
	else if (s1.Count != s2.Count)
		return s1.Count < s2.Count;
	else
		return s1.SchName < s2.SchName;
}

int main()
{
	int n, cnt = 0;
	cin >> n;	
	for (int i = 0; i < n; ++i)
	{
		cin >> s[i].id >> s[i].sc >> s[i].name;
		for (int j = 0; j < (int)s[i].name.length(); ++j)
			s[i].name[j] = tolower(s[i].name[j]);
	}
	sort(s, s + n, cmp1);
	string Temp = s[0].name;
	for (int i = 0; i < n;)
	{
		if (s[i].name == Temp)
		{
			res[cnt].SchName = s[i].name;
			res[cnt].Count++;
			res[cnt].Score += GetScore(s[i]);
			i++;
		}
		else
		{
			res[cnt].Score = floor(res[cnt].Score);
			cnt++;
			Temp = s[i].name;
		}
	}
	cout << ++cnt << endl;
	int rk = 1;
	sort(res, res + cnt, cmp2);
	res[0].rank = rk;
	for (int i = 1; i < cnt; ++i)
	{
		rk++;
		if (res[i].Score != res[i - 1].Score)
			res[i].rank = rk;
		else
			res[i].rank = res[i - 1].rank;
	}
	for (int i = 0; i < cnt; ++i)
		cout << res[i].rank << ' ' << res[i].SchName << ' ' << (int)res[i].Score << ' ' << res[i].Count << endl;
	return 0;
}

这种最后一个点不能AC的算法设计思路是：

我一开始对学生类的对象数组，进行排序，排序的准则是学校的校名。这样可以保证同一个学校的学生在一块，然后我就可以遍历排序后的数组，处理每个学校的总分。我觉得这个思路貌似也没错，但是最后一个点就是没通过！还请高人指教！

我的AC代码：这题我要好好分析，不错的题!

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

struct School {
	string id;
	int rk = 1, num = 0;
	double score = 0;
};
bool cmp(School s1, School s2) {
	if (floor(s1.score) != floor(s2.score))
		return floor(s1.score) > floor(s2.score);
	else if (s1.num != s2.num)
		return s1.num < s2.num;
	else
		return s1.id < s2.id;
}
int main() {
	int n;
	unordered_map<string, School> ump;
	scanf("%d", &n);
	while (n--) {
		char StuId[10] = { '\0' }, sch[10] = { '\0' };
		double StuSc;
		scanf("%s %lf %s", StuId, &StuSc, sch);
		for (int j = 0; '\0' != sch[j]; ++j)
			if (sch[j] >= 'A' && sch[j] <= 'Z')
				sch[j] += 32;
		ump[string(sch)].id = string(sch);
		ump[sch].num++;
		ump[sch].score += ('T' == StuId[0] ? StuSc * 1.5 : ('A' == StuId[0] ? StuSc * 1.0 : StuSc / 1.5));
	}
	vector<School> VecSch;
	for (unordered_map<string, School>::iterator it = ump.begin(); ump.end() != it; ++it) {
		it->second.score = floor(it->second.score);
		VecSch.push_back(it->second);
	}
	sort(VecSch.begin(), VecSch.end(), cmp);
	int j = 1; VecSch[0].rk = j;
	for (vector<School>::iterator it = VecSch.begin() + 1; VecSch.end() != it; ++it) {
		j++;
		if ((*it).score == (*(it - 1)).score)
			(*it).rk = (*(it - 1)).rk;
		else
			(*it).rk = j;
	}
	printf("%d\n", (int)VecSch.size());
	for (vector<School>::iterator it = VecSch.begin(); VecSch.end() != it; ++it)
	{
		printf("%d ", (*it).rk); cout << (*it).id << ' '; printf("%d %d\n", int((*it).score), (*it).num);
	}
	return 0;
}

AC代码的算法设计思路：

我们设计一个学校类，然后学校的校名是学校的标识id，设计一个unordered_map，用校名当key，对每个每个学校所对应的学生的分数进行累计！使用这个unordered_map的原因是因为快（粗糙的说，稍后细说），然后因为是一个关联容器嘛，所以与key相同的值都会累计到与key相关联的value里面去。然后把unordered_map的内容（value）放入一个vector中，对vector排序。这样处理我认为的好处是，因为我觉得我第一份代码的错误在于数据的精度！可能没有在某一学校的分数计算完之后再向下取整！所以我先用关联容器累计，累计完之后再向下取整。另外还有一个很大的好处就是，用关联容器可以很大程度的减少空间开销。用关联容器适合在键值对数据比较大，然后相对比较离散的情况下使用（避免离散化）

明天写博客讲解map 与 unordered_map以及一些坑点！

今天就讲本题的一个坑点：
本题中，最好不要用：unordered_map<char*, School> ump;每次关联容器进行增加的时候，先会根据key的类型的hash值进行判断。大家可以设想，如果不判断，我怎么知道是遇到新的key，要新建一组新的键值对了呢？然而char的本身是没有hash的，但是有比hash更底层的东西，就是地址。而char本身是char类型指针，这个指针指向的值无论怎么改变，指针的地址没变（如果说错，请指出，谢谢！）。所以这样使用带来的后果就是：每次存储键值对，都会覆盖上一个存下的键值对，导致整个键值对集合，值存下来了一个，也就是我们最后一次输入的那个！关于这个问题的研究，其实我还是有些别的设想，比如把char改成const char是否可以？我明天会具体实验，然后把c++的stl的所有关联容器予以总结！

讲解 && 提示：

这个题的第四个测试点我一开始也没通过，题目说：给定一个 单链表，这个词：一个，一定要注意，这个测试数据可能出现两个甚至多个单链表吗？其实是可能出现的！我们的测试数据给出了原始链表的起始节点的地址，我们就只能根据这个起始节点的地址去遍历这个“一个”的单链表，那其他的链表，或者其他的节点数据不在这个链表上呢？怎么办？那么这些数据就不用处理，因为它不在我们题目所说的链表上！

这题确实还是质量很高！

算法设计思路：

对当前链表进行遍历，一开始给出的数据是乱套的，我们不能逐数据次序遍历，而是要逐地址，逐链表的那种链接关系去遍历。遍历的同时保留三种分类的节点的地址，以便稍后按照这个地址进行拼接。因为题目说了，不能破坏同一类的原本的次序关系，所以这个每个类的次序也需要用数组存储，用来维护在原始链表中的位次关系！
然后拼接就是把三个类比的地址数组合并，然后由于地址对应着原链表的下标（其实也可重建链表），我们就按照题目说的次序，去遍历合并后的数组，按照地址->地址的值->下一个地址的次序去遍历，这里需要注意，因为我们一开始存储下标，用的是整形，但是下标（id、地址）是可能有前导零的，这里注意了！最好在处理这种规模不大的id（地址）的时候，别用字符串，多用int、long long！然后在输出的时候，选择C语言的printf格式输出，比如输出的id都是五位，然后不足五位的前导零，就是：printf("%05d", id);

我的AC代码：

#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 1e5 + 5;
struct Node {
	int data;
	int Next;
}L[maxn];
int order1[maxn], order2[maxn], order3[maxn];
int main() {
	int addF, n, k, cnt1 = 0, cnt2 = 0, cnt3 = 0;
	cin >> addF >> n >> k;
	while (n--) {
		int add;
		int val, Nex;
		cin >> add >> val >> Nex;
		L[add].data = val;
		L[add].Next = Nex;
	}
	int addTemp = addF;
	while (-1 != addTemp) {
		if (L[addTemp].data < 0)
			order1[cnt1++] = addTemp;
		else if (L[addTemp].data >= 0 && L[addTemp].data <= k)
			order2[cnt2++] = addTemp;
		else
			order3[cnt3++] = addTemp;
		addTemp = L[addTemp].Next;
	}
	for (int i = 0; i < cnt2; ++i)
		order1[cnt1++] = order2[i];
	for (int i = 0; i < cnt3; ++i)
		order1[cnt1++] = order3[i];
	for (int i = 0; i < cnt1; ++i) {
		printf("%05d %d ", order1[i], L[order1[i]].data);
		if (i < cnt1 - 1)
			printf("%05d\n", order1[i + 1]);
		else
			printf("-1\n");
	}
	return 0;
}