Code – 第207页

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;

}

1032. Sharing (25)-PAT甲级真题

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, “loading” and “being” are stored as showed in Figure 1.

Snip20160807_66
Figure 1
You are supposed to find the starting position of the common suffix (e.g. the position of “i” in Figure 1).

Input Specification:

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (<= 105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive 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 the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.

Output Specification:

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output “-1” instead.

Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1

题目大意：求两个链表的首个共同结点的地址。如果没有，就输出-1
分析：用结构体数组存储，node[i]表示地址为i的结点，key表示值，next为下一个结点的地址，flag表示第一条链表有没有该结点
遍历第一条链表，将访问过的结点的flag都标记为true，当遍历第二条结点的时候，如果遇到了true的结点就输出并结束程序，没有遇到就输出-1

#include <cstdio>
using namespace std;
struct NODE {
    char key;
    int next;
    bool flag;
}node[100000];
int main() {
    int s1, s2, n, a, b;
    scanf("%d%d%d", &s1, &s2, &n);
    char data;
    for(int i = 0; i < n; i++) {
        scanf("%d %c %d", &a, &data, &b);
        node[a] = {data, b, false};
    }
    for(int i = s1; i != -1; i = node[i].next)
        node[i].flag = true;
    for(int i = s2; i != -1; i = node[i].next) {
        if(node[i].flag == true) {
            printf("%05d", i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

#include <cstdio>

using namespace std;

struct NODE {

char key;

int next;

bool flag;

}node[100000];

int main() {

int s1, s2, n, a, b;

scanf("%d%d%d", &s1, &s2, &n);

char data;

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

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

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

}

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

node[i].flag = true;

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

if(node[i].flag == true) {

printf("%05d", i);

return 0;

}

printf("-1");

return 0;

}

L2-002. 链表去重-PAT团体程序设计天梯赛GPLT

给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。

输入格式：

输入第一行包含链表第一个结点的地址、以及结点个数N（<= 105 的正整数）。结点地址是一个非负的5位整数，NULL指针用-1表示。

随后N行，每行按下列格式给出一个结点的信息：

Address Key Next

其中Address是结点的地址，Key是绝对值不超过104的整数，Next是下一个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除结点组成的链表。每个结点占一行，按输入的格式输出。

输入样例：
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例：
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;
}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 < maxn; i++) {
        node[i].num = 2 * maxn;
    }
    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;

}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 < maxn; i++) {

node[i].num = 2 * maxn;

}

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;

}

1096. Consecutive Factors (20)-PAT甲级真题

Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3*5*6*7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.

Input Specification:

Each input file contains one test case, which gives the integer N (1<N<231).

Output Specification:

For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format “factor[1]*factor[2]*…*factor[k]”, where the factors are listed in increasing order, and 1 is NOT included.

Sample Input:
630
Sample Output:
3
5*6*7

题目大意：一个正整数N的因子中可能存在若干连续的数字。例如630可以分解为3*5*6*7，其中5、6、7就是3个连续的数字。给定任一正整数N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列～

[Update v2.0] 由github用户littlesevenmo提供的更高效的解法：
不用算连续因子最多不会超过12个，也不需要三重循环，两重循环即可，直接去计算当前部分乘积能不能整除N
分析：1、如果只有一个因子，那么这个数只能为1或者质数。因此我们主要去计算两个及以上因数的情况。
2、在有两个及以上的数连乘中，因数的最大上限为sqrt(N) + 1
3、因此思路就是，不断构造连乘，看连乘的积是否是N的因数，如果是，则看这部分连乘的数的个数是否比已记录的多。
4、用变量first记录连乘的第一个数字，这里我把它赋初值为0，如果在寻找N的因数过程中，first没有改变，那么就表明N是1或者是一个质数～

#include <iostream>
#include <cmath>
using namespace std;
long int num, temp;
int main(){
    cin >> num;
    int first = 0, len = 0, maxn = sqrt(num) + 1;
    for (int i = 2; i <= maxn; i++) {
        int j; 
        temp = 1;
        for (j = i; j <= maxn; j++) {
            temp *= j;
            if (num % temp != 0) break;
        }
        if (j - i > len) {
            len = j - i;
            first = i;
        }
    }
    if (first == 0) {
        cout << 1 << endl << num;
    } else {
        cout << len << endl;
        for (int i = 0; i < len; i++) {
            cout << first + i;
            if (i != len - 1) cout << '*';
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

long int num, temp;

int main(){

cin >> num;

int first = 0, len = 0, maxn = sqrt(num) + 1;

for (int i = 2; i <= maxn; i++) {

int j;

temp = 1;

for (j = i; j <= maxn; j++) {

temp *= j;

if (num % temp != 0) break;

}

if (j - i > len) {

len = j - i;

first = i;

}

if (first == 0) {

cout << 1 << endl << num;

} else {

cout << len << endl;

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

cout << first + i;

if (i != len - 1) cout << '*';

}

return 0;

}

1081. Rational Sum (20)-PAT甲级真题

Given N rational numbers in the form “numerator/denominator”, you are supposed to calculate their sum.

Input Specification:

Each input file contains one test case. Each case starts with a positive integer N (<=100), followed in the next line N rational numbers “a1/b1 a2/b2 …” where all the numerators and denominators are in the range of “long int”. If there is a negative number, then the sign must appear in front of the numerator.

Output Specification:

For each test case, output the sum in the simplest form “integer numerator/denominator” where “integer” is the integer part of the sum, “numerator” < “denominator”, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.

Sample Input 1:
5
2/5 4/15 1/30 -2/60 8/3
Sample Output 1:
3 1/3
Sample Input 2:
2
4/3 2/3
Sample Output 2:
2
Sample Input 3:
3
1/3 -1/6 1/8
Sample Output 3:
7/24

题目大意：给N个有理数（以分子/分母的形式给出），计算这N个数的总和，最后总和要以（整数分子/分母）的形式给出～

分析：先根据分数加法的公式累加，后分离出整数部分和分数部分
分子和分母都在长整型内，所以不能用int存储，否则有一个测试点不通过
一开始一直是浮点错误，按理来说应该是出现了/0或者%0的情况，找了半天也不知道错在哪里，后来注意到应该在累加的时候考虑是否会超出long long的范围，所以在累加每一步之前进行分子分母的约分处理，然后就AC了～
应该还要考虑整数和小数部分都为0时候输出0的情况，但是测试用例中不涉及，所以如果没有最后两句也是可以AC的（PS：据说更新后的系统已经需要考虑全零的情况了～）

#include <iostream>
#include <cstdlib>
using namespace std;
long long gcd(long long a, long long b) {return b == 0 ? abs(a) : gcd(b, a % b);}
int main() {
    long long n, a, b, suma = 0, sumb = 1, gcdvalue;
    scanf("%lld", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld/%lld", &a, &b);
        gcdvalue = gcd(a, b);
        a = a / gcdvalue;
        b = b / gcdvalue;
        suma = a * sumb + suma * b;
        sumb = b * sumb;
        gcdvalue = gcd(suma, sumb);
        sumb = sumb / gcdvalue;
        suma = suma / gcdvalue;
    }
    long long integer = suma / sumb;
    suma = suma - (sumb * integer);
    if(integer != 0) {
        printf("%lld", integer);
        if(suma != 0) printf(" ");
    }
    if(suma != 0)
        printf("%lld/%lld", suma, sumb);
    if(integer == 0 && suma == 0)
        printf("0");
    return 0;
}

#include <iostream>

#include <cstdlib>

using namespace std;

long long gcd(long long a, long long b) {return b == 0 ? abs(a) : gcd(b, a % b);}

int main() {

long long n, a, b, suma = 0, sumb = 1, gcdvalue;

scanf("%lld", &n);

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

scanf("%lld/%lld", &a, &b);

gcdvalue = gcd(a, b);

a = a / gcdvalue;

b = b / gcdvalue;

suma = a * sumb + suma * b;

sumb = b * sumb;

gcdvalue = gcd(suma, sumb);

sumb = sumb / gcdvalue;

suma = suma / gcdvalue;

}

long long integer = suma / sumb;

suma = suma - (sumb * integer);

if(integer != 0) {

printf("%lld", integer);

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

}

if(suma != 0)

printf("%lld/%lld", suma, sumb);

if(integer == 0 && suma == 0)

printf("0");

return 0;

}