PAT – 第54页 – 柳婼の blog

1025. 反转链表 (25)-PAT乙级真题

给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10^5)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

分析：输入样例正确连接顺序应该是：
/*
00100 1 12309
12309 2 33218
33218 3 00000
00000 4 99999
99999 5 68237
68237 6 -1
*/
还应该考虑输入样例中有不在链表中的结点的情况。所以用个sum计数~

而且，algorithm头文件里面有reverse函数可以直接调用～

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int first, k, n, temp;
    cin >> first >> n >> k;
    int data[100005], next[100005], list[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];
    }
    int sum = 0;//不一定所有的输入的结点都是有用的，加个计数器
    while (first != -1) {
        list[sum++] = first;
        first = next[first];
    }
    for (int i = 0; i < (sum - sum % k); i += k)
        reverse(begin(list) + i, begin(list) + i + k);
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);
    printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int first, k, n, temp;

cin >> first >> n >> k;

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

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

cin >> temp;

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

}

int sum = 0;//不一定所有的输入的结点都是有用的，加个计数器

while (first != -1) {

list[sum++] = first;

first = next[first];

}

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

reverse(begin(list) + i, begin(list) + i + k);

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

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

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

return 0;

}

1003. 我要通过！(20)-PAT乙级真题

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。
得到“答案正确”的条件是：
1. 字符串中必须仅有P, A, T这三种字符，不可以包含其它字符；
2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a, b, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：

每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。

输出格式：

每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出YES，否则输出NO。

输入样例：

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例：

YES
YES
YES
YES
NO
NO
NO
NO

分析：

任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
那么正确的有这些：
PAT
APATA
AAPATAA
AAAPATAAA
…不说了，就是中间一个A左右加上等量的A（不加也行）都是正确的。

如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a, b, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
拿上面的那几个正确的举例子，那么正确的有这些：
PAT —— 对于 aPbTc 来说ac是空，b是A。所以 PAAT 是正确的。同理PAAAAAT中间加多少个A都是正确哒～
APATA —— 对于aPbTc来说，abc都是A。所以 APAATAA 是正确的。再类推一下，那么 APAAATAAA 是正确的。
AAPATAA —— 对于aPbTc来说，a和c是AA，b是A。所以AAPAATAAAA是正确的，再类推一下，AAPAAATAAAAAA 是正确的～～
所以说规律就是，可以在P和T中间加A并且在T后面加A，要求必须是，中间加上一个A，末尾就得加上几倍的(P前面A的那个字符串)。换句话说就是，中间的A的个数如果是3，那么末尾的A的个数就得是开头A的个数的3倍。很巧，当中间A为一个的时候，末尾和开头A的个数必须相等正好是第二条的要求～

所以一句话总结字符串的要求：只能有一个P一个T，中间末尾和开头可以随便插入A。但是必须满足开头的A的个数 * 中间的A的个数 = 结尾的A的个数，而且P和T中间不能没有A～

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n, p = 0, t = 0;
    string s;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> s;
        map<char, int> m;
        for(int j = 0; j < s.size(); j++) {
            m[s[j]]++;
            if (s[j] == 'P') p = j;
            if (s[j] == 'T') t = j;
        }
        if (m['P'] == 1 && m['A'] != 0 && m['T'] == 1 && m.size() == 3 && t-p != 1 && p * (t-p-1) == s.length()-t-1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int n, p = 0, t = 0;

string s;

cin >> n;

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

cin >> s;

map<char, int> m;

for(int j = 0; j < s.size(); j++) {

m[s[j]]++;

if (s[j] == 'P') p = j;

if (s[j] == 'T') t = j;

}

if (m['P'] == 1 && m['A'] != 0 && m['T'] == 1 && m.size() == 3 && t-p != 1 && p * (t-p-1) == s.length()-t-1)

printf("YES\n");

else

printf("NO\n");

}

return 0;

}

1005. 继续(3n+1)猜想 (25)-PAT乙级真题

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。
当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候，我们需要计算3、5、8、4、2、1，则当我们对n=5、8、4、2进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这4个数已经在验证3的时候遇到过了，我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”，如果n不能被数列中的其他数字所覆盖。
现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

输入格式：

每个测试输入包含1个测试用例，第1行给出一个正整数K(<100)，第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值，数字间用空格隔开。

输出格式：

每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用1个空格隔开，但一行中最后一个数字后没有空格。

输入样例：

6
3 5 6 7 8 11

输出样例：

7 6

分析：对每一个输入的数字n进行验证，把验证过的数字对应的arr标记为1，然后对这些输入的数字从大到小排序，输出所有arr=0的数字即为关键数字～

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[10000];
bool cmp(int a, int b) {return a > b;}
int main() {
    int k, n, flag = 0;
    cin >> k;
    vector<int> v(k);
    for (int i = 0; i < k; i++) {
        cin >> n;
        v[i] = n;
        while (n != 1) {
            if (n % 2 != 0) n = 3 * n + 1;
            n = n / 2;
            if (arr[n] == 1) break;
            arr[n] = 1;
        }
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++) {
        if (arr[v[i]] == 0) {
            if (flag == 1) cout << " ";
            cout << v[i];
            flag = 1;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int arr[10000];

bool cmp(int a, int b) {return a > b;}

int main() {

int k, n, flag = 0;

cin >> k;

vector<int> v(k);

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

cin >> n;

v[i] = n;

while (n != 1) {

if (n % 2 != 0) n = 3 * n + 1;

n = n / 2;

if (arr[n] == 1) break;

arr[n] = 1;

}

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

for (int i = 0; i < v.size(); i++) {

if (arr[v[i]] == 0) {

if (flag == 1) cout << " ";

cout << v[i];

flag = 1;

}

return 0;

}

1084. Broken Keyboard (20)-PAT甲级试题

On a broken keyboard, some of the keys are worn out. So when you type some sentences, the characters corresponding to those keys will not appear on screen.

Now given a string that you are supposed to type, and the string that you actually type out, please list those keys which are for sure worn out.

Input Specification:

Each input file contains one test case. For each case, the 1st line contains the original string, and the 2nd line contains the typed-out string. Each string contains no more than 80 characters which are either English letters [A-Z] (case insensitive), digital numbers [0-9], or “_” (representing the space). It is guaranteed that both strings are non-empty.

Output Specification:

For each test case, print in one line the keys that are worn out, in the order of being detected. The English letters must be capitalized. Each worn out key must be printed once only. It is guaranteed that there is at least one worn out key.

Sample Input:
7_This_is_a_test
hssaes
Sample Output:
7TI

题目大意：旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键～

分析：用string的find函数～遍历字符串s1，当当前字符s1[i]不在s2中，它的大写也不在ans中时，将当前字符的大写放入ans中，最后输出ans字符串即可～
ps：感谢github上的@xiaorong61给我发的pull request中strchr()函数带来的灵感～让我想到了曾经用过的string的find函数～

#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string s1, s2, ans;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); i++)
        if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos)
            ans += toupper(s1[i]);
    cout << ans;
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

int main() {

string s1, s2, ans;

cin >> s1 >> s2;

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

if (s2.find(s1[i]) == string::npos && ans.find(toupper(s1[i])) == string::npos)

ans += toupper(s1[i]);

cout << ans;

return 0;

}

1049. 数列的片段和(20)-PAT乙级真题

给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列{0.1, 0.2, 0.3, 0.4}，我们有(0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这10个片段。
给定正整数数列，求出全部片段包含的所有的数之和。如本例中10个片段总和是0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。
输入格式：
输入第一行给出一个不超过105的正整数N，表示数列中数的个数，第二行给出N个不超过1.0的正数，是数列中的数，其间以空格分隔。
输出格式：
在一行中输出该序列所有片段包含的数之和，精确到小数点后2位。
输入样例：
4
0.1 0.2 0.3 0.4
输出样例：
5.00

分析：将数列中的每个数字读取到temp中，假设我们选取的片段中包括temp，且这个片段的首尾指针分别为p和q，那么对于p，有i种选择，即12…i，对于q，有n-i+1种选择，即i, i+1, … n，所以p和q组合形成的首尾片段有i * (n-i+1)种，因为每个里面都会出现temp，所以temp引起的总和为temp * i * (n – i + 1)；遍历完所有数字，将每个temp引起的总和都累加到sum中，最后输出sum的值～

【Update 2020-6-18】PS：题目更新了测试样例，导致之前的代码测试点2（第3个测试点）无法通过，研究到凌晨四点找错误原因…后来找到了给PAT这道题提反馈改测试用例的这位同学写的关于这道题的博客：https://blog.zhengrh.com/post/about-double/，感谢他让我找到了错误的原因，大概意思是：N比较大时，double类型的值多次累加导致的精度误差，因为输入为十进制小数，存储到double中时，计算机内部使用二进制表示，且计算机的字长有限，有的十进制浮点数使用二进制无法精确表示只能无限接近，在字长的限制下不可避免会产生舍入误差，这些细微的误差在N较大时多次累加会产生较大误差，所以建议不要使用double类型进行多次累加的精确计算，而是转为能够精确存储的整型。尝试把输入的double类型的值扩大1000倍后转为long long整型累加，同时使用long long类型保存sum的值，输出时除以1000.0转为浮点型再输出（相当于把小数点向后移动3位后再计算，避免double类型的小数部分存储不精确，多次累加后对结果产生影响）
但我觉得乘以1000也未必严谨，可能测试样例最小只有小数点后三位，如果测试样例变成小数点后四位、五位、六位，乘以1000相当于直接在小数点后三位处截断，而原本第四五六位经过多次累加进位后依然可能会引起精度问题，但如果乘以10000就会超出long long的值，我认为最精确的应该是截取到所有小数中最大的位数的那一位。。可能我的想法有疏漏，经过测试，测试样例确实没有超过小数点后三位，虽然修改为乘以1000后代码已经AC，但如果对测试样例稍加修改，可能又会导致不AC了…所以这道题先打个问号吧，我猜可能将来题目样例还会被修改…

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long sum = 0;
    double temp;
    for (int i = 1; i <= n; i++) { 
        cin >> temp;
        sum += (long long)(temp * 1000) * i * (n - i + 1);
    }
    printf("%.2f", sum / 1000.0);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long long sum = 0;

double temp;

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

cin >> temp;

sum += (long long)(temp * 1000) * i * (n - i + 1);

}

printf("%.2f", sum / 1000.0);

return 0;

}