Code – 第212页

1009. Product of Polynomials (25)-PAT甲级真题

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 3 3.6 2 6.0 1 1.6

题目大意：给出两个多项式A和B，求A*B的结果～

分析：简单模拟～double类型的arr数组保存第一组数据，ans数组保存结果。当输入第二组数据的时候，一边进行运算一边保存结果。最后按照指数递减的顺序输出所有不为0的项～
注意：因为相乘后指数可能最大为2000，所以ans数组最大要开到2001

#include <iostream>
using namespace std;
int main() {
    int n1, n2, a, cnt = 0;
    scanf("%d", &n1);
    double b, arr[1001] = {0.0}, ans[2001] = {0.0};
    for(int i = 0; i < n1; i++) {
        scanf("%d %lf", &a, &b);
        arr[a] = b;
    }
    scanf("%d", &n2);
    for(int i = 0; i < n2; i++) {
        scanf("%d %lf", &a, &b);
        for(int j = 0; j < 1001; j++)
                ans[j + a] += arr[j] * b;
    }
    for(int i = 2000; i >= 0; i--)
        if(ans[i] != 0.0) cnt++;
    printf("%d", cnt);
    for(int i = 2000; i >= 0; i--)
        if(ans[i] != 0.0)
            printf(" %d %.1f", i, ans[i]);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n1, n2, a, cnt = 0;

scanf("%d", &n1);

double b, arr[1001] = {0.0}, ans[2001] = {0.0};

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

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

arr[a] = b;

}

scanf("%d", &n2);

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

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

for(int j = 0; j < 1001; j++)

ans[j + a] += arr[j] * b;

}

for(int i = 2000; i >= 0; i--)

if(ans[i] != 0.0) cnt++;

printf("%d", cnt);

for(int i = 2000; i >= 0; i--)

if(ans[i] != 0.0)

printf(" %d %.1f", i, ans[i]);

return 0;

}

1065. A+B and C (64bit) (20)-PAT甲级真题

Given three integers A, B and C in [-263, 263], you are supposed to tell whether A+B > C.

Input Specification:

The first line of the input gives the positive number of test cases, T (<=10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

Output Specification:

For each test case, output in one line “Case #X: true” if A+B>C, or “Case #X: false” otherwise, where X is the case number (starting from 1).”
Sample Input:
3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0
Sample Output:
Case #1: false
Case #2: true
Case #3: false
分析：
因为A、B的大小为[-2^63, 2^63]，用long long 存储A和B的值，以及他们相加的值sum：
如果A > 0, B < 0 或者 A < 0, B > 0，sum是不可能溢出的
如果A > 0, B > 0，sum可能会溢出，sum范围理应为(0, 2^64 – 2]，溢出得到的结果应该是[-2^63, -2]是个负数，所以sum < 0时候说明溢出了
如果A < 0, B < 0，sum可能会溢出，同理，sum溢出后结果是大于0的，所以sum > 0 说明溢出了

#include <cstdio>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        long long a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        long long sum = a + b;
        if(a > 0 && b > 0 && sum < 0) {
            printf("Case #%d: true\n", i + 1);
        } else if(a < 0 && b < 0 && sum >= 0){
            printf("Case #%d: false\n", i + 1);
        } else if(sum > c) {
            printf("Case #%d: true\n", i + 1);
        } else {
            printf("Case #%d: false\n", i + 1);
        }
    }
    return 0;
}

#include <cstdio>

using namespace std;

int main() {

int n;

scanf("%d", &n);

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

long long a, b, c;

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

long long sum = a + b;

if(a > 0 && b > 0 && sum < 0) {

printf("Case #%d: true\n", i + 1);

} else if(a < 0 && b < 0 && sum >= 0){

printf("Case #%d: false\n", i + 1);

} else if(sum > c) {

printf("Case #%d: true\n", i + 1);

} else {

printf("Case #%d: false\n", i + 1);

}

return 0;

}

1046. Shortest Distance (20)-PAT甲级真题

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=104), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 107.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:
5 1 2 4 14 9
3
1 3
2 5
4 1
Sample Output:
3
10
7

分析：简单模拟。所有结点连起来会形成一个环形，dis[i]存储第1个结点到第i个结点的下一个结点的距离，sum保存整个路径一圈的总和值。求得结果就是dis[right – 1] – dis[left – 1]和 sum – dis[right – 1] – dis[left – 1]中较小的那一个～～
注意：可能left和right的顺序颠倒了，这时候要把left和right的值交换～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> dis(n + 1);
    int sum = 0, left, right, cnt;
    for(int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        sum += temp;
        dis[i] = sum;
    }
    scanf("%d", &cnt);
    for(int i = 0; i < cnt; i++) {
        scanf("%d %d", &left, &right);
        if(left > right)
            swap(left, right);
        int temp = dis[right - 1] - dis[left - 1];
        printf("%d\n", min(temp, sum - temp));
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

scanf("%d", &n);

vector<int> dis(n + 1);

int sum = 0, left, right, cnt;

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

int temp;

scanf("%d", &temp);

sum += temp;

dis[i] = sum;

}

scanf("%d", &cnt);

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

scanf("%d %d", &left, &right);

if(left > right)

swap(left, right);

int temp = dis[right - 1] - dis[left - 1];

printf("%d\n", min(temp, sum - temp));

}

return 0;

}

1042. Shuffling Machine (20)-PAT甲级真题

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.

The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:

S1, S2, …, S13, H1, H2, …, H13, C1, C2, …, C13, D1, D2, …, D13, J1, J2

where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer K (<= 20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.

Sample Input:
2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47
Sample Output:
S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

分析：简单模拟。使用start和end数组保存每一次变换的开始顺序和结束顺序（以1~54的编号存储），最后根据编号与扑克牌字母数字的对应关系输出end数组

#include <cstdio>
using namespace std;
int main() {
    int cnt;
    scanf("%d", &cnt);
    int start[55], end[55], scan[55];
    for(int i = 1; i < 55; i++) {
        scanf("%d", &scan[i]);
        end[i] = i;
    }
    for(int i = 0; i < cnt; i++) {
        for(int j = 1; j < 55; j++)
            start[j] = end[j];
        for(int k = 1; k < 55; k++)
            end[scan[k]] = start[k];
    }
    char c[6] = {"SHCDJ"};
    for(int i = 1; i < 55; i++) {
        end[i] = end[i] - 1;
        printf("%c%d", c[end[i]/13], end[i]%13+1);
        if(i != 54) printf(" ");
    }
    return 0;
}

#include <cstdio>

using namespace std;

int main() {

int cnt;

scanf("%d", &cnt);

int start[55], end[55], scan[55];

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

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

end[i] = i;

}

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

for(int j = 1; j < 55; j++)

start[j] = end[j];

for(int k = 1; k < 55; k++)

end[scan[k]] = start[k];

}

char c[6] = {"SHCDJ"};

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

end[i] = end[i] - 1;

printf("%c%d", c[end[i]/13], end[i]%13+1);

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

}

return 0;

}

1006. Sign In and Sign Out (25)-PAT甲级真题

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:

Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:

ID_number Sign_in_time Sign_out_time

where times are given in the format HH:MM:SS, and ID number is a string with no more than 15 characters.

Output Specification:

For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.

Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

Sample Input:

CS301111 15:30:28 17:00:10

SC3021234 08:00:00 11:25:25

CS301133 21:45:00 21:58:40

Sample Output:

SC3021234 CS301133

题目大意：给出n个人的id、sign in时间、sign out时间，求最早进来的人和最早出去的人的ID～

分析：将时间都转换为总秒数，最早和最迟的时间保存在变量minn和maxn中，并同时保存当前最早和最迟的人的ID，最后输出～

#include <iostream>
#include <climits>
using namespace std;
int main() {
    int n, minn = INT_MAX, maxn = INT_MIN;
    scanf("%d", &n);
    string unlocked, locked;
    for(int i = 0; i < n; i++) {
        string t;
        cin >> t;
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int tempIn = h1 * 3600 + m1 * 60 + s1;
        int tempOut = h2 * 3600 + m2 * 60 + s2;
        if (tempIn < minn) {
            minn = tempIn;
            unlocked = t;
        }
        if (tempOut > maxn) {
            maxn = tempOut;
            locked = t;
        }
    }
    cout << unlocked << " " << locked;
    return 0;
}

#include <iostream>

#include <climits>

using namespace std;

int main() {

int n, minn = INT_MAX, maxn = INT_MIN;

scanf("%d", &n);

string unlocked, locked;

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

string t;

cin >> t;

int h1, m1, s1, h2, m2, s2;

scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);

int tempIn = h1 * 3600 + m1 * 60 + s1;

int tempOut = h2 * 3600 + m2 * 60 + s2;

if (tempIn < minn) {

minn = tempIn;

unlocked = t;

}

if (tempOut > maxn) {

maxn = tempOut;

locked = t;

}

cout << unlocked << " " << locked;

return 0;

}

C++：string类中size()和length()的区别

此文献给好友风临神上(^-^)

结论是，两者没有任何区别。

解释：

C++ Reference中对于String字符串中函数size和length的解释是这样的：

size	Return length of string
length	Return length of string

连两者的具体解释都一样：

std::string::size

Return length of string

Returns the length of the string, in terms of bytes.
This is the number of actual bytes that conform the contents of the string, which is not necessarily equal to its storagecapacity.
Note that string objects handle bytes without knowledge of the encoding that may eventually be used to encode the characters it contains. Therefore, the value returned may not correspond to the actual number of encoded characters in sequences of multi-byte or variable-length characters (such as UTF-8).
Both string::size and string::length are synonyms and return the same value.

std::string::length

Return length of string

所以两者的微小区别就是：

size() 一般用作返回容器大小的方法

length() 一般用作返回一个序列的长度