PAT – 第42页 – 柳婼の blog

1101. Quick Sort (25)-PAT甲级真题

There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?

For example, given N = 5 and the numbers 1, 3, 2, 4, and 5. We have:

1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;
3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;
2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;
and for the similar reason, 4 and 5 could also be the pivot.
Hence in total there are 3 pivot candidates.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 105). Then the next line contains N distinct positive integers no larger than 109. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

Sample Input:
5
1 3 2 4 5
Sample Output:
3
1 4 5

题目大意：快速排序中，我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？例如给定N = 5, 排列是1、3、2、4、5。则：
1的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管3的左边元素都比它小，但是它右边的2它小，所以它不能是主元；
尽管2的右边元素都比它大，但其左边的3比它大，所以它不能是主元；
类似原因，4和5都可能是主元。
因此，有3个元素可能是主元。
给N个数，第一行输出可能是主元的个数，第二行输出这些元素～

分析：对原序列sort排序，逐个比较，当当前元素没有变化并且它左边的所有值的最大值都比它小的时候就可以认为它一定是主元（很容易证明正确性的，毕竟无论如何当前这个数要满足左边都比他小右边都比他大，那它的排名【当前数在序列中处在第几个】一定不会变）～
如果硬编码就直接运行超时了…后来才想到这种方法～
一开始有一个测试点段错误，后来才想到因为输出时候v[0]是非法内存，改正后发现格式错误（好像可以说明那个第2个测试点是0个主元？…）然后加了最后一句printf(“\n”);才正确（难道是当没有主元的时候必须要输出空行吗…）

#include <iostream>
#include <algorithm>
#include <vector>
int v[100000];
using namespace std;
int main() {
    int n, max = 0, cnt = 0;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        if(a[i] == b[i] && b[i] > max)
            v[cnt++] = b[i];
        if (b[i] > max)
            max = b[i];
    }
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++) {
        if (i != 0) printf(" ");
        printf("%d", v[i]);
    }
    printf("\n");
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

int v[100000];

using namespace std;

int main() {

int n, max = 0, cnt = 0;

scanf("%d", &n);

vector<int> a(n), b(n);

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

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

b[i] = a[i];

}

sort(a.begin(), a.end());

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

if(a[i] == b[i] && b[i] > max)

v[cnt++] = b[i];

if (b[i] > max)

max = b[i];

}

printf("%d\n", cnt);

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

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

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

}

printf("\n");

return 0;

}

1061. Dating (20)-PAT甲级真题

Sherlock Holmes received a note with some strange strings: “Let’s date! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”. It took him only a minute to figure out that those strange strings are actually referring to the coded time “Thursday 14:04” — since the first common capital English letter (case sensitive) shared by the first two strings is the 4th capital letter ‘D’, representing the 4th day in a week; the second common character is the 5th capital letter ‘E’, representing the 14th hour (hence the hours from 0 to 23 in a day are represented by the numbers from 0 to 9 and the capital letters from A to N, respectively); and the English letter shared by the last two strings is ‘s’ at the 4th position, representing the 4th minute. Now given two pairs of strings, you are supposed to help Sherlock decode the dating time.

Input Specification:

Each input file contains one test case. Each case gives 4 non-empty strings of no more than 60 characters without white space in 4 lines.

Output Specification:

For each test case, print the decoded time in one line, in the format “DAY HH:MM”, where “DAY” is a 3-character abbreviation for the days in a week — that is, “MON” for Monday, “TUE” for Tuesday, “WED” for Wednesday, “THU” for Thursday, “FRI” for Friday, “SAT” for Saturday, and “SUN” for Sunday. It is guaranteed that the result is unique for each case.

Sample Input:
3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm
Sample Output:
THU 14:04

题目大意：福尔摩斯接到一张奇怪的字条：“我们约会吧！3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”。大侦探很快就明白了，前面两字符串中第1对相同的大写英文字母（大小写有区分）是第4个字母D，代表星期四；第2对相同的字符是E，那是第5个英文字母，代表一天里的第14个钟头（于是一天的0点到23点由数字0到9、以及大写字母A到N表示）；后面两字符串第1对相同的英文字母s出现在第4个位置（从0开始计数）上，代表第4分钟。现给定两对字符串，要求解码得到约会的时间~

分析：按照题目所给的方法找到相等的字符后判断即可，如果输出的时间不足2位数要在前面添0，即用%02d输出～

#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string a, b, c, d;
    cin >> a >> b >> c >> d;
    char t[2];
    int pos, i = 0, j = 0;
    while(i < a.length() && i < b.length()) {
        if (a[i] == b[i] && (a[i] >= 'A' && a[i] <= 'G')) {
            t[0] = a[i];
            break;
        }
        i++;
    }
    i = i + 1;
    while (i < a.length() && i < b.length()) {
        if (a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) {
            t[1] = a[i];
            break;
        }
        i++;
    }
    while (j < c.length() && j < d.length()) {
        if (c[j] == d[j] && isalpha(c[j])) {
            pos = j;
            break;
        }
        j++;
    }
    string week[7] = {"MON ", "TUE ", "WED ", "THU ", "FRI ", "SAT ", "SUN "};
    int m = isdigit(t[1]) ? t[1] - '0' : t[1] - 'A' + 10;
    cout << week[t[0]-'A'];
    printf("%02d:%02d", m, pos);
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

int main() {

string a, b, c, d;

cin >> a >> b >> c >> d;

char t[2];

int pos, i = 0, j = 0;

while(i < a.length() && i < b.length()) {

if (a[i] == b[i] && (a[i] >= 'A' && a[i] <= 'G')) {

t[0] = a[i];

break;

}

i++;

}

i = i + 1;

while (i < a.length() && i < b.length()) {

if (a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) {

t[1] = a[i];

break;

}

i++;

}

while (j < c.length() && j < d.length()) {

if (c[j] == d[j] && isalpha(c[j])) {

pos = j;

break;

}

j++;

}

string week[7] = {"MON ", "TUE ", "WED ", "THU ", "FRI ", "SAT ", "SUN "};

int m = isdigit(t[1]) ? t[1] - '0' : t[1] - 'A' + 10;

cout << week[t[0]-'A'];

printf("%02d:%02d", m, pos);

return 0;

}

1070. Mooncake (25)-PAT甲级真题

Mooncake is a Chinese bakery product traditionally eaten during the Mid-Autumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the regions culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to tell the maximum profit that can be made.
Note: partial inventory storage can be taken. The sample shows the following situation: given three kinds of mooncakes with inventory amounts being 180, 150, and 100 thousand tons, and the prices being 7.5, 7.2, and 4.5 billion yuans. If the market demand can be at most 200 thousand tons, the best we can do is to sell 150 thousand tons of the second kind of mooncake, and 50 thousand tons of the third kind. Hence the total profit is 7.2 + 4.5/2 = 9.45 (billion yuans).

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (<=1000), the number of different kinds of mooncakes, and D (<=500 thousand tons), the maximum total demand of the market. Then the second line gives the positive inventory amounts (in thousand tons), and the third line gives the positive prices (in billion yuans) of N kinds of mooncakes. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print the maximum profit (in billion yuans) in one line, accurate up to 2 decimal places.

Sample Input:
3 200
180 150 100
7.5 7.2 4.5
Sample Output:
9.45

题目大意：N表示月饼种类，D表示月饼的市场最大需求量，给出每种月饼的数量和总价，问根据市场最大需求量，这些月饼的最大销售利润为多少～

分析：首先根据月饼的总价和数量计算出每一种月饼的单价，然后将月饼数组按照单价从大到小排序，根据需求量need的大小，从单价最大的月饼开始售卖，将销售掉这种月饼的价格累加到result中，最后输出result即可～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct mooncake{
    float num, price, unit;
};
int cmp(mooncake a, mooncake b) {
    return a.unit > b.unit;
}
int main() {
    int n, need;
    cin >> n >> need;
    vector<mooncake> a(n);
    for (int i = 0; i < n; i++) scanf("%f", &a[i].num);
    for (int i = 0; i < n; i++) scanf("%f", &a[i].price);
    for (int i = 0; i < n; i++) a[i].unit = a[i].price / a[i].num;
    sort(a.begin(), a.end(), cmp);
    float result = 0.0;
    for (int i = 0; i < n; i++) {
        if (a[i].num <= need) {
            result = result + a[i].price;
        } else {
            result = result + a[i].unit * need;
            break;
        }
        need = need - a[i].num;
    }
    printf("%.2f",result);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct mooncake{

float num, price, unit;

};

int cmp(mooncake a, mooncake b) {

return a.unit > b.unit;

}

int main() {

int n, need;

cin >> n >> need;

vector<mooncake> a(n);

for (int i = 0; i < n; i++) scanf("%f", &a[i].num);

for (int i = 0; i < n; i++) scanf("%f", &a[i].price);

for (int i = 0; i < n; i++) a[i].unit = a[i].price / a[i].num;

sort(a.begin(), a.end(), cmp);

float result = 0.0;

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

if (a[i].num <= need) {

result = result + a[i].price;

} else {

result = result + a[i].unit * need;

break;

}

need = need - a[i].num;

}

printf("%.2f",result);

return 0;

}

1074. Reversing Linked List (25)-PAT甲级真题

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

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 (<=N) which is the length of the sublist to be reversed. 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, and Next is the position of the next node.

Output Specification:

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

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

分析：把地址为temp的数的数值存入data[temp]中，把temp的下一个结点的地址存入next[temp]中。
注意：不一定所有的输入的结点都是有用的，加个计数器sum

#include <iostream>
using namespace std;
int main() {
    int first, k, n, sum = 0;
    cin >> first >> n >> k;
    int temp, data[100005], next[100005], list[100005], result[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];
    }
    while (first != -1) {
        list[sum++] = first;
        first = next[first];
    }
    for (int i = 0; i < sum; i++) result[i] = list[i];
    for (int i = 0; i < (sum - sum % k); i++)
        result[i] = list[i / k * k + k - 1 - i % k];
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
    printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int first, k, n, sum = 0;

cin >> first >> n >> k;

int temp, data[100005], next[100005], list[100005], result[100005];

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

cin >> temp;

cin >> data[temp] >> next[temp];

}

while (first != -1) {

list[sum++] = first;

first = next[first];

}

for (int i = 0; i < sum; i++) result[i] = list[i];

for (int i = 0; i < (sum - sum % k); i++)

result[i] = list[i / k * k + k - 1 - i % k];

for (int i = 0; i < sum - 1; i++)

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

printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);

return 0;

}

1085. Perfect Sequence (25)-PAT甲级真题

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.
Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:
10 8
2 3 20 4 5 1 6 7 8 9
Sample Output:
8

题目大意：给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。输入第一行给出两个正整数N（输入正数的个数）和p（给定的参数），第二行给出N个正整数。在一行中输出最多可以选择多少个数可以用它们组成一个完美数列

分析：简单题。首先将数列从小到大排序，设当前结果为result = 0，当前最长长度为temp = 0；从i = 0～n，j从i + result到n，【因为是为了找最大的result，所以下一次j只要从i的result个后面开始找就行了】每次计算temp若大于result则更新result，最后输出result的值～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    long long p;
    scanf("%d%lld", &n, &p);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    int result = 0, temp = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + result; j < n; j++) {
            if (v[j] <= v[i] * p) {
                temp = j - i + 1;
                if (temp > result)
                    result = temp;
            } else {
                break;
            }
        }
    }
    cout << result;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

int n;

long long p;

scanf("%d%lld", &n, &p);

vector<int> v(n);

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

cin >> v[i];

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

int result = 0, temp = 0;

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

for (int j = i + result; j < n; j++) {

if (v[j] <= v[i] * p) {

temp = j - i + 1;

if (temp > result)

result = temp;

} else {

break;

}

cout << result;

return 0;

}

【solution 2】如果熟练使用upper_bound()，可以使用以下解法解决问题（代码由Github用户littlesevenmo提供，在此表达感谢）：

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int main() {
    int n;
    long long p;
    cin >> n >> p;
    if (n == 0) {
        cout << n;
        return 0;
    }
    long long int *a = new long long int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    int result = 1;
    for (int i = 0; i < n; i++) {
        result = max((int)(upper_bound(a, a+n, a[i] * p) - (a+i)), result);
    }
    cout << result;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <stdlib.h>

using namespace std;

int main() {

int n;

long long p;

cin >> n >> p;

if (n == 0) {

cout << n;

return 0;

}

long long int *a = new long long int[n];

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

cin >> a[i];

sort(a, a + n);

int result = 1;

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

result = max((int)(upper_bound(a, a+n, a[i] * p) - (a+i)), result);

}

cout << result;

return 0;

}

1088. Rational Arithmetic (20)-PAT甲级真题

For two rational numbers, your task is to implement the basic arithmetics, that is, to calculate their sum, difference, product and quotient.

Input Specification:

Each input file contains one test case, which gives in one line the two rational numbers in the format “a1/b1 a2/b2”. The numerators and the denominators are all in the range of long int. If there is a negative sign, it must appear only in front of the numerator. The denominators are guaranteed to be non-zero numbers.

Output Specification:

For each test case, print in 4 lines the sum, difference, product and quotient of the two rational numbers, respectively. The format of each line is “number1 operator number2 = result”. Notice that all the rational numbers must be in their simplest form “k a/b”, where k is the integer part, and a/b is the simplest fraction part. If the number is negative, it must be included in a pair of parentheses. If the denominator in the division is zero, output “Inf” as the result. It is guaranteed that all the output integers are in the range of long int.

Sample Input 1:
2/3 -4/2
Sample Output 1:
2/3 + (-2) = (-1 1/3)
2/3 – (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)
Sample Input 2:
5/3 0/6
Sample Output 2:
1 2/3 + 0 = 1 2/3
1 2/3 – 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

题目大意：输入在一行中按照“a1/b1 a2/b2”的格式给出两个分数形式的有理数，其中分子和分母全是整型范围内的整数，负号只可能出现在分子前，分母不为0，分别在4行中按照“有理数1 运算符有理数2 = 结果”的格式顺序输出2个有理数的和、差、积、商。注意输出的每个有理数必须是该有理数的最简形式“k a/b”，其中k是整数部分，a/b是最简分数部分；若为负数，则须加括号；若除法分母为0，则输出“Inf”～题目保证正确的输出中没有超过整型范围的整数～

分析：func(m, n)的作用是对m/n的分数进行化简，gcd(t1, t2)的作用是计算t1和t2的最大公约数～在func函数中，先看m和n里面是否有0（即m*n是否等于0），如果分母n=0，输出Inf，如果分子m=0，输出”0″～flag表示m和n是否异号，flag=true表示后面要添加负号”(-“和括号”)”，再将m和n都转为abs(m)和abs(n)，即取他们的正数部分方便计算～x = m/n为m和n的可提取的整数部分，先根据flag的结果判断是否要在前面追加”(-“，然后根据x是否等于0判断要不要输出这个整数位，接着根据m%n是否等于0的结果判断后面还有没有小分数，如果m能被n整除，表示没有后面的小分数，那么就根据flag的结果判断要不要加”)”，然后直接return～如果有整数位，且后面有小分数，则要先输出一个空格，接着处理剩下的小分数，先把m分子减去已经提取出的整数部分，然后求m和n的最大公约数t，让m和n都除以t进行化简～最后输出“m/n”，如果flag==true还要在末尾输出”)”

注意：判断m和n是否异号千万不要写成判断m*n是否小于0，因为m*n的结果可能超过了long long int的长度，导致溢出大于0，如果这样写的话会有一个测试点无法通过～（(⊙o⊙)嗯为了这一个测试点找bug找到凌晨两三点的就是我…我好菜啊.jpg）

#include <iostream>
#include <cmath>
using namespace std;
long long a, b, c, d;
long long gcd(long long t1, long long t2) {
    return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}
void func(long long m, long long n) {
    if (m * n == 0) {
        printf("%s", n == 0 ? "Inf" : "0");
        return ;
    }
    bool flag = ((m < 0 && n > 0) || (m > 0 && n < 0));
    m = abs(m); n = abs(n);
    long long x = m / n;
    printf("%s", flag ? "(-" : "");
    if (x != 0) printf("%lld", x);
    if (m % n == 0) {
        if(flag) printf(")");
        return ;
    }
    if (x != 0) printf(" ");
    m = m - x * n;
    long long t = gcd(m, n);
    m = m / t; n = n / t;
    printf("%lld/%lld%s", m, n, flag ? ")" : "");
}
int main() {
    scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);
    func(a, b); printf(" + "); func(c, d); printf(" = "); func(a * d + b * c, b * d); printf("\n");
    func(a, b); printf(" - "); func(c, d); printf(" = "); func(a * d - b * c, b * d); printf("\n");
    func(a, b); printf(" * "); func(c, d); printf(" = "); func(a * c, b * d); printf("\n");
    func(a, b); printf(" / "); func(c, d); printf(" = "); func(a * d, b * c);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

long long a, b, c, d;

long long gcd(long long t1, long long t2) {

return t2 == 0 ? t1 : gcd(t2, t1 % t2);

}

void func(long long m, long long n) {

if (m * n == 0) {

printf("%s", n == 0 ? "Inf" : "0");

return ;

}

bool flag = ((m < 0 && n > 0) || (m > 0 && n < 0));

m = abs(m); n = abs(n);

long long x = m / n;

printf("%s", flag ? "(-" : "");

if (x != 0) printf("%lld", x);

if (m % n == 0) {

if(flag) printf(")");

return ;

}

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

m = m - x * n;

long long t = gcd(m, n);

m = m / t; n = n / t;

printf("%lld/%lld%s", m, n, flag ? ")" : "");

}

int main() {

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

func(a, b); printf(" + "); func(c, d); printf(" = "); func(a * d + b * c, b * d); printf("\n");

func(a, b); printf(" - "); func(c, d); printf(" = "); func(a * d - b * c, b * d); printf("\n");

func(a, b); printf(" * "); func(c, d); printf(" = "); func(a * c, b * d); printf("\n");

func(a, b); printf(" / "); func(c, d); printf(" = "); func(a * d, b * c);

return 0;

}