Code – 第195页

L3-001. 凑零钱-PAT团体程序设计天梯赛GPLT（01背包，动态规划）

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式：

输入第一行给出两个正整数：N（<=104）是硬币的总个数，M（<=102）是韩梅梅要付的款额。第二行给出N枚硬币的正整数面值。数字间以空格分隔。

输出格式：

在一行中输出硬币的面值 V1 <= V2 <= … <= Vk，满足条件 V1 + V2 + … + Vk = M。数字间以1个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出“No Solution”。

注：我们说序列{A[1], A[2], …}比{B[1], B[2], …}“小”，是指存在 k >= 1 使得 A[i]=B[i] 对所有 i < k 成立，并且 A[k] < B[k]。

输入样例1：
8 9
5 9 8 7 2 3 4 1
输出样例1：
1 3 5
输入样例2：
4 8
7 2 4 3
输出样例2：
No Solution

分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010];
int w[10010];
bool choice[10010][10010];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010];

int w[10010];

bool choice[10010][10010];

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

int main() {

int n, m;

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

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

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

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

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

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

if(i != 0) printf(" ");

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

}

return 0;

}

【算法】动态规划笔记

将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解
动态规划会将每个求解过的子问题的解记录下来，这样下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算
可以用递归或者递推的写法实现，递归的写法又叫记忆化搜索
重叠子问题：如果一个问题可以被分解成若干个子问题，且这些子问题会重复出现，就称这个问题拥有重叠子问题。一个问题必须拥有重叠子问题，才能用动态规划去解决。
最优子结构：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称为这个问题拥有的最优子结构。最优子结构保证了动态规划中的原问题的最优解可以由子问题的最优解推导而来
动态规划与分治的区别：都是分解为子问题然后合并子问题得到解，但是分治分解出的子问题是不重叠的
动态规划与贪心的区别：都有最优子结构，但是贪心直接选择一个子问题去求解，会抛弃一些子问题，这种选择的正确性需要用归纳法证明，而动态规划会考虑所有的子问题

动态规划的递归和递推写法

递归写法

//不使用动态规划
int F(int n) {
  if(n == 0 || n == 1) return 1;
  else return F(n - 1) + F(n - 2);
}
// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)
int dp[10000];
memeset(dp, -1, sizeof(dp));
int F(int n) {
  if(n == 0 || n == 1) return 1;
  if(dp[n] != -1) return dp[n];
  else {
    dp[n] = F(n-1) + F(n - 2);
    return dp[n];
  }
}

//不使用动态规划

int F(int n) {

if(n == 0 || n == 1) return 1;

else return F(n - 1) + F(n - 2);

}

// 此时F(5) = F(4) + F(3), F(4) = F(3) + F(2),3会被计算两次

// 采用动态规划的方法(记忆化搜索)

int dp[10000];

memeset(dp, -1, sizeof(dp));

int F(int n) {

if(n == 0 || n == 1) return 1;

if(dp[n] != -1) return dp[n];

else {

dp[n] = F(n-1) + F(n - 2);

return dp[n];

}

递推写法

// 数塔为例
// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])
// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j]   [(j从1~n)]
// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]
// f[i][j]为第i行j列数字的大小
// 采用自底向上递推的方法
// 数组从1开始作为下标存储
for(int i = n - 1; i >= 1; i--) {
  for(int j = 1; j <= i; j++)
    f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
return f[1][1];

// 数塔为例

// 递推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])

// 如果非要建立dp数组，先要初始化dp[n][j] = f[n][j] [(j从1~n)]

// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

// f[i][j]为第i行j列数字的大小

// 采用自底向上递推的方法

// 数组从1开始作为下标存储

for(int i = n - 1; i >= 1; i--) {

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

f[i][j] += max(f[i+1][j], f[i+1][j+1]);

}

return f[1][1];

最大连续子序列和

给定序列，求连续的子序列要求和最大，求最大的和为多少
dp[i]表示以a[i]作为末尾的连续序列的最大和（a[i]必须是末尾被选的数啊啊），dp数组中所有的数据的最大值就是所求
dp[0]初始化为a[0]，dp数组从1生成到n-1
因为a[i]一定是所选序列的末尾，所以分为两种情况：
- a[i]开始，a[i]结束
- 某数开始，到a[i]结束（最大和是dp[i-1] + a[i]）
所以递推方程为dp[i] = max(a[i], dp[i-1]+a[i]);
dp数组中所有的数据的最大值就是所求：maxn = max(dp[i], maxn);

// a数组从下标0开始
dp[0] = a[0];
int maxn = a[0];
for(int i = 1; i < n; i++) {
  dp[i] = max(a[i], dp[i-1]+a[i]);
  maxn = max(dp[i], maxn);
}
printf("%d", maxn);

// a数组从下标0开始

dp[0] = a[0];

int maxn = a[0];

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

dp[i] = max(a[i], dp[i-1]+a[i]);

maxn = max(dp[i], maxn);

}

printf("%d", maxn);

最长不下降子序列（LIS）

求一个序列的最长的子序列（可以不连续），使得这个子序列是不下降的
dp[i]表示必须以a[i]结尾的最长不下降子序列的长度，dp数组中所有数据的最大值即为所求
i从0到n-1依次更新dp[i]的值，dp[i]的值需要由之前所生成的所有dp[j]递推而得（j从1到i-1），每次检查是否a[i]>=a[j]，即是否构成最长不下降子序列，如果构成，会有两种结果：
- dp[j]+1比dp[i]大，则更新dp[i] = dp[j] + 1
- dp[j]+1比dp[i]小，则dp[i]保持不变
所以递推方程为dp[i] = max{dp[i], dp[j] + 1};
dp数组中所有数据的最大值即为所求：ans = max(dp[i], ans);

int ans = 0;
for(int i = 0; i < n; i++) {
  for(int j = 1; j < i; j++) {
    if(a[i] >= a[j])
      dp[i] = max(dp[i], dp[j] + 1);
  }
  ans = max(dp[i], ans);
}

printf("%d", ans);

int ans = 0;

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

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

if(a[i] >= a[j])

dp[i] = max(dp[i], dp[j] + 1);

}

ans = max(dp[i], ans);

}

printf("%d", ans);

最长公共子序列（LCS）

给定两个字符串或者数字序列A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）
dp[i][j]表示A的第 i 位之前和B的第 j 位之前的这两个序列的LCS最长公共子序列的长度（下标从1开始），那么dp[lena][lenb]即为所求
递推方程：
- 当a[i] == b[j] : dp[i][j] = dp[i-1][j-1] + 1
- 当a[i] != b[j] : dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 边界：dp[i][0] = dp[0][j] = 0(0 <= i <= lena, 1 <= j <= lenb)

char a[100], b[100];
scanf("%s", a+1);
scanf("%s", b+1);
int lena = strlen(a + 1), lenb = strlen(b + 1);
for(int i = 0; i <= lena; i++) dp[i][0] = 0;
for(int j = 0; j <= lenb; j++) dp[0][j] = 0;
for(int i = 1; i <= lena; i++) {
  for(int j = 1; j <= lenb; j++) {
    if(a[i] == b[j])
      dp[i][j] = dp[i-1][j-1] + 1;
    else
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  }
}
printf("%d", dp[lena][lenb]);

char a[100], b[100];

scanf("%s", a+1);

scanf("%s", b+1);

int lena = strlen(a + 1), lenb = strlen(b + 1);

for(int i = 0; i <= lena; i++) dp[i][0] = 0;

for(int j = 0; j <= lenb; j++) dp[0][j] = 0;

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

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

if(a[i] == b[j])

dp[i][j] = dp[i-1][j-1] + 1;

else

dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

}

printf("%d", dp[lena][lenb]);

最长回文子串

给出一个字符串s，求s的最长回文子串的长度
dp[i][j]表示 s[i] 到 s[j] 所表示的字串是否是回文字串，值只有0和1
初始化长度1和2的值：dp[i][i] = 1, dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0，然后长度L从3到len，满足的最大长度L即为所求的ans值
递推方程：
- 当s[i] == s[j] : dp[i][j] = dp[i+1][j-1]
- 当s[i] != s[j] : dp[i][j] = 0
因为i、j如果从小到大的顺序来枚举的话，无法保证更新dp[i][j]的时候dp[i+1][j-1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举，即第一遍将长度为3的子串的dp的值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp的值…这样就可以避免状态无法转移的问题

int len = s.length();
//先把1和2长度的都初始化了
int ans = 1;
for(int i = 0; i < len; i++) {
  dp[i][i] = 1;
  if(i < len - 1 && s[i] == s[i+1]) {
    dp[i][i+1] = 1;
    ans = 2;
  }
}
//状态转移方程
for(int L = 3; L <= len; L++) {
  for(int i = 0; i + L - 1 < len; i++) {
    int j = i + L - 1;
    if(s[i] == s[j] && dp[i+1][j-1] == 1) {
      dp[i][j] = 1;
      ans = L;
    }
  }
}
printf("%d", ans);

int len = s.length();

//先把1和2长度的都初始化了

int ans = 1;

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

dp[i][i] = 1;

if(i < len - 1 && s[i] == s[i+1]) {

dp[i][i+1] = 1;

ans = 2;

}

//状态转移方程

for(int L = 3; L <= len; L++) {

for(int i = 0; i + L - 1 < len; i++) {

int j = i + L - 1;

if(s[i] == s[j] && dp[i+1][j-1] == 1) {

dp[i][j] = 1;

ans = L;

}

printf("%d", ans);

背包问题

01背包问题

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个重量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件
dp[i][j]表示前i件物品恰好装入容量为j的背包所能获得的最大价值
- 不放第i件物品，则 dp[i][j] = dp[i-1][j]
- 放第i件物品，那么问题转化为前i – 1件物品恰好装入容量j – w[i]的背包中所能获得的最大价值 dp[i-1][j-w[i]] + c[i]
递推方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i]);

for(int i = 1; i <= n; i++) {
  for(int j = 1, j <= v; j++)
    if(j - w[i] >= 0) 
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);
    else
      dp[i][j] = dp[i-1][j];    
}

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

for(int j = 1, j <= v; j++)

if(j - w[i] >= 0)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);

else

dp[i][j] = dp[i-1][j];

}

一维：

for(int i = 1; i <= n; i++) {
  for(int j = v; j >= w[i]; j--)
    dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
}

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

for(int j = v; j >= w[i]; j--)

dp[v] = max(dp[v], dp[v-w[i]] + c[i]);

}

1068. Find More Coins (30)-PAT甲级真题（01背包）

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.

Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].

Sample Input 1:
8 9
5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8
7 2 4 3
Sample Output 2:
No Solution
题目大意：用n个硬币买价值为m的东西，输出使用方案，使得正好几个硬币加起来价值为m。从小到大排列，输出最小的那个排列方案
分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010], w[10010];
bool choice[10010][110];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010], w[10010];

bool choice[10010][110];

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

int main() {

int n, m;

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

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

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

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

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

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

if(i != 0) printf(" ");

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

}

return 0;

}

L3-008. 喊山-PAT团体程序设计天梯赛GPLT（广度优先搜索）

喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：

输入第一行给出3个正整数n、m和k，其中n（<=10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（<=10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：

依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：
7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7
输出样例：
2
6
4
0

分析：用二维数组，结点push_back的方式存储，因为每次都从1遍历到n会超时，而只要遍历到v[top].size()就不会超时。
用广度优先搜索，level记录当前结点的层数，level为自己的上一层结点的level+1，遇到更大层数的时候就令ans又为最大值，让ans取当层的最小值（在不等于被搜索结点本身的时候）。book记录当前结点有没有被访问过，如果没有被访问过就压入队列中，因为可能重复然后导致无限循环，无法输出～

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> v(10010);
int book[10010];
int main() {
    int n, m, k, a, b;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 0; i < k; i++) {
        scanf("%d", &a);
        queue<int> q;
        fill(book, book + 10010, 0);
        q.push(a);
        int level[10010];
        int ans = 10010, maxlevel = 0;
        book[a] = 1;
        while(!q.empty()) {
            int top = q.front();
            q.pop();
            if(level[top] > maxlevel) {
                maxlevel = level[top];
                ans = 10010;
            }
            if(top != a)
                ans = min(ans, top);
            for(int j = 0; j < v[top].size(); j++) {
                if(book[v[top][j]] == 0) {
                    q.push(v[top][j]);
                    book[v[top][j]] = 1;
                    level[v[top][j]] = level[top] + 1;
                }
            }
        }
        if(ans != 10010) printf("%d\n", ans);
        else printf("0\n");
    }
    return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

vector<vector<int>> v(10010);

int book[10010];

int main() {

int n, m, k, a, b;

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

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

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

v[a].push_back(b);

v[b].push_back(a);

}

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

scanf("%d", &a);

queue<int> q;

fill(book, book + 10010, 0);

q.push(a);

int level[10010];

int ans = 10010, maxlevel = 0;

book[a] = 1;

while(!q.empty()) {

int top = q.front();

q.pop();

if(level[top] > maxlevel) {

maxlevel = level[top];

ans = 10010;

}

if(top != a)

ans = min(ans, top);

for(int j = 0; j < v[top].size(); j++) {

if(book[v[top][j]] == 0) {

q.push(v[top][j]);

book[v[top][j]] = 1;

level[v[top][j]] = level[top] + 1;

}

if(ans != 10010) printf("%d\n", ans);

else printf("0\n");

}

return 0;

}

L2-016. 愿天下有情人都是失散多年的兄妹-PAT团体程序设计天梯赛GPLT（广度优先bfs）

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

输入格式：

输入第一行给出一个正整数N（2 <= N <= 104），随后N行，每行按以下格式给出一个人的信息：

本人ID 性别父亲ID 母亲ID

其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。

接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。

注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式：

对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出“Never Mind”；如果是异性并且关系出了五服，输出“Yes”；如果异性关系未出五服，输出“No”。

输入样例：
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011
输出样例：
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

分析：我用的方法是广度优先，然后把每个人和他们的祖先们压入一个set里面，判断set前后有没有大小改变，如果没改变说明重复了，所以有相同祖先，所以就输出No，用level数组标记他们当前的层数在push一层的时候令他们的层数为上一层+1，一直到五层判断结束。如果结束了还没有输出过No，那么就输出yes。（其实后来想到可以用数组标记的方法，不用集合来这么复杂的。。）
有三个注意点：1.一开始有三个测试点不过，然后。。发现。。每次在输入的时候把它们父母的性别也要标记一下，因为！测试数据里面可能会判断某个人的父亲（但是不在给出的本人id的列表中），或者母亲和某个人是否能结婚。。。。也就是说测试数据里面如果出现了09999，它是某个人的父母，那么也可能会被判断。。所以。。所以。。要在输入的时候加上父母的性别的标记。。。PAT教我做人。。
【有可爱的小伙伴和我说不太明白第一个注意点的意思，我的意思是，测试用例里面，除了测试样例那样常规的9种询问的是否可以通婚的用例，还有可能会问02222和03333是否可以通婚，02222和04444是否可以通婚。但是我们不知道02222和03333和04444的父母是谁，所以就默认他们之间是没有血缘关系的，接下来考虑的就是他们的性别问题了，因为02222是男的（因为他是父亲嘛）而03333是女的，那就要输出可以通婚；同理，04444是男的，就要输出never mind~】
2.因为我开的是全局数组，用全局数组的时候就千万要记得，用完之后记得把它。。置回0啊啊啊。。。因为下一组测试数据用这个数组的时候可能会不小心用到了上一组测试数据保存的结果。。。就会出错了。。
3.用exist数组标记是否存在这个结点，否则避免不小心把0压入。。。到队列里面（就是求对于一个父母，他们可能不存在在本人id里面，那么把他们的孩子结点放入queue里面就会出现0.。不断标记0的话把0当他们的共同祖先可能会误输出No）

#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
    int f, m, sex;
};
node v[100010];
int level[100010];
bool exist[100010];
int main() {
    int n, m, id, father, mother, a, b;
    scanf("%d", &n);
    char c;
    for(int i = 0; i < n; i++) {
        scanf("%d %c %d %d", &id, &c, &father, &mother);
        v[id].f = father, v[id].m = mother;
        if(c == 'M') v[id].sex = 0;
        else v[id].sex = 1;
        exist[id] = true;
        v[father].sex = 0;
        v[mother].sex = 1;
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        fill(level, level + 100010, 0);
        scanf("%d%d", &a, &b);
        if(v[a].sex == v[b].sex) {
            printf("Never Mind\n");
            continue;
        }
        queue<int> q;
        q.push(a);
        q.push(b);
        level[a] = 1;
        level[b] = 1;
        set<int> s;
        int flag = 0;
        while(!q.empty()) {
            int top = q.front();
            q.pop();
            int size = s.size();
            s.insert(top);
            if(size == s.size()) {
                printf("No\n");
                flag = 1;
                break;
            }
            if(exist[top] == false) continue;
            if(level[top] <= 4) {
                int fa = v[top].f;
                int mo = v[top].m;
                if(fa != -1) {
                    q.push(fa);
                    level[fa] = level[top] + 1;
                }
                if(mo != -1) {
                    q.push(mo);
                    level[mo] = level[top] + 1;
                }
            }
        }
        if(flag == 0) printf("Yes\n");
    }
    return 0;
}

#include <cstdio>

#include <set>

#include <queue>

#include <algorithm>

using namespace std;

struct node {

int f, m, sex;

};

node v[100010];

int level[100010];

bool exist[100010];

int main() {

int n, m, id, father, mother, a, b;

scanf("%d", &n);

char c;

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

scanf("%d %c %d %d", &id, &c, &father, &mother);

v[id].f = father, v[id].m = mother;

if(c == 'M') v[id].sex = 0;

else v[id].sex = 1;

exist[id] = true;

v[father].sex = 0;

v[mother].sex = 1;

}

scanf("%d", &m);

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

fill(level, level + 100010, 0);

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

if(v[a].sex == v[b].sex) {

printf("Never Mind\n");

continue;

}

queue<int> q;

q.push(a);

q.push(b);

level[a] = 1;

level[b] = 1;

set<int> s;

int flag = 0;

while(!q.empty()) {

int top = q.front();

q.pop();

int size = s.size();

s.insert(top);

if(size == s.size()) {

printf("No\n");

flag = 1;

break;

}

if(exist[top] == false) continue;

if(level[top] <= 4) {

int fa = v[top].f;

int mo = v[top].m;

if(fa != -1) {

q.push(fa);

level[fa] = level[top] + 1;

}

if(mo != -1) {

q.push(mo);

level[mo] = level[top] + 1;

}

if(flag == 0) printf("Yes\n");

}

return 0;

}

【数据结构】堆的建立（边输入数据边建立）（给定数字顺序插入）

堆的建立有两种方式，一个向上调整，一个向下调整，这两个得到的结果可能不同
- 向上调整一般用于边输入数据边建立，是给定数字顺序插入
- 向下调整一般是将所有结点先加入到一棵完全二叉树中，然后对二叉树的所有非叶子结点进行向下调整（从非叶子结点n/2开始，一直到1）

向上调整（大顶堆为例）：

void upAdjust(int i) {
  if(i == 1) return ;
  while(i != 1) {
    if(heap[i] > heap[i / 2]) {
    	swap(heap[i], heap[i / 2]);
    	i = i / 2;
    } else {
      break;
    }
  }
}

for(int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        upAdjust(i);
}

void upAdjust(int i) {

if(i == 1) return ;

while(i != 1) {

if(heap[i] > heap[i / 2]) {

swap(heap[i], heap[i / 2]);

i = i / 2;

} else {

break;

}

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

scanf("%d", &v[i]);

upAdjust(i);

}

向下调整（以大顶堆为例）：先将所有输入得到的数组存储到heap[i]中（构成了一颗完全二叉树，下标从1开始）

void createHeap() {
  for(int i = n / 2; i >= 1; i--)
    downAdjust(i, n);
}

void createHeap() {

for(int i = n / 2; i >= 1; i--)

downAdjust(i, n);

}

const int maxn = 100;
int heap[maxn], n = 10;

//对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标（其实可以省去high，就是用全局变量n表示）
void downAdjust(int low, int high) {
  int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子
  while(j <= high) {
    if(j + 1 <= high && heap[j + 1] > heap[j])
      j = j + 1; //那就让j存储数值最大的那个结点所对应的下标
    if(heap[j] > heap[i]) {
      swap(heap[i], heap[j]);
      i = j; j = i * 2;
    } else {
      break;
    }
  }
}

const int maxn = 100;

int heap[maxn], n = 10;

//对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标（其实可以省去high，就是用全局变量n表示）

void downAdjust(int low, int high) {

int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子

while(j <= high) {

if(j + 1 <= high && heap[j + 1] > heap[j])

j = j + 1; //那就让j存储数值最大的那个结点所对应的下标

if(heap[j] > heap[i]) {

swap(heap[i], heap[j]);

i = j; j = i * 2;

} else {

break;

}