OJ – 第12页 – liuchuo

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;

}

1097. Deduplication on a Linked List (25)-PAT甲级真题

Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (<= 105) which is the total number of nodes. 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 Key Next

where Address is the position of the node, Key is an integer of which absolute value is no more than 104, and Next is the position of the next node.

Output Specification:

For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
Sample Output:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

题目大意：给一个链表，去重（去掉值或者绝对值相等的），先输出删除后的链表，再输出删除了的链表。
分析：用结构体数组存储这个链表，大小为maxn = 100000，node[i]表示地址为i的结点。在结构体中定义一个num变量，将num变量先初始化为2 * maxn。通过改变num变量的值最后sort排序来改变链表的顺序。
将没有删除的结点的num标记为cnt1，cnt1为当前没有删除的结点的个数；将需要删除的结点的num标记为maxn + cnt2，cnt2表示当前删除了的结点的个数，因为一开始初始化为了2 * maxn，所以我们可以通过对num排序达到：num = 0~maxn为不删除结点，num = maxn~2maxn为删除结点，num = 2maxn为无效结点
这样sort后就会按照需要输出的顺序将结点排序，我们只需要输出前cnt1+cnt2个结点即可～～

#include <cstdio>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int maxn = 100000;
struct NODE {
    int address, key, next, num = 2 * maxn;
}node[maxn];
bool exist[maxn];
int cmp1(NODE a, NODE b){
    return a.num < b.num;
}
int main() {
    int begin, n, cnt1 = 0, cnt2 = 0, a;
    scanf("%d%d", &begin, &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a);
        scanf("%d%d", &node[a].key, &node[a].next);
        node[a].address = a;
    }
    for(int i = begin; i != -1; i = node[i].next) {
        if(exist[abs(node[i].key)] == false) {
            exist[abs(node[i].key)] = true;
            node[i].num = cnt1;
            cnt1++;
        }
        else {
            node[i].num = maxn + cnt2;
            cnt2++;
        }
    }
    sort(node, node + maxn, cmp1);
    int cnt = cnt1 + cnt2;
    for(int i = 0; i < cnt; i++) {
        if(i != cnt1 - 1 && i != cnt - 1) {
            printf("%05d %d %05d\n", node[i].address, node[i].key, node[i+1].address);
        } else {
            printf("%05d %d -1\n", node[i].address, node[i].key);
        }
    }
    return 0;
}

#include <cstdio>

#include <stdlib.h>

#include <algorithm>

using namespace std;

const int maxn = 100000;

struct NODE {

int address, key, next, num = 2 * maxn;

}node[maxn];

bool exist[maxn];

int cmp1(NODE a, NODE b){

return a.num < b.num;

}

int main() {

int begin, n, cnt1 = 0, cnt2 = 0, a;

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

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

scanf("%d", &a);

scanf("%d%d", &node[a].key, &node[a].next);

node[a].address = a;

}

for(int i = begin; i != -1; i = node[i].next) {

if(exist[abs(node[i].key)] == false) {

exist[abs(node[i].key)] = true;

node[i].num = cnt1;

cnt1++;

}

else {

node[i].num = maxn + cnt2;

cnt2++;

}

sort(node, node + maxn, cmp1);

int cnt = cnt1 + cnt2;

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

if(i != cnt1 - 1 && i != cnt - 1) {

printf("%05d %d %05d\n", node[i].address, node[i].key, node[i+1].address);

} else {

printf("%05d %d -1\n", node[i].address, node[i].key);

}

return 0;

}

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

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (< 105) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by -1.

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

Address Key Next

where Address is the address of the node in memory, Key is an integer in [-105, 105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:
5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345
Sample Output:
5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1

题目大意：给出一个链表，将链表排序，然后把链表上的结点按照data值的从小到大顺序输出
分析：建立结构体数组，按照从首地址开始的顺序（直到-1）遍历一遍整个链表，将在链表中的结点的flag标记为true，并且统计cnt（有效结点的个数）。（因为有的结点根本不在链表中）
然后将链表进行排序，如果flag == false就把他们移动到后面（即：reuturn a.flag > b.flag）,最后只输出前cnt个链表的信息～

#include <iostream>
#include <algorithm>
using namespace std;
struct NODE {
    int address, key, next;
    bool flag;
}node[100000];
int cmp1(NODE a, NODE b) {
    return !a.flag || !b.flag ? a.flag > b.flag : a.key < b.key;
}
int main() {
    int n, cnt = 0, s, a, b, c;
    scanf("%d%d", &n, &s);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        node[a] = {a, b, c, false};
    }
    for(int i = s; i != -1; i = node[i].next) {
        node[i].flag = true;
        cnt++;
    }
    if(cnt == 0) {
        printf("0 -1");
    } else {
        sort(node, node + 100000, cmp1);
        printf("%d %05d\n", cnt, node[0].address);
        for(int i = 0; i < cnt; i++) {
            printf("%05d %d ", node[i].address, node[i].key);
            if(i != cnt - 1)
                printf("%05d\n", node[i + 1].address);
            else
                printf("-1\n");
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

struct NODE {

int address, key, next;

bool flag;

}node[100000];

int cmp1(NODE a, NODE b) {

return !a.flag || !b.flag ? a.flag > b.flag : a.key < b.key;

}

int main() {

int n, cnt = 0, s, a, b, c;

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

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

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

node[a] = {a, b, c, false};

}

for(int i = s; i != -1; i = node[i].next) {

node[i].flag = true;

cnt++;

}

if(cnt == 0) {

printf("0 -1");

} else {

sort(node, node + 100000, cmp1);

printf("%d %05d\n", cnt, node[0].address);

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

printf("%05d %d ", node[i].address, node[i].key);

if(i != cnt - 1)

printf("%05d\n", node[i + 1].address);

else

printf("-1\n");

}

return 0;

}