kkbtrainingI

奶牛碑文 原题链接：https://oj.haizeix.com/problem/516 约翰和他的奶牛在大草原漫游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C,O,W。 尽管约翰看不懂，但是令他高兴的是，C,O,W的顺序形式构成了一句他最喜欢的奶牛单词 “COW”。 现在，他想知道有多少次 COW出现在文本中。 如果 COW内穿插了其他字符，只要COW字符出现在正确的顺序，约翰也不介意。 他也不介意出现不同的COW共享一些字母。例如CWOW出现了1次COW，CCOW算出现了2次COW，CCOOWW算出现了8次COW。 输入： 第一行一个整数 N。（1≤N≤105） 第二行为含有 N 个字符的字符串，字符只可能是 C,O,W。 输出： 输出 COW 作为输入字符串的子串出现的次数（不一定是连续的），答案可能会很大。 样例： 126COOWWW 16 参考代码 暴力法：三重for循环分别对C,O,W进行遍历，可能会导致超时。 利用前缀和思想：空间复杂度换时间复杂度， 1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;char str[100005];int numc[100005], numw[100005], n;long long ans;int main() { cin >> n >> str; for (int i = 0; str[i]; ++i) {//从前向后遍历 计算有多少个C（前缀和C） if (i == 0) { numc[i] = (str[i] == 'C'); } else { numc[i] = numc[i - 1] + (str[i] == 'C'); } } for (int i = n - 1; i >= 0; --i) {//从后向前遍历 计算有多少个W（后缀和W） if (i == n - 1) { numw[i] = (str[i] == 'W' ...

三角形个数 原题链接：https://oj.haizeix.com/problem/517 输入一根木棒的长度 n，将其分成三段，每段的长度是正整数，输出由这三小段木棒组成的不一样的三角形个数。 输入： 第一行一个整数 n。（1 ≤ n ≤ 104） 输出： 输出组成的不一样的三角形的个数。 样例： 110 12 样例说明： 两个能组成的三角形边长分别为 2,4,4 和 3,3,4。 参考代码123456789101112131415161718#include<iostream>using namespace std;int main() { int ans = 0; int n; cin >> n; //注意枚举范围 for (int i = 1; i <= n / 3; ++i) {//枚举最小边 for (int j = i; j <= (n - i) / 2; ++j) {//枚举次小边 if ((i + j) > (n - i - j)) {//判断最长边的合法性 ans++; //cout << i << " " << j << " " << n - i - j << endl; } } } cout << ans << endl; return 0;}

优雅数 原题链接：https://oj.haizeix.com/problem/519 优雅枚举 给定两个数 L,R 求 L,R 之间（含）有多少个“优雅数”。 优雅数的定义：把一个数看做一个长度为 n 的字符串，n 个字符中 n−1 个全相同，有且仅有一个字符不同。例如 33323,119 都是优雅的，99999, 2332 都是不优雅的。 输入： 输入一行两个整数 L, R。（100 ≤ L ≤ R ≤ 1016） 输出： 输出两数间优雅数的个数。 样例： 1110 133 113 样例说明： 1110,112,113,114,115,116,117,118,119,121,122,131,133 参考代码 思路1：暴力法，遍历两数区间，直接对优雅数进行判定。 思路2：构造优雅数，将区间之内的所有优雅数直接构造出来，判定是否构造的优雅数是否在给定区间范围内。 单独的数字是几 多个的数字是几 优雅数的长度 单独的数字在优雅数中的位置（构造优雅数） 若一堆数为0的话，单独的数字必须要在优雅数的首位（不允许前导零） 若一个数为0的话，单独的0数字必须不能在首位（不允许前导零） 123456789101112131415161718192021222324252627282930#include<iostream>using namespace std;int main() { long long ans = 0; long long a, b; cin >> a >> b; for (int i = 0; i < 10; ++i) {//枚举单个的数字 for (int j = 0; j < 10; ++j) {//枚举多个的数字 if (i == j) continue; for (int k = 3; k < 18; ++k) {//枚举优雅数的数字长度 for (int l = 1; l <= k; ++l) {//枚举单独的数字在优雅数中的位置 if (i == 0 && l == 1) continue; if (j == 0 && l != 1) bre ...

火柴棒等式 原题链接：https://oj.haizeix.com/problem/514 给出 n 根火柴棒，可以拼出多少个形如 a + b = c 的等式。 等式中的 a,b,c 是用火柴棒拼出的整数（不能有前导零），数字和符号使用的火柴棒数量如下： 1234567891011120:61:22:53:54:45:56:67:38:79:6+:2=:2 有以下注意事项： 加号和等号各自需要两根火柴棒 如果 a ≠ b，则 a + b = c 和 b + a = c 视为不同的等式，a,b,c 均不小于 0 n 根火柴棒必须全部用上。 输入： 共一行一个整数 n。（1 ≤ n ≤ 24） 输出： 输出能组成的等式数。 样例： 114 12 样例说明：两个等式如下 120 + 1 = 11 + 0 = 1 参考代码难点：枚举范围的确定，取火柴消耗数量最少的数字1举例（使得相加数值最大，由此确定最大范围），最大为1111+1111=2222。 123456789101112131415161718192021222324252627282930#include<iostream>using namespace std;int n;//火柴数量int ans;int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};int func(int x) { int count = 0; if (x == 0) return 6; while (x) { count += num[x % 10]; x /= 10; } return count;} int main() { cin >> n; for (int i = 0; i <= 2000; ++i) { for (int j = 0; j <= 2000; ++j) { if ((func(i) + func(j) + func(i + j) + 4) == n) { ans++; cout << i << " + " << ...

比例简化 原题链接：https://oj.haizeix.com/problem/515 在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为 1498:902 不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。 现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A’ 比 B’， 要求在 A’ 和 B’ 均不大于L，且 A’ 和 B’ 互质的前提下， A’ / B’ ≥ A / B 且 A’ / B’ − A / B的值尽可能小 输入： 共一行三个整数 A, B, L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限 输出： 共一行两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例 样例： 11498 902 10 15 3 参考代码==思路==： 若从1开始枚举， 如果枚举出一个答案 A’，B’（互质），当在继续枚举出一个新的答案 A’，B’（不互质），必然存在一个原来就有的A’，B’（互质） 并且新的答案与原来的答案，比例应该是一样的。 即使用两个暴力for循环遍历，保证答案满足A’ / B’ ≥ A / B ，且A’ / B’ − A / B的值尽可能小即可。 1 3.OnlineJ516：奶牛碑文约翰和他的奶牛在大草原漫游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C,O,W。 尽管约翰看不懂，但是令他高兴的是，C,O,W的顺序形式构成了一句他最喜欢的奶牛单词 “COW”。 现在，他想知道有多少次 COW出现在文本中。 如果 COW内穿插了其他字符，只要COW字符出现在正确的顺序，约翰也不介意。 他也不介意出现不同的COW共享一些字母。例如CWOW出现了1次COW，CCOW算出现了2次COW，CCOOWW ...

独木舟 原题链接：https://oj.haizeix.com/problem/503 一群人去旅行要租用独木舟，每艘独木舟最多乘两人，且所有独木舟有一个统一的载重限度。 给出独木舟的载重限度和每个人的体重，现求最少需要租用多少独木舟。 输入 第一行一个整数 w，表示独木舟的载重量。（80 ≤ w ≤ 200） 第二行一个整数 n，表示旅游人数。 （1 ≤ n ≤ 30000） 接下来 n 行，每行一个数表示 ai，即每个人的重量 （5 ≤ ai ≤ w） 输出 接下来 n 行，每行一个数表示 ai，即每个人的重量 （5 ≤ ai ≤ w） 样例： 12345678910111009902020305060708090 16 参考代码123456789101112131415161718192021222324252627282930313233#include<iostream>#include<algorithm>using namespace std;int weight[30005];int main() { //1.数据录入 int w;//独木舟载重量 int n;//旅游的人数 cin >> w >> n; for (int i = 0; i < n; ++i) cin >> weight[i]; sort(weight, weight + n); //2.进行数据处理 int count = 0; if (weight[0] * 2 > w) {//特殊情况处理 count = n; } else {//一般情况处理 for (int i = 0; i < n; ++i) { for (int j = n - 1; j >= 0; --j) { if (weight[j] == 0) continue; if ((weight[i] + weight[j]) <= w || i == j) { count++; weight[j] = 0; weight[i] = 0; break; } } } ...

删数 原题链接：https://oj.haizeix.com/problem/504 输入一个高精度的正整数 n（长度不大于 240 位）， 去掉其中任意 s 个数字后，剩下的数字按原左右次序将组成一个新的正整数，现求一种方案，使得新的正整数数值最小。 输入 第一行一个整数 n 第二行一个正整数 s 输出 输出一个数表示最小值，输出时忽略数字的前导零 样例： 123//样例11795664 115 123//样例29030713 11 参考代码 让小的数字在前面、大的数字在后面，使得整体的数字变小。 删除违反该规则的数字， 如果没有违反规则的数字，则删除最后一个数字（最大的数字） 12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<string>using namespace std;int main() { string str; cin >> str; int n; cin >> n; //1.数据操作 for (int i = 0; i < n; ++i) { int ind = str.size() - 1;//默认删除最后一位-1 for (int j = 1; j < str.size(); ++j) { if (str[j - 1] > str[j]) {//优先删除违反规则的数字 ind = j - 1; break; } } str.replace(ind, 1, ""); } //2.前置零的特殊处理 int flag = 0; for (int i = 0; i < str.size(); ++i) { if (flag == 1) { cout << str[i]; } else if (str[i] != '0') { cout << str[i ...

最大整数 原题链接：https://oj.haizeix.com/problem/505 现在有 n 个正整数，将他们连成一排，组成一个最大的整数。 例如，现在有三个整数 13, 312, 343，连接成最大整数为 34331213。 输入： 第一行一个整数 n。（1 ≤ n ≤ 100000） 第二行 n 个不超过 int 类型范围的正整数。 输出： 输出一个数表示组成的最大整数。 样例： 123121 12 96 19612121 参考代码思路：按照某种规则进行排序（前面的字符串 连接上 后面的字符串的字典序，大于后面的字符串连接上前面的字符串的字典序） 123456789101112131415161718192021#include<iostream>#include<algorithm>#include<string>using namespace std;int n;string str[100005];bool cmp(const string &str1, const string &str2) { //前面连接上后面的字典序 大于 后面连接上前面的字典序 return str1 + str2 > str2 + str1;}int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> str[i]; sort(str, str + n, cmp); for (int i = 0; i < n; ++i) cout << str[i]; cout << endl; return 0;}

打热水 原题链接：https://oj.haizeix.com/problem/506 寝室楼里只有热水间能接热水，且每天烧水机器只在指定时间工作，去晚了机器就关掉了，每天晚上去接热水的同学能排起小长队。 某天在总计四个烧水机中，坏了三个只剩下一台机器能打水了。 现在有 n 名同学等待接水，因为每名同学所带的水壶有大有小，规格各不相同所以他们每人的接水时间分别为 Ti， 现求一个顺序，使得所有接水的同学平均等待接水时间最小，等待接水时间为该同学之前接水的同学所花费时间和。 输入 第一行一个整数 n。（1 ≤ n ≤ 30） 第二行 n 个整数表示 Ti。（1 ≤ Ti ≤ 2000） 输出 第一行输出排队顺序 第二行输出平均等待时间，结果保留两位小数。 样例： 121056 12 1 99 1000 234 33 55 99 812 123 2 7 8 1 4 9 6 10 5291.90 参考代码1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>#include<algorithm>#include<cstdio>using namespace std;struct node { int cnt;//打水同学的编号 int time;//所需的打水时间};node stu[35];int n;//同学的数量bool cmp(const node &a, const node &b) { return a.time < b.time;}int main() { //1.数据存储 cin >> n; for (int i = 1; i <= n; ++i) { cin >> stu[i].time; stu[i].cnt = i; } //2.数据处理 sort(stu + 1, stu + n + 1, cmp); int sum = 0;//总打水时间 int now = 0;//某个同学的打水等待时间 for (int i = 1; i <= n; ++i)  ...

两人过河 原题链接：https://oj.haizeix.com/problem/508 有 n 个人希望在晚上通过一座桥。 在任何时刻，最多只能有两个人在桥上，并且必须要带着手电筒才能过桥。 现在只有一个手电筒，所以必须安排某种顺序，使得手电筒可以被带回去让更多的人过桥。 每个人都有不同的过桥时间，两个人一起过桥所用的时间等于其中较慢的一个人的过桥时间。 现求所有人过桥的最短时间。 输入 第一行一个整数 n。（1 ≤ n ≤ 1000） 接下来 n 行，每行一个整数表示第 i 人的过桥时间 Ti。（1 ≤ Ti ≤ 100） 输出 输出所有人过桥的最短时间。 样例： 12345415210 117 让 1, 2 先过桥，然后让 1 回来，让 5,10 过桥，然后 2 回来再和 1 一起过桥，时间为 2+1+10+2+2=17。 思路==思路==：让时间短的人优先过桥，作为工具人。 递归解决问题 有时使用1个人当工具人过桥时间较短，有时使用2个人当工具人过桥时间较短 取两种方案中速度较快的一种（将两种方案结合起来） 参考代码设最快的过桥时间为num[0]、次快过桥时间为num[1]、次慢过桥时间为num[i - 1]、最慢过桥时间为num[i]： 则有： n = 1时，最快过桥时间为num[0] n = 2时，最快过桥时间为num[1] n = 3时，最快过桥时间为num[1] + num[0] + num[2] n > 3时，最快过桥时间为 方案1（2个工具人）：num[1] + num[0] + num[i] + num[1]（此时两个工具人都在起点） 方案2（1个工具人）：num[i] + num[0] + num[i - 1] + num[0]（此时工具人在起点） 1234567891011121314151617181920212223242526272829#include<iostream>#include<algorithm>using namespace std;int n, num[1005];int ans;int main() { cin >> n; for (int i = 0; i & ...