liuchuo – 第196页 – 柳婼の blog

1034. Head of a Gang (30)-PAT甲级真题（连通分量、图的遍历dfs）

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 1:
2
AAA 3
GGG 3
Sample Input 2:
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 2:
0

题目大意：给出1000条以内的通话记录A B和权值w，和阈值k，如果一个团伙人数超过2人并且通话总权值超过k，令团伙里面的自身权值的最大值为头目，输出所有满足条件的团伙的头目，和他们团伙里面的人数
分析：总的来说是一个判断一个图的连通分量的个数，用图的遍历解决，深度优先遍历。
1.因为给的是字母，要用两个map把它们转换成数字，从1开始排列命名所有不同的人的id，存储在两个map里面，一个字符串对应id，一个id对应字符串，方便查找，正好顺便统计了总共的人数idNumber。
2.建立两个数组，weight和G，分别存储每条边的权值和每个结点的权值，因为这两个题目中都要求得后判断。
3.用传递引用的方法深度优先dfs，这样传入的参数在dfs后还能保存想要求得的值
4.遍历过一条边之后就把这条边的权值设为0（ G[u][v] = G[v][u] = 0;）防止出现回路遍历死循环

#include <iostream>
#include <map>
using namespace std;
map<string, int> stringToInt;
map<int, string> intToString;
map<string, int> ans;
int idNumber = 1, k;
int stoifunc(string s) {
    if(stringToInt[s] == 0) {
        stringToInt[s] = idNumber;
        intToString[idNumber] = s;
        return idNumber++;
    } else {
        return stringToInt[s];
    }
}
int G[2010][2010], weight[2010];
bool vis[2010];
void dfs(int u, int &head, int &numMember, int &totalweight) {
    vis[u] = true;
    numMember++;
    if(weight[u] > weight[head])
        head = u;
    for(int v = 1; v < idNumber; v++) {
        if(G[u][v] > 0) {
            totalweight += G[u][v];
            G[u][v] = G[v][u] = 0;
            if(vis[v] == false)
                dfs(v, head, numMember, totalweight);
        }
    }
}
void dfsTrave() {
    for(int i = 1; i < idNumber; i++) {
        if(vis[i] == false) {
            int head = i, numMember = 0, totalweight = 0;
            dfs(i, head, numMember, totalweight);
            if(numMember > 2 && totalweight > k)
                ans[intToString[head]] = numMember;
        }
    }
}
int main() {
    int n, w;
    cin >> n >> k;
    string s1, s2;
    for(int i = 0; i < n; i++) {
        cin >> s1 >> s2 >> w;
        int id1 = stoifunc(s1);
        int id2 = stoifunc(s2);
        weight[id1] += w;
        weight[id2] += w;
        G[id1][id2] += w;
        G[id2][id1] += w;
    }
    dfsTrave();
    cout << ans.size() << endl;
    for(auto it = ans.begin(); it != ans.end(); it++)
        cout << it->first << " " << it->second << endl;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

map<string, int> stringToInt;

map<int, string> intToString;

map<string, int> ans;

int idNumber = 1, k;

int stoifunc(string s) {

if(stringToInt[s] == 0) {

stringToInt[s] = idNumber;

intToString[idNumber] = s;

return idNumber++;

} else {

return stringToInt[s];

}

int G[2010][2010], weight[2010];

bool vis[2010];

void dfs(int u, int &head, int &numMember, int &totalweight) {

vis[u] = true;

numMember++;

if(weight[u] > weight[head])

head = u;

for(int v = 1; v < idNumber; v++) {

if(G[u][v] > 0) {

totalweight += G[u][v];

G[u][v] = G[v][u] = 0;

if(vis[v] == false)

dfs(v, head, numMember, totalweight);

}

void dfsTrave() {

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

if(vis[i] == false) {

int head = i, numMember = 0, totalweight = 0;

dfs(i, head, numMember, totalweight);

if(numMember > 2 && totalweight > k)

ans[intToString[head]] = numMember;

}

int main() {

int n, w;

cin >> n >> k;

string s1, s2;

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

cin >> s1 >> s2 >> w;

int id1 = stoifunc(s1);

int id2 = stoifunc(s2);

weight[id1] += w;

weight[id2] += w;

G[id1][id2] += w;

G[id2][id1] += w;

}

dfsTrave();

cout << ans.size() << endl;

for(auto it = ans.begin(); it != ans.end(); it++)

cout << it->first << " " << it->second << endl;

return 0;

}

1024. Palindromic Number (25)-PAT甲级真题（大整数相加）

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.

Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers N and K, where N (<= 10^10) is the initial numer and K (<= 100) is the maximum number of steps. The numbers are separated by a space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.

Sample Input 1:
67 3
Sample Output 1:
484
2
Sample Input 2:
69 3
Sample Output 2:
1353
3
题目大意：给定一个数字，和允许翻转后相加的次数cnt，求要多少次才能变成一个回文数字，输出那个回文数字和翻转相加了多少次，如果本身就是回文数字就输出0次，如果超过给定的次数cnt了，就输出那个不是回文的结果，并且输出给定的次数cnt
分析：1、会超出long int类型（会有两个点溢出错误），所以用字符串存储，大整数相加
2、可以通过对字符串翻转后比较来判断是否为回文串

#include <iostream>
#include <algorithm>
using namespace std;
string s;
void add(string t) {
    int len = s.length(), carry = 0;
    for(int i = 0; i < len; i++) {
        s[i] = s[i] + t[i] + carry - '0';
        carry = 0;
        if(s[i] > '9') {
            s[i] = s[i] - 10;
            carry = 1;
        }
    }
    if(carry) s += '1';
    reverse(s.begin(), s.end());
}
int main() {
    int cnt, i;
    cin >> s >> cnt;
    for(i = 0; i <= cnt; i++) {
        string t = s;
        reverse(t.begin(), t.end());
        if(s == t || i == cnt) break;
        add(t);
    }
    cout << s << endl << i;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

string s;

void add(string t) {

int len = s.length(), carry = 0;

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

s[i] = s[i] + t[i] + carry - '0';

carry = 0;

if(s[i] > '9') {

s[i] = s[i] - 10;

carry = 1;

}

if(carry) s += '1';

reverse(s.begin(), s.end());

}

int main() {

int cnt, i;

cin >> s >> cnt;

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

string t = s;

reverse(t.begin(), t.end());

if(s == t || i == cnt) break;

add(t);

}

cout << s << endl << i;

return 0;

}

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;

}