liuchuo – 第204页 – 我不管，反正我最萌～

L2-009. 抢红包-PAT团体程序设计天梯赛GPLT

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N（<= 104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

K N1 P1 … NK PK

其中K（0 <= K <= 20）是发出去的红包个数，Ni是抢到红包的人的编号，Pi（> 0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：
10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10
输出样例：
1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

分析：用结构体存储下每一个结点的id、收入、收到红包的总数，然后进行排序后输出

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int id, total, getnum;
};
bool cmp1(node a, node b) {
    if(a.total != b.total)
        return a.total > b.total;
    else if(a.getnum != b.getnum)
        return a.getnum > b.getnum;
    else
        return a.id < b.id;
}
int main() {
    int n, k, a, b;
    scanf("%d", &n);
    vector<node> v(n + 1);
    for(int i = 1; i <= n; i++) {
        v[i].id = i;
        scanf("%d", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d %d", &a, &b);
            v[a].total += b;
            v[a].getnum++;
            v[i].total -= b;
        }
    }
    sort(v.begin()+1, v.end(), cmp1);
    for(int i = 1; i <= n; i++) {
        double temp = (double)(v[i].total * 1.0 / 100);
        printf("%d %.2f\n", v[i].id, temp);
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

int id, total, getnum;

};

bool cmp1(node a, node b) {

if(a.total != b.total)

return a.total > b.total;

else if(a.getnum != b.getnum)

return a.getnum > b.getnum;

else

return a.id < b.id;

}

int main() {

int n, k, a, b;

scanf("%d", &n);

vector<node> v(n + 1);

for(int i = 1; i <= n; i++) {

v[i].id = i;

scanf("%d", &k);

for(int j = 0; j < k; j++) {

scanf("%d %d", &a, &b);

v[a].total += b;

v[a].getnum++;

v[i].total -= b;

}

sort(v.begin()+1, v.end(), cmp1);

for(int i = 1; i <= n; i++) {

double temp = (double)(v[i].total * 1.0 / 100);

printf("%d %.2f\n", v[i].id, temp);

}

return 0;

}

【数据结构】并查集的概念与实现

并查集（Union、Find、Set）支持两个操作：合并两个集合、查找：判断两个元素是否在一个集合。

用一个与n等长的数组存储每个结点的父结点：

int father[n];

1	int father[n];

初始化，先令它们属于各自不同的集合，父结点都是自己：

for(int i = 1; i <= n; i++)
  father[i] = i;

1 2	for(int i = 1; i <= n; i++) father[i] = i;

查找：不断找父结点直到father[x] = x，递推或者递归方法都可以

int findFather(int x) {
  while(x != father[x])
    x = father[x];
  return x;
}

//或者递归
int findFather(int x) {
  if(x == father[x]) return x;
  else return findFather(father[x]);
}

int findFather(int x) {

while(x != father[x])

x = father[x];

return x;

}

//或者递归

int findFather(int x) {

if(x == father[x]) return x;

else return findFather(father[x]);

}

合并两个集合：找到a和b的根结点，如果根结点不同，就把其中一个的最高处的根结点的父亲设为另一个根结点

void Union(int a, int b) {
  int faA = findFather(a);
  int faB = findFather(b);
  if(faA != faB)
    father[faA] = faB;
}

void Union(int a, int b) {

int faA = findFather(a);

int faB = findFather(b);

if(faA != faB)

father[faA] = faB;

}

*对findFather函数进行路径压缩：

按原先的写法（递推写法）先获得根结点root
重新从x开始走一遍寻找根结点的过程，把路径上经过的所有结点的父亲全部改为根结点root

int findFather(int x) {
  int a = x;
  while(x != father[x])
    x = father[x];
  while(a != fahter[a]) { //路径压缩代码，可以省略
    int z = a;
    a = father[a];
    father[z] = x;
  }
  return x;
}

int findFather(int x) {

int a = x;

while(x != father[x])

x = father[x];

while(a != fahter[a]) { //路径压缩代码，可以省略

int z = a;

a = father[a];

father[z] = x;

}

return x;

}

如果判定条件是两个人有共同喜欢的课程，可以开一个数组course[1000]，1000为课程数，course[t]表示任意一个喜欢t课程的人的编号，这样的话，如果course[t] == 0说明当前读入的这个课程就他自己一个人喜欢，那么就令course[t] = i，他自己就是喜欢课程t的人的编号。findFather(course[t])就是这个人所在的社交网络的根结点，只需要合并当前读入的人的编号i和findFather(course[t])，表示把这两个人合并到了同一个圈子。

如果要统计一共有多少个圈子，只需要遍历一遍1~n，把它们的父结点对应的isRoot数组++，那么isRoot[i] = j表示以i为父结点的社交圈子中有j个人~~~

如果两个人之间不是可传递的关系，可以用一个二维数组enemy[a][b] = enemy[b][a] = 1存储a和b之间是否有关系。

L2-010. 排座位-PAT团体程序设计天梯赛GPLT（并查集）

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（<= 100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：“宾客1 宾客2 关系”，其中“关系”为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出“No problem”；如果他们之间并不是朋友，但也不敌对，则输出“OK”；如果他们之间有敌对，然而也有共同的朋友，则输出“OK but…”；如果他们之间只有敌对关系，则输出“No way”。

输入样例：
7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2
输出样例：
No problem
OK
OK but…
No way

分析：朋友之间的关系用并查集解决，敌人之间的关系用enemy[a][b] = enemy[b][a] = 1解决，因为朋友之间的朋友也是朋友，是传递关系，而敌人的敌人不一定是敌人，所以只需要用一个二维数组即可标记。

#include <cstdio>
#include <vector>
using namespace std;
vector<int> fri;
int enemy[101][101];
int findfri(int x) {
    while(x != fri[x])
        x = fri[x];
    return x;
}
void Union(int a, int b) {
    int fria = findfri(a);
    int frib = findfri(b);
    if(fria != frib)
        fri[fria] = frib;
}
int main() {
    int n, m, k, a, b, c;
    scanf("%d %d %d", &n, &m, &k);
    fri.resize(n + 1);
    for(int i = 1; i <= n; i++)
        fri[i] = i;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if(c == 1)
            Union(a, b);
        else {
            enemy[a][b] = 1;
            enemy[b][a] = 1;
        }
    }
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &a, &b);
        if(findfri(a) == findfri(b) && enemy[a][b] == 0)
            printf("No problem\n");
        else if(findfri(a) != findfri(b) && enemy[a][b] == 0)
            printf("OK\n");
        else if(findfri(a) == findfri(b) && enemy[a][b] == 1)
            printf("OK but...\n");
        else if(enemy[a][b] == 1)
            printf("No way\n");
    }
    return 0;
}

#include <cstdio>

#include <vector>

using namespace std;

vector<int> fri;

int enemy[101][101];

int findfri(int x) {

while(x != fri[x])

x = fri[x];

return x;

}

void Union(int a, int b) {

int fria = findfri(a);

int frib = findfri(b);

if(fria != frib)

fri[fria] = frib;

}

int main() {

int n, m, k, a, b, c;

scanf("%d %d %d", &n, &m, &k);

fri.resize(n + 1);

for(int i = 1; i <= n; i++)

fri[i] = i;

for(int i = 0; i < m; i++) {

scanf("%d %d %d", &a, &b, &c);

if(c == 1)

Union(a, b);

else {

enemy[a][b] = 1;

enemy[b][a] = 1;

}

for(int i = 0; i < k; i++) {

scanf("%d %d", &a, &b);

if(findfri(a) == findfri(b) && enemy[a][b] == 0)

printf("No problem\n");

else if(findfri(a) != findfri(b) && enemy[a][b] == 0)

printf("OK\n");

else if(findfri(a) == findfri(b) && enemy[a][b] == 1)

printf("OK but...\n");

else if(enemy[a][b] == 1)

printf("No way\n");

}

return 0;

}

L3-003. 社交集群-PAT团体程序设计天梯赛GPLT（并查集）

在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。
输入格式：
输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好：
Ki: hi[1] hi[2] … hi[Ki]
其中Ki（>0）是第i个人的兴趣的数量，hi[j]是第i个人的第j项兴趣的编号，编号范围为[1, 1000]内的整数。
输出格式：
首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
输出样例：
3
4 3 1
分析：并查集。先写好init、findFather、Union。
0. 每个社交圈的结点号是人的编号，而不是课程。课程是用来判断是否处在一个社交圈的。
1. course[t]表示任意一个喜欢t活动的人的编号。如果当前的课程t，之前并没有人喜欢过，那么就course[t] = i，i为它自己的编号，表示i为喜欢course[t]的一个人的编号
2. course[t]是喜欢t活动的人的编号，那么findFather(course[t])就是喜欢这个活动的人所处的社交圈子的根结点，合并根结点和当前人的编号的结点i。即Union(i, findFather(course[t]))，把它们处在同一个社交圈子里面
3. isRoot[i]表示编号i的人是不是它自己社交圈子的根结点，如果等于0表示不是根结点，如果不等于0，每次标记isRoot[findFather(i)]++，那么isRoot保存的就是如果当前是根结点，那么这个社交圈里面的总人数
4. isRoot中不为0的编号的个数cnt就是社交圈圈子的个数
5. 把isRoot从大到小排列，输出前cnt个，就是社交圈人数的从大到小的输出顺序

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> father, isRoot;
int cmp1(int a, int b){
    return a > b;
}
int findFather(int x) {
    int a = x;
    while(x != father[x])
        x = father[x];
    while(a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB)
        father[faA] = faB;
}
int main() {
    int n, k, t, cnt = 0;
    int course[1001] = {0};
    scanf("%d", &n);
    father.resize(n + 1);
    isRoot.resize(n + 1);
    for(int i = 1; i <= n; i++)
        father[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &t);
            if(course[t] == 0)
                course[t] = i;
            Union(i, findFather(course[t]));
        }
    }
    for(int i = 1; i <= n; i++)
        isRoot[findFather(i)]++;
    for(int i = 1; i <= n; i++) {
        if(isRoot[i] != 0)
            cnt++;
    }
    printf("%d\n", cnt);
    sort(isRoot.begin(), isRoot.end(), cmp1);
    for(int i = 0; i < cnt; i++) {
        printf("%d", isRoot[i]);
        if(i != cnt - 1) printf(" ");
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> father, isRoot;

int cmp1(int a, int b){

return a > b;

}

int findFather(int x) {

int a = x;

while(x != father[x])

x = father[x];

while(a != father[a]) {

int z = a;

a = father[a];

father[z] = x;

}

return x;

}

void Union(int a, int b) {

int faA = findFather(a);

int faB = findFather(b);

if(faA != faB)

father[faA] = faB;

}

int main() {

int n, k, t, cnt = 0;

int course[1001] = {0};

scanf("%d", &n);

father.resize(n + 1);

isRoot.resize(n + 1);

for(int i = 1; i <= n; i++)

father[i] = i;

for(int i = 1; i <= n; i++) {

scanf("%d:", &k);

for(int j = 0; j < k; j++) {

scanf("%d", &t);

if(course[t] == 0)

course[t] = i;

Union(i, findFather(course[t]));

}

for(int i = 1; i <= n; i++)

isRoot[findFather(i)]++;

for(int i = 1; i <= n; i++) {

if(isRoot[i] != 0)

cnt++;

}

printf("%d\n", cnt);

sort(isRoot.begin(), isRoot.end(), cmp1);

for(int i = 0; i < cnt; i++) {

printf("%d", isRoot[i]);

if(i != cnt - 1) printf(" ");

}

return 0;

}

1107. Social Clusters (30)-PAT甲级真题（并查集）

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A “social cluster” is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.
Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (<=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:
Ki: hi[1] hi[2] … hi[Ki]
where Ki (>0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].
Output Specification:
For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
Sample Output:
3
4 3 1

题目大意：有n个人，每个人喜欢k个活动，如果两个人有任意一个活动相同，就称为他们处于同一个社交网络。求这n个人一共形成了多少个社交网络。
分析：并查集。先写好init、findFather、Union。
0. 每个社交圈的结点号是人的编号，而不是课程。课程是用来判断是否处在一个社交圈的。
1. course[t]表示任意一个喜欢t活动的人的编号。如果当前的课程t，之前并没有人喜欢过，那么就course[t] = i，i为它自己的编号，表示i为喜欢course[t]的一个人的编号
2. course[t]是喜欢t活动的人的编号，那么findFather(course[t])就是喜欢这个活动的人所处的社交圈子的根结点，合并根结点和当前人的编号的结点i。即Union(i, findFather(course[t]))，把它们处在同一个社交圈子里面
3. isRoot[i]表示编号i的人是不是它自己社交圈子的根结点，如果等于0表示不是根结点，如果不等于0，每次标记isRoot[findFather(i)]++，那么isRoot保存的就是如果当前是根结点，那么这个社交圈里面的总人数
4. isRoot中不为0的编号的个数cnt就是社交圈圈子的个数
5. 把isRoot从大到小排列，输出前cnt个，就是社交圈人数的从大到小的输出顺序

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> father, isRoot;
int cmp1(int a, int b){return a > b;}
int findFather(int x) {
    int a = x;
    while(x != father[x])
        x = father[x];
    while(a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB) father[faA] = faB;
}
int main() {
    int n, k, t, cnt = 0;
    int course[1001] = {0};
    scanf("%d", &n);
    father.resize(n + 1);
    isRoot.resize(n + 1);
    for(int i = 1; i <= n; i++)
        father[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &t);
            if(course[t] == 0)
                course[t] = i;
            Union(i, findFather(course[t]));
        }
    }
    for(int i = 1; i <= n; i++)
        isRoot[findFather(i)]++;
    for(int i = 1; i <= n; i++) {
        if(isRoot[i] != 0) cnt++;
    }
    printf("%d\n", cnt);
    sort(isRoot.begin(), isRoot.end(), cmp1);
    for(int i = 0; i < cnt; i++) {
        printf("%d", isRoot[i]);
        if(i != cnt - 1) printf(" ");
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> father, isRoot;

int cmp1(int a, int b){return a > b;}

int findFather(int x) {

int a = x;

while(x != father[x])

x = father[x];

while(a != father[a]) {

int z = a;

a = father[a];

father[z] = x;

}

return x;

}

void Union(int a, int b) {

int faA = findFather(a);

int faB = findFather(b);

if(faA != faB) father[faA] = faB;

}

int main() {

int n, k, t, cnt = 0;

int course[1001] = {0};

scanf("%d", &n);

father.resize(n + 1);

isRoot.resize(n + 1);

for(int i = 1; i <= n; i++)

father[i] = i;

for(int i = 1; i <= n; i++) {

scanf("%d:", &k);

for(int j = 0; j < k; j++) {

scanf("%d", &t);

if(course[t] == 0)

course[t] = i;

Union(i, findFather(course[t]));

}

for(int i = 1; i <= n; i++)

isRoot[findFather(i)]++;

for(int i = 1; i <= n; i++) {

if(isRoot[i] != 0) cnt++;

}

printf("%d\n", cnt);

sort(isRoot.begin(), isRoot.end(), cmp1);

for(int i = 0; i < cnt; i++) {

printf("%d", isRoot[i]);

if(i != cnt - 1) printf(" ");

}

return 0;

}

1025. PAT Ranking (25)-PAT甲级真题

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (<=100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (<=300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank

The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input:
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
Sample Output:
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

题目大意：有n个考场，每个考场有若干数量的学生，给出每个考场中考生的编号和分数，要求算排名，输出所有考生的编号、排名、考场号、考场内排名
分析：先按照考场内排名然后赋值给总数组fin，然后总排名，最后输出。注意相同的分数情况下按照学号的从小到大排列，但是他们的排名应该是一样的数字～

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct student {
    long long int no;
    int score, finrank, loca, locarank;
};
bool cmp1(student a, student b) {
    return a.score != b.score ? a.score > b.score : a.no < b.no;
}
int main() {
    int n, m;
    scanf("%d", &n);
    vector<student> fin;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &m);
        vector<student> v(m);
        for(int j = 0; j < m; j++) {
            scanf("%lld %d", &v[j].no, &v[j].score);
            v[j].loca = i;
        }
        sort(v.begin(), v.end(), cmp1);
        v[0].locarank = 1;
        fin.push_back(v[0]);
        for(int j = 1; j < m; j++) {
            v[j].locarank = (v[j].score == v[j - 1].score) ? (v[j - 1].locarank) : (j + 1);
            fin.push_back(v[j]);
        }
    }
    sort(fin.begin(), fin.end(), cmp1);
    fin[0].finrank = 1;
    for(int j = 1; j < fin.size(); j++)
        fin[j].finrank = (fin[j].score == fin[j - 1].score) ? (fin[j - 1].finrank) : (j + 1);
    printf("%d\n", fin.size());
    for(int i = 0; i < fin.size(); i++)
        printf("%013lld %d %d %d\n", fin[i].no, fin[i].finrank, fin[i].loca, fin[i].locarank);
    return 0;
}

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

struct student {

long long int no;

int score, finrank, loca, locarank;

};

bool cmp1(student a, student b) {

return a.score != b.score ? a.score > b.score : a.no < b.no;

}

int main() {

int n, m;

scanf("%d", &n);

vector<student> fin;

for(int i = 1; i <= n; i++) {

scanf("%d", &m);

vector<student> v(m);

for(int j = 0; j < m; j++) {

scanf("%lld %d", &v[j].no, &v[j].score);

v[j].loca = i;

}

sort(v.begin(), v.end(), cmp1);

v[0].locarank = 1;

fin.push_back(v[0]);

for(int j = 1; j < m; j++) {

v[j].locarank = (v[j].score == v[j - 1].score) ? (v[j - 1].locarank) : (j + 1);

fin.push_back(v[j]);

}

sort(fin.begin(), fin.end(), cmp1);

fin[0].finrank = 1;

for(int j = 1; j < fin.size(); j++)

fin[j].finrank = (fin[j].score == fin[j - 1].score) ? (fin[j - 1].finrank) : (j + 1);

printf("%d\n", fin.size());

for(int i = 0; i < fin.size(); i++)

printf("%013lld %d %d %d\n", fin[i].no, fin[i].finrank, fin[i].loca, fin[i].locarank);

return 0;

}