PAT – 第36页

L1-009. N个数求和-PAT团体程序设计天梯赛GPLT

输入格式：
输入第一行给出一个正整数N（<=100）。随后一行按格式“a1/b1 a2/b2 …”给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

输出格式：
输出上述数字和的最简形式 —— 即将结果写成“整数部分分数部分”，其中分数部分写成“分子/分母”，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

输入样例1：
5
2/5 4/15 1/30 -2/60 8/3
输出样例1：
3 1/3
输入样例2：
2
4/3 2/3
输出样例2：
2
输入样例3：
3
1/3 -1/6 1/8
输出样例3：
7/24

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

#include <cstdio>
#include <cstdlib>
using namespace std;
long long gcd(long long a, long long b) {return b == 0 ? 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 = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));
        sumb = sumb / gcdvalue;
        suma = suma / gcdvalue;
        gcdvalue = (a == 0 || b == 0) ? 1 : gcd(abs(a), abs(b));
        a = a / gcdvalue;
        b = b / gcdvalue;
        suma = a * sumb + suma * b;
        sumb = b * sumb;
    }
    long long integer = suma / sumb;
    suma = suma - (sumb * integer);
    gcdvalue = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));
    suma = suma / gcdvalue;
    sumb = sumb / gcdvalue;
    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 <cstdio>

#include <cstdlib>

using namespace std;

long long gcd(long long a, long long b) {return b == 0 ? 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 = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));

sumb = sumb / gcdvalue;

suma = suma / gcdvalue;

gcdvalue = (a == 0 || b == 0) ? 1 : gcd(abs(a), abs(b));

a = a / gcdvalue;

b = b / gcdvalue;

suma = a * sumb + suma * b;

sumb = b * sumb;

}

long long integer = suma / sumb;

suma = suma - (sumb * integer);

gcdvalue = (suma == 0 || sumb == 0) ? 1 : gcd(abs(suma), abs(sumb));

suma = suma / gcdvalue;

sumb = sumb / gcdvalue;

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;

}

浮点错误的意思-PAT 、OJ

浮点错误: 您的程序运行时发生浮点错误，比如遇到了除以 0 的情况

所以发生浮点错误应该考虑程序中：

是否可能出现了一个数除以0的情况
是否可能出现了一个数取余0的情况
是否发生了数据溢出而导致的除以0或者取余0的情况

L2-005. 集合相似度-PAT团体程序设计天梯赛GPLT

给定两个整数集合，它们的相似度定义为：Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：

输入第一行给出一个正整数N（<=50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（<=104），是集合中元素的个数；然后跟M个[0, 109]区间内的整数。

之后一行给出一个正整数K（<=2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。

输出格式：

对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例：
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例：
50.00%
33.33%

题目大意：nc是两个集合的公共元素个数，nt是两个集合的所有包含的元素个数（其中元素个数表示各个元素之间互不相同）。

分析：因为给出的集合里面含有重复的元素，而计算nc和nt不需要考虑两个集合里面是否分别有重复的元素，所以可以直接使用set存储每一个集合，然后把set放进一个数组里面存储。当需要计算集合a和集合b的相似度nc和nt的时候，遍历集合a中的每一个元素，寻找集合b中是否有该元素，如果有，说明是两个人公共的集合元素，则nc++，否则nt++（nt的初值为b集合里面本有的元素）。

#include <set>
#include <vector>
#include <cstdio>
using namespace std;
int main() {
    int n, m, k, temp, a, b;
    scanf("%d", &n);
    vector<set<int>> v(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &m);
        set<int> s;
        for(int j = 0; j < m; j++) {
            scanf("%d", &temp);
            s.insert(temp);
        }
        v[i] = s;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &a, &b);
        int nc = 0, nt = v[b-1].size();
        for(auto it = v[a-1].begin(); it != v[a-1].end(); it++) {
            if(v[b-1].find(*it) == v[b-1].end()) 
                nt++;
            else
                nc++;
        }
        double ans = (double)nc / nt * 100;
        printf("%.2f%%\n", ans);
    }
    return 0;
}

#include <set>

#include <vector>

#include <cstdio>

using namespace std;

int main() {

int n, m, k, temp, a, b;

scanf("%d", &n);

vector<set<int>> v(n);

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

scanf("%d", &m);

set<int> s;

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

scanf("%d", &temp);

s.insert(temp);

}

v[i] = s;

}

scanf("%d", &k);

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

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

int nc = 0, nt = v[b-1].size();

for(auto it = v[a-1].begin(); it != v[a-1].end(); it++) {

if(v[b-1].find(*it) == v[b-1].end())

nt++;

else

nc++;

}

double ans = (double)nc / nt * 100;

printf("%.2f%%\n", ans);

}

return 0;

}

1112. Stucked Keyboard (20)-PAT甲级真题

On a broken keyboard, some of the keys are always stucked. So when you type some sentences, the characters corresponding to those keys will appear repeatedly on screen for k times.

Now given a resulting string on screen, you are supposed to list all the possible stucked keys, and the original string.

Notice that there might be some characters that are typed repeatedly. The stucked key will always repeat output for a fixed k times whenever it is pressed. For example, when k=3, from the string “thiiis iiisss a teeeeeest” we know that the keys “i” and “e” might be stucked, but “s” is not even though it appears repeatedly sometimes. The original string could be “this isss a teest”.

Input Specification:

Each input file contains one test case. For each case, the 1st line gives a positive integer k ( 1<k<=100 ) which is the output repeating times of a stucked key. The 2nd line contains the resulting string on screen, which consists of no more than 1000 characters from {a-z}, {0-9} and “_”. It is guaranteed that the string is non-empty.

Output Specification:

For each test case, print in one line the possible stucked keys, in the order of being detected. Make sure that each key is printed once only. Then in the next line print the original string. It is guaranteed that there is at least one stucked key.

Sample Input:
3
caseee1__thiiis_iiisss_a_teeeeeest
Sample Output:
ei
case1__this_isss_a_teest

题目大意：键盘某些键卡住了，按一次重复k次，要求找出可能的键，并且输出正确的字符串顺序。可能的键要求按照被发现的顺序输出。

分析：考察STL的应用～
map<char, bool>存储出现的键是否坏，set<char>存储输出可能坏的键的时候，当前字符是否已经被输出过，输出过的键放在set里面.

寻找坏键：遍历字符串的每个字符的时候，与pre（字符串当前字符s[i]的前一个字符）相比较，如果相等就继续计数cnt++，如果不相等，令cnt = 1表示当前字符出现了一次～如果cnt % k等于0 则令s[i]可能是坏键，置map对应的字符的bool值为true～

输出坏键：由于需要根据坏键发现的顺序输出，所以遍历整个字符串的方式输出～，并且确保不会重复输出～（用set集合确保，输出过了的放在set里面）
输出整个正确的字符串：如果当前s[i]是坏键，在输出一次后，令 i = i + k – 1，再输出，保证坏键出现k次只输出一次～

tips：谢谢在csdn博客的评论里的同学友情提醒，如果出现了先不是坏建后又判断是坏键的情况，这种情况会出现错误，因为前面已经认为它不是坏键了，说明它一定不是坏建，所以要加一个sureNoBroken，把确定不是坏键的键标记出来，在map都设置完成后把确定不是坏键的m标记为false。虽然测试用例里面没有考虑到这种情况，但是如果输入3 aabbaaa，应该输出没有坏键。

#include <iostream>
#include <map>
#include <cstdio>
#include <set>
using namespace std;
bool sureNoBroken[256];
int main() {
    int k, cnt = 1;
    scanf("%d", &k);
    string s;
    cin >> s;
    map<char, bool> m;
    set<char> printed;
    char pre = '#';
    s = s + '#';
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == pre) {
            cnt++;
        } else {
            if(cnt % k != 0) {
                sureNoBroken[pre] = true;
            }
            cnt = 1;
        }
        if(i != s.length() - 1) m[s[i]] = (cnt % k == 0);
        pre = s[i];
    }
    for(int i = 0; i < s.length() - 1; i++) {
        if(sureNoBroken[s[i]] == true)
            m[s[i]] = false;
    }
    for(int i = 0; i < s.length() - 1; i++) {
        if(m[s[i]] && printed.find(s[i]) == printed.end()) {
            printf("%c", s[i]);
            printed.insert(s[i]);
        }
    }
    printf("\n");
    for(int i = 0; i < s.length() - 1; i++) {
        printf("%c", s[i]);
        if(m[s[i]])
            i = i + k - 1;
    }
    return 0;
}

#include <iostream>

#include <map>

#include <cstdio>

#include <set>

using namespace std;

bool sureNoBroken[256];

int main() {

int k, cnt = 1;

scanf("%d", &k);

string s;

cin >> s;

map<char, bool> m;

set<char> printed;

char pre = '#';

s = s + '#';

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

if(s[i] == pre) {

cnt++;

} else {

if(cnt % k != 0) {

sureNoBroken[pre] = true;

}

cnt = 1;

}

if(i != s.length() - 1) m[s[i]] = (cnt % k == 0);

pre = s[i];

}

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

if(sureNoBroken[s[i]] == true)

m[s[i]] = false;

}

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

if(m[s[i]] && printed.find(s[i]) == printed.end()) {

printf("%c", s[i]);

printed.insert(s[i]);

}

printf("\n");

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

printf("%c", s[i]);

if(m[s[i]])

i = i + k - 1;

}

return 0;

}

1105. Spiral Matrix (25)-PAT甲级真题

This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and n columns, where m and n satisfy the following: m*n must be equal to N; m>=n; and m-n is the minimum of all the possible values.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains N positive integers to be filled into the spiral matrix. All the numbers are no more than 104. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

Sample Input:
12
37 76 20 98 76 42 53 95 60 81 58 93
Sample Output:
98 95 93
42 37 81
53 20 76
58 60 76

题目大意：将给定的N个正整数按非递增的顺序，填入“螺旋矩阵”~所谓“螺旋矩阵”，是指从左上角第1个格子开始，按顺时针螺旋方向填充~要求矩阵的规模为m行n列，满足条件：m*n等于N；m>=n；且m-n取所有可能值中的最小值~

分析：先计算行数m和列数n的值，n从根号N的整数部分开始，往前推一直到1，找到第一个满足N % n== 0的，m的值等于N/n～将N个给定的值输入数组a，并将a数组中的值按非递增排序，接着建立m行n列的数组b，填充时按层数填充，一个包裹矩阵的口字型为一层，计算螺旋矩阵的层数level，如果m的值为偶数，层数为m/2，如果m为奇数，层数为m/2+1，所以level = m / 2 + m % 2；因为是从左上角第1个格子开始，按顺时针螺旋方向填充，所以外层for循环控制层数i从0到level，内层for循环按左上到右上、右上到右下、右下到左下、左下到左上的顺序一层层填充，注意内层for循环中还要控制t <= N – 1，因为如果螺旋矩阵中所有的元素已经都填充完毕，就不能再重复填充～填充完毕后，输出整个矩阵～

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int cmp(int a, int b) {return a > b;}
int main() {
    int N, m, n, t = 0;
    scanf("%d", &N);
    for (n = sqrt((double)N); n >= 1; n--) {
        if (N % n == 0) {
            m = N / n;
            break;
        }
    }
    vector<int> a(N);
    for (int i = 0; i < N; i++)
        scanf("%d", &a[i]);
    sort(a.begin(), a.end(), cmp);
    vector<vector<int> > b(m, vector<int>(n));
    int level = m / 2 + m % 2;
    for (int i = 0; i < level; i++) {
        for (int j = i; j <= n - 1 - i && t <= N - 1; j++)
                b[i][j] = a[t++];
        for (int j = i + 1; j <= m - 2 - i && t <= N - 1; j++)
                b[j][n - 1 - i] = a[t++];
        for (int j = n - i - 1; j >= i && t <= N - 1; j--)
                b[m - 1 - i][j] = a[t++];
        for (int j = m - 2 - i; j >= i + 1 && t <= N - 1; j--)
                b[j][i] = a[t++];
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0 ; j < n; j++) {
            printf("%d", b[i][j]);
            if (j != n - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

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

int main() {

int N, m, n, t = 0;

scanf("%d", &N);

for (n = sqrt((double)N); n >= 1; n--) {

if (N % n == 0) {

m = N / n;

break;

}

vector<int> a(N);

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

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

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

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

int level = m / 2 + m % 2;

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

for (int j = i; j <= n - 1 - i && t <= N - 1; j++)

b[i][j] = a[t++];

for (int j = i + 1; j <= m - 2 - i && t <= N - 1; j++)

b[j][n - 1 - i] = a[t++];

for (int j = n - i - 1; j >= i && t <= N - 1; j--)

b[m - 1 - i][j] = a[t++];

for (int j = m - 2 - i; j >= i + 1 && t <= N - 1; j--)

b[j][i] = a[t++];

}

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

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

printf("%d", b[i][j]);

if (j != n - 1) printf(" ");

}

printf("\n");

}

return 0;

}

1050. 螺旋矩阵(25)-PAT乙级真题

本题要求将给定的N个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第1个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为m行n列，满足条件：m*n等于N；m>=n；且m-n取所有可能值中的最小值。

输入格式：

输入在第1行中给出一个正整数N，第2行给出N个待填充的正整数。所有数字不超过10^4，相邻数字以空格分隔。

输出格式：

输出螺旋矩阵。每行n个数字，共m行。相邻数字以1个空格分隔，行末不得有多余空格。

输入样例：

12
37 76 20 98 76 42 53 95 60 81 58 93

输出样例：

98 95 93
42 37 81
53 20 76
58 60 76

分析：首先计算行数m和列数n的值，n从根号N的整数部分开始，往前推一直到1，找到第一个满足N % n== 0的，m的值等于N/n～将N个给定的值输入数组a，并将a数组中的值按非递增排序，接着建立m行n列的数组b，填充时按层数填充，一个包裹矩阵的口字型为一层，计算螺旋矩阵的层数level，如果m的值为偶数，层数为m/2，如果m为奇数，层数为m/2+1，所以level = m / 2 + m % 2；因为是从左上角第1个格子开始，按顺时针螺旋方向填充，所以外层for循环控制层数i从0到level，内层for循环按左上到右上、右上到右下、右下到左下、左下到左上的顺序一层层填充，注意内层for循环中还要控制t <= N – 1，因为如果螺旋矩阵中所有的元素已经都填充完毕，就不能再重复填充～填充完毕后，输出整个矩阵～

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int cmp(int a, int b) {return a > b;}
int main() {
    int N, m, n, t = 0;
    scanf("%d", &N);
    for (n = sqrt((double)N); n >= 1; n--) {
        if (N % n == 0) {
            m = N / n;
            break;
        }
    }
    vector<int> a(N);
    for (int i = 0; i < N; i++)
        scanf("%d", &a[i]);
    sort(a.begin(), a.end(), cmp);
    vector<vector<int> > b(m, vector<int>(n));
    int level = m / 2 + m % 2;
    for (int i = 0; i < level; i++) {
        for (int j = i; j <= n - 1 - i && t <= N - 1; j++)
                b[i][j] = a[t++];
        for (int j = i + 1; j <= m - 2 - i && t <= N - 1; j++)
                b[j][n - 1 - i] = a[t++];
        for (int j = n - i - 1; j >= i && t <= N - 1; j--)
                b[m - 1 - i][j] = a[t++];
        for (int j = m - 2 - i; j >= i + 1 && t <= N - 1; j--)
                b[j][i] = a[t++];
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0 ; j < n; j++) {
            printf("%d", b[i][j]);
            if (j != n - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

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

int main() {

int N, m, n, t = 0;

scanf("%d", &N);

for (n = sqrt((double)N); n >= 1; n--) {

if (N % n == 0) {

m = N / n;

break;

}

vector<int> a(N);

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

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

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

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

int level = m / 2 + m % 2;

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

for (int j = i; j <= n - 1 - i && t <= N - 1; j++)

b[i][j] = a[t++];

for (int j = i + 1; j <= m - 2 - i && t <= N - 1; j++)

b[j][n - 1 - i] = a[t++];

for (int j = n - i - 1; j >= i && t <= N - 1; j--)

b[m - 1 - i][j] = a[t++];

for (int j = m - 2 - i; j >= i + 1 && t <= N - 1; j--)

b[j][i] = a[t++];

}

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

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

printf("%d", b[i][j]);

if (j != n - 1) printf(" ");

}

printf("\n");

}

return 0;

}