1、万万没想到之聪明的编辑
题目描述：
我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：
（1）三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
（2）两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
（3）上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC
我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！
……
万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……
请听题：请实现大锤的自动校对程序
输入描述:
第一行包括一个数字N，表示本次用例包括多少个待校验的字符串。 后面跟随N行，每行为一个待校验的字符串。
输出描述:
N行，每行包括一个被修复后的字符串。
输入例子1:
2 helloo wooooooow
输出例子1:
hello woow
分析
本题主要考察对字符串的操作，因为数据量不大，可以直接暴力法解题。主要要找到的两个特征字符子串的形式应该为AAA和AABB，对于AAA型的子串我们可以去掉第一个A那个位置的字符即可，AABB型的子串我们则需要去掉第一个B那个位置的字符，且优先“从左到右”匹配，以上操作可以通过字符串遍历的形式完成修改。在实际代码中，为了避免频繁对数组数据进行移动，我选择了使用‘0’来替换掉需要删去的字符来进行标记，具体实现代码如下：
代码
#include<stdio.h> #include<string.h> int main() { int n,i; scanf("%d",&n); //待校验的字符串数量 char str[1005]; while(n--){ int frist = 1,second = 0; scanf("%s",str); for(i=1;i<strlen(str);i++){ if(str[i] == str[i-1] && frist < 3 && second == 0){ frist ++; //满足AAA形式，去掉第一个A if(frist == 3){ str[i-2] = '0'; frist = 2; } } else if(str[i] != str[i-1] && frist > 1 && second == 0 ){ second = 1; } else if(str[i] == str[i-1] && frist > 1 && second != 0){ //满足AABB形式，去掉第一个B str[i-1] = '0'; second = 1; } else{ frist = 1; second = 0; } } for(i=0;i<strlen(str);i++){ //输出没被替换（去掉）的字符 if(str[i]!='0') printf("%c",str[i]); } printf("\n"); } return 0; }
2、万万没想到之抓捕孔连顺
题目描述
我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议
（1） 我们在字节跳动大街的N个建筑中选定3个埋伏地点。
（2）为了相互照应，我们决定相距最远的两名特工间的距离不超过D。
我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！
……
万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！
请听题：给定N（可选作为埋伏点的建筑物数）、D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
注意：
（1） 两个特工不能埋伏在同一地点
（2）三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
输入描述:
第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000) 第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）
输出描述:
一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模
输入例子1:
4 3 1 2 3 4
输出例子1:
4 • 1
例子说明1:
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
输入例子2:
5 19 1 10 20 30 50
输出例子2:
1
例子说明2:
可选方案 (1, 10, 20)
分析
该题目主要考察排列组合的相关知识点。每次输入一个位置点的时候，我们可以先将该位置选上，然后确定在该位置之前符合条件的位置中选出两个位置的组合数，注意对 99997867 取模，代码如下：
代码
#include<stdio.h> #include <iostream> #include <vector> using namespace std; //算出在该位置之前符合条件的位置中选出两个位置的组合数 long long int C(long long int n){ return (n-1) * n / 2; } int main(){ long long int n, d, count = 0; // scanf("%lld %lld",&n,&d); cin>> n>> d; vector<long long int> v(n); int i,j; for (i = 0, j = 0; i < n; i++) { // scanf("%lld",&v[i]); cin>> v[i]; //确定符合条件的位置 while (i >= 2 && (v[i] - v[j]) > d) { j++; } count += C(i - j); } // printf("%lld\n",count % 99997867); cout << count % 99997867; return 0; }
3、找零
题目描述
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为)的商品，请问最少他会收到多少硬币？
输入描述:
一行，包含一个数N。
输出描述:
一行，包含一个数，表示最少收到的硬币数。
输入例子1:
200
输出例子1:
17
例子说明1:
花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。
分析
先找大面值的零钱，在找小面值的零钱。
代码
#include<stdio.h> int main(){ int N,sum = 0; scanf("%d",&N); N = 1024 - N; while(N!=0){ if(N>=64) N-=64; else if(N>=16) N-=16; else if(N>=4) N-=4; else N-=1; sum++; } printf("%d\n",sum); return 0; }
4、雀魂启动！
问题描述
小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：
- 总共有36张牌，每张牌是1~9。每个数字4张牌。
- 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
- 14张牌中有2张相同数字的牌，称为雀头。
- 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）
例如：
1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌
1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。
现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。
输入描述:
输入只有一行，包含13个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最多出现4次。
输出描述:
输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0
输入例子1:
1 1 1 2 2 2 5 5 5 6 6 6 9
输出例子1:
9
例子说明1:
可以组成1,2,6,7的4个刻子和9的雀头
输入例子2:
1 1 1 1 2 2 3 3 5 6 7 8 9
输出例子2:
4 7
例子说明2:
用1做雀头，组123,123,567或456,789的四个顺子
输入例子3:
1 1 1 2 2 2 3 3 3 5 7 7 9
输出例子3:
0
例子说明3:
来任何牌都无法和牌
分析
该问题可用回溯算法来进行计算，但数据量不大，在这里我选择使用暴力法解题，主要使用三重嵌套循环来遍历所有情况，找出符合要求的结果。
代码
#include<stdio.h> int main(){ int ans=0,a[10]={0},i,j,k,temp,b[12]={0},flag=0; for(i=0;i<13;i++){ scanf("%d",&temp); a[temp]++; } //第一重循环，假设答案，假设应该取的牌为k for(k=1;k<10;k++){ //一种牌最多只能拥有四张 if(a[k]==4) continue; a[k]++;//取牌 //第二重循环，假设雀头 for(i=1;i<10;i++){ for(j=1;j<10;j++) b[j] = a[j]; ans = k; int f=0;//顺子和刻子的数量 //假设i为雀头 if(b[i]>=2){ b[i]-=2; //第三重循环，确定能否和牌 for(j=1;j<10;j++){ //刻子 if(b[j]>=3) { b[j]-=3; f++; } //顺子 while(b[j]>0&&b[j+1]>0&&b[j+2]>0){ b[j]--; b[j+1]--; b[j+2]--; f++; } //剪枝 if(b[j-1]>0&&b[j-1]<3&&j>1) break; } } //和牌 if(f==4) break; ans = 0; } if(ans!=0){ printf("%d ",ans); flag=1;//修改和牌标记 } a[k]--;//拟回溯 } if(flag==0) printf("0"); //未和牌 printf("\n"); return 0; }
