2022年SCAU计算智能题库

头文件及宏定义

基础

18104 练习使用多case解题

注意事项：

代码实现：

递归和分治 (Recursion and Divide and Conquer)

1142 巡逻的士兵

注意事项：

代码实现：

18441 偷懒的士兵

注意事项：

代码实现：

18442 偷懒的士兵2

注意事项：

代码实现：

19144 偷懒的士兵3

注意事项：

代码实现：

排序和优先队列 (Sorting and Priority Queue)

18105 银行的叫号顺序

注意事项：

代码实现：

18216 银行服务

注意事项：

代码实现：

18107 校赛排名

注意事项：

代码实现：

18290 校赛排名2

注意事项：

代码实现：

暴力枚举 (Brute Force)

18443 除法等式

注意事项：

代码实现：

1079 三角形

注意事项

代码实现：

18444 分数拆分

注意事项：

代码实现：

动态规划 (Dynamic Programming)

19116 丑数

注意事项：

代码实现：

18005 它不是丑数

注意事项：

代码实现：

18308 最长公共子序列

注意事项：

代码实现：

8615 快乐

注意事项：

代码实现：

回溯算法 (BackTracking)

18124 N皇后问题

注意事项：

代码实现：

19010 最小的特殊数字

注意事项：

代码实现：

搜索 (Search)

18276 走迷宫

注意事项：

代码实现：

18440 走迷宫2

注意事项：

代码实现：

实用类数据结构 (Pratical Data Structure)

18130 繁忙的公路

注意事项：

代码实现：

18233 万湖之国的形成

注意事项：

代码实现：

贪心算法 (Greedy)

18118 勇者斗恶龙

注意事项：

代码实现：

——————————————————————————————————–

头文件及宏定义

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0);
typedef long long ll;

基础

18104 练习使用多case解题

时间限制:1000MS 代码长度限制 : 10KB

Description
多CASE的问题在般有3种情形：（1）有一个数字开始表明CASE数目；（2）以特殊标志表示结束；（3）要求处理到最后一行。
现要求你在程序一次运行中，依次处理上述3种情况。

有三批测试数据，第1批测试数据，开头会以一个数字告之该批CASE数量，每一个CASE是两个正整数；
第1批测试数据结束后，紧接着是第2批数据，每一个CASE同样是两个正整数，第2批测试数据以两个0结束；
第2批测试数据结束后，紧接着是第3批数据，每一个CASE也是两个正整数，第3批测试数据一直到数据输入结束；

要求，每一个CASE，输出两数的最小公倍数
第1批测试数据处理完毕时，输出“group 1 done”
第2批测试数据处理完毕时，输出“group 2 done”
第3批测试数据处理完毕时，输出“group 3 done”

输入格式
有三批测试数据，第1批测试数据，开头会以一个数字告之该批CASE数量，每一个CASE是两个正整数(最大2的31次方)；
第1批测试数据结束后，紧接着是第2批数据，每一个CASE同样是两个正整数，第2批测试数据以两个0结束；
第2批测试数据结束后，紧接着是第3批数据，每一个CASE也是两个正整数，第3批测试数据一直到数据输入结束；

输出格式
要求，每一个CASE，输出两数的最小公倍数
第1批测试数据处理完毕时，输出“group 1 done”
第2批测试数据处理完毕时，输出“group 2 done”
第3批测试数据处理完毕时，输出“group 3 done”

输入样例
2
6 10
5 12
8 16
12 18
8 4
0 0
4 5
4 6

输出样例
30
60
group 1 done
16
36
8
group 2 done
20
12
group 3 done

注意事项：

该题注意数据都用long long

代码实现：

ll GCD(ll num1, ll num2) { // 最大公约数ll r; while (num1 % num2) {r = num1 % num2;num1 = num2;num2 = r;}return num2;
}ll LCM(ll num1, ll num2) { // 最小公倍数return ((num1 * num2) / GCD(num1, num2));
}int main() {IOS;ll num1, num2;// 有给定Case的数量ll n; cin >> n;while (n--) {cin >> num1 >> num2;cout << LCM(num1, num2) << endl;}cout << "group 1 done" << endl;// 没有给定Case的数量，但是有输入结束的标志for (;;) {cin >> num1 >> num2;if (num1 == 0 && num2 == 0) {break;}cout << LCM(num1, num2) << endl;}cout << "group 2 done" << endl;// 没有给定Case的数量，读取数据到最后一行while (cin >> num1 >> num2) {cout << LCM(num1, num2) << endl;}cout << "group 3 done" << endl;return 0;
}

递归和分治 (Recursion and Divide and Conquer)

1142 巡逻的士兵

时间限制 : 1000MS 代码长度限制 : 10KB
Description
有N个士兵站成一队列, 现在需要选择几个士兵派去侦察。为了选择合适的士兵, 多次进行如下操作: 如果队列超过三个士兵, 那么去除掉所有站立位置为奇数的士兵,或者是去除掉所有站立位置为偶数的士兵。直到不超过三个战士，他们将被送去侦察。

现要求统计按这样的方法，总共可能有多少种不同的正好三个士兵去侦察的士兵组合方案。

注 : 按上法得到少于三士兵的情况不统计。

1 <= N <= 2的32次方 – 1

输入格式
有多行（可能有上百行，尽量优化代码），每行一个数字N，最后一行是0

输出格式
对每一行的数字N，输出针对N的方案数
直到没有数字

输入样例
10
4
0

输出样例
2
0

注意事项：

该题数据量很大，需要使用备忘录 (memo) 来记录计算过的结果来减少重复计算

代码实现：

constexpr auto MAX = 1000000; // 定义限制
vector<int> memo(MAX, 0); // 备忘录int solve(int n) {if (n < MAX && memo[n] != 0) { // 在备忘录中的计算直接返回之前计算的结果return memo[n];}if (n < 3) { // 最后剩下少于3个士兵的情况不用去巡逻return 0;}if (n == 3) { // 最后剩下刚好3个士兵都要去巡逻，为一个方案return 1;}int res = solve(n / 2) + solve((n + 1) / 2); // 最终的结果是去掉偶数站位的士兵的方案数加上去掉奇数站位的士兵的方案数if (n < MAX) { memo[n] = res;}return res;
}int main() {IOS;int n;while (cin >> n && n) {cout << solve(n) << endl;}return 0;
}

18441 偷懒的士兵

时间限制 : 1000MS 代码长度限制 : 10KB

Description
有N个士兵站成一队列, 现在需要选择几个士兵派去侦察。为了选择合适的士兵, 多次进行如下操作: 如果队列超过三个士兵, 那么去除掉所有站立位置为奇数的士兵,或者是去除掉所有站立位置为偶数的士兵。直到不超过三个战士，他们将被送去侦察。现有一个“聪明”的士兵，经常通过选择站在合适的初始位置，成功避免被选中去侦察。这引起了陈教官的注意。

陈教官希望你编写一个程序，当给定士兵数之后，输出有多少个位置上的士兵是不可能被选中去巡逻的。

注 : 按上法得到少于三士兵的情况不用去巡逻。

1 <= N <= 21亿

输入格式
有多行（可能有上百行，请尽量优化代码），每行一个数字N，最后一行是0

输出格式
对每一行的数字N，不可能被选中去巡逻的位置数
直到没有数字

输入样例
10
6
0

输出样例
4
0

注意事项：

该题数据量很大，需要使用备忘录 (memo) 来记录计算过的结果来减少重复计算

代码实现：

#define MAX 1000000
vector<int> memo(MAX, 0);
int solve(int n) {if (n < MAX && memo[n]) {return memo[n];}if (n < 3) {return 0;}if (n == 3) {return 1;}int res = solve(n / 2) + solve((n + 1) / 2);if (n < MAX) {memo[n] = res;}return res;
}int main() {IOS;int n;while (cin >> n && n) {cout << n - 3 * solve(n) << endl; // 要得到不会选去巡逻的士兵数量，即是所有士兵的数量减去 3 * 士兵去巡逻的方案数（每次巡逻都是3个人，所以乘以3）}return 0;
}

18442 偷懒的士兵2

时间限制 : 1000MS 代码长度限制 : 10KB

注 : 按上法得到少于三士兵的情况不用去巡逻。

1 <= N <= 100000

输入格式
有多行（不多于20行），每行一个数字N，最后一行是0

输出格式
对每一行的数字N，不可能被选中去巡逻的最小位置
直到没有数字

输入样例
9
6
0

输出样例
2
0

注意事项：

无

代码实现：

int solve(int n, int _min, int step) {if (n < 3) { // 此时不用去巡逻，得到的结果即为此时队伍的第一名士兵的编号return _min;}if (n == 3) { // 此时都要去巡逻，无法得到结果，返回INT32_MAX来排除答案return INT32_MAX;}int deleteOdd = solve(n / 2, _min + step, 2 * step); // 删除掉占位为奇数的士兵，此时第一名士兵的编号为之前第一名士兵的编号加上一个跨度int deleteEven = solve((n + 1) / 2, _min, 2 * step); // 删除掉占位为偶数的士兵， 此时第一名的士兵的编号不变return min(deleteOdd, deleteEven); // 取最小
}int main() {IOS;int n;while (cin >> n && n) {int result = solve(n, 1, 1);cout << (result < INT32_MAX ? result : 0) << endl;}return 0;
}

19144 偷懒的士兵3

时间限制 : 1000MS 代码长度限制 : 10KB

注 : 按上法得到少于三士兵的情况不用去巡逻。

1 <= N <= 100000

输入格式
有多行（不多于10000行），每行两个数字，第一个数字是士兵人数，第二个数字是位置编号，最后一行是两个0，表示结束

输出格式
对每一行输入，输出一行结果，能被抽中输出Y，不能抽中输出N
最后一行两个0不需要

输入样例
4 1
5 1
0 0

输出样例
N
Y

注意事项：

无

代码实现：

bool Check(int n, int m) {if (n < 3) {return false;}if (n == 3) {return true;}if (m % 2) { // 如果站位是奇数return Check((n + 1) / 2, (m + 1) / 2); // 去除站位是偶数的士兵}else {return Check(n / 2, m / 2); // 去除站位是奇数的士兵}
}
int main() {IOS;int n, m;while (cin >> n >> m && n && m) {cout << (Check(n, m) ? 'Y' : 'N') << endl;}return 0;
}

排序和优先队列 (Sorting and Priority Queue)

18105 银行的叫号顺序

时间限制 : 8000MS 代码长度限制 : 10KB

Description
银行的叫号过程是一个优先队列的典型应用，假设，银行有4类客户，分别用优先级1，2，3，4表示，级别越高则更优先得到服务，例如，当前有三个人排队，两个1级客户，一个3级客户，则银行叫号时，3级客户将先得到服务，即使另两个1级有客户比他先到。当多个同级的客户将获得服务时，由先到的客户先得到服务。

假设，银行只有一个服务窗口，一次只能服务一个客户，假设该窗口每5分钟服务一个客户，即叫号的时刻分别为0分钟、5分钟、10分钟、…..如果在叫号的时侯，没有客户，银行职员会去喝杯咖啡或上个洗手间，5分钟后再继续叫号。

银行给出一系列客户到来的记录，每条记录包括“客户到来的时”，“客户等级”，“客户姓名”（由一个单词构成），请输出银行服务的客户的顺序。

输入格式
第一数字是客户的数量n（n <= 100000）此后，每一行是一个客户来访信息，包括3个数字，到来的时刻（分钟整点, 最大10的8次方）、等级、姓名（最多20个字母）（已经按到来时刻排序）

输出格式
按服务的先后顺序输出客户的姓名

输入样例
4
0 1 John
3 1 Smith
3 1 Tom
4 2 Flod

输出样例
John
Flod
Smith
Tom

注意事项：

无

代码实现：

int main() {IOS;int arrivalTime, level; string name;priority_queue<pair<int, string>> q; // 排队的队列const int levelIndex = 100000; // 客户等级所占比重的参数值int timeIndex = 99999; // 时间所占的参数值，且随着时间推移，该参数会递减int realTime = 0; // 实时的时间int numberOfClient; cin >> numberOfClient;while (numberOfClient--) {cin >> arrivalTime >> level >> name;for (;;) {if (arrivalTime <= realTime) {q.push(make_pair(level * levelIndex + timeIndex, name));timeIndex--;break;}if (!q.empty()) {cout << q.top().second << endl;q.pop();}realTime += 5;}}while (!q.empty()) {cout << q.top().second << endl;q.pop();}return 0;
}

18216 银行服务

时间限制 : 8000MS 代码长度限制 : 10KB

Description
银行通过叫号来决定服务用户的顺序，假设，银行有4类客户，分别用优先级1，2，3，4表示，级别越高则更优先得到服务，例如，当前有三个人排队，两个1级客户，一个3级客户，则银行叫号时，3级客户将先得到服务，即使另两个1级的客户比他先到。当多个同级的客户将获得服务时，由先到的客户先得到服务。

有一种情况，银行工作到一定时间是要下班的，所以到一定时间，如果后面还有客户，将不再提供服务。

银行给出一系列客户到来的记录，每条记录包括“客户到来的时间”，“客户等级”，“客户姓名”（由一个单词构成），请输出该银行这一轮服务的客户的顺序。

输入格式
第一行两个数字，第一数字是客户的数量n（n <= 100000），第二个数字是银行关门的时间，到这个时间，即关门，该点及之后，不再叫号，但之前已经叫号的客户会继续服务到完结。
此后，每一行是一个客户来访信息，包括3个数字，到来的时刻（分钟整点, 最大10的8次方）、等级、姓名（最多20个字母）（已经按到来时刻排序，注意：同一时刻可能会同时到来多个客户，这时若为同等级的，数据出现得早的稍早得到服务）

输出格式
按服务的先后顺序输出客户的姓名

输入样例
4 12
0 1 John
3 1 Smith
3 1 Tom
4 2 Flod

输出样例
John
Flod
Smith

注意事项：

该题相比上一题只是多了一个时间的限制

代码实现：

int main() {IOS;priority_queue<pair<int, string>> q;const int levelIndex = 100000;int timeIndex = 99999;int arrivalTime, level; string name;int realTime = 0;int numberOfClient, timeLimit; cin >> numberOfClient >> timeLimit;while (numberOfClient--) {cin >> arrivalTime >> level >> name;for (;;) {if (arrivalTime <= realTime) {q.push(make_pair(level * levelIndex + timeIndex, name));timeIndex--;break;}if (!q.empty()) {cout << q.top().second << endl;q.pop();}realTime += 5;}}while (!q.empty()) {if (realTime >= timeLimit) { // 多了一个限制return 0;}cout << q.top().second << endl;q.pop(); realTime += 5;}return 0;
}

18107 校赛排名

时间限制 : 4000MS 代码长度限制 : 10KB

Description
校赛结束了，每一个参赛选手由3个数据项构成（通过题数，用时分钟数，姓名），排名按照通过题数排序通过题数多的排前，同题数的，罚时少的排前。如果题数相同，罚时也相同，而按数据读取的先后排。
给你N个参赛选手的数据，按排序先后，输出姓名

输入格式
第一个数为N，（N <= 500000）
此后，每行一个参赛选手的数据，通过题数，用时分钟数，姓名，前两者为整型数，姓名为字符串（不多于20个字符）

输出格式
姓名排名

输入样例
4
3 5 Jon
5 100 Smith
3 5 Tom
6 95 Hel

输出样例
Hel
Smith
Jon
Tom

提示
由于有500000个数据，输入和输出务必使用scanf和printf

注意事项：

该题重点就是多重比较，写出比较函数进行排序即可

代码实现：

struct candidate {int AC;int time;string name;int id;
};bool cmp(candidate a, candidate b) {if (a.AC != b.AC) {return a.AC > b.AC;}else if (a.time != b.time) {return a.time < b.time;}else {return a.id < b.id;}
}int main() {IOS;vector<candidate> list;int n; cin >> n;for (int i = 1; i <= n; i++) {int AC, time; string name; cin >> AC >> time >> name;list.push_back({ AC, time, name, i });}sort(list.begin(), list.end(), cmp);for (candidate one : list) {cout << one.name << endl;}return 0;
}

18290 校赛排名2

时间限制 : 1000MS 代码长度限制 : 10KB

Description
下面是校赛的排名规则：
比赛期间，提交代码后，系统会返回正确或错误等结果。最后的获胜者为正确解答题目最多，如果同题数则总用时最少的队伍。
每道试题的时间花费将从竞赛开始到试题提交并且被判定为正确为止，其间每一次提交运行结果被判错误的话将被加罚20分钟时间，未正确解答的试题不记时，如果已经返回正确的题目再重复提交则不影响结果。例如：A、B两队都正确完成两道题目，其中A队提交这两题的时间分别是比赛开始后60分钟和165分钟，B队为80分钟和130分钟，但B队第一个题提交了2次才通过。这样A队的总用时为60 + 165 = 225而B队为（80 + 20） + 130 = 230，所以A队以总用时少而获胜。
现在给出裁判机上面所有队伍的提交时间(分钟数)和返回结果，需要你编程输出当前比赛的排行榜。

输入格式
每行一个评判结果，格式为：时间（第几分钟提交的） + 半角空格 + 队名 + 半角空格 + 题号 + 半角空格 + 评判结果（0通过，其它为出错）
题号由大写A字符开始，第2题是B，依次类推，最多不超过15题
所有评判结果已经按时间排序好

输出格式
输出排名，一行一个，格式为队名 + 半角空格 + 通过题数 + 半角空格 + 罚时

注：0题的队伍不需要输出
测试数据中，没有同题且同罚时的情况

输入样例
2 abc A 4
5 abc B 0
6 def A 0
10 abc A 0
13 xyx A 4
20 def B 5

输出样例
abc 2 35
def 1 6

注意事项：

无

代码实现：

class group {
public:int AC;string name;int timeUsed;vector<vector<int>> info; // 存放题目的完成情况, info[i][0]是题目的通过标记（0即是通过，其他都不是）,info[i][1]是题目错误的次数group() { // 默认构造函数进行初始化this->AC = 0;this->timeUsed = 0;this->info = vector<vector<int>>(15, vector<int>(2, -1));}
};vector<group> groups; // 存放各队伍的链表int Search(string name) { // 在列表中查找for (int i = 0; i < groups.size(); i++) {if (groups[i].name == name) {return i; // 查找成功则返回队伍的编号}}return -1; // 查找失败返回-1
}bool cmp(group a, group b) {if (a.AC != b.AC) {return a.AC > b.AC;}return a.timeUsed < b.timeUsed;
}int main() {IOS;int submissionTime; string groupName; char problemID; int submissionStatus;while (cin >> submissionTime >> groupName >> problemID >> submissionStatus) {int index = Search(groupName);if (index == -1) { // 如果是新出现的队伍，则进行队伍的创建group newGroup;newGroup.name = groupName;index = groups.size(); // 队伍在列表中的编号groups.push_back(newGroup);}if (groups[index].info[problemID - 'A'][0] == 0) { // 如果该题之前通过了，不影响continue;}groups[index].info[problemID - 'A'][0] = submissionStatus;if (submissionStatus != 0) { // 没有通过，在队伍题目信息里进行标记groups[index].info[problemID - 'A'][1]++;}else { // 题目通过了groups[index].timeUsed += (submissionTime + (groups[index].info[problemID - 'A'][1] + 1) * 20); // 所用时间为提交的时间加上罚时groups[index].AC++;}}sort(groups.begin(), groups.end(), cmp);for (group one : groups) {if (one.AC == 0) {break;}cout << one.name << ' ' << one.AC << ' ' << one.timeUsed << endl;}return 0;
}

暴力枚举 (Brute Force)

18443 除法等式

时间限制 : 2000MS 代码长度限制 : 10KB

Description
输入正整数n，按从小到大的顺序输出所有形如abcde / fghij = n的表达式，其中a~j各代表0~9中的一个数字，除了0可以重复外，其它数字不能重复，2 <= n <= 90000。

输入格式
多case，每行一个数字，最后一个数字是0

输出格式
除了最后一行0不用处理，其它每个case，按被除数由小到大输出所有满足等式的情况
注：如果没有满足条件的等式，该case结束后，也需要输出一个空行

两个case之间用一个空行分隔

输入样例
666
0

输出样例
27306 / 00041 = 666
41958 / 00063 = 666
43290 / 00065 = 666
52614 / 00079 = 666
53946 / 00081 = 666
63270 / 00095 = 666

注意事项：

注意看清题意，题意要求的是abcde / fghij = n的表达式，并且要尽量减小枚举的范围，否则就会超时

代码实现：

bool isQualifiedNumber(int number1, int number2) {vector<bool> digitChecker(10, false);while (number1 > 0) {int digit = number1 % 10;if (digit != 0 && digitChecker[digit] == true) {return false;}else {digitChecker[digit] = true;}number1 /= 10;}while (number2 > 0) {int digit = number2 % 10;if (digit != 0 && digitChecker[digit] == true) {return false;}else {digitChecker[digit] = true;}number2 /= 10;}return true;
}int main() {IOS;int n;while (cin >> n && n) {for (int i = 1, j = 1; i <= 98765; i++) {j = i * n;if (j > 98765) {continue;}if (isQualifiedNumber(i, j)) {printf("%05d/%05d=%dn", j, i, n);}}printf("n");}return 0;
}

1079 三角形

时间限制 : 500MS 代码长度限制 : 10KB

Description
著名的数学家毕达哥拉斯可能从来都不曾想过有人居然会问他这样的一个问题：给出一个整数，存在多少个直角三角形，它的某一条边的长度等于这个整数，而且其他边的长度也是整数。既然毕达哥拉斯不可能预见到有计算机的出现，如果他回答不出来，那谁又能责怪他呢？但是现在既然你有了计算机，那么回答不出来就说不过去了。

输入格式
第一行有一个整数n，代表有多少个数据（1 <= n <= 20）。接下来有n行，每行代表一个数据。一个数据就是一个整数ai(a <= i <= n，1 <= ai <= 100)。

输出格式
每个数据都必须有相应的输出。两个数据的输出之间有一个空行。
对于每一个数据，如果找不到解，则输出一个空行。如果找到解，就把符合条件的所有直角三角形输出。每个三角形占一行，输出该三角形的另外两条边，必须先输出长边，然后一个逗号，再输出短边。两个三角形之间不能有空行，而且必须按照长边降序排列。

输入样例
2
20
12

输出样例
101, 99
52, 48
29, 21
25, 15
16, 12

37, 35
20, 16
15, 9
13, 5

注意事项

要尽量减小枚举的范围，否则就会超时

代码实现：

int main() {IOS;int n; cin >> n;while (n--) {int side; cin >> side;vector<pair<int, int>> result;// 情况一：该边为直角边for (int side1 = 1;; side1++) {int side2 = sqrt(side * side + side1 * side1);if (side2 - side1 >= side) { // 斜边与另一直角边的差已经大于第三边，说明已超出范围break;}if (side2 * side2 == side * side + side1 * side1) {result.push_back(make_pair(side2, side1));}}for (int i = result.size() - 1; i >= 0; i--) { // 从大到小输出cout << result[i].first << ',' << result[i].second << endl;}// 情况二：该边为斜边for (int side1 = side - 1; side1 > 0; side1--) {int side2 = sqrt(side * side - side1 * side1);if (side2 > side1) {break;}if (side * side == side1 * side1 + side2 * side2) {cout << side1 << ',' << side2 << endl;}}cout << endl;}return 0;
}

18444 分数拆分

时间限制 : 2500MS 代码长度限制 : 10KB

Description
输入正整数k（k <= 1000），将1 / k变为不少于2项，但不多于3项的1 / (xi)之和，xi为正整数，且i表示序号

注：请使用long long

输入格式
多case，一行一个整数k
最后一行是0

输出格式
对每一个case，按等式最右边一项分母，由小到大排序输出满足条件的等式，最右边一项分母相同，则按最右边第二项，依次类推
每一个case完成后，输出一个空行（没有满足的等式时，也要输出该空行）

输入样例
2
3
4
0

输出样例
1 / 2 = 1 / 6 + 1 / 3
1 / 2 = 1 / 42 + 1 / 7 + 1 / 3
1 / 2 = 1 / 24 + 1 / 8 + 1 / 3
1 / 2 = 1 / 18 + 1 / 9 + 1 / 3
1 / 2 = 1 / 15 + 1 / 10 + 1 / 3
1 / 2 = 1 / 12 + 1 / 12 + 1 / 3
1 / 2 = 1 / 4 + 1 / 4
1 / 2 = 1 / 20 + 1 / 5 + 1 / 4
1 / 2 = 1 / 12 + 1 / 6 + 1 / 4
1 / 2 = 1 / 8 + 1 / 8 + 1 / 4
1 / 2 = 1 / 10 + 1 / 5 + 1 / 5
1 / 2 = 1 / 6 + 1 / 6 + 1 / 6

1 / 3 = 1 / 12 + 1 / 4
1 / 3 = 1 / 156 + 1 / 13 + 1 / 4
1 / 3 = 1 / 84 + 1 / 14 + 1 / 4
1 / 3 = 1 / 60 + 1 / 15 + 1 / 4
1 / 3 = 1 / 48 + 1 / 16 + 1 / 4
1 / 3 = 1 / 36 + 1 / 18 + 1 / 4
1 / 3 = 1 / 30 + 1 / 20 + 1 / 4
1 / 3 = 1 / 28 + 1 / 21 + 1 / 4
1 / 3 = 1 / 24 + 1 / 24 + 1 / 4
1 / 3 = 1 / 120 + 1 / 8 + 1 / 5
1 / 3 = 1 / 45 + 1 / 9 + 1 / 5
1 / 3 = 1 / 30 + 1 / 10 + 1 / 5
1 / 3 = 1 / 20 + 1 / 12 + 1 / 5
1 / 3 = 1 / 15 + 1 / 15 + 1 / 5
1 / 3 = 1 / 6 + 1 / 6
1 / 3 = 1 / 42 + 1 / 7 + 1 / 6
1 / 3 = 1 / 24 + 1 / 8 + 1 / 6
1 / 3 = 1 / 18 + 1 / 9 + 1 / 6
1 / 3 = 1 / 15 + 1 / 10 + 1 / 6
1 / 3 = 1 / 12 + 1 / 12 + 1 / 6
1 / 3 = 1 / 21 + 1 / 7 + 1 / 7
1 / 3 = 1 / 12 + 1 / 8 + 1 / 8
1 / 3 = 1 / 9 + 1 / 9 + 1 / 9

1 / 4 = 1 / 20 + 1 / 5
1 / 4 = 1 / 420 + 1 / 21 + 1 / 5
1 / 4 = 1 / 220 + 1 / 22 + 1 / 5
1 / 4 = 1 / 120 + 1 / 24 + 1 / 5
1 / 4 = 1 / 100 + 1 / 25 + 1 / 5
1 / 4 = 1 / 70 + 1 / 28 + 1 / 5
1 / 4 = 1 / 60 + 1 / 30 + 1 / 5
1 / 4 = 1 / 45 + 1 / 36 + 1 / 5
1 / 4 = 1 / 40 + 1 / 40 + 1 / 5
1 / 4 = 1 / 12 + 1 / 6
1 / 4 = 1 / 156 + 1 / 13 + 1 / 6
1 / 4 = 1 / 84 + 1 / 14 + 1 / 6
1 / 4 = 1 / 60 + 1 / 15 + 1 / 6
1 / 4 = 1 / 48 + 1 / 16 + 1 / 6
1 / 4 = 1 / 36 + 1 / 18 + 1 / 6
1 / 4 = 1 / 30 + 1 / 20 + 1 / 6
1 / 4 = 1 / 28 + 1 / 21 + 1 / 6
1 / 4 = 1 / 24 + 1 / 24 + 1 / 6
1 / 4 = 1 / 140 + 1 / 10 + 1 / 7
1 / 4 = 1 / 42 + 1 / 12 + 1 / 7
1 / 4 = 1 / 28 + 1 / 14 + 1 / 7
1 / 4 = 1 / 8 + 1 / 8
1 / 4 = 1 / 72 + 1 / 9 + 1 / 8
1 / 4 = 1 / 40 + 1 / 10 + 1 / 8
1 / 4 = 1 / 24 + 1 / 12 + 1 / 8
1 / 4 = 1 / 16 + 1 / 16 + 1 / 8
1 / 4 = 1 / 36 + 1 / 9 + 1 / 9
1 / 4 = 1 / 18 + 1 / 12 + 1 / 9
1 / 4 = 1 / 20 + 1 / 10 + 1 / 10
1 / 4 = 1 / 15 + 1 / 12 + 1 / 10
1 / 4 = 1 / 12 + 1 / 12 + 1 / 12

注意事项：

要尽量减小枚举的范围，否则就会超时

代码实现：

int main() {IOS;int A;while (cin >> A && A) {long long B, D, C = 0;for (D = A + 1; D <= 3 * A; D++) { if ((A * D) % (D - A) == 0) { B = (A * D) / (D - A); if (D <= B) {printf("1/%d=1/%lld+1/%lldn", A, B, D);}}long long bound = (A * D * 2) / (D - A) + 1; for (C = (A * D) / (D - A) + 1; C <= bound; C++) {if ((A * C * D) % (C * D - A * D - A * C) == 0) {B = (A * C * D) / (C * D - A * D - A * C); if (C >= D && B > 0) {printf("1/%d=1/%lld+1/%lld+1/%lldn", A, B, C, D);}}}}printf("n");}return 0;
}

动态规划 (Dynamic Programming)

19116 丑数

Description
“丑数”是指除了质因子2, 3，5，不含其它质因子的正整数，例如由小到大前10个“丑数”为1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …
现要求编写一个程序，输出指定第几位的“丑数”。

输入格式
第一行为正整数T（T <= 10000）, 表示case的数目。
此后T行，每行一个正整数 n(n <= 100000000).

输出格式
每一个n，输出第n个“丑数”

输入样例
3
1
2
9

输出样例
1
2
10

注意事项：

无

代码实现：

int main() {IOS;int n; cin >> n;while (n--) {int nth; cin >> nth;vector<int> dp(nth * 10, 0);dp[1] = 1;int p2 = 1, p3 = 1, p5 = 1;for (int i = 2; i <= nth; i++) {dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));// 去重if (dp[i] == dp[p2] * 2) {p2++;}if (dp[i] == dp[p3] * 3) {p3++;}if (dp[i] == dp[p5] * 5) {p5++;}}cout << dp[nth] << endl;}return 0;
}

18005 它不是丑数

Description
“丑数”是指除了质因子2, 3，5，不含其它质因子的正整数，例如由小到大前10个“丑数”为
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …
非“丑数”的前10个数为
7, 11, 13, 14, 17, 19, 21, 22, 23, 26, …
现要求编写一个程序，输出指定第几位的非“丑数”。

输入格式
第一行为正整数T（T <= 10000）, 表示case的数目。
此后T行，每行一个正整数 n(n <= 100000000).

输出格式
每一个n，输出第n个非“丑数”

输入样例
3
1
2
9

输出样例
7
11
23

注意事项：

无

代码实现：

vector<int> uglyNumber(3000, 0); void GenerateUglyNumber() { // 生成出前3000个丑数uglyNumber[1] = 1;int p2 = 1, p3 = 1, p5 = 1;for (int i = 2; i < 3000; i++) {uglyNumber[i] = min(2 * uglyNumber[p2], min(3 * uglyNumber[p3], 5 * uglyNumber[p5]));if (uglyNumber[i] == 2 * uglyNumber[p2]) {p2++;}if (uglyNumber[i] == 3 * uglyNumber[p3]) {p3++;}if (uglyNumber[i] == 5 * uglyNumber[p5]) {p5++;}}
}int main() {IOS;int n; cin >> n;GenerateUglyNumber();while (n--) {int nth; cin >> nth;int count = 0; // 第几个非丑数int index = 1; // 第几个丑数while (nth > count) {count += uglyNumber[index + 1] - uglyNumber[index] - 1;index++;}index--;count -= uglyNumber[index + 1] - uglyNumber[index] - 1;cout << uglyNumber[index] + (nth - count) << endl;}return 0;
}

18308 最长公共子序列

Description
给定两个字符串，请输出这两个字符串的最大公共子序列

输入格式
两行，一行一个字符串（不包括空格，Tab键）, 长度不超过1000

输出格式
输出最大公共子序列的长度

输入样例
abbca
aba

输出样例
3

注意事项：

无

代码实现：

int main() {IOS;string s1, s2; cin >> s1 >> s2;vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));for (int i = 1; i <= s1.size(); i++) {for (int j = 1; j <= s2.size(); j++) {if (s1[i - 1] == s2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}cout << dp[s1.size()][s2.size()] << endl;return 0;
}

8615 快乐

时间限制 : 500MS 代码长度限制 : 10KB

Description
Lian是一个喜欢看动画片的人，自从成为ACMer（ACM爱好者）之后，他又迷上了网上做题。做题让他快乐，不过这也是需要付出精力的！！
假设有n道题，Lian做出第i道题后，他可以获得的快乐指数将增加gethappy[i]，而消耗掉的精力将是losspow[i]。
假设Lian初始的快乐指数为1，精力为2000。可以理解，如果他消耗完了所有的精力那他得到再多的快乐都没有用。
你的任务就是帮他计算他所能得到的最多的快乐指数，且最后他依然有多余的精力（即至少为1）。

输入格式
第一行输入一个整数n，表示有n道题。(n <= 50)
第二行输入n个整数，表示gethappy[1]到gethappy[n]
第三行输入n个整数，表示losspow[1]到losspow[n]。

输出格式
一个整数，表示Lian所能获得的最大快乐指数。

输入样例
3
15 23 61
350 1301 1513

输出样例
77

注意事项：

初始快乐指数为1，因此最后的结果要加1

代码实现：

int main() {IOS;int n; cin >> n;vector<int> getHappy(n + 1, 0);vector<int> lossPower(n + 1, 0);vector<vector<int>> dp(n + 1, vector<int>(2000 + 1, 0));for (int i = 1; i <= n; i++) {cin >> getHappy[i];}for (int i = 1; i <= n; i++) {cin >> lossPower[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= 2000; j++) {int currentPower = j, currentLossPower = lossPower[i], currentHappiness = getHappy[i];if (currentPower < currentLossPower) {dp[i][j] = dp[i - 1][j];}else {dp[i][j] = max(dp[i - 1][j], (dp[i - 1][currentPower - currentLossPower] + currentHappiness));}}}cout << dp[n][2000] + 1 << endl;return 0;
}

回溯算法 (BackTracking)

18124 N皇后问题

时间限制 : 5000MS 代码长度限制 : 10KB

Description
有N* N的国际象棋棋盘，要求在上面放N个皇后，要求任意两个皇后不会互杀，有多少种不同的放法？

输入格式
每一个数为T，代表CASE的数量，T <= 13
此后，每行一个数N（13 >= N > 0）

输出格式
每一个CASE，输出对应答案

输入样例
2
4
5

输出样例
2
10

注意事项：

无

代码实现：

//int ans;
//
//bool isValidPosition(int row, int col, const vector<string> board) {
//	for (int i = row - 1; i >= 0; i--) {
//		if (board[i][col] == 'Q') {
//			return false;
//		}
//	}
//	for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
//		if (board[i][j] == 'Q') {
//			return false;
//		}
//	}
//	for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); i--, j++) {
//		if (board[i][j] == 'Q') {
//			return false;
//		}
//	}
//	return true;
//}
//
//void Backtracking(int row, vector<string>& board) {
//	if (row == board.size()) {
//		ans++;
//		return;
//	}
//	for (int col = 0; col < board.size(); col++) {
//		if (!isValidPosition(row, col, board)) {
//			continue;
//		}
//		board[row][col] = 'Q';
//		Backtracking(row + 1, board);
//		board[row][col] = '.';
//	}
//}int main() {IOS;int n; cin >> n;while (n--) {int size; cin >> size;/*vector<string> board(size, string(size, '.'));Backtracking(0, board);cout << ans << endl;ans = 0;*/switch (size){case 1: cout << 1 << endl; break;case 2: cout << 0 << endl; break;case 3: cout << 0 << endl; break;case 4: cout << 2 << endl; break;case 5: cout << 10 << endl; break;case 6: cout << 4 << endl; break;case 7: cout << 40 << endl; break;case 8: cout << 92 << endl; break;case 9: cout << 352 << endl; break; case 10: cout << 724 << endl; break;case 11: cout << 2680 << endl; break;case 12: cout << 14200 << endl; break;case 13: cout << 73712 << endl; break;default:break;}}return 0;
}

19010 最小的特殊数字

时间限制 : 1000MS 代码长度限制 : 10KB

Description
用全部N(N <= 10)个0 – 9的数字组成一个“有效”整数（即没有前置0的整数），
求这些组成的数中能被K(0 < K < 10 ^ 10)整除的最小数字。

输入格式
输入分两行，第一行输入N,K，第二行输入N个数字。

输出格式
输出满足条件的最小的数（不含前置0），如果没有满足条件的数输出-1。

输入样例
4 7
4 0 1 3

输出样例
1043

提示
413%7=0，但是有前置0，所以满足条件的最小数是1043%7=0。
此类题目需注意特殊情况，比如n=1时,如只输入一个0，答案只能是0。
注意long long

注意事项：

第一个符合条件的数据即是最终答案

代码实现：

int main() {IOS;ll n, k, ans = 0;cin >> n >> k;vector<int> num(n, 0);for (int i = 0; i < n; i++) {cin >> num[i];}if (n == 1) { // 只有一个数字的情况，直接对其进行判断if (num[0] % k == 0) {cout << num[0] << endl;}else {cout << -1 << endl;}return 0;}sort(num.begin(), num.end()); // 使用next_permutation()前一定先排序do {if (num[0] == 0) { // 开头字母为0，不是有效数学，跳过continue;}ll cur = 0;for (int i = 0; i < n; i++) {cur = 10 * cur + num[i];}if (cur % k == 0) {ans = cur;break; // 此时已经得到最终答案}} while (next_permutation(num.begin(), num.end()));if (!ans) {cout << -1 << endl;}else {cout << ans;}return 0;
}

搜索 (Search)

18276 走迷宫

时间限制 : 1000MS 代码长度限制 : 10KB

Description
有一个N* M的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，另外，在迷宫中有一些传送门，走到传送门的入口即会自动被传送到传送门的出口（一次传送算1步）。人在迷宫中可以尝试上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口，以及起点和终点，
问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

输入格式
该程序为多CASE，第1行为CASE的数量
每一个CASE，第1行为两个数N（行）和M（列）
然后N行每行M个数
之后是一个数W，为传送门的数量
之后每行一个传送门的入口坐标c1(行), r1(列)和出口坐标c2, r2
之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)

注：传送门出入口和起点坐标和终点坐标不会出现在墙的位置
所有数字不超过100

输出格式
如题

输入样例
2
4 3
011
011
110
110
1
1 0 2 2
0 0 3 2
2 2
01
10
0
0 0 1 1

输出样例
3
die

注意事项：

走过的路一定要进行标记，防止死循环导致的超时

代码实现：

int startRow, startColumn, exitRow, exitColumn;
map<pair<int, int>, pair<int, int>> portal; // 构造传送门的起点坐标和终点坐标的映射struct Node {int row;int column;int step;Node() {this->row = startRow;this->column = startColumn;this->step = 0;}
};vector<vector<int>> GenerateMaze(int row, int column) {vector<vector<int>> maze(row, vector<int>(column, 1));for (int i = 0; i < row; i++) {string line; cin >> line;for (int j = 0; j < column; j++) {maze[i][j] = line[j] - '0';}}return maze;
}bool isExit(int row, int column) {if (row == exitRow && column == exitColumn) {return true;}return false;
}int Solve(vector<vector<int>> maze) {Node node;queue<Node> aux;aux.push(node);while (!aux.empty()) {Node currentNode = aux.front(); aux.pop();maze[currentNode.row][currentNode.column] = -1;if (isExit(currentNode.row, currentNode.column)) {return currentNode.step;}pair<int, int> p = make_pair(currentNode.row, currentNode.column);auto it = portal.find(p);Node trialNode = currentNode;for (int direction = 0; direction <= 4; direction++, trialNode = currentNode) {switch (direction){case 0: 		if (it != portal.end()) {trialNode.row = portal[p].first; trialNode.column = portal[p].second; trialNode.step++;aux.push(trialNode);direction = 5;}break;case 1: trialNode.row++; break;case 2: trialNode.column--; break;case 3: trialNode.row--; break;case 4: trialNode.column++; break;default: break;}if (trialNode.row >= maze.size() || trialNode.row < 0 || trialNode.column >= maze[0].size() || trialNode.column < 0) {continue;}if (maze[trialNode.row][trialNode.column] == 0) { trialNode.step++;aux.push(trialNode);maze[trialNode.row][trialNode.column] = -1;}}}return -1;
}int main() {IOS;// freopen("tests.txt", "r", stdin);int numberOfCase; cin >> numberOfCase;while (numberOfCase--) {// 构造迷宫int row, column; cin >> row >> column;vector<vector<int>> maze = GenerateMaze(row, column);// 构造传送门int numberOfPortal; cin >> numberOfPortal;for (int i = 0; i < numberOfPortal; i++) {int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;portal[make_pair(x1, y1)] = make_pair(x2, y2);}cin >> startRow >> startColumn >> exitRow >> exitColumn;int result = Solve(maze);if (result == -1) {cout << "die" << endl;}else {cout << result << endl;}portal.clear();}// fclose(stdin);return 0;
}

18440 走迷宫2

时间限制 : 1000MS 代码长度限制 : 10KB

Description
有一个N* M(N, M <= 10)的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，人在迷宫中可以尝试上下左右四个方向移动。
另外，在迷宫中如果从左边走出迷宫会回到迷宫最右边一格（只要该格不是墙），行不变，同样，从右边走出迷宫会回到迷宫最左边一格，向上走出迷宫会回到迷宫最下边一格，向下走出迷宫会回到迷宫最上边一格。
现在给定一个迷宫，以及起点和终点，问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

输入格式
该程序为多CASE，第1行为CASE的数量
每一个CASE，第1行为两个数N（行）和M（列）
然后N行每行M个数，之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)

输出格式
如题

输入样例
2
4 3
011
010
110
110
0 0 3 2
2 2
01
10
0 0 1 1

输出样例
4
die

提示
第一个case，可以从（1，0）走到（1，2）

注意事项：

无

代码实现：

int startRow, startColumn, exitRow, exitColumn;struct Node {int row;int column;int step;Node() {this->row = startRow;this->column = startColumn;this->step = 0;}
};vector<vector<int>> GenerateMaze(int row, int column) {vector<vector<int>> maze(row, vector<int>(column, 0));for (int i = 0; i < row; i++) {string line; cin >> line;for (int j = 0; j < column; j++) {maze[i][j] = line[j] - '0';}}return maze;
}bool isExit(Node node) {if (node.row == exitRow && node.column == exitColumn) {return true;}return false;
}int Solve(vector<vector<int>> maze) {Node node;queue<Node> aux;aux.push(node);while (!aux.empty()) {Node currentNode = aux.front(); aux.pop();if (isExit(currentNode)) {return currentNode.step;}maze[currentNode.row][currentNode.column] = -1;Node trialNode = currentNode;for (int direction = 1; direction <= 4; direction++, trialNode = currentNode) {switch (direction){case 1: trialNode.row = (trialNode.row + 1) % maze.size(); break;case 2: trialNode.column = (trialNode.column + 1) % maze[0].size(); break;case 3: trialNode.row = (trialNode.row - 1 + maze.size()) % maze.size(); break;case 4: trialNode.column = (trialNode.column - 1 + maze[0].size()) % maze[0].size(); break;default: break;}if (maze[trialNode.row][trialNode.column] == 0) {maze[trialNode.row][trialNode.column] = -1; // 走过的路径要进行特殊标记，防止死循环trialNode.step++;aux.push(trialNode);}}}return -1;
}int main() {IOS;int numberOfCase; cin >> numberOfCase;while (numberOfCase--) {int row, column; cin >> row >> column;vector<vector<int>> maze = GenerateMaze(row, column);cin >> startRow >> startColumn >> exitRow >> exitColumn;int result = Solve(maze);if (result == -1) {cout << "die" << endl;}else {cout << result << endl;}}return 0;
}

实用类数据结构 (Pratical Data Structure)

18130 繁忙的公路

时间限制 : 6000MS 代码长度限制 : 10KB

Description
在一条笔直的大道（单方向行车道）上，汽车川流不息。道路从起点到终点，等距离的标记了1到N，即起点是1，然后分别是2、3、4…..，终点是N。每一个标记处，安装了智能探头，可以感知
在该点处车辆的增减数量。
一开始，整条道路上，没有车，然后，是不断接收到的智能探头发回的信息，格式如下：
H 5 9
H表明收到的是智能探头的回传信息，5表示标记5处的车辆信息，9表示该处车辆增加了9辆。
同时，在某个时刻，需要查询在一段连续的道路上，共有多少辆车
查询格式如下：
Q 3 10
Q表明收到的是查询，3是起点，10是终点（包括3和10两处）
要求编程实现正确处理上述信息处理和查询

输入格式
第一行一个整数N（1 <= N <= 1, 000, 000），表示标记范围是1到N
第二行一个整数M（1 <= M <= 100, 000），表示探头信息（或查询）的总数量
此后M行，每行一个探头信息或查询请求

输出格式
每逢遇到查询的时候，输出查询范围内的有多少辆车，占一行，查询结果最大不超过2的63次方

输入样例
10
4
H 5 10
Q 1 10
H 6 20
Q 1 10

输出样例
10
30

提示
开始时，整条路上没有车辆

注意事项：

注意使用long long

代码实现：

ll treeArray[1000010];
ll n, numberOfOperation;ll Lowbit(ll x) {return x & (-x);
}void Update(ll index, ll value) {while (index <= n) {treeArray[index] += value;index += Lowbit(index);}
}ll Query(ll index) {ll sum = 0;while (index > 0) {sum += treeArray[index];index -= Lowbit(index);}return sum;
}int main() {IOS;cin >> n >> numberOfOperation;for (int i = 1; i <= n; i++) {treeArray[i] = 0;}while (numberOfOperation--) {ll index1, index2; char sign;cin >> sign >> index1 >> index2;if (sign == 'H') {Update(index1, index2);}else {cout << Query(index2) - Query(index1 - 1) << endl;}}return 0;
}

18233 万湖之国的形成

时间限制 : 2500MS 代码长度限制 : 10KB

Description
N国原是一块平原上，没有湖，直到一颗小行星撞入大气层碎成成千上万的碎片，碎片再撞击地面形成一个一个的坑，下雨之后，最终形成万湖之国。
现在科学家想用计算机模拟万湖之国形成过程，假设每一块碎片撞击地面，都撞出一个园形坑，现在知道
每一个碎片造成的坑的圆心和半径，问每个坑都注满水后，最终形成多少个湖？

输入格式
第一行一个整数N，1 <= N <= 100, 000，表示坑的数量
此后N行，每一行三个double实数，前两个数是圆心的坐标x和y，最后一个数是圆半径（不大于1000）(数据随机产生，分布均匀)

输出格式
湖的个数

输入样例
3
0 0 5
10 0 5
11.1 0 2.5

输出样例
2

注意事项：

需要通过排序来进行剪枝

代码实现：

struct Pit {double x, y, r;Pit(double x, double y, double r) : x(x), y(y), r(r) {};bool operator <(const Pit a) const { return x + r < a.x + a.r;}
};vector<Pit> pits;
map<ll, ll> parent; // 这里一定要用全局变量ll Find(ll x) {ll root = x;while (root != parent[root]) {root = parent[root];}return root;
}int main() {IOS;ll numberOfPit; cin >> numberOfPit;ll answer = numberOfPit;for (ll i = 0; i < numberOfPit; i++) {double x, y, r; cin >> x >> y >> r;Pit newPit(x, y, r);pits.push_back(newPit);parent[i] = i;}sort(pits.begin(), pits.end());for (ll i = 0; i < numberOfPit; i++) {for (ll j = i - 1; j >= 0; j--) {if (pits[j].x + pits[j].r < pits[i].x - pits[i].r) {break;}if (pow(pits[i].x - pits[j].x, 2) + pow(pits[i].y - pits[j].y, 2) < pow(pits[i].r + pits[j].r, 2)) {ll rootOfI = Find(i);ll rootOfJ = Find(j);if (rootOfI != rootOfJ) {answer--;parent[rootOfI] = rootOfJ;}}}}cout << answer << endl;return 0;
}

贪心算法 (Greedy)

18118 勇者斗恶龙

时间限制 : 800MS 代码长度限制 : 10KB
Description
有n个头的恶龙，你希望雇一些骑士把它杀死（即砍掉所有头）。村里有ｍ个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头，且需要支付的金币最少？注意，一个骑士只能砍一个头（且不能被雇佣两次）

输入格式
多组数据，每组数据的第一行为正整数n和m(1 <= n, m <= 200000)；以下n行每行为一个整数，即恶龙每个头的直径；以下m行每行为
一个整数，即每个骑士的能力。输入结束标志ｎ＝ｍ＝0;

输出格式
每组数据，输出最少花费，无解输出"Loowater is doomed!"

输入样例
2 3
5
4
7
8
4
2 1
5
5
10
0 0

输出样例
11
Loowater is doomed!

注意事项：

无

代码实现：

int main() {IOS;int n, m;while (cin >> n >> m) {if (n == 0 && m == 0) {break;}vector<int> heads(n, 0);vector<int> knights(m, 0);for (int i = 0; i < n; i++) {cin >> heads[i];}for (int i = 0; i < m; i++) {cin >> knights[i];}sort(heads.begin(), heads.end());sort(knights.begin(), knights.end());int cost = 0;int i = 0, j = 0;while (i < n && j < m) {if (heads[i] > knights[j]) {j++;}else {cost += knights[j];i++;j++;}}if (i == n) { // 头都砍完了即为胜利cout << cost << endl;}else {cout << "Loowater is doomed!" << endl;}}return 0;
}

头文件及宏定义

基础

18104 练习使用多case解题

注意事项：

代码实现：

递归和分治 (Recursion and Divide and Conquer)

1142 巡逻的士兵

注意事项：

代码实现：

18441 偷懒的士兵

注意事项：

代码实现：

18442 偷懒的士兵2

注意事项：

代码实现：

19144 偷懒的士兵3

注意事项：

代码实现：

排序和优先队列 (Sorting and Priority Queue)

18105 银行的叫号顺序

注意事项：

代码实现：

18216 银行服务

注意事项：

代码实现：

18107 校赛排名

注意事项：

代码实现：

18290 校赛排名2

注意事项：

代码实现：

暴力枚举 (Brute Force)

18443 除法等式

注意事项：

代码实现：

1079 三角形

注意事项

代码实现：

18444 分数拆分

注意事项：

代码实现：

动态规划 (Dynamic Programming)

19116 丑数

注意事项：

代码实现：

18005 它不是丑数

注意事项：

代码实现：

18308 最长公共子序列

注意事项：

代码实现：

8615 快乐

注意事项：

代码实现：

回溯算法 (BackTracking)

18124 N皇后问题

注意事项：

代码实现：

19010 最小的特殊数字

注意事项：

代码实现：

搜索 (Search)

18276 走迷宫

注意事项：

代码实现：

18440 走迷宫2

注意事项：

代码实现：

实用类数据结构 (Pratical Data Structure)

18130 繁忙的公路

注意事项：

代码实现：

18233 万湖之国的形成

注意事项：

代码实现：

贪心算法 (Greedy)

18118 勇者斗恶龙

注意事项：

代码实现：

Published by