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

1134. Vertex Cover (25)-PAT甲级真题

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Now given a graph with several vertex sets, you are supposed to tell if each of them is a vertex cover or not.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104), being the total numbers of vertices and the edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N-1) of the two ends of the edge.

After the graph, a positive integer K (<= 100) is given, which is the number of queries. Then K lines of queries follow, each in the format:

Nv v[1] v[2] … v[Nv]

where Nv is the number of vertices in the set, and v[i]’s are the indices of the vertices.

Output Specification:

For each query, print in a line “Yes” if the set is a vertex cover, or “No” if not.

Sample Input:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
Sample Output:
No
Yes
Yes
No
No

题目大意：给n个结点m条边，再给k个集合。对这k个集合逐个进行判断。每个集合S里面的数字都是结点编号，求问整个图所有的m条边两端的结点，是否至少一个结点出自集合S中。如果是，输出Yes否则输出No

分析：用vector v[n]保存某结点属于的某条边的编号，比如a b两个结点构成的这条边的编号为0，则v[a].push_back(0)，v[b].push_back(0)——表示a属于0号边，b也属于0号边。对于每一个集合做判断，遍历集合中的每一个元素，将当前元素能够属于的边的编号i对应的hash[i]标记为1，表示这条边是满足有一个结点出自集合S中的。最后判断hash数组中的每一个值是否都是1，如果有不是1的，说明这条边的两端结点没有一个出自集合S中，则输出No。否则输出Yes～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, k, nv, a, b, num;
    scanf("%d%d", &n, &m);
    vector<int> v[n];
    for (int i = 0;i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(i);
        v[b].push_back(i);
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &nv);
        int flag = 0;
        vector<int> hash(m, 0);
        for (int j = 0; j < nv; j++) {
            scanf("%d", &num);
            for (int t = 0; t < v[num].size(); t++)
                hash[v[num][t]] = 1;
        }
        for (int j = 0; j < m; j++) {
            if (hash[j] == 0) {
                printf("No\n");
                flag = 1;
                break;
            }
        }
        if (flag == 0) printf("Yes\n");
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m, k, nv, a, b, num;

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

vector<int> v[n];

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

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

v[a].push_back(i);

v[b].push_back(i);

}

scanf("%d", &k);

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

scanf("%d", &nv);

int flag = 0;

vector<int> hash(m, 0);

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

scanf("%d", &num);

for (int t = 0; t < v[num].size(); t++)

hash[v[num][t]] = 1;

}

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

if (hash[j] == 0) {

printf("No\n");

flag = 1;

break;

}

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

}

return 0;

}

1075. 链表元素分类(25)-PAT乙级真题

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而[0, K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K为10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出：第1个结点的地址；结点总个数，即正整数N (<= 105)；以及正整数K (<=1000)。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为[-105, 105]区间内的整数；Next是下一结点的地址。题目保证给出的链表不为空。

输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
输出样例：
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

分析：将结点用list[10000]保存，list为node类型，node中保存结点的值value和它的next地址。list的下标就是结点的地址。将<0、0～k、>k三部分的结点地址分别保存在v[0]、v[1]、v[2]中，最后将vector中的值依次输出即可～

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}list[100000];
vector<int> v[3];
int main() {
    int start, n, k, a;
    scanf("%d%d%d", &start, &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        scanf("%d%d", &list[a].data, &list[a].next);
    }
    int p = start;
    while(p != -1) {
        int data = list[p].data;
        if (data < 0)
            v[0].push_back(p);
        else if (data >= 0 && data <= k)
            v[1].push_back(p);
        else
            v[2].push_back(p);
        p = list[p].next;
    }
    int flag = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < v[i].size(); j++) {
            if (flag == 0) {
                printf("%05d %d ", v[i][j], list[v[i][j]].data);
                flag = 1;
            } else {
                printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data);
            }
        }
    }
    printf("-1");
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int data, next;

}list[100000];

vector<int> v[3];

int main() {

int start, n, k, a;

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

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

scanf("%d", &a);

scanf("%d%d", &list[a].data, &list[a].next);

}

int p = start;

while(p != -1) {

int data = list[p].data;

if (data < 0)

v[0].push_back(p);

else if (data >= 0 && data <= k)

v[1].push_back(p);

else

v[2].push_back(p);

p = list[p].next;

}

int flag = 0;

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

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

if (flag == 0) {

printf("%05d %d ", v[i][j], list[v[i][j]].data);

flag = 1;

} else {

printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data);

}

printf("-1");

return 0;

}

1133. Splitting A Linked List (25)-PAT甲级真题

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.

Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=1000). The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer in [-105, 105], and Next is the position of the next node. It is guaranteed that the list is not empty.

Output Specification:
For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
Sample Output:
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

题目大意：给一个链表和K，遍历链表后将<0的结点先输出，再将0～k区间的结点输出，最后输出>k的结点

分析：1.所有节点用结构体｛id, data, next｝存储
2.遍历链表，找出在此链表中的节点，放入容器v中
3.把节点分三类｛（-无穷，0）, [0,k], (k,+无穷) ｝,把他们按段，按先后顺序依次放进容器ans中，最后输出即可～

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int id, data, next;
};
int main() {
    int begin, n, k, s, d, e;
    scanf("%d%d%d", &begin, &n, &k);
    node a[100010];
    vector<node> v, ans;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &s, &d, &e);
        a[s] = {s, d, e};
    }
    for (; begin != -1; begin = a[begin].next)
        v.push_back(a[begin]);
    for (int i = 0; i < v.size(); i++)
        if (v[i].data < 0) ans.push_back(v[i]);
    for (int i = 0; i < v.size(); i++)
        if (v[i].data >= 0 && v[i].data <= k) ans.push_back(v[i]);
    for (int i = 0; i < v.size(); i++)
        if (v[i].data > k) ans.push_back(v[i]);
    for (int i = 0; i < ans.size() - 1; i++)
        printf("%05d %d %05d\n", ans[i].id, ans[i].data, ans[i + 1].id);
    printf("%05d %d -1\n", ans[ans.size() - 1].id, ans[ans.size() - 1].data);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int id, data, next;

};

int main() {

int begin, n, k, s, d, e;

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

node a[100010];

vector<node> v, ans;

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

scanf("%d%d%d", &s, &d, &e);

a[s] = {s, d, e};

}

for (; begin != -1; begin = a[begin].next)

v.push_back(a[begin]);

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

if (v[i].data < 0) ans.push_back(v[i]);

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

if (v[i].data >= 0 && v[i].data <= k) ans.push_back(v[i]);

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

if (v[i].data > k) ans.push_back(v[i]);

for (int i = 0; i < ans.size() - 1; i++)

printf("%05d %d %05d\n", ans[i].id, ans[i].data, ans[i + 1].id);

printf("%05d %d -1\n", ans[ans.size() - 1].id, ans[ans.size() - 1].data);

return 0;

}

1132. Cut Integer (20)-PAT甲级真题

Cutting an integer means to cut a K digits long integer Z into two integers of (K/2) digits long integers A and B. For example, after cutting Z = 167334, we have A = 167 and B = 334. It is interesting to see that Z can be devided by the product of A and B, as 167334 / (167 x 334) = 3. Given an integer Z, you are supposed to test if it is such an integer.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 20). Then N lines follow, each gives an integer Z (10<=Z<=231). It is guaranteed that the number of digits of Z is an even number.

Output Specification:

For each case, print a single line “Yes” if it is such a number, or “No” if not.

Sample Input:
3
167334
2333
12345678
Sample Output:
Yes
No
No

题目大意：给一个偶数个位的正整数num，把它从中间分成左右两个整数a、b，问num能不能被a和b的乘积整除，能的话输出yes，不能的话输出no

分析：要注意a*b如果为0的时候不能取余，否则会浮点错误～
直接用int保存num的值，计算出num的长度len，则令d = pow(10, len / 2)时，num取余d能得到后半部分的整数，num除以d能得到前半部分的整数，计算num % (a*b)是否等于0就可以得知是否可以被整除～

#include <iostream>
using namespace std;
int main() {
    int n, num;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        string s = to_string(num);
        int len = s.length();
        int a = stoi(s.substr(0, len/2));
        int b = stoi(s.substr(len/2));
        if (a * b != 0 && num % (a * b) == 0)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, num;

scanf("%d", &n);

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

scanf("%d", &num);

string s = to_string(num);

int len = s.length();

int a = stoi(s.substr(0, len/2));

int b = stoi(s.substr(len/2));

if (a * b != 0 && num % (a * b) == 0)

printf("Yes\n");

else

printf("No\n");

}

return 0;

}

谨以此献给正在努力刷题的你^_^

1018. Public Bike Management (30)-PAT甲级真题（Dijkstra + DFS）

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

Snip20160825_77
Figure 1 illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths:

1. PBMC -> S1 -> S3. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3, so that both stations will be in perfect conditions.

2. PBMC -> S2 -> S3. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (<= 100), always an even number, is the maximum capacity of each station; N (<= 500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci (i=1,…N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0->S1->…->Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.

Sample Input:
10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1
Sample Output:
3 0->2->3 0
题目大意：每个自行车车站的最大容量为一个偶数cmax，如果一个车站里面自行车的数量恰好为cmax / 2，那么称处于完美状态。如果一个车站容量是满的或者空的，控制中心（处于结点0处）就会携带或者从路上收集一定数量的自行车前往该车站，一路上会让所有的车站沿途都达到完美。现在给出cmax，车站的数量n，问题车站sp，m条边，还有距离，求最短路径。如果最短路径有多个，求能带的最少的自行车数目的那条。如果还是有很多条不同的路，那么就找一个从车站带回的自行车数目最少的（带回的时候是不调整的）～
分析：Dijkstra + DFS。如果只有Dijkstra是不可以的，因为minNeed和minBack在路径上的传递不满足最优子结构，不是简单的相加的过程，只有在所有路径都确定了之后才能区选择最小的need和最小的back～
Dijkstra求最短路径，dfs求minNeed和minBack和path，dfs的时候模拟一遍需要调整的过程，求出最后得到的need和back，与minNeed和minBack比较然后根据情况更新path，最后输出minNeed path 和 minBack，记得path是从最后一个结点一直到第一个结点的，所以要倒着输出～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 99999999;
int cmax, n, sp, m;
int minNeed = inf, minBack = inf;
int e[510][510], dis[510], weight[510];
bool visit[510];
vector<int> pre[510], path, temppath;
void dfs(int v) {
    temppath.push_back(v);
    if(v == 0) {
        int need = 0, back = 0;
        for(int i = temppath.size() - 1; i >= 0; i--) {
            int id = temppath[i];
            if(weight[id] > 0) {
                back += weight[id];
            } else {
                if(back > (0 - weight[id])) {
                    back += weight[id];
                } else {
                    need += ((0 - weight[id]) - back);
                    back = 0;
                }
            }
        }
        if(need < minNeed) {
            minNeed = need;
            minBack = back;
            path = temppath;
        } else if(need == minNeed && back < minBack) {
            minBack = back;
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    for(int i = 0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    scanf("%d%d%d%d", &cmax, &n, &sp, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &weight[i]);
        weight[i] = weight[i] - cmax / 2;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &e[a][b]);
        e[b][a] = e[a][b];
    }
    dis[0] = 0;
    for(int i = 0; i <= n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j <= n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v <= n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    dfs(sp);
    printf("%d 0", minNeed);
    for(int i = path.size() - 2; i >= 0; i--)
        printf("->%d", path[i]);
    printf(" %d", minBack);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int inf = 99999999;

int cmax, n, sp, m;

int minNeed = inf, minBack = inf;

int e[510][510], dis[510], weight[510];

bool visit[510];

vector<int> pre[510], path, temppath;

void dfs(int v) {

temppath.push_back(v);

if(v == 0) {

int need = 0, back = 0;

for(int i = temppath.size() - 1; i >= 0; i--) {

int id = temppath[i];

if(weight[id] > 0) {

back += weight[id];

} else {

if(back > (0 - weight[id])) {

back += weight[id];

} else {

need += ((0 - weight[id]) - back);

back = 0;

}

if(need < minNeed) {

minNeed = need;

minBack = back;

path = temppath;

} else if(need == minNeed && back < minBack) {

minBack = back;

path = temppath;

}

temppath.pop_back();

return ;

}

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

int main() {

fill(e[0], e[0] + 510 * 510, inf);

fill(dis, dis + 510, inf);

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

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

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

weight[i] = weight[i] - cmax / 2;

}

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

int a, b;

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

scanf("%d", &e[a][b]);

e[b][a] = e[a][b];

}

dis[0] = 0;

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

int u = -1, minn = inf;

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

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

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

if(visit[v] == false && e[u][v] != inf) {

if(dis[v] > dis[u] + e[u][v]) {

dis[v] = dis[u] + e[u][v];

pre[v].clear();

pre[v].push_back(u);

}else if(dis[v] == dis[u] + e[u][v]) {

pre[v].push_back(u);

}

dfs(sp);

printf("%d 0", minNeed);

for(int i = path.size() - 2; i >= 0; i--)

printf("->%d", path[i]);

printf(" %d", minBack);

return 0;

}