Code – 第217页

1093. Count PAT’s (25)-PAT甲级真题

The string APPAPT contains two PAT’s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT’s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT’s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:
APPAPT
Sample Output:
2

分析：要想知道构成多少个PAT，那么遍历字符串后对于每一A，它前面的P的个数和它后面的T的个数的乘积就是能构成的PAT的个数。然后把对于每一个A的结果相加即可～辣么就简单啦，只需要先遍历字符串数一数有多少个T～然后每遇到一个T呢～countt–;每遇到一个P呢，countp++;然后一遇到字母A呢就countt * countp～～把这个结果累加到result中～～最后输出结果就好啦～对了别忘记要对10000000007取余哦～～

【PS：假设神奇的你对每次都遇到的神奇的为什么要对1000000007取模感兴趣，戳那个加下划线的链接即可~~~^_^】

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int len = s.length(), result = 0, countp = 0, countt = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'T')
            countt++;
    }
    for (int i = 0; i < len; i++) {
        if (s[i] == 'P') countp++;
        if (s[i] == 'T') countt--;
        if (s[i] == 'A') result = (result + (countp * countt) % 1000000007) % 1000000007;
    }
    cout << result;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

int len = s.length(), result = 0, countp = 0, countt = 0;

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

if (s[i] == 'T')

countt++;

}

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

if (s[i] == 'P') countp++;

if (s[i] == 'T') countt--;

if (s[i] == 'A') result = (result + (countp * countt) % 1000000007) % 1000000007;

}

cout << result;

return 0;

}

1100. Mars Numbers (20)-PAT甲级真题

People on Mars count their numbers with base 13:

Zero on Earth is called “tret” on Mars.
The numbers 1 to 12 on Earch is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively.
For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.
For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (< 100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.

Output Specification:
For each number, print in a line the corresponding number in the other language.

Sample Input:
4
29
5
elo nov
tam

Sample Output:
hel mar
may
115
13

题目大意：火星人是以13进制计数的：地球人的0被火星人称为tret。地球人数字1到12的火星文分别为：jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。火星人将进位以后的12个高位数字分别称为：tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。例如地球人的数字“29”翻译成火星文就是“hel mar”；而火星文“elo nov”对应地球数字“115”。为了方便交流，请你编写程序实现地球和火星数字之间的互译～

分析：因为给出的可能是数字（地球文）也有可能是字母（火星文），所以用字符串s保存每一次的输入，因为如果是火星文则会出现空格，所以用getline接收一行的输入～计算string s的长度len，判断s[0]是否是数字，如果是数字，表示是地球文，则需要转为火星文，执行func1()；如果不是数字，则说明是火星文，需要转为地球文，执行func2()；

func1(int t)中，传入的值是string转int后的结果stoi(s)，因为数字最大不超过168，所以最多只会输出两位火星文，如果t / 13不等于0，说明有高位，所以输出b[t/13]；如果输出了高位（t/13不等于0）并且t % 13不等于0，说明有高位且有低位，所以此时输出空格；如果t % 13不等于0，说明有低位，此时输出a[t % 13]；注意，还有个数字0没有考虑，因为数字0取余13等于0，但是要特别输出tret，所以在func1的最后一句判断中加一句t == 0，并将a[0]位赋值成tret即可解决0的问题～

func2()中，t1和t2一开始都赋值0，s1和s2用来分离火星文单词，因为火星文字符串只可能一个单词或者两个单词，而且一个单词不会超过4，所以先将一个单词的赋值给s1，即s1 = s.substr(0, 3)；如果len > 4，就将剩下的一个单词赋值给s2，即s2 = s.substr(4, 3)；然后下标j从1到12遍历a和b两个数组，如果a数组中有和s1或者s2相等的，说明低位等于j，则将j赋值给t2；如果b数组中有和s1相等的（b数组不会和s2相等，因为如果有两个单词，s2只可能是低位），说明高位有值，将j赋值给t1，最后输出t1 * 13 + t2即可～

#include <iostream>
#include <string>
using namespace std;
string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string b[13] = {"####", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
string s;
int len;
void func1(int t) {
    if (t / 13) cout << b[t / 13];
    if ((t / 13) && (t % 13)) cout << " ";
    if (t % 13 || t == 0) cout << a[t % 13];
}
void func2() {
    int t1 = 0, t2 = 0;
    string s1 = s.substr(0, 3), s2;
    if (len > 4) s2 = s.substr(4, 3);
    for (int j = 1; j <= 12; j++) {
        if (s1 == a[j] || s2 == a[j]) t2 = j;
        if (s1 == b[j]) t1 = j;
    }
    cout << t1 * 13 + t2;
}
int main() {
    int n;
    cin >> n;
    getchar();
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        len = s.length();
        if (s[0] >= '0' && s[0] <= '9')
            func1(stoi(s));
        else
            func2();
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};

string b[13] = {"####", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};

string s;

int len;

void func1(int t) {

if (t / 13) cout << b[t / 13];

if ((t / 13) && (t % 13)) cout << " ";

if (t % 13 || t == 0) cout << a[t % 13];

}

void func2() {

int t1 = 0, t2 = 0;

string s1 = s.substr(0, 3), s2;

if (len > 4) s2 = s.substr(4, 3);

for (int j = 1; j <= 12; j++) {

if (s1 == a[j] || s2 == a[j]) t2 = j;

if (s1 == b[j]) t1 = j;

}

cout << t1 * 13 + t2;

}

int main() {

int n;

cin >> n;

getchar();

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

getline(cin, s);

len = s.length();

if (s[0] >= '0' && s[0] <= '9')

func1(stoi(s));

else

func2();

cout << endl;

}

return 0;

}

1002. A+B for Polynomials (25)-PAT甲级真题

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

Input

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

For each test case you should output the sum 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 to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 2 1.5 1 2.9 0 3.2

题目大意：计算多项式A+B的和～

分析：设立c数组，长度为指数的最大值，c[i] = j表示指数i的系数为j，接收a和b输入的同时将对应指数的系数加入到c中，累计c中所有非零系数的个数，然后从后往前输出所有系数不为0的指数和系数～

#include <iostream>
using namespace std;
int main() {
    float c[1001] = {0};
    int m, n, t;
    float num;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%f", &t, &num);
        c[t] += num;
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%f", &t, &num);
        c[t] += num;
    }
    int cnt = 0;
    for (int i = 0; i < 1001; i++) {
        if (c[i] != 0) cnt++;
    }
    printf("%d", cnt);
    for (int i = 1000; i >= 0; i--) {
        if (c[i] != 0.0)
            printf(" %d %.1f", i, c[i]);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

float c[1001] = {0};

int m, n, t;

float num;

scanf("%d", &m);

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

scanf("%d%f", &t, &num);

c[t] += num;

}

scanf("%d", &n);

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

scanf("%d%f", &t, &num);

c[t] += num;

}

int cnt = 0;

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

if (c[i] != 0) cnt++;

}

printf("%d", cnt);

for (int i = 1000; i >= 0; i--) {

if (c[i] != 0.0)

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

}

return 0;

}

1001. A+B Format (20)-PAT甲级真题

Calculate a + b and output the sum in standard format — that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

Input

Each input file contains one test case. Each case contains a pair of integers a and b where -1000000 <= a, b <= 1000000. The numbers are separated by a space.

Output

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

Sample Input

-1000000 9

Sample Output

-999,991

题目大意：计算A+B的和，然后以每三位加一个”,”的格式输出～

分析：把a+b的和转为字符串s～除了第一位是负号的情况，只要当前位的下标i满足(i + 1) % 3 == len % 3并且i不是最后一位，就在逐位输出的时候在该位输出后的后面加上一个逗号～

#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    string s = to_string(a + b);
    int len = s.length();
    for (int i = 0; i < len; i++) {
        cout << s[i];
        if (s[i] == '-') continue;
        if ((i + 1) % 3 == len % 3 && i != len - 1) cout << ",";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b;

cin >> a >> b;

string s = to_string(a + b);

int len = s.length();

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

cout << s[i];

if (s[i] == '-') continue;

if ((i + 1) % 3 == len % 3 && i != len - 1) cout << ",";

}

return 0;

}

1005. Spell It Right (20)-PAT甲级真题

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

Input Specification:

Each input file contains one test case. Each case occupies one line which contains an N (<= 10100).

Output Specification:

For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.

Sample Input:

12345

Sample Output:

one five

题目大意：给一个非负正数N，计算N的每一位相加的和，然后输出和的每一位的英文读音～

分析：1、求出每一位相加的和sum 2、将sum转换为string s 3、将string s的每一位输出对应的英文读音～

#include <iostream>
using namespace std;
int main() {
    string a;
    cin >> a;
    int sum = 0;
    for (int i = 0; i < a.length(); i++)
        sum += (a[i] - '0');
    string s = to_string(sum);
    string arr[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    cout << arr[s[0] - '0'];
    for (int i = 1; i < s.length(); i++)
        cout << " " << arr[s[i] - '0'];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string a;

cin >> a;

int sum = 0;

for (int i = 0; i < a.length(); i++)

sum += (a[i] - '0');

string s = to_string(sum);

string arr[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};

cout << arr[s[0] - '0'];

for (int i = 1; i < s.length(); i++)

cout << " " << arr[s[i] - '0'];

return 0;

}

LeetCode 371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

分析：位运算~
首先，已知异或（就是这个“^”符号）可以得到：
0^0 = 0
0^1 = 1
1^1 = 0
正是位相加时该位的结果~（只不过还有个进位没加罢了~）
所以对于还没有加进位的result，result可以暂时等于a^b

其次，已知与运算（就是这个“&”符号）可以得到：
0&0 = 0
0&1 = 0
1&1 = 1
正是位相加时候有进位的那一位标注为了1~
但是进位是往前一个位相加上去的呀~
所以carry = (a & b) << 1

现在处理要把result加上进位的事情～
如果进位carry等于0，那么不用加～直接等于result的值就好了～
如果进位不等于0，那么就要把result和carry的值按位相加～
按位相加的结果也可能导致进位~所以先用个临时变量temp把carry的值保存，然后令carry = (result & temp) << 1（也就是result和原来carry按位相加后进位的结果～），然后result = result ^ temp（也就是result和原来carry按位相加的结果～），不断循环往复，直到有一次carry等于0，不再需要进位了～～

class Solution {
public:
    int getSum(int a, int b) {
        int carry = (a & b) << 1;
        int result = (a ^ b);
        while(carry != 0) {
            int temp = carry;
            carry = (result & temp) << 1;
            result = result ^ temp;
        };
        return result;
    }
};

class Solution {

public:

int getSum(int a, int b) {

int carry = (a & b) << 1;

int result = (a ^ b);

while(carry != 0) {

int temp = carry;

carry = (result & temp) << 1;

result = result ^ temp;

};

return result;

}

};