PAT – 第33页

1048. Find Coins (25)-PAT甲级真题(Hash散列)

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 could only use exactly two coins to pay the exact amount. Since she has as many as 105 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 two 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 (<=105, the total number of coins) and M(<=103, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the two face values V1 and V2 (separated by a space) such that V1 + V2 = M and V1 <= V2. If such a solution is not unique, output the one with the smallest V1. If there is no solution, output “No Solution” instead.

Sample Input 1:
8 15
1 2 8 7 2 4 11 15
Sample Output 1:
4 11
Sample Input 2:
7 14
1 8 7 2 4 11 15
Sample Output 2:
No Solution
题目大意：给出n个正整数和一个正整数m，问n个数字中是否存在一对数字a和b(a <= b),使a+b=m成立。如果有多个，输出a最小的那一对。
分析：建立数组a保存每个数字出现的次数，然后判断输出

#include <iostream>
using namespace std;
int a[1001];
int main() {
    int n, m, temp;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d", &temp);
        a[temp]++;
    }
    for(int i = 0; i < 1001; i++) {
        if(a[i]) {
            a[i]--;
            if(m > i && a[m-i]) {
                printf("%d %d", i, m - i);
                return 0;
            }
            a[i]++;
        }
    }
    printf("No Solution");
    return 0;
}

#include <iostream>

using namespace std;

int a[1001];

int main() {

int n, m, temp;

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

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

scanf("%d", &temp);

a[temp]++;

}

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

if(a[i]) {

a[i]--;

if(m > i && a[m-i]) {

printf("%d %d", i, m - i);

return 0;

}

a[i]++;

}

printf("No Solution");

return 0;

}

1041. Be Unique (20)-PAT甲级真题（Hash散列）

Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1, 104]. The first one who bets on a unique number wins. For example, if there are 7 people betting on 5 31 5 88 67 88 17, then the second one who bets on 31 wins.

Input Specification:

Each input file contains one test case. Each case contains a line which begins with a positive integer N (<=105) and then followed by N bets. The numbers are separated by a space.

Output Specification:

For each test case, print the winning number in a line. If there is no winner, print “None” instead.

Sample Input 1:
7 5 31 5 88 67 88 17
Sample Output 1:
31
Sample Input 2:
5 888 666 666 888 888
Sample Output 2:
None
题目大意：给n个数字，按照读入顺序，哪个数字是第一个在所有数字中只出现一次的数字。如果所有数字出现都超过了一次，则输出None
分析：建立一个数组，存储每个数字出现的次数，然后遍历一遍输入的顺序看是否有出现次数为1的数字

#include <cstdio>
using namespace std;
int a[100001], m[100000];
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        m[a[i]]++;
    }
    for(int i = 0; i < n; i++) {
        if(m[a[i]] == 1) {
            printf("%d", a[i]);
            return 0;
        }
    }
    printf("None");
    return 0;
}

#include <cstdio>

using namespace std;

int a[100001], m[100000];

int main() {

int n;

scanf("%d", &n);

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

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

m[a[i]]++;

}

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

if(m[a[i]] == 1) {

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

return 0;

}

printf("None");

return 0;

}

1050. String Subtraction (20)-PAT甲级真题（哈希）

Given two strings S1 and S2, S = S1 – S2 is defined to be the remaining string after taking all the characters in S2 from S1. Your task is simply to calculate S1 – S2 for any given strings. However, it might not be that simple to do it fast.

Input Specification:

Each input file contains one test case. Each case consists of two lines which gives S1 and S2, respectively. The string lengths of both strings are no more than 104. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.

Output Specification:

For each test case, print S1 – S2 in one line.

Sample Input:
They are students.
aeiou
Sample Output:
Thy r stdnts.
题目大意：给出两个字符串，在第一个字符串中删除第二个字符串中出现过的所有字符并输出～
分析：用flag[256]数组变量标记str2出现过的字符为true，输出str1的时候根据flag[str1[i]]是否为true,如果是true就不输出
注意：使用int lens1 = strlen(s1);int lens2 = strlen(s2);的形式，否则直接放在for循环里面会超时～
如果使用gets前面请使用char str[100000]而非char *str～～

#include <iostream>
#include <string>
#include <string.h>
using namespace std;
char s1[100000], s2[100000];
int main() {
    cin.getline(s1, 100000);
    cin.getline(s2, 100000);
    int lens1 = strlen(s1), lens2 = strlen(s2);
    bool flag[256] = {false};
    for(int i = 0; i < lens2; i++)
        flag[s2[i]] = true;
    for(int i = 0; i < lens1; i++) {
        if(!flag[s1[i]])
            printf("%c", s1[i]);
    }
    return 0;
}

#include <iostream>

#include <string>

#include <string.h>

using namespace std;

char s1[100000], s2[100000];

int main() {

cin.getline(s1, 100000);

cin.getline(s2, 100000);

int lens1 = strlen(s1), lens2 = strlen(s2);

bool flag[256] = {false};

for(int i = 0; i < lens2; i++)

flag[s2[i]] = true;

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

if(!flag[s1[i]])

printf("%c", s1[i]);

}

return 0;

}

1083. List Grades (25)-PAT甲级真题

Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of which the grades are in a given interval.

Input Specification:

Each input file contains one test case. Each case is given in the following format:

N
name[1] ID[1] grade[1]
name[2] ID[2] grade[2]
… …
name[N] ID[N] grade[N]
grade1 grade2
where name[i] and ID[i] are strings of no more than 10 characters with no space, grade[i] is an integer in [0, 100], grade1 and grade2 are the boundaries of the grade’s interval. It is guaranteed that all the grades are distinct.

Output Specification:

For each test case you should output the student records of which the grades are in the given interval [grade1, grade2] and are in non-increasing order. Each student record occupies a line with the student’s name and ID, separated by one space. If there is no student’s grade in that interval, output “NONE” instead.

Sample Input 1:
4
Tom CS000001 59
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95
60 100
Sample Output 1:
Mike CS991301
Mary EE990830
Joe Math990112
Sample Input 2:
2
Jean AA980920 60
Ann CS01 80
90 95
Sample Output 2:
NONE

题目大意：给出n个考生的信息，按照分数从高到低排序，并且输出给定区间的考生信息。如果不存在满足条件的考生就输出NONE。
分析：建立结构体数组，将不满足条件的学生grade改为-1，并统计满足条件的学生的个数cnt，然后进行排序，输出前cnt个考生的信息～～
注意：因为每个学生的成绩都不同，所以按照下降排列即可，return a.grade > b.grade;

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct stu {
    char name[12];
    char id[12];
    int grade;
};
int cmp1(stu a, stu b) {
    return a.grade > b.grade;
}
int main() {
    int n, low, high, cnt = 0;
    scanf("%d", &n);
    vector<stu> v(n);
    for(int i = 0; i < n; i++) {
        scanf("%s %s %d", v[i].name, v[i].id, &v[i].grade);
    }
    scanf("%d %d", &low, &high);
    for(int i = 0; i < n; i++) {
        if(v[i].grade < low || v[i].grade > high) {
            v[i].grade = -1;
        } else {
            cnt++;
        }
    }
    sort(v.begin(), v.end(), cmp1);
    for(int i = 0; i < cnt; i++) {
        printf("%s %s\n", v[i].name, v[i].id);
    }
    if(cnt == 0)
        printf("NONE");
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct stu {

char name[12];

char id[12];

int grade;

};

int cmp1(stu a, stu b) {

return a.grade > b.grade;

}

int main() {

int n, low, high, cnt = 0;

scanf("%d", &n);

vector<stu> v(n);

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

scanf("%s %s %d", v[i].name, v[i].id, &v[i].grade);

}

scanf("%d %d", &low, &high);

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

if(v[i].grade < low || v[i].grade > high) {

v[i].grade = -1;

} else {

cnt++;

}

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

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

printf("%s %s\n", v[i].name, v[i].id);

}

if(cnt == 0)

printf("NONE");

return 0;

}

1007. Maximum Subsequence Sum (25)-PAT甲级真题（最大连续子序列和、动态规划dp）

Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1 <= i <= j <= K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
题目大意：求最大连续子序列和，输出最大的和以及这个子序列的开始值和结束值。如果所有数都小于0，那么认为最大的和为0，并且输出首尾元素～
分析：sum为要求的最大和，temp为临时最大和，leftindex和rightindex为所求的子序列的下标，tempindex标记left的临时下标～
temp = temp + v[i]，当temp比sum大，就更新sum的值、leftindex和rightindex的值；当temp < 0，那么后面不管来什么值，都应该舍弃temp < 0前面的内容，因为负数对于总和只可能拉低总和，不可能增加总和，还不如舍弃～
舍弃后，直接令temp = 0，并且同时更新left的临时值tempindex。因为对于所有的值都为负数的情况要输出0，第一个值，最后一个值，所以在输入的时候用flag判断是不是所有的数字都是小于0的，如果是，要在输入的时候特殊处理～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    int leftindex = 0, rightindex = n - 1, sum = -1, temp = 0, tempindex = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        temp = temp + v[i];
        if (temp < 0) {
            temp = 0;
            tempindex = i + 1;
        } else if (temp > sum) {
            sum = temp;
            leftindex = tempindex;
            rightindex = i;
        }
    }
    if (sum < 0) sum = 0;
    printf("%d %d %d", sum, v[leftindex], v[rightindex]);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

scanf("%d", &n);

vector<int> v(n);

int leftindex = 0, rightindex = n - 1, sum = -1, temp = 0, tempindex = 0;

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

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

temp = temp + v[i];

if (temp < 0) {

temp = 0;

tempindex = i + 1;

} else if (temp > sum) {

sum = temp;

leftindex = tempindex;

rightindex = i;

}

if (sum < 0) sum = 0;

printf("%d %d %d", sum, v[leftindex], v[rightindex]);

return 0;

}

1028. List Sorting (25)-PAT甲级真题

Excel can sort records according to any column. Now you are supposed to imitate this function.

Input
Each input file contains one test case. For each case, the first line contains two integers N (<=100000) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student’s record consists of his or her distinct ID (a 6-digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).

Output
For each test case, output the sorting result in N lines. That is, if C = 1 then the records must be sorted in increasing order according to ID’s; if C = 2 then the records must be sorted in non-decreasing order according to names; and if C = 3 then the records must be sorted in non-decreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID’s in increasing order.

Sample Input 1
3 1
000007 James 85
000010 Amy 90
000001 Zoe 60
Sample Output 1
000001 Zoe 60
000007 James 85
000010 Amy 90
Sample Input 2
4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98
Sample Output 2
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
Sample Input 3
4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90
Sample Output 3
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90

题目大意：根据c的值是1还是2还是3，对相应的列排序。第一列升序，第二列不降序，第三列不降序
分析：注意，按照名称的不降序排序，因为strcmp比较的是ACSII码，所以A < Z。写cmp函数的时候return strcmp(a.name, b.name) <= 0; return语句返回的是true或者false的值，所以要写 <= 0 这样的形式。比较ACSII码的大小，strcmp(‘a’, ‘z’)返回负值，因为a<z a – z < 0
按照分数的不降序排序，a.score <= b.score

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 100001;
struct NODE {
    int no, score;
    char name[10];
}node[maxn];
int c;
int cmp1(NODE a, NODE b) {
    if(c == 1) {
        return a.no < b.no;
    } else if(c == 2) {
        if(strcmp(a.name, b.name) == 0) return a.no < b.no;
        return strcmp(a.name, b.name) <= 0;
    } else {
        if(a.score == b.score) return a.no < b.no;
        return a.score <= b.score;
    }
}
int main() {
    int n;
    scanf("%d%d", &n, &c);
    for(int i = 0; i < n; i++)
        scanf("%d %s %d", &node[i].no, node[i].name, &node[i].score);
    sort(node, node + n, cmp1);
    for(int i = 0; i < n; i++)
        printf("%06d %s %d\n", node[i].no, node[i].name, node[i].score);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string.h>

using namespace std;

const int maxn = 100001;

struct NODE {

int no, score;

char name[10];

}node[maxn];

int c;

int cmp1(NODE a, NODE b) {

if(c == 1) {

return a.no < b.no;

} else if(c == 2) {

if(strcmp(a.name, b.name) == 0) return a.no < b.no;

return strcmp(a.name, b.name) <= 0;

} else {

if(a.score == b.score) return a.no < b.no;

return a.score <= b.score;

}

int main() {

int n;

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

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

scanf("%d %s %d", &node[i].no, node[i].name, &node[i].score);

sort(node, node + n, cmp1);

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

printf("%06d %s %d\n", node[i].no, node[i].name, node[i].score);

return 0;

}