柳婼の blog – 第2页 – 我不管，反正我最萌～

1123 舍入 – PAT乙级真题

不同的编译器对浮点数的精度有不同的处理方法。常见的一种是“四舍五入”，即考察指定有效位的后一位数字，如果不小于 5，就令有效位最后一位进位，然后舍去后面的尾数；如果小于 5 就直接舍去尾数。另一种叫“截断”，即不管有效位后面是什么数字，一概直接舍去。还有一种是“四舍六入五成双”，即当有效位的后一位数字是 5 时，有 3 种情况要考虑：如果 5 后面还有其它非 0 尾数，则进位；如果没有，则当有效位最后一位是单数时进位，双数时舍去，即保持最后一位是双数。

本题就请你写程序按照要求处理给定浮点数的舍入问题。

输入格式：

输入第一行给出两个不超过 100 的正整数 N 和 D，分别是待处理数字的个数和要求保留的小数点后的有效位数。随后 N 行，每行给出一个待处理数字的信息，格式如下：

指令符数字

其中指令符是表示舍入方法的一位数字，1 表示“四舍五入”，2 表示“截断”，3 表示“四舍六入五成双”；数字是一个总长度不超过 200 位的浮点数，且不以小数点开头或结尾，即 0.123 不会写成 .123，123 也不会写成 123.。此外，输入保证没有不必要的正负号（例如 -0.0 或 +1）。

输出格式：

对每个待处理数字，在一行中输出根据指令符处理后的结果数字。

输入样例：

7 3
1 3.1415926
2 3.1415926
3 3.1415926
3 3.14150
3 3.14250
3 3.14251
1 3.14

输出样例：

3.142
3.141
3.142
3.142
3.142
3.143
3.140

分析：Z存储操作数，I表示小数点的下标，jin存储是否需要进位，now存储现在位数的数值，fu表示刚开始这个数是否有负号，fl表示输出的有效位内是否有非零数。
刚开始判断一下第一位是不是负号，是的话先存一下，因为如果最后全部是0的情况，不用输出负号(如D = 3, s = -0.0000001时0.000)。
记录一下小数点的位置，如果是个整数就没有小数点，可以自己手动补充一个，因为D是正整数。同时，我们可以在原来的数后面加几个零，方便后续的运算。
如果操作数是1，可以在有效位后1位上加5表示进位，如果操作数是2则不用操作，如果操作为是3，按照题目要求进行模拟。
最后按照大数加法（高精加）的计算方式将数字更新一下，如果前面还有进位就加一个1在左边。在fu和fl都位1的情况下，提早输出一个负号。

#include <iostream>
using namespace std;
int N, D, Z, I, jin, now, fu, fl;
string s, zero(200, '0');
int main() {
    cin >> N >> D;
    while (N--) {
        I = jin = fu = fl = 0;
        cin >> Z >> s;
        if (s[0] == '-') {
            fu = 1;
            s.erase(0, 1);
        }
        while (I < s.size() && s[I] != '.') ++I;
        if (I == s.size()) s = s + '.';
        s = s + zero;
        if (Z != 2) {
            if (Z == 1) s[I + D + 1] += 5;
            else {
                if (s[I + D + 1] >= '6') s[I + D]++;
                else if (s[I + D + 1] == '5') {
                    int flag = 0;
                    for (int i = I + D + 2; i < s.size(); i++) {
                        if(s[i] != '0') {
                            s[I + D]++;
                            flag = 1;
                            break;
                        }
                    }
                    if (flag == 0 && s[I + D] & 1) ++s[I + D];
                }
            }
            for (int i = I + D + 1; i >= 0; i--) {
                if (s[i] == '.') continue;
                now = s[i] - '0' + jin;
                s[i] = '0' + now % 10;
                jin = now / 10;
            }
        }
        if (jin) s = '1' + s, I++;
        if (fu) {
            for (int i = 0; i <= I + D; i++) {
                if (s[i] != '0' && s[i] != '.') fl = 1;
            }
        }
        if (fu && fl) cout << '-';
        cout << s.substr(0, I + D + 1) << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int N, D, Z, I, jin, now, fu, fl;

string s, zero(200, '0');

int main() {

cin >> N >> D;

while (N--) {

I = jin = fu = fl = 0;

cin >> Z >> s;

if (s[0] == '-') {

fu = 1;

s.erase(0, 1);

}

while (I < s.size() && s[I] != '.') ++I;

if (I == s.size()) s = s + '.';

s = s + zero;

if (Z != 2) {

if (Z == 1) s[I + D + 1] += 5;

else {

if (s[I + D + 1] >= '6') s[I + D]++;

else if (s[I + D + 1] == '5') {

int flag = 0;

for (int i = I + D + 2; i < s.size(); i++) {

if(s[i] != '0') {

s[I + D]++;

flag = 1;

break;

}

if (flag == 0 && s[I + D] & 1) ++s[I + D];

}

for (int i = I + D + 1; i >= 0; i--) {

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

now = s[i] - '0' + jin;

s[i] = '0' + now % 10;

jin = now / 10;

}

if (jin) s = '1' + s, I++;

if (fu) {

for (int i = 0; i <= I + D; i++) {

if (s[i] != '0' && s[i] != '.') fl = 1;

}

if (fu && fl) cout << '-';

cout << s.substr(0, I + D + 1) << "\n";

}

return 0;

}

1122 找奇葩 – PAT乙级真题

在一个长度为 n 的正整数序列中，所有的奇数都出现了偶数次，只有一个奇葩奇数出现了奇数次。你的任务就是找出这个奇葩。

输入格式：

输入首先在第一行给出一个正整数 n（≤10^4），随后一行给出 n 个满足题面描述的正整数。每个数值不超过 10^5，数字间以空格分隔。

输出格式：

在一行中输出那个奇葩数。题目保证这个奇葩是存在的。

输入样例：

12
23 16 87 233 87 16 87 233 23 87 233 16

输出样例：

233

分析：把每个数字当成下标存，出现一次就在tong里加1。最后数组里的数字就是对应下标出现了多少次，看一下哪一个奇数出现奇数次。

#include <iostream>
using namespace std;
int n, num, tong[100001]; 
int main() {
    cin >> n;
    while (n--) {
        cin >> num;
        tong[num]++;
    }
    for (int i = 1; i < 100000; i += 2) {
        if(tong[i] & 1) cout << i;
    }
    return 0; 
}

#include <iostream>

using namespace std;

int n, num, tong[100001];

int main() {

cin >> n;

while (n--) {

cin >> num;

tong[num]++;

}

for (int i = 1; i < 100000; i += 2) {

if(tong[i] & 1) cout << i;

}

return 0;

}

1121 祖传好运 – PAT乙级真题

我们首先定义 0 到 9 都是好运数，然后从某个好运数开始，持续在其右边添加数字，形成新的数字。我们称一个大于 9 的数字 N 具有祖传好运，如果它是由某个好运数添加了一个个位数字得到的，并且它能被自己的位数整除。

例如 123 就是一个祖传好运数。首先因为 1 是一个好运数的老祖宗，添加了 2 以后，形成的 12 能被其位数 2 （即 12 是一个 2 位数）整除，所以 12 是一个祖传好运数；在 12 后面添加了 3 以后，形成的 123 能被其位数 3 整除，所以 123 是一个祖传好运数。

本题就请你判断一个给定的正整数 N 是不是具有祖传的好运。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 K (≤1000)；第 2 行给出 K 个不超过 10^9 的待评测的正整数，注意这些数字都保证没有多余的前导零。

输出格式：

对每个待评测的数字，在一行中输出 Yes 如果它是一个祖传好运数，如果不是则输出 No。

输入样例：

5
123 7 43 2333 56160

输出样例：

Yes
Yes
No
No
Yes

分析：num存储每一个需要判断的数字，good用来标记该数字是否为祖传好运数。
由于需要保证任意一个位置作为结尾都是祖传好运数，所以可以先按当前的数字进行判断，然后移除最后一位（num /= 10）而不需要按照题目说的从最左边一位开始看（方便编码）。
类似从右到左分解各个位数，循环查看当前数字能否整除位数，位数这里我们将数字转换成string再用size()函数比较方便。不能整除就做好标记跳出循环，最后查看标记输出对应的答案

#include <iostream>
using namespace std;
int main() {
    int K, num, good;
    cin >> K;
    while (K--) {
        cin >> num;
        good = 1;
        while (num) {
            if (num % to_string(num).size() != 0) {
                good = 0;
                break;
            }
            num /= 10;
        }
        if (good) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0; 
}

#include <iostream>

using namespace std;

int main() {

int K, num, good;

cin >> K;

while (K--) {

cin >> num;

good = 1;

while (num) {

if (num % to_string(num).size() != 0) {

good = 0;

break;

}

num /= 10;

}

if (good) cout << "Yes\n";

else cout << "No\n";

}

return 0;

}

1175 Professional Ability Test – PAT甲级真题

Professional Ability Test (PAT) consists of several series of subject tests. Each test is divided into several levels. Level A is a prerequisite (前置要求) of Level B if one must pass Level A with a score no less than S in order to be qualified to take Level B. At the mean time, one who passes Level A with a score no less than S will receive a voucher（代金券）of D yuans (Chinese dollar) for taking Level B.

At the moment, this PAT is only in design and hence people would make up different plans. A plan is NOT consistent if there exists some test T so that T is a prerequisite of itself. Your job is to test each plan and tell if it is a consistent one, and at the mean time, find the easiest way (with minimum total S) to obtain the certificate of any subject test. If the easiest way is not unique, find the one that one can win the maximum total value of vouchers.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤1000) and M, being the total numbers of tests and prerequisite relations, respectively. Then M lines follow, each describes a prerequisite relation in the following format:

T1 T2 S D

where T1 and T2 are the indices (from 0 to N−1) of the two distinct tests; S is the minimum score (in the range (0, 100]) required to pass T1 in order to be qualified to take T2; and D is the value of the voucher (in the range (0, 500]) one can receive if one passes T1 with a score no less than S and plan to take T2. It is guaranteed that at most one pair of S and D are defined for a prerequisite relation.

Then another positive integer K (≤N) is given, followed by K queries of tests. All the numbers in a line are separated by spaces.

Output Specification:

Print in the first line Okay. if the whole plan is consistent, or Impossible. if not.

If the plan is consistent, for each query of test T, print in a line the easiest way to obtain the certificate of this test, in the format:

T0->T1->…->T

However, if T is the first level of some subject test (with no prerequisite), print You may take test T directly. instead.

If the plan is impossible, for each query of test T, check if one can take it directly or not. If the answer is yes, print in a line You may take test T directly.; or print Error. instead.

Sample Input 1:

8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7

Sample Output 1:

Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7

Sample Input 2:

4 5
0 1 1 10
1 2 2 10
3 0 4 10
3 2 5 10
2 0 3 10
2
3 1

Sample Output 2:

Impossible.
You may take test 3 directly.
Error.

题目大意：PAT由一系列学科测试组成。每个测试被划分为几个级别。如果要资格参加 Level B，那么必须以不低于 S 的分数通过 Level A，Level A 就成为 Level B 的前置要求。同时，以不低于 S 的分数通过 Level A 的人将获得一张代金券，用于参加 Level B。目前，这个PAT仅处于设计阶段，因此人们可以制定不同的计划。如果存在某个测试 T，使得 T 是其自身的前提条件，那么该计划就不一致。您的任务是测试每个计划，并判断它是否一致，并同时找出获得任何学科测试证书的最简单方法（具有最小总分S）。如果最简单的方法不唯一，找出一个可以获得最大代金券总额的方法。

分析：node结构用来存储最短路中的结点信息，其中重载了小于号(<)的运算规则，让优先队列能以题目要求的顺序排列。bian是用来存储边信息的结构体。E是存储边信息的邻接表，Dis中存储最短路的距离，存的是从源点到第i个点所要考的最少分数和可以获得的最多的代金券。f用来标记是否有环，为1时表示有环，对应题目中说明的，某个课程是自己的前置课程。in和in2都用来存储每个结点的入度，Last数组存储最短路中每个结点的前一个结点是什么。
首先，我们可以用构造拓扑排序的方法判断一下图中是否存在环。可以使用bfs，将当前入度为0的结点存在队列里，取出后将其所有能到达的结点的入度减1，最后看一下能让入度为0的结点有多少，每次把他们存在S中，最后看S的大小和N之间的关系，如果全部都能拿到，则说明无环。
先建立一个初始点，这里用1002当初始点，然后把入度为0的结点和这个初始点连接上。这样只要使用1002当作起点，然后用Dijkstra计算最短的路径，和对应的每个结点上一步的结点是什么。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int v, score, voucher;
    bool operator < (const node &x) const {
        if(score != x.score) return score > x.score;
        else return voucher < x.voucher;
    }
};
struct bian {
    int next, S, D;
};
vector<bian> E[1005];
vector<pair<int,int>> Dis(1005, {2e9, -1});
int N, M, T1, T2, S, D, f, T, in[1005], in2[1005], Last[1005];
queue<int> DAG;
int huan() {
    vector<int> S;
    while(DAG.size()) {
        int now = DAG.front();
        DAG.pop();
        S.push_back(now);
        for(auto it : E[now]) {
            in2[it.next]--;
            if(!in2[it.next]) DAG.push(it.next);
        }
    }
    return S.size() == N;
}
void dijkstra() {
    vector<int> vis(1005);
    priority_queue<node> Q;
    Q.push({1002, 0, 0});
    Dis[1002].first = Dis[1002].second = 0;
    while(Q.size()) {
        node now = Q.top();
        Q.pop();
        if(vis[now.v]) continue;
        vis[now.v] = 1;
        Dis[now.v].first = now.score;
        Dis[now.v].second = now.voucher;
        for (auto it : E[now.v]) {
            if(vis[it.next]) continue;
            if((Dis[it.next].first > Dis[now.v].first + it.S) || ((Dis[it.next].first == Dis[now.v].first + it.S) && (Dis[it.next].second < Dis[now.v].second + it.D))) {
                Dis[it.next].first = Dis[now.v].first + it.S;
                Dis[it.next].second = Dis[now.v].second + it.D;
                Last[it.next] = now.v;
                Q.push({it.next, Dis[it.next].first, Dis[it.next].second});
            }
        }
    }
    return;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> T1 >> T2 >> S >> D;
        E[T1].push_back({T2, S, D});
        in[T2]++, in2[T2]++;
    }
    for (int i = 0; i < N; i++) {
        if (in[i] == 0) {
            E[1002].push_back({i, 0, 0});
            DAG.push(i);
        }
    }
    f = huan();
    dijkstra();
    cin >> T;
    if(f) cout << "Okay.\n";
    else cout << "Impossible.\n";
    for (int i = 1, q; i <= T; i++) {
        cin >> q;
        if(!in[q]) cout << "You may take test " << q << " directly.\n";
        else if(!f) cout << "Error.\n";
        else {
            vector<int> path;
            int now = q;
            while(q != 1002) {
                path.push_back(q);
                q = Last[q];
            }
            for (int j = path.size() - 1; j >= 0; j--) {
                cout << path[j];
                if(j) cout << "->";
            }
            cout << '\n';
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

struct node {

int v, score, voucher;

bool operator < (const node &x) const {

if(score != x.score) return score > x.score;

else return voucher < x.voucher;

}

};

struct bian {

int next, S, D;

};

vector<bian> E[1005];

vector<pair<int,int>> Dis(1005, {2e9, -1});

int N, M, T1, T2, S, D, f, T, in[1005], in2[1005], Last[1005];

queue<int> DAG;

int huan() {

vector<int> S;

while(DAG.size()) {

int now = DAG.front();

DAG.pop();

S.push_back(now);

for(auto it : E[now]) {

in2[it.next]--;

if(!in2[it.next]) DAG.push(it.next);

}

return S.size() == N;

}

void dijkstra() {

vector<int> vis(1005);

priority_queue<node> Q;

Q.push({1002, 0, 0});

Dis[1002].first = Dis[1002].second = 0;

while(Q.size()) {

node now = Q.top();

Q.pop();

if(vis[now.v]) continue;

vis[now.v] = 1;

Dis[now.v].first = now.score;

Dis[now.v].second = now.voucher;

for (auto it : E[now.v]) {

if(vis[it.next]) continue;

if((Dis[it.next].first > Dis[now.v].first + it.S) || ((Dis[it.next].first == Dis[now.v].first + it.S) && (Dis[it.next].second < Dis[now.v].second + it.D))) {

Dis[it.next].first = Dis[now.v].first + it.S;

Dis[it.next].second = Dis[now.v].second + it.D;

Last[it.next] = now.v;

Q.push({it.next, Dis[it.next].first, Dis[it.next].second});

}

return;

}

int main() {

cin >> N >> M;

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

cin >> T1 >> T2 >> S >> D;

E[T1].push_back({T2, S, D});

in[T2]++, in2[T2]++;

}

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

if (in[i] == 0) {

E[1002].push_back({i, 0, 0});

DAG.push(i);

}

f = huan();

dijkstra();

cin >> T;

if(f) cout << "Okay.\n";

else cout << "Impossible.\n";

for (int i = 1, q; i <= T; i++) {

cin >> q;

if(!in[q]) cout << "You may take test " << q << " directly.\n";

else if(!f) cout << "Error.\n";

else {

vector<int> path;

int now = q;

while(q != 1002) {

path.push_back(q);

q = Last[q];

}

for (int j = path.size() - 1; j >= 0; j--) {

cout << path[j];

if(j) cout << "->";

}

cout << '\n';

}

return 0;

}

1174 Left-View of Binary Tree – PAT甲级真题

The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is { 1, 2, 3, 4, 5 }

Given the inorder and preorder traversal sequences of a binary tree, you are supposed to output its left-view.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20), which is the total number of nodes in the tree. Then given in the following 2 lines are the inorder and preorder traversal sequences of the tree, respectively. All the keys in the tree are distinct positive integers in the range of int.

Output Specification:

For each case, print in a line the left-view of the tree. All the numbers in a line are separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

8
2 3 1 5 4 7 8 6
1 2 3 6 7 4 5 8

Sample Output:

1 2 3 4 5

题目大意：二叉树的左视图是通过从左侧向右上方查看树而获得的结点列表。例如，给定如图所示的树，其左视图为{1,2,3,4,5}。给定二叉树的中序遍历和前序遍历序列，输出其左视图。

分析：pre与in数组分别存储前序和中序遍历的结果，t存储某一层最左边的结点值，ins、ine分别表示当前操作在中序遍历数组中的起始位置与终止位置，prerootindex表示当前的子树根结点在前缀序列中的位置，level表示现在处于第几层，pos表示当前子树根结点在中序遍历数组中的位置。用前序和中序遍历的序列可以唯一确定一棵树。由于是从左到右的顺序遍历树的，所以每次判断当前层的t数组中没有元素（值为0）的时候，就表示这一层最左边的结点是现在这一个。

#include <iostream>
using namespace std;
int N, pre[30], in[30], t[30];
void deal(int ins, int ine, int prerootindex, int level) {
    if (ins > ine) return;
    if (t[level] == 0) {
        t[level] = pre[prerootindex];
    }
    int pos = ins;
    while(in[pos] != pre[prerootindex]) ++pos;
    deal(ins, pos - 1, prerootindex + 1, level + 1);
    deal(pos + 1, ine, prerootindex + 1 + pos - ins, level + 1);
}
int main(){
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> in[i];
    for (int i = 1; i <= N; i++) cin >> pre[i];
    deal(1, N, 1, 1);
    for (int i = 1; t[i]; i++) {
        if (i != 1) cout << ' ';
        cout << t[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int N, pre[30], in[30], t[30];

void deal(int ins, int ine, int prerootindex, int level) {

if (ins > ine) return;

if (t[level] == 0) {

t[level] = pre[prerootindex];

}

int pos = ins;

while(in[pos] != pre[prerootindex]) ++pos;

deal(ins, pos - 1, prerootindex + 1, level + 1);

deal(pos + 1, ine, prerootindex + 1 + pos - ins, level + 1);

}

int main(){

cin >> N;

for (int i = 1; i <= N; i++) cin >> in[i];

for (int i = 1; i <= N; i++) cin >> pre[i];

deal(1, N, 1, 1);

for (int i = 1; t[i]; i++) {

if (i != 1) cout << ' ';

cout << t[i];

}

return 0;

}

1173 How Many Ways to Buy a Piece of Land – PAT甲级真题

The land is for sale in CyberCity, and is divided into several pieces. Here it is assumed that each piece of land has exactly two neighboring pieces, except the first and the last that have only one. One can buy several contiguous（连续的） pieces at a time. Now given the list of prices of the land pieces, your job is to tell a customer in how many different ways that he/she can buy with a certain amount of money.

Input Specification:

Each input file contains one test case. Each case first gives in a line two positive integers: N (≤10^4), the number of pieces of the land (hence the land pieces are numbered from 1 to N in order), and M (≤10^9), the amount of money that your customer has.

Then in the next line, N positive integers are given, where the i-th one is the price of the i-th piece of the land.

It is guaranteed that the total price of the land is no more than 10^9.

Output Specification:

For each test case, print the number of different ways that your customer can buy. Notice that the pieces must be contiguous.

Sample Input:

5 85
38 42 15 24 9

Sample Output:

Hint:

The 11 different ways are:

38
42
15
24
9
38 42
42 15
42 15 24
15 24
15 24 9
24 9

题目大意：数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。

分析：使用pre数组保存土地价格前缀和，pre[i]表示从第一个土地到第i个土地的总价。在计算从第j个房子到第i个土地的总价的时候，只需要计算pre[i]-pre[j-1]即可。两个for循环，枚举所有i与j的值，然后计算出可以购买的方案数量即可。喵喵喵~

#include <iostream>
using namespace std;
int N, M, ans, a, pre[10005];
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> a;
        pre[i] = pre[i - 1] + a;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            if (pre[j] - pre[i - 1] <= M) ++ans;
            else break;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int N, M, ans, a, pre[10005];

int main(){

cin >> N >> M;

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

cin >> a;

pre[i] = pre[i - 1] + a;

}

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

for (int j = i; j <= N; j++) {

if (pre[j] - pre[i - 1] <= M) ++ans;

else break;

}

cout << ans;

return 0;

}