liuchuo – 第6页 – 柳婼の blog

L2-045 堆宝塔-PAT团体程序设计天梯赛GPLT

堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小，按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下：

首先准备两根柱子，一根 A 柱串宝塔，一根 B 柱用于临时叠放。
把第 1 块彩虹圈作为第 1 座宝塔的基座，在 A 柱放好。
将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下，如果比最上面的小，就直接放上去；否则把 C 跟 B 柱最上面的彩虹圈比一下：
- 如果 B 柱是空的、或者 C 大，就在 B 柱上放好；
- 否则把 A 柱上串好的宝塔取下来作为一件成品；然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上，最后把 C 也放到 A 柱上。

重复此步骤，直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品，B 柱上剩下的彩虹圈被逐一取下，堆成另一座宝塔。问：宝宝一共堆出了几个宝塔？最高的宝塔有多少层？

输入格式：

输入第一行给出一个正整数 N（≤10^3），为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数，对应每个彩虹圈的直径。

输出格式：

在一行中输出宝宝堆出的宝塔个数，和最高的宝塔的层数。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

11
10 8 9 5 12 11 4 3 1 9 15

输出样例：

4 5

样例解释：

宝宝堆成的宝塔顺次为：

10、8、5
12、11、4、3、1
9
15、9

分析：A、B数组分别代表A柱和B柱，a、b分别表示A柱、B柱最上面的一个彩虹圈放在哪个位置。我们把当前抓到的彩虹圈的大小记为c。num存储一共有几个宝塔，mt表示最高的塔多高。
如果当前A柱没有彩虹圈或者新抓的彩虹圈比A柱最少面的小，就放在A柱最上面。如果当前B柱没有彩虹圈或者新抓的彩虹圈比B柱最少面的大，就放在B柱最上面。不然就让A柱清空，这里让a直接变成0就可以，顺便看一下现在的a是不是最大的高度，让数量num+1。把B中所有的比c大的彩虹圈，拿到A柱上。结束之后，如果B柱上还有彩虹圈，则宝塔数量加1，最后num还要+1因为现在的A柱还能拿下一个宝塔。

#include <iostream>
using namespace std;
int N, A[1005], B[1005], a, b, c, num, mt;
int main() {
    cin >> N;
    while (N--) {
        cin >> c;
        if (a == 0 || A[a] > c) {
            A[++a] = c;
        } else if (b == 0 || B[b] < c) {
            B[++b] = c;
        } else {
            mt = max(mt, a);
            a = 0;
            num++;
            while (b && B[b] > c) {
                A[++a] = B[b--];
            }
            A[++a] = c;
        }
    }
    mt = max(mt, a);
    if (b) ++num;
    cout << num + 1 << ' ' << mt;
    return 0;
}

#include <iostream>

using namespace std;

int N, A[1005], B[1005], a, b, c, num, mt;

int main() {

cin >> N;

while (N--) {

cin >> c;

if (a == 0 || A[a] > c) {

A[++a] = c;

} else if (b == 0 || B[b] < c) {

B[++b] = c;

} else {

mt = max(mt, a);

a = 0;

num++;

while (b && B[b] > c) {

A[++a] = B[b--];

}

A[++a] = c;

}

mt = max(mt, a);

if (b) ++num;

cout << num + 1 << ' ' << mt;

return 0;

}

L2-044 大众情人-PAT团体程序设计天梯赛GPLT

人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。

一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 Dij；将 i 的“异性缘”定义为 1/maxj∈S(i){Dij}，其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。

本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。

输入格式：

输入在第一行中给出一个正整数 N（≤500），为总人数。于是我们默认所有人从 1 到 N 编号。

随后 N 行，第 i 行描述了编号为 i 的人与其他人的关系，格式为：

性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K

其中 性别 是这个人的性别，F 表示女性，M 表示男性；K（<N 的非负整数）为这个人直接认识的朋友数；随后给出的是这 K 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 10^6 的正整数。

题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。

输出格式：

第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。

输入样例：

6
F 1 4:1
F 2 1:3 4:10
F 2 4:2 2:2
M 2 5:1 3:2
M 2 2:2 6:2
M 2 3:1 2:5

输出样例：

2 3
4

分析：Dis中存储两个人之间的距离，Nan中存储男人的编号，Nv中存储女人的编号，M_Ans与F_Ans分别存储各个异性缘倒数的人，那么最小的那个就是异性缘最大的人了。中间使用Floyd计算两个点的最短路径。然后再遍历计算每个人的异性缘即可。^_^

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
int N, Dis[501][501];
char c;
vector<int> Nan, Nv;
map<int, set<int> > M_Ans, F_Ans;
void findlover(vector<int> &Find, vector<int> &Base, map<int, set<int> > &Target, int mark = 0) {
    for (int i = 0, score = 0; i < (int)Find.size(); i++, score = 0) {
        for (int j = 0; j < (int)Base.size(); j++) score = max(score, Dis[Base[j]][Find[i]]);
        Target[score].insert(Find[i]);
    }
    for (auto ite : Target.begin()->second) {
        if (mark++) cout << ' ';
        cout << ite;
    }
}
int main() {
    cin >> N;
    fill (Dis[0], Dis[0] + 501 * 501, 1e9);
    for (int i = 1, K, fri, dis; i <= N; i++) {
        cin >> c >> K;
        if (c == 'F') Nv.push_back(i);
        else Nan.push_back(i);
        for (int j = 0; j < K; ++j) {
            cin >> fri >> c >> dis;
            Dis[i][fri] = dis;
        }
    }
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                Dis[i][j] = min(Dis[i][j], Dis[i][k] + Dis[k][j]);
    findlover(Nv, Nan, F_Ans);
    cout << '\n';
    findlover(Nan, Nv, M_Ans);
    return 0;
}

#include <iostream>

#include <vector>

#include <map>

#include <set>

using namespace std;

int N, Dis[501][501];

char c;

vector<int> Nan, Nv;

map<int, set<int> > M_Ans, F_Ans;

void findlover(vector<int> &Find, vector<int> &Base, map<int, set<int> > &Target, int mark = 0) {

for (int i = 0, score = 0; i < (int)Find.size(); i++, score = 0) {

for (int j = 0; j < (int)Base.size(); j++) score = max(score, Dis[Base[j]][Find[i]]);

Target[score].insert(Find[i]);

}

for (auto ite : Target.begin()->second) {

if (mark++) cout << ' ';

cout << ite;

}

int main() {

cin >> N;

fill (Dis[0], Dis[0] + 501 * 501, 1e9);

for (int i = 1, K, fri, dis; i <= N; i++) {

cin >> c >> K;

if (c == 'F') Nv.push_back(i);

else Nan.push_back(i);

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

cin >> fri >> c >> dis;

Dis[i][fri] = dis;

}

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

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

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

Dis[i][j] = min(Dis[i][j], Dis[i][k] + Dis[k][j]);

findlover(Nv, Nan, F_Ans);

cout << '\n';

findlover(Nan, Nv, M_Ans);

return 0;

}

L2-043 龙龙送外卖-PAT团体程序设计天梯赛GPLT

龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。

每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……

看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。

输入格式:

输入第一行是两个数 N 和 M (2≤N≤10^5, 1≤M≤10^5)，分别对应树上节点的个数（包括外卖站），以及新增的送餐地址的个数。

接下来首先是一行 N 个数，第 i 个数表示第 i 个点的双亲节点的编号。节点编号从 1 到 N，外卖站的双亲编号定义为 −1。

接下来有 M 行，每行给出一个新增的送餐地点的编号 Xi。保证送餐地点中不会有外卖站，但地点有可能会重复。

为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 1，且从外卖站出发可以访问到所有地点。

注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。

输出格式:

对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。

输入样例:

7 4
-1 1 1 1 2 2 3
5
6
2
4

输出样例:

2
4
4
6

分析：Parent中存储双亲结点，mark标记某个点是否走过，Distance中存储某个店铺到岛外卖战（根结点）的距离。由于在外送不同岔路时，需要回到交叉路口再向目标出发，对最优配送来说，等于每条路径走2遍，并减去最长的那条路（最后不用回来）。对距离来说，需要找到未走过的距离外卖战最近的那个点，减去当前添加的配送点到那个店的距离就是添加的路径长度。

#include <iostream>
#include <queue>
using namespace std;
int N, M, Parent_num, new_address, passed_close_to_root, Round, Longest_path, Parent[100001], mark[100001], Distance[100001];
vector<int> Child[100001];
queue<pair<int, int> > Q;
int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> Parent_num;
        if (Parent_num < 0) Parent[0] = i;
        else Child[Parent_num].push_back(i);
        Parent[i] = Parent_num;
    }
    mark[Parent[0]] = 1;
    Q.push({Parent[0], 0});
    while(!Q.empty()) {
        int id = Q.front().first, deep = Q.front().second;
        Q.pop();
        Distance[id] = deep;
        for (auto ite : Child[id]) Q.push({ite, deep + 1});
    }
    for (int i = 0; i < M; i++) {
        cin >> new_address;
        passed_close_to_root = new_address;
        while(!mark[passed_close_to_root]) {
            mark[passed_close_to_root] = 1;
            passed_close_to_root = Parent[passed_close_to_root];
        }
        Round += Distance[new_address] - Distance[passed_close_to_root];
        Longest_path = max(Longest_path, Distance[new_address]);
        cout << Round * 2 - Longest_path * 1 << '\n'; 
    } 
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int N, M, Parent_num, new_address, passed_close_to_root, Round, Longest_path, Parent[100001], mark[100001], Distance[100001];

vector<int> Child[100001];

queue<pair<int, int> > Q;

int main() {

cin >> N >> M;

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

cin >> Parent_num;

if (Parent_num < 0) Parent[0] = i;

else Child[Parent_num].push_back(i);

Parent[i] = Parent_num;

}

mark[Parent[0]] = 1;

Q.push({Parent[0], 0});

while(!Q.empty()) {

int id = Q.front().first, deep = Q.front().second;

Q.pop();

Distance[id] = deep;

for (auto ite : Child[id]) Q.push({ite, deep + 1});

}

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

cin >> new_address;

passed_close_to_root = new_address;

while(!mark[passed_close_to_root]) {

mark[passed_close_to_root] = 1;

passed_close_to_root = Parent[passed_close_to_root];

}

Round += Distance[new_address] - Distance[passed_close_to_root];

Longest_path = max(Longest_path, Distance[new_address]);

cout << Round * 2 - Longest_path * 1 << '\n';

}

return 0;

}

L2-042 老板的作息表-PAT团体程序设计天梯赛GPLT

新浪微博上有人发了某老板的作息时间表，表示其每天 4:30 就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？

本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。

输入格式：

输入第一行给出一个正整数 N，为作息表上列出的时间段的个数。随后 N 行，每行给出一个时间段，格式为：

hh:mm:ss – hh:mm:ss

其中 hh、mm、ss 分别是两位数表示的小时、分钟、秒。第一个时间是开始时间，第二个是结束时间。题目保证所有时间都在一天之内（即从 00:00:00 到 23:59:59）；每个区间间隔至少 1 秒；并且任意两个给出的时间区间最多只在一个端点有重合，没有区间重叠的情况。

输出格式：

按照时间顺序列出时间表中没有出现的区间，每个区间占一行，格式与输入相同。题目保证至少存在一个区间需要输出。

输入样例：

8
13:00:00 – 18:00:00
00:00:00 – 01:00:05
08:00:00 – 09:00:00
07:10:59 – 08:00:00
01:00:05 – 04:30:00
06:30:00 – 07:10:58
05:30:00 – 06:30:00
18:00:00 – 19:00:00

输出样例：

04:30:00 – 05:30:00
07:10:58 – 07:10:59
09:00:00 – 13:00:00
19:00:00 – 23:59:59

分析：用set存储工作时间表，可自动对工作时间表进行排序，记录在在record中。遍历工作时间表，检查下一次工作开始时间是否大于上一次的工作结束时间，是的话就输出中间间隔时间。

#include <iostream>
#include <set>
using namespace std;
set<pair<string, string> > record;
string work_start_time, work_end_time, last_start = "00:00:00";
int main() {
    cin >> work_start_time;
    while (cin >> work_start_time >> work_end_time >> work_end_time) record.insert({work_start_time, work_end_time});
    record.insert({"23:59:59", ""});
    for (auto ite : record) {
        if (last_start < ite.first) cout << last_start << " - " << ite.first << '\n';
        last_start = ite.second;
    }
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

set<pair<string, string> > record;

string work_start_time, work_end_time, last_start = "00:00:00";

int main() {

cin >> work_start_time;

while (cin >> work_start_time >> work_end_time >> work_end_time) record.insert({work_start_time, work_end_time});

record.insert({"23:59:59", ""});

for (auto ite : record) {

if (last_start < ite.first) cout << last_start << " - " << ite.first << '\n';

last_start = ite.second;

}

return 0;

}

L2-041 插松枝-PAT团体程序设计天梯赛GPLT

人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：

每人手边有一只小盒子，初始状态为空。
每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：

（1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。

（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。

（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。

现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。

输入格式：

输入在第一行中给出 3 个正整数：N（≤10^3），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。

随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。

输出格式：

每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8 3 4
20 25 15 18 20 18 8 5

输出样例：

20 15
20 18 18 8
25 5

分析：tui表示推送器上的松针，he表示盒子，temp为现在正在插的松枝。整体就是一个模拟题，依照题目条件依次模拟即可

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int N, M, K, tui;
stack<int> he;
vector<int> temp;
void outprint() {
    for (int i = 0; i < temp.size(); i++) {
        if (i) cout << ' ';
            cout << temp[i];
        }
    cout << '\n';
    temp.clear();
}
int main() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        cin >> tui;
        tuihaimeiyong:
        while (!he.empty()) {
            if (temp.empty() || he.top() <= temp.back()) {
                temp.push_back(he.top());
                he.pop();
            }
            else break;
            if (temp.size() == K) outprint();
        }
        if (temp.empty() || tui <= temp.back()) temp.push_back(tui);
        else if(he.size() < M) he.push(tui);
        else {
            outprint();
            goto tuihaimeiyong;
        }
        if (temp.size() == K) outprint();
    }
    while(!he.empty()) {
        if (temp.empty() || he.top() <= temp.back()) {
            temp.push_back(he.top());
            he.pop();
        }
        else outprint();
        if (temp.size() == K) outprint();
    }
    for (int j = 0; j < temp.size(); j++) {
        if (j) cout << ' ';
        cout << temp[j];
    }
    return 0;
}

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

int N, M, K, tui;

stack<int> he;

vector<int> temp;

void outprint() {

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

if (i) cout << ' ';

cout << temp[i];

}

cout << '\n';

temp.clear();

}

int main() {

cin >> N >> M >> K;

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

cin >> tui;

tuihaimeiyong:

while (!he.empty()) {

if (temp.empty() || he.top() <= temp.back()) {

temp.push_back(he.top());

he.pop();

}

else break;

if (temp.size() == K) outprint();

}

if (temp.empty() || tui <= temp.back()) temp.push_back(tui);

else if(he.size() < M) he.push(tui);

else {

outprint();

goto tuihaimeiyong;

}

if (temp.size() == K) outprint();

}

while(!he.empty()) {

if (temp.empty() || he.top() <= temp.back()) {

temp.push_back(he.top());

he.pop();

}

else outprint();

if (temp.size() == K) outprint();

}

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

if (j) cout << ' ';

cout << temp[j];

}

return 0;

}

L1-096 谁管谁叫爹-PAT团体程序设计天梯赛GPLT

《咱俩谁管谁叫爹》是网上一首搞笑饶舌歌曲，来源于东北酒桌上的助兴游戏。现在我们把这个游戏的难度拔高一点，多耗一些智商。
不妨设游戏中的两个人为 A 和 B。游戏开始后，两人同时报出两个整数 NA 和 NB。判断谁是爹的标准如下：

将两个整数的各位数字分别相加，得到两个和 SA 和 SB。如果 NA 正好是 SB 的整数倍，则 A 是爹；如果 NB 正好是 SA 的整数倍，则 B 是爹；
如果两人同时满足、或同时不满足上述判定条件，则原始数字大的那个是爹。
本题就请你写一个自动裁判程序，判定谁是爹。

输入格式：

输入第一行给出一个正整数 N（≤100），为游戏的次数。以下 N 行，每行给出一对不超过 9 位数的正整数，对应 A 和 B 给出的原始数字。题目保证两个数字不相等。

输出格式：

对每一轮游戏，在一行中给出赢得“爹”称号的玩家（A 或 B）。

输入样例：

4
999999999 891
78250 3859
267537 52654299
6666 120

输出样例：

B
A
B
A

分析：使用A、B分别存储数字，a和b分别存储A、B各位相加的和，对于字符要把它转换成int型数字，我们只需要让它-‘0’即可。stoi()函数表示把string转换成数字，然后按照题目的要求写一下判定条件，就完成啦。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N, a, b;
string A, B;
int main() {
    cin >> N;
    while(N--) {
        cin >> A >> B;
        a = b = 0;
        for (auto it : A) {
            a += it - '0';
        }
        for (auto it : B) {
            b += it - '0';
        }
        if (stoi(A) % b == 0 && stoi(B) % a != 0) cout << "A\n";
        else if (stoi(A) % b != 0 && stoi(B) % a == 0) cout << "B\n";
        else if (stoi(A) > stoi(B)) cout << "A\n";
        else cout << "B\n";
    }
    return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int N, a, b;

string A, B;

int main() {

cin >> N;

while(N--) {

cin >> A >> B;

a = b = 0;

for (auto it : A) {

a += it - '0';

}

for (auto it : B) {

b += it - '0';

}

if (stoi(A) % b == 0 && stoi(B) % a != 0) cout << "A\n";

else if (stoi(A) % b != 0 && stoi(B) % a == 0) cout << "B\n";

else if (stoi(A) > stoi(B)) cout << "A\n";

else cout << "B\n";

}

return 0;

}