杂题题解~~

1、单词翻转

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
char s[N];int main()
{gets(s);int len = strlen(s), sum = 0;s[len] = ' ';for(int i = 0; i <= len; i++){if(s[i]!=' ')sum++;else{int p = i;for(int j = 1; j <= sum; j++){cout << s[--p];}sum = 0;if(i!=len)cout << ' ';}}cout << endl;return 0;
} 

---

2、导弹拦截

经过 11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。

当工作半径为 0 时，则能够拦截与它位置恰好相同的导弹。

但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。

而当天的使用代价，就是所有系统工作半径的平方和。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统尚处于试验阶段，所以只有两套系统投入工作。

如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

输入格式
第一行包含 4 个整数 x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为 (x1,y1)、(x2,y2)。

第二行包含 1 个整数 N，表示有 N 颗导弹。

接下来 N 行，每行两个整数 x、y，中间用一个空格隔开，表示一颗导弹的坐标 (x,y)，不同导弹的坐标可能相同。

输出格式
只有一行，包含一个整数，即当天的最小使用代价。

数据范围
1≤N≤105,所有坐标分量的绝对值都不超过 1000。

输入样例：
0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1
输出样例：
30
难度：中等
时/空限制：1s / 64MB
总通过数：176
总尝试数：373
来源：NOIP2010普及组

#include <iostream>
using namespace std;
#include <algorithm>
#include <cstring>
#include <cmath>
const int N = 100010;
int d[N];  // 自第i个导弹起到最后一个导弹，他们之间到第二个拦截系统最大的距离
struct dd
{int x;int y;int dis1;int dis2;
}daodan[N];int cmp(dd a, dd b)
{return a.dis1 < b.dis1;
}int main()
{int x1, x2, y1, y2, n;cin >> x1 >> y1 >> x2 >> y2;cin >> n;for(int i = 1; i <= n; i++){cin >> daodan[i].x >> daodan[i].y;daodan[i].dis1 = pow((daodan[i].x - x1),2) + pow((daodan[i].y - y1), 2);daodan[i].dis2 = pow((daodan[i].x - x2),2) + pow((daodan[i].y - y2), 2);}sort(daodan+1,daodan+1+n,cmp);int minx = daodan[n].dis1;d[n] = daodan[n].dis2;for(int i = n-1; i>=1; i--){if(daodan[i].dis2 > d[i+1]) d[i] = daodan[i].dis2;else d[i] = d[i+1];}for(int i = n - 1; i >= 1; i--){minx = min(minx,daodan[i].dis1 + d[i+1]);}cout << min(minx, d[1]);return 0;
}

---

3、N皇后问题（dfs)

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q…
…Q
Q…
…Q.

…Q.
Q…
…Q
.Q…

#include <iostream>
using namespace std;const int N = 11;
char q[N][N];
bool col[N], dg[2*N], udg[2*N];
int n;void dfs(int h)
{if(h==n){for(int i = 0; i < n; i++){for(int j = 0; j < n; j++)cout << q[i][j];cout << endl;}cout << endl;}for(int i = 0; i < n; i++){if(!col[i]&&!dg[h+i]&&!udg[n-h+i]){q[h][i] = 'Q';col[i] = dg[h+i] = udg[n-h+i] = true;dfs(h+1);col[i] = dg[h+i] = udg[n-h+i] = false;q[h][i] = '.';}}
}int main()
{cin >> n;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++)q[i][j] = '.';}dfs(0);return 0;
}

4、迷宫问题

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8
难度：简单
时/空限制：1s / 64MB
总通过数：23222
总尝试数：41241
来源：模板题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 110;
int g[N][N], f[N][N];
int n, m;void bfs(int a, int b)
{queue<PII> q;q.push({a,b});while(!q.empty()){PII start = q.front();q.pop();g[start.first][start.second] = 1;int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};for(int i = 0; i < 4; i++){int x = start.first + dx[i], y = start.second + dy[i];if(g[x][y] == 0){f[x][y] = f[start.first][start.second] + 1;g[x][y] = 1;q.push({x,y}); }}} cout << f[n][m];
}int main()
{memset(g ,1, sizeof(g));cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> g[i][j];bfs(1,1);return 0;
}

---

5、矩阵乘法

#include <iostream>
using namespace std;const int N = 110;
int a[N][N], b[N][N], c[N][N];
int n, m, k;int main()
{cin >> n >> m >> k;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> a[i][j];for(int i = 1; i <= m; i++) for(int j = 1; j <= k; j++)cin >> b[i][j];for(int i = 1; i <= n; i++){for(int j = 1; j <= k; j++){for(int p = 1; p <= m; p++){c[i][j] += a[i][p]*b[p][j];}cout << c[i][j] << ' ';}cout << endl;
}
return 0;
}

---

6、鸡兔同笼

一个笼子里面关了鸡和兔子（鸡有 22只脚，兔子有 4 只脚，没有残疾的）。已经知道了笼子里面脚的总数 a，问笼子里面至少有多少只动物，至多有多少只动物。

输入格式
一行，一个正整数 a (a < 32768)

输出格式
一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。

如果没有满足要求的答案，则输出两个 0，中间用一个空格分开。

Sample Input
20
Sample Output
5 10

#include <iostream>
using namespace std;int main()
{int a;cin >> a;if(a%2!=0) cout << "0 0" << endl;else{if(a%4==0) cout << a/4 << ' ' << a/2 << endl;else cout << a/4 + 1 << ' ' << a/2 << endl;}return 0;
}

---

7、图书管理员

#include <iostream>
#include <cmath>
using namespace std;
const int N = 1010;
int book[N];
int n, q;int main()
{cin >> n >> q;for(int i = 1; i <= n; i++) cin >> book[i];while(q--){int a, b, f = 1e9, e = 0;cin >> a >> b;for(int i = 1; i <= n; i++){int x = 0, y = 0, m = a;while(m){y = book[i]/(pow(10,--m));x = x*10 + y%10;}if(x==b){e = 1;f = min(f, book[i]);}}if(e) cout << f << endl;else cout << "-1" << endl;}return 0;
}

8、百钱买百鸡问题

我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题，该问题叙述如下：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？
翻译过来，意思是公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，现在要用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？

#include <stdio.h>
int main()
{int n, h = 0;    // 输入钱数和个数 nscanf("%d", &n);for(int i = 0; i <= n/5; i++){for(int j = 0; j <= n/3; j++){if((i+j+(n-i*5-j*3)*3==n)&&(i*5+j*3+(n-i-j)/3 == n)){printf("公鸡数为： %d, 母鸡数为： %d, 小鸡数为： %d \n", i, j, n-i-j); h = 1;}}}if(h == 0) printf("No answer\n");return 0;
}

9、求最小公倍数和最大公约数（辗转相除法）

// 单独求最大公约数 
#include <iostream>using namespace std;int main()
{int a, b, c;cin >> a >> b;if(a < b) swap(a,b);while(c = a % b, c != 0){a = b;b = c;}cout << b << endl;return 0;
}

#include <iostream>
using namespace std;int main()
{int a, b, c;cin >> a >> b;if(a < b) swap(a,b);int m = a, n = b;while(c = m % n, c != 0){m = b;n = c;}cout << "最大公约数为： " << n << endl;cout << "最小公倍数为： " << a*b/n << endl;return 0;
}

10、求最小公倍数、最大公约数（枚举法）

#include <stdio.h>
int main()
{int a, b;scanf("%d%d", &a,&b);int temp = (a>b)? b:a;while(temp){if(a%temp==0&&b%temp==0)break;temp--;}printf("最大公约数为： %d\n", temp);int p, q;p = (a>b)? a:b;q = (a>b)?b:a;temp = p;while(1){if(p%q==0)break;p+= temp;}printf("最小公倍数为： %d\n", p);return 0;
}

11、阶乘之和

题目描述
用高精度计算出 S = 1! + 2! + 3! + … + n!（n≤50）。

其中“!”表示阶乘，例如：5! =5×4×3×2×1。

输入格式
一个正整数 n。

输出格式
一个正整数 S，表示计算结果。

输入输出样例
输入
3
输出
9

// 首先 我想吐槽一下 洛谷的某些牛马大神 故意把简单的代码写的复杂，无关变量一个比一个多 真的是吐了！ 对新手非常不友好！
#include <iostream> 
using namespace std;
#include <cstring>
int a[1000], b[1000];  
/* 这为什么要开1000呢？  因为接下来我们是要用数组来存大数的每一位，但是可能有人会说 50！很大啊 1000是不是不太够？ 其实非也！这是一个很难理解的地方（自我认为） 50！中大概有12个0 这样想确实 1000 好像不太够但是数组是 1 到 1000  可以存 1000个0！ 最大 可以是 1000个 9  这不比12个0 大的多吗？ 所以开1000 或者说 开 15 都是没问题的！我为什么要强调这个？ 因为一开始我也不会做，我看人家的题解，人家没有解释为什么开1000，让我纠结了好久，所以我深知懵逼的滋味！*/
// 求阶乘 可以在草稿纸上模拟一下
void mult(int *a, int c)
{int t = 0;  // t表示进位for(int i = 1; i <= 1000; i++){a[i] = a[i] * c + t;t = a[i] / 10;a[i] %= 10;}
}
// 求大数之和
void add(int *a, int *b)
{int t = 0;  // t表示进位for(int i = 1; i <= 1000; i++){b[i] += a[i] + t;t = b[i] / 10;b[i] %= 10;}
}
int main()
{int n;cin >> n;memset(a, 0, sizeof(a));  // 最开始要初始化所有位为0memset(b, 0, sizeof(b)); // +1a[1] = 1; // 这个是因为 0！ = 1， for(int i = 1; i <= n; i++){mult(a, i);add(a, b);}bool flag = 0;  // 标记，下面会说清楚for(int i = 1000; i >= 1; i--){if(b[i]!=0) flag = 1；/* 在上面的阶乘等操作中，我们不难发现，数组的第一个数存的是最低位数，但是我们人类的习惯是高位在前，因此要倒叙输出！ 并且 从数组的后面开始，我们会发现后面的有些数组元素还是0， 因为我们的大数没有大到那个程度， 故i一直往前走，直到遇到不为0的地方，（因为数的最高位不会为0， 如果为0， 那么数就会降一级）， 这个时候flag = 1告诉电脑，这个地方开始，就要输出数了！*/if(flag == 1) cout << b[i];}cout << endl;return 0;
}

12、到底有多二？（真的二）

一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值。如果这个数是负数，则程度增加0.5倍；如果还是个偶数，则再增加1倍。例如数字-13142223336是个11位数，其中有3个2，并且是负数，也是偶数，则它的犯二程度计算为：3/11×1.5×2×100%，约为81.82%。本题就请你计算一个给定整数到底有多二。

输入格式：
输入第一行给出一个不超过50位的整数N。

输出格式：
在一行中输出N犯二的程度，保留小数点后两位。

输入样例：
-13142223336
结尾无空行
输出样例：
81.82%
结尾无空行

这道题弄了我好久，各种调试，就是有数据过不了，到后来，我突发奇想，02怎么样？ -02怎么样？ 果不其然！ 我没有考虑到前导零的情况！之前是直接用while求数字长度的，但是从这题我发现这样有一个bug，如果数字中间就有一个零呢？ 这样不就提前终止循环了吗？ 搜嘎！！！ 所以 用字符串来做，就不用担心前导零和中间零的问题了！ Prefect！！！

#include <iostream>
#include <cstring>
using namespace std;
char q[60];
int main()
{int len, count = 0;double total;cin >> q;len = strlen(q);for(int i = 0; i < len; i++){if(q[i] == '2') count ++;}if(q[0] == '-'){if((q[len-1]-'0') % 2 == 0) total = count * 1.0 /( len - 1) * 1.5 * 2;else total = count * 1.0 / (len - 1) * 1.5; // 这里len - 1 是因为第一个元素是- 符号，所以要减一！}else{if((q[len-1]-'0') % 2 == 0) total = count * 1.0 / len * 2;else total = count * 1.0 / len;}printf("%.2f%%", total*100);return 0;
}

13、 正整数A+B

这题真他妈坑！ 一定要好好审题！ 而且要加强刷字符串类型的题目
题的目标很简单，就是求两个正整数A和B的和，其中A和B都在区间[1,1000]。稍微有点麻烦的是，输入并不保证是两个正整数。

输入格式：
输入在一行给出A和B，其间以空格分开。问题是A和B不一定是满足要求的正整数，有时候可能是超出范围的数字、负数、带小数点的实数、甚至是一堆乱码。

注意：我们把输入中出现的第1个空格认为是A和B的分隔。题目保证至少存在一个空格，并且B不是一个空字符串。

输出格式：
如果输入的确是两个正整数，则按格式A + B = 和输出。如果某个输入不合要求，则在相应位置输出?，显然此时和也是?。

输入样例1：
123 456
结尾无空行
输出样例1：
123 + 456 = 579
结尾无空行
输入样例2：
22. 18
输出样例2：
? + 18 = ?
输入样例3：
-100 blabla bla…33
输出样例3：
? + ? = ?

#include <iostream>
#include <cstring>
using namespace std;
int main()
{string S;getline(cin, S);int flag_1 = 1, flag_2 = 1, A = 0, B = 0, t;for(int i = 0; i < S.length(); i++){if(S[i] == ' '){t = 1;if(i==0)flag_1 = 0;for(int j = i - 1; j >= 0; j--){if(S[j] < '0' || S[j] > '9'){flag_1 = 0;break;}else{A += (S[j] - '0') * t;t *= 10;}}if(A > 1000 || A < 1) flag_1 = 0;t = 1;for(int j = S.length() - 1; j > i; j--){if(S[j] < '0' || S[j] > '9'){flag_2 = 0;break;}else{B += (S[j] - '0') * t;t *= 10; }}if(B > 1000 || B < 1)  flag_2 = 0; break;}}if(flag_1&&flag_2) printf("%d + %d = %d", A, B, A+B);else if(flag_2) printf("? + %d = ?", B);else if(flag_1) printf("%d + ? = ?", A);else printf("? + ? = ?");return 0;
}

14、出生年

题目的许多细节 现在的我还把握不住 ε=(´ο｀)))唉

以上是新浪微博中一奇葩贴：“我出生于1988年，直到25岁才遇到4个数字都不相同的年份。”也就是说，直到2013年才达到“4个数字都不相同”的要求。本题请你根据要求，自动填充“我出生于y年，直到x岁才遇到n个数字都不相同的年份”这句话。

输入格式：
输入在一行中给出出生年份y和目标年份中不同数字的个数n，其中y在[1, 3000]之间，n可以是2、或3、或4。注意不足4位的年份要在前面补零，例如公元1年被认为是0001年，有2个不同的数字0和1。

输出格式：
根据输入，输出x和能达到要求的年份。数字间以1个空格分隔，行首尾不得有多余空格。年份要按4位输出。注意：所谓“n个数字都不相同”是指不同的数字正好是n个。如“2013”被视为满足“4位数字都不同”的条件，但不被视为满足2位或3位数字不同的条件。

输入样例1：
1988 4
结尾无空行
输出样例1：
25 2013
结尾无空行
输入样例2：
1 2
输出样例2：
0 0001

#include <iostream>
#include <cstring>
using namespace std;int judge(int year)
{int a[10], count = 0;memset(a, 0, sizeof(a));for(int i = 1; i <= 4; i++){a[year%10] ++;year /= 10;}for(int i = 0; i < 10; i++){if(a[i]!=0) count ++;}return count;
}
int main()
{int y, n;cin >> y >> n;int m = y;while(1){if(judge(m) == n){printf("%d %.4d", m - y, m);break;}m ++;}return 0;
}

15、 倒数第N个字符串 （天梯赛）

给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。例如当 L 为 3 时，序列为 { aaa, aab, aac, …, aaz, aba, abb, …, abz, …, zzz }。这个序列的倒数第27个字符串就是 zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。

输入格式：
输入在一行中给出两个正整数 L（2 ≤ L ≤ 6）和 N（≤10
5
）。

输出格式：
在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。

输入样例：
3 7417
结尾无空行
输出样例：
pat

#include <iostream>
using namespace std;
int q[10];
int main()
{int L, N;cin >> L >> N;N = N - 1;for(int i = L; i >= 1; i--){q[i] = N % 26;N /= 26;}for(int i = 1; i <= L; i++)printf("%c", 'z' - q[i]);return 0;
}

16、福到了（天梯赛）

“福”字倒着贴，寓意“福到”。不论到底算不算民俗，本题且请你编写程序，把各种汉字倒过来输出。这里要处理的每个汉字是由一个 N × N 的网格组成的，网格中的元素或者为字符 @ 或者为空格。而倒过来的汉字所用的字符由裁判指定。

输入格式：
输入在第一行中给出倒过来的汉字所用的字符、以及网格的规模 N （不超过100的正整数），其间以 1 个空格分隔；随后 N 行，每行给出 N 个字符，或者为 @ 或者为空格。

输出格式：
输出倒置的网格，如样例所示。但是，如果这个字正过来倒过去是一样的，就先输出bu yong dao le，然后再用输入指定的字符将其输出。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int main()
{char c;int n, flag = 1;cin >> c >> n;vector<string>v(n);getchar();for(int i = 0; i < n; i++){getline(cin,v[i]);}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(v[i][j] != v[n-1-i][n-1-j]){flag = 0;break;}}}if(flag == 1) cout << "bu yong dao le" << endl;for(int i = n-1; i >= 0; i--){for(int j = n-1; j >= 0; j--){if(v[i][j] != ' ') cout << c;else cout << ' ';}if(i!=0) cout << endl;}return 0;
}

17、九宫格输入法

假设有九宫格输入法键盘布局如下：

[ 1,.?! ] [ 2ABC ] [ 3DEF ]
[ 4GHI ] [ 5JKL ] [ 6MNO ]
[ 7PQRS ] [ 8TUV ] [ 9WXYZ ]
[ 0空 ]
注意：中括号[ ]仅为了表示键盘的分隔，不是输入字符。每个中括号中，位于首位的数字字符即是键盘的按键，按一下即可输入该数字字符。多次按同一个键，则输入的字符依次循环轮流，例如按两次3，则输入D；按5次7，则输入S；按6次2，则输入A。按键0的输入组合是0和空格字符，即按两次0输入空格。

你需要对于给定的按键组合，给出该组合对应的文本。

输入格式:
输入在一行中给出数个字符的按键组合（例如 999 表示按3次9），每个字符的按键组合之间用空格间隔，最后一个输入法组合之后以换行结束。输入数据至少包括一个字符的按键组合，且输入总长度不超过500个字符。

输出格式:
在一行中输出该按键组合对应的文本。

输入样例:
22 5555 22 666 00 88 888 7777 4444 666 44
结尾无空行
输出样例:
ALAN TURING

#include <iostream>
#include <cstring>
using namespace std;
int main()
{char a[10][10]= {"0 ", "1,.?!", "2ABC", "3DEF", "4GHI", "5JKL", "6MNO", "7PQRS", "8TUV", "9WXYZ"};char b[510];while(scanf("%s", b) != EOF){int m = strlen(b)%strlen(a[b[0] - '0']);if(m==0) m = strlen(a[b[0] - '0']);printf("%c", a[b[0] - '0'][m-1]);}return 0;
}

18、单词长度

你的程序要读入一行文本，其中以空格分隔为若干个单词，以.结束。你要输出每个单词的长度。这里的单词与语言无关，可以包括各种符号，比如it’s算一个单词，长度为4。注意，行中可能出现连续的空格；最后的.不计算在内。

输入格式：
输入在一行中给出一行文本，以.结束

提示：用scanf("%c",…);来读入一个字符，直到读到.为止。

输出格式：
在一行中输出这行文本对应的单词的长度，每个长度之间以空格隔开，行末没有最后的空格。

输入样例：
It’s great to see you here.
结尾无空行
输出样例：
4 5 2 3 3 4

#include <iostream>
#include <cstring>
using namespace std;
int main()
{char c;int wordlength = 0, flag = 1;while(1){scanf("%c", &c);if(c == ' '){if(wordlength != 0){if(flag != 1){cout << ' ';}cout << wordlength;wordlength = 0;flag = 0;}continue;}if(c == '.'){if(wordlength != 0){if(flag!=1)cout << ' ';cout << wordlength;}break;}wordlength ++;}return 0;
}

19、棋盘覆盖（分治）

在一个2k∗2k（k为正整数，k<=10，length=2k）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格（其坐标为a,b，分别代表行坐标号和列坐标号），以及有四种L型骨牌（如下图）。求用若干块这种L型骨牌实现除该特殊点棋盘的全覆盖。（本题要求采用分治算法做）


输入格式:
输入三个数，分别是a,b,length.

输出格式:
输出整个棋盘。其中特殊方格填为0，然后铺棋盘的顺序为：先铺四个子棋盘交界的部分，然后递归的对每个子棋盘按照左上，右上，右下，左下的顺时针顺序铺满棋盘。每一块骨牌中三个方格数字相同，按照顺序标号，即第一块骨牌全标为1，第二块骨牌全标为2，…，以此类推。输出的每个数占4个场宽，右对齐。

输入样例:
1 1 4

表示：特殊格子为（1，1），棋盘有4行4列。

输出样例:
0 2 3 3
2 2 1 3
5 1 1 4
5 5 4 4

提示：先铺三个1，再铺三个2，…，最后铺三个5（即先处理子问题交界的地方，再处理左上，右上，右下，左下的子问题）.

#include <iostream>
using namespace std;
int board[10010][10010];
int count = 1;void chessboard(int x, int y, int dx, int dy, int n)
{if(n==1)return;int s = n/2;int t = count ++;if(dx < x + s && dy < y + s){chessboard(x, y, dx, dy, s);}else{board[x + s - 1][y + s - 1] = t;chessboard(x, y, x + s - 1, y + s - 1, s);}if(dx < x + s && dy >= y + s){chessboard(x, y + s, dx, dy, s);} else{board[x + s - 1][y + s] = t;chessboard(x, y + s, x + s - 1, y + s, s);}if(dx >= x + s && dy >= y + s){chessboard(x + s, y + s, dx, dy, s);}else{board[x + s][y + s] = t;chessboard(x + s, y + s, x + s, y + s, s);}if(dx >= x + s && dy < y + s){chessboard(x + s, y, dx, dy, s);}else{board[x + s][y + s - 1] = t;chessboard(x + s, y, x + s, y + s - 1, s);}
}
int main()
{int dx, dy, n;cin >> dx >> dy >> n;chessboard(1, 1, dx, dy, n);for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)printf("%4d", board[i][j]);cout << endl;}return 0;
}

20、 循环日程表（分治）

设有N个选手进行循环比赛，其中N=2
M
，要求每名选手要与其他N−1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N−1天，要求每天没有选手轮空。

输入格式:
输入：M(M<=7)。

输出格式:
输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。

输入样例:
3
结尾无空行
输出样例:
在这里给出相应的输出。例如：

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

#include <iostream>
#include <cmath>
using namespace std;
int q[10010][10010];
int main()
{double n;  // 点睛之笔！cin >> n;int m = pow(2,n);q[0][0] = 1;int h = 1;while(n--){for(int i = 0; i < h; i++){for(int j = 0; j < h; j++)q[i+h][j] = q[i][j] + h;}for(int i = 0; i < h; i++){for(int j = 0; j < h; j++)q[i+h][j+h] = q[i][j];}for(int i = 0; i < h; i++){for(int j = 0; j < h; j++)q[i][j+h] = q[i+h][j];}h *= 2;}n = pow(n, 2);for(int i = 0; i < m; i++){for(int j = 0; j < m; j++)cout << q[i][j] << ' ';cout << endl;}return 0;
}

总结：
在用pow函数时， pow函数的参数是double型，如果用int型的话，结果可能会出错！！！
当然 在算2的几次方时，我们也可以用左移运算符来算！下面给出用左移运算符的代码

#include <iostream>
#include <cmath>
using namespace std;
int q[10010][10010];
int main()
{int n;cin >> n;int m = 1 << n; // 在这 n就要求是int型了 否则会报错！q[0][0] = 1;int h = 1;while(n--){for(int i = 0; i < h; i++){for(int j = 0; j < h; j++)q[i+h][j] = q[i][j] + h;}for(int i = 0; i < h; i++){for(int j = 0; j < h; j++)q[i+h][j+h] = q[i][j];}for(int i = 0; i < h; i++){for(int j = 0; j < h; j++)q[i][j+h] = q[i+h][j];}h *= 2;}n = pow(n, 2);for(int i = 0; i < m; i++){for(int j = 0; j < m; j++)cout << q[i][j] << ' ';cout << endl;}return 0;
}

21、P1957 口算练习题

题目描述
王老师正在教简单算术运算。细心的王老师收集了i道学生经常做错的口算题，并且想整理编写成一份练习。 编排这些题目是一件繁琐的事情，为此他想用计算机程序来提高工作效率。王老师希望尽量减少输入的工作量，比如5+8的算式最好只要输入5和8，输出的结果要尽量详细以方便后期排版的使用，比如对于上述输入进行处理后输出 5+8=13 以及该算式的总长度6。王老师把这个光荣的任务交给你，请你帮他编程实现以上功能。

输入格式
第一行为数值i

接着的i行为需要输入的算式，每行可能有三个数据或两个数据。

若该行为三个数据则第一个数据表示运算类型，a表示加法运算，b表示减法运算，c表示乘法运算，接着的两个数据表示参加运算的运算数。

若该行为两个数据，则表示本题的运算类型与上一题的运算类型相同，而这两个数据为运算数。

输出格式
输出2*i行。对于每个输入的算式，输出完整的运算式及结果，第二行输出该运算式的总长度

输入输出样例
输入 #1复制
4
a 64 46
275 125
c 11 99
b 46 64
输出 #1复制
64+46=110
9
275+125=400
11
11*99=1089
10
46-64=-18
9

#include <cctype>
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
int main()
{char s[110], ch[110], k;int n;cin >> n;while(n--){int x, y;cin >> s;if(isalpha(s[0])){k = s[0];cin >> x >> y;}else{x = atoi(s);cin >> y;}memset(ch, 0, sizeof(ch));if(k=='a')sprintf(ch, "%d+%d=%d", x, y, x + y);else if(k=='b')sprintf(ch, "%d-%d=%d", x, y, x-y);else if(k=='c')sprintf(ch, "%d*%d=%d", x, y, x*y);cout << ch << endl << strlen(ch) << endl;}return 0;
}

22、P5734 【深基6.例6】文字处理软件

题目描述
你需要开发一款文字处理软件。最开始时输入一个字符串（不超过 100 个字符）作为初始文档。可以认为文档开头是第 0 个字符。需要支持以下操作：

1 str：后接插入，在文档后面插入字符串 str，并输出文档的字符串。

2 a b：截取文档部分，只保留文档中从第 a 个字符起 b 个字符，并输出文档的字符串。

3 a str：插入片段，在文档中第 a 个字符前面插入字符串 str，并输出文档的字符串。

4 str：查找子串，查找字符串 str 在文档中最先的位置并输出；如果找不到输出 -1。

为了简化问题，规定初始的文档和每次操作中的 str 都不含有空格或换行。最多会有 q(q\le100)q(q≤100) 次操作。

输入格式
无

输出格式
无

输入输出样例
输入 #1复制
4
ILove
1 Luogu
2 5 5
3 3 guGugu
4 gu
输出 #1复制
ILoveLuogu
Luogu
LuoguGugugu
3

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{int n;cin >> n;string s;cin >> s;while(n--){int x;cin >> x;if(x==1){string c;cin >> c;s += c;cout << s << endl;}else if(x==2){int a, b;cin >> a >> b;string c;c = s.substr(a,b);s = c;cout << s << endl;}else if(x==3){int a;cin >> a;string c;cin >> c;s.insert(a,c);cout << s << endl;}else if(x==4){string c;cin >> c;if(s.find(c) < s.size())cout << s.find(c) << endl;else cout << -1 << endl;}}return 0;
}

22、装箱问题（贪心策略）

假设有N项物品，大小分别为s
1
​
、s
2
​
、…、s
i
​
、…、s
N
​
，其中s
i
​
为满足1≤s
i
​
≤100的整数。要把这些物品装入到容量为100的一批箱子（序号1-N）中。装箱方法是：对每项物品, 顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程，并输出每个物品所在的箱子序号，以及放置全部物品所需的箱子数目。

输入格式：
输入第一行给出物品个数N（≤1000）；第二行给出N个正整数s
i
​
（1≤s
i
​
≤100，表示第i项物品的大小）。

输出格式：
按照输入顺序输出每个物品的大小及其所在的箱子序号，每个物品占1行，最后一行输出所需的箱子数目。

输入样例：
8
60 70 80 90 30 40 10 20
结尾无空行
输出样例：
60 1
70 2
80 3
90 4
30 1
40 5
10 1
20 2
5

#include <iostream>
using namespace std;
int a[1010], b[1010];int main()
{int n, j;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];b[i] = 0;}for(int i = 1; i <= n; i++){for(j = 1; j <= n; j++){if(b[j] + a[i] <= 100) break;}b[j] += a[i];cout << a[i] << ' ' << j << endl;}j = 1;while(b[j]!=0) j++;cout << j - 1 << endl;return 0;
} 

这里 原本用结构体做，但是后面被烦死了，看了一下dalao的题解，知道可以用两个数组来操作，使得思路更加清晰，代码也好敲了许多！dalao不愧是dalao！ （知道解题思路和写出解题过程是两回事！！！）

23、小红的彩排

由于学校的迎新典礼快要到了，小红想要安排一个节目在迎新典礼上，以表示她对新生们的欢迎。。。
在小红的召集下，有n个同学愿意参加这个节目，在这个节目中需要所有的同学都站成一排，并且已经安排好了他们每个人在队列里的位置，其中第i个人的身高为H
i
​
(1≤i≤n)。
但因为这些同学的身高可能参差不齐，由于是表演，当然观赏性要高才行，所以小红不得不动用某些特殊手段将某些身高不合适的同学换成具有特定身高的同学。
由于小红的特殊手段很特殊，因此她可以将任意一个同学的身高换成他想要的任意身高。
小红认为，对于一个队列H，每个i(1≤i<n)，都满足H
i
​
+1=H
i+1
​
，则认为是漂亮的。
由于特殊手段很特殊，小红想要尽可能减少其使用次数，因此你能帮小红计算出最少需要使用几次特殊手段使得队列是漂亮的吗？

输入格式:
第一行输入一个正整数T，表示共有T组测试数据。
对于每组测试数据：
第一行包含一个正整数n，代表这个队列是由n位同学组成的。
第二行包含n个正整数，其中第i个正整数H i表示开始第i个同学的身高为Hi

输出格式:
对于每组测试数据，输出一行一个正整数，代表最少需要使用几次特殊手段使得队列是漂亮的。

输入样例:
在这里给出一组输入。例如：

2
5
1 2 4 4 5
5
1 2 3 4 5
结尾无空行
输出样例:
在这里给出相应的输出。例如：

1
0
结尾无空行
对于所有测试数据保证：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int q[N];
int main()
{int n;cin >> n;for(int i = 0; i < n; i++){cin >> q[i];q[i] -= i;}sort(q, q+n);int ans = 1,maxans=1;for(int i = 1; i < n; i++){if(q[i]==q[i-1])ans++;else{if(ans>maxans)maxans  = ans;ans = 1;}}if(ans>maxans)maxans = ans;cout << n-maxans;return 0;
}

24、第K大的数（基于快读思想）

给定一个长度为nn的整数数列，输出其中第kk大的数。

Input
第一行两个数n, k，分别表示1≤n≤10 与 k (1≤k≤n)。

第二行包含n个整数，表示整个序列。数据保证整数均在int范围内。

Output
仅一行，包含1个整数，表示整个序列中第k大的数。

Example
Input
5 2
3 1 2 4 5
Output
4

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e7 + 10;
int n,k,a[N];
inline int read()
{int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x<<1) + (x<<3) + (ch^48);ch = getchar();}return x * f;
}
int finding(int low,int high,int k)
{if(low==high)return a[low];int i=low,j=high;int mid=(low+high)>>1;int x=a[mid];while(i<=j){while(a[i] > x)i++;while(a[j] < x)j--;if(i<=j){swap(a[i],a[j]);i++;j--;}}if(k<=j)return finding(low,j,k);else if(k>=i)return finding(i,high,k);elsereturn a[k];
}
int main()
{n=read();k=read();for(int i=1; i<=n; i++) a[i]=read();cout<<finding(1,n,k)<<endl;return 0;
}

**这道题很烦! **