提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

洛谷选题

• P1001 A+B Problem
• P1888 三角函数
• P1035 [NOIP2002 普及组] 级数求和
• P1047 [NOIP2005 普及组] 校门外的树
• P1125 [NOIP2008 提高组] 笨小猴
• P1321 单词覆盖还原
• P5738 【深基7.例4】歌唱比赛
• P1116 车厢重组
• P2670 [NOIP2015 普及组] 扫雷游戏
• P1618 三连击（升级版）
• P1067 [NOIP2009 普及组] 多项式输出
• P2249 【深基13.例1】查找
• P1102 A-B 数对
• P5461 赦免战俘
• P1255 数楼梯
• P1177 【模板】快速排序

题解

1.A+B problem

• P1001 A+B Problem
  这道题代码就不说了
  大家可以做一做：- P1601 A+B Problem（高精）

2.三角函数

考点：排序，求最大公约数
做题思路：
根据“大边对大角，小边对小角”我们就可以推出，较小边与斜边的正弦值就是较小锐角的正弦值。

#include<stdio.h>int main(void) {int a, b, c;                                    //记录边长int min = 0,max=0;                     //存最大值最小值int m, n, t;                                   //用于约分scanf("%d%d%d", &a, &b, &c);max = a;                                     //假设a是最小值if (max < b) max = b;                if (max < c) max = c;                  min = a;                                     //同理if (min > b) min = b;if (min > c) min = c;//辗转相除法m = max; n = min;                      //用mn代替max，min计算，//防止max，min计算后值改变t = m % n;                                  //求余数while (t != 0) {m = n;n = t;t = m % n;}printf("%d/%d", min/n, max/n);
}

3.级数求和

考点：循环

#include<stdio.h>int main(void) {int n = 0;           //分母double sum=0;        //记录和int k;                                                           scanf("%d", &k);while (sum <= k) {   //当sum<=k时执行循环n++;sum += 1.0 / n; //整数与浮点数运算时自动转化成浮点型，类似于强制转化}printf("%d", n);
}

4.校门外的树

考点：模拟
解法一：利用数组模拟：

#include <stdio.h>
int main(void) {int a[10001] = { 0 }, L, m, q, k, res = 0;scanf("%d %d", &L, &m);for (int i = 0; i < m; i++) {scanf("%d %d", &q, &k);for (int i = q; i <= k; i++)a[i] = 1;}for (int i = 0; i <= L; i++)if (a[i] == 0)res++;printf("%d", res);return 0;
}

解法二：排序减重

#include<stdio.h>
int main(void) {int n, m, i, j, k, t, sum = 0;int a[100][2];scanf("%d %d ", &n, &m);                                       //n为长度，m为区域数目for (i = 0; i < m; i++) {scanf("%d %d", &a[i][0], &a[i][1]);          //}for (i = 0; i < m; i++) {                                            //根据a[i][0],进行选择排序k = i;for (j = i; j < m; j++)if (a[k][0] > a[j][0])k = j;if (k != i) {t = a[k][1];a[k][1] = a[i][1];a[i][1] = t;t = a[k][0];a[k][0] = a[i][0];a[i][0] = t;}}for (i = 1; i < m; i++)                                                //调整区域范围，防止重合if (a[i][0] <= a[i - 1][1]) {                           //如果这个区域的左端//比上一个区域的右端小，有重合a[i][0] = a[i - 1][1] + 1;if(a[i][1]<a[i-1][1])                     //如果这个区域的右端也比上个区域的右端小，a[i][1] = a[i - 1][1];           //则舍弃这个区域，赋左右端一样的值}for (i = 0; i < m; i++) {                                              //计算总和if (a[i][1] >= a[i][0])sum += a[i][1] - a[i][0] + 1;}printf("%d", n - sum + 1);                                          //输出剩余return 0;
}

5.笨小猴

考点：字符串，统计

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
bool isprime(int n)//判断n是不是质数
{int i;if (n % 2 == 0 && n != 2 || n == 1) return false;for (i = 3; i * i <= n; i += 2) if (n % i == 0) return false;return true;
}int main(void)
{char str[110] = { 0 };int word[26] = { 0 };//记录26个字母是否出现int i, j, sum, maxn = 0, minn = 110;//maxn初值保证小于等于可能的最小值//minn初值保证大于 等于可能的最大值scanf("%s", str);int n = strlen(str); //求str长度for (i = 0; i < n; i++) {sum = 0;if (word[str[i] - 97] == 1)continue;//防止重复查找，这题也可以不写这部分word[str[i] - 97] = 1;  for (j = 0; j < n; j++) {//找与i位置的字母相同的字母//有的话sum++if (str[i] == str[j]) sum++;}if (maxn < sum && sum) maxn = sum;                         if (minn > sum && sum) minn = sum;                          }bool flag = isprime(maxn - minn); //判断maxn-minn是不是质数if (flag) {printf("Lucky Word\n%d", maxn - minn);}else {printf("No Answer\n0");}return 0;
}

6.单词覆盖还原

考点：模拟，字符串

#include<stdio.h>
#include<string.h>int main(){char str[256];int i,bount = 0,gcount = 0;//bcount保存boy，gcount保存girlscanf("%s",&str);for(i = 0; i < strlen(str); i++){                        if(str[i] == 'b' || str[i] == 'o' || str[i] == 'y') bount++;//遇到b,o,y字母计数增加 if(str[i] == 'b' && str[i+1] == 'o') bount--;//遇到bo连着,重复计数，总计数减一if(str[i] == 'o' && str[i+1] == 'y') bount--;//遇到oy连着,重复计数，总计数减一if(str[i] == 'g' || str[i] == 'i' || str[i] == 'r' || str[i] == 'l') gcount++;//同理if(str[i] == 'g' && str[i+1] == 'i') gcount--;if(str[i] == 'i' && str[i+1] == 'r') gcount--;if(str[i] == 'r' && str[i+1] == 'l') gcount--;}printf("%d\n%d",bount,gcount);return 0;
}

7.歌唱比赛

考点：数组

#include<stdio.h>int main() {int i, j, m, n, max=0, min=10, b[100][20],sum=0;double c = 0, mmax = 0;scanf("%d %d", &n, &m);for (i = 0; i < n; i++) {                                              //存入数据for (j = 0; j < m; j++) {scanf("%d", &b[i][j]);}}for (i = 0; i < n; i++) {                                               sum = 0;                                                              //初始化max = 0;min = 10;for (j = 0; j < m; j++) {                                        //求出每行的和，最大值，最小值sum += b[i][j];                       if (b[i][j] > max )max = b[i][j];if (b[i][j] < min) min = b[i][j];}c = (sum*1.0 - max - min) / (m - 2.0);               //计算每行的平均值if (mmax < c)mmax = c;                                    //是否是最大平均值}printf("%.2f", mmax);return 0;
}

8.车厢重组

考点：冒泡排序

#include<stdio.h>
void swap(int* a, int* b);
int main(void) {int a[100000];int n, i,j,count=0;scanf("%d", &n);for (i = 0; i < n; i++)scanf("%d", &a[i]);for (i = 0; i < n; i++) {                                //冒泡排序for (j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {swap(&a[j], &a[j + 1]);count++;   //记录交换次数}}}printf("%d", count);return 0;
}void swap(int* a, int* b) {                                            //交换函数int t;t = *a;*a = *b;*b = t;return;
}

9.扫雷游戏

考点：字符串

#include <stdio.h>
int a[105][105] = { 0 };                                                             //用于记录每个格子周围的地雷个数
int b[10000][2];                                                                       //用于记录位置
int main(void) {int n, m, i, j, k = 0, o;char ch;scanf("%d %d", &n, &m);for (i = 0; i < n; i++) {getchar();//清除回车for (j = 0; j < m; j++) {scanf("%c", &ch);if (ch == '*') {b[k][0] = i;//记录雷的位置b[k][1] = j;a[i][j] = -1;//雷所在位置雷个数记为-1k++;}}}for (i = 0; i < k; i++) {for (j = b[i][0] - 1; j < b[i][0] + 2; j++) {//遍历以雷为中心的3*3范围内的格子for (p = b[i][1] - 1; p < b[i][1] + 2; p++) {if (j < 0 || j >= n)//判断是否越界continue;  if (p < 0 || p >= m)//判断是否越界continue;if (a[j][p] != -1) //如果不是雷，那么a[j][p]++;}}}for (i = 0; i < n; i++) {//输出for (j = 0; j < m; j++) {if (a[i][j] == -1)printf("*");elseprintf("%d", a[i][j]);}printf("\n");}return 0;
}

10.三连击

考点：暴力枚举

#include <stdio.h>
#include<stdbool.h>
bool judge(int a, int b, int c)                                         //判断a,b,c三个数中是否有重复数字
{int arr[10] = { 0 };int sum = a*1000000+b*1000+c;                           //a,b,c都是3位数，用sum保存a,b,c全部数字while (sum > 0) {                                                     //取出sum的每个位置的数字              arr[sum % 10]++; sum /= 10;}for (int i = 1; i < 10; i++)                                        //判断是否有重复{if (arr[i] > 1 || arr[i] == 0)return false;}return true;
}int main()
{int a, b, c;int flag = 1;//用于判断是否有结果scanf("%d%d%d", &a, &b, &c);for (int i = 123; i * c / a <= 987; i++)//因为没有重复数字，所以上限为987，下限为123                     //三个数成比例，因此枚举i，其他两个用比例转化{if (judge(i, i * b / a, i * c / a)) //判断是否有重复{flag = 0;printf("%d %d %d\n", i, i * b / a, i * c / a);}}if (flag) printf("No!!!");return 0;
}

11.多项式输出

考点：细节

#include<stdio.h>
int main(void) {int n, i,m;int a[102];//数组a存系数scanf("%d", &n);m = n;//m为指数for (i = 0; i <= n; i++)//存入数据scanf("%d", &a[i]);if (a[0] == 1)//第一个位置单独判断printf("x^%d", m);else if (a[0] == -1)printf("-x^%d", m);else printf("%dx^%d", a[0], m);m--;for (i = 1; i <= n; i++) {                                    if (a[i] == 0) {//系数为0m--;continue;}if (m != 0&&m!=1)//指数m不为0或1{if (a[i] == 1)//系数为1printf("+x^%d", m);else if (a[i] == -1)//系数为-1printf("-x^%d", m);else if (a[i] > 0)//系数大于0printf("+%dx^%d", a[i], m);else //(a[i] < 0)//系数小于0printf("%dx^%d", a[i], m);}else if(m==0){//指数m为0if (a[i] > 0)printf("+%d", a[i]);else //(a[i] < 0)printf("%d", a[i]);}else {//指数m为1if (a[i] == 1)printf("+x");else if (a[i] == -1)printf("-x");else if (a[i] > 0)printf("+%dx", a[i]);else //(a[i] < 0)printf("%dx", a[i]);}m--;}return 0;
}

12.A-B数对

解题思路：排序后，遍历

#include<stdio.h>
typedef struct Node {int cha;int num;
}Node;//结构体cha变量保存相邻和前一个数的差值，
//num变量保存一个数出现次数
void Insert(int* a, int m, int n);//插入排序
Node a[2005];
int u[200005];
int main(void) {int n, c, i, m1, m2, k = 0, sum = 0, count = 0, prev;scanf("%d %d", &n, &c);scanf("%d", &m1);//对第一个数特殊处理u[0] = m1;a[k].cha = 0;a[k].num = 1;for (i = 1; i < n; i++) {scanf("%d", &m2);Insert(u, m2, i);}m1 = u[0];for (i = 1; i < n; i++) {//处理数据，保存相邻和前一个数的差值//保存一个数出现次数m2 = u[i];if (m1 == m2)a[k].num++;else {k++;a[k].cha = m2 - m1;a[k].num = 1;m1 = m2;}}//从prev开始，往后累加cha值，当和小于c时，继续往后加，//                        当和等于c时，符合条件，count增加，prev移动//                        当和大于c时，不符合条件，移动prev，sum归0prev = 0;for (i = 1; i <= k; i++) {sum += a[i].cha;if (sum > c) {sum = 0;prev++;i = prev;//i返回prev位置重新遍历}else if (sum == c) {count += a[prev].num * a[i].num;//count加上数字的个数相乘sum = 0;prev++;i = prev;}}printf("%d", count);return 0;
}
void Insert(int* a, int m, int n) {int i = n - 1;while (i > -1 && m < a[i]) {a[i + 1] = a[i];i--;}a[i + 1] = m;return;
}

13.赦免战俘

考点：递归，模拟

#include<stdio.h>
#include<math.h>
int a[1025][1025];
void chengfa(int x, int y,int x1,int y1);//"惩罚"函数 //(x,y)表示左上角坐标//(x1,y1)表示右下角坐标
int main(void) {int n,i,j;scanf("%d", &n);chengfa(0,0,pow(2,n),pow(2, n));//调用函数for (i = 0; i < pow(2, n); i++) {//输出结果for (j = 0; j < pow(2, n); j++) {printf("%d ", a[i][j]);}printf("\n");}return 0;
}void chengfa(int x, int y, int x1, int y1) {//“惩罚”函数//用递归处理//四个变量表示要处理的方阵的对角坐标if (x + 2 == x1) {                                                 //当要处理的方阵只有4格大小时a[x + 1][y] = 1;a[x][y + 1] = 1;a[x + 1][y + 1] = 1;return;}//将矩阵分成四份chengfa((x + x1) / 2, y, x1, (y + y1) / 2);//处理右上角的方阵chengfa(x, (y + y1) / 2, (x + x1) / 2, y1);//处理左下角的方阵chengfa((x + x1) / 2, (y + y1) / 2, x1, y1);//处理右下角的方阵
}

14.数楼梯

考点：斐波那契数列，递推，大数相加

#include<stdio.h> 	 /*思路：楼梯数为1 时 方法数为1楼梯数为2 时 方法数为2楼梯数为3 时 方法数为3楼梯数为4 时 方法数为5.........方法数按照"斐波那契数列"递增即a[n]=a[n-1]+a[n]*/
int a[5010];   	                                                               //数字很大，用数组存
int b[5010];                                                                            /*两个数交替增加，即a=a+b或b=b+a即可以"斐波那契数列"形式递增例：a=1,b=2   第一次 a=a+b a=3,b=2   第二次 b=a+ba=3,b=5   第三次 a=a+ba=8,b=5 .........a,b交替上升*/int judge(int* a, int*b, int top);                                                //实现a=a+b，top为最高位数
int output(int* a,int n);                                                             //输出结果的函数
int main(void) {int n,i,f=1,top=1;                                                   //f用于判断累加到a上还是累加到b上scanf("%d", &n);a[0] = 1;b[0] = 1;if (n < 2) {printf("%d",n);return 0;}for (i = 2; i <= n; i++) {if (f == 1) {top = judge(a,b, top);   //实现a=a+b}else {top = judge(b,a, top);   //交换a,b,实现b=b+a} f = -f;}if (f == 1)output(b,top);elseoutput(a,top);return 0;
}
int judge(int* a,int*b,int top) {int j;for (j = 0; j < top; j++) a[j] = a[j] + b[j];j = 0;while (a[j] >= 10||j<top) {    //进位a[j + 1] += a[j] / 10;a[j] %= 10;j++;}if (j > top||a[j]>0)top = j+1;  //调整最高位数return top;
}int output(int* a,int n) {int i;for (i = n - 1; i >= 0; i--)printf("%d", a[i]);return 0;
}

15.快速排序

考点：快排以及快排的优化

#include<stdio.h>
int a[100000];
void qsort(int left, int right);//快速排序，left为左端，right为右端
void Insertsort(int left, int right);//插入排序，数量少的时候插排优于快排
int main(void) {int n, i, j, t;scanf("%d", &n);for (i = 0; i < n; i++)scanf("%d", &a[i]);//导入数据qsort(0, n - 1);//调用函数for (i = 0; i < n; i++)printf("%d ", a[i]);//输出数据return 0;
}
void qsort(int left, int right) {//快排int i = left, j = right, t;int k;if (right <= left)return;if (right - left < 50) {//当数目小的时候用插排Insertsort(left, right);return;}t = a[left];a[left] = a[(i + j) / 2];a[(i + j) / 2] = t;k = a[left];while (i < j) {while (i < j && a[j] >= k)j--;a[i] = a[j];while (i < j && k >= a[i])i++;a[j] = a[i];}a[i] = k;i--;j++;while (i > left && a[i] == a[i - 1])i--;while (j < right && a[j] == a[j + 1])j++;qsort(left, i);qsort(j, right);
}void Insertsort(int left, int right) {//插排int t, i, j;for (i = left + 1; i <= right; i++) {t = a[i];j = i - 1;while (j >= left && t < a[j]) {a[j + 1] = a[j];j--;}a[j + 1] = t;}return;
}

16.查找

考点：二分查找

#include<stdio.h>                                             //二分查找，找中间数//如果偏大，再找左边区域的中间数(假设升序)//如果偏小，再找右边区域的中间数(假设升序)//以此类推，直到找到那个数或者区域内的数字个数为1
int a[1000010];
int b[100010];
int main(void) {int n, m, i, j, k, q, mid;scanf("%d %d", &n, &m);for (i = 0; i < n; i++)scanf("%d", &a[i]);for (q = 0; q < m; q++) {scanf("%d", &k);i = 0, j = n - 1;while (i <= j) {mid = (i + j) / 2;if (a[mid] < k)i = mid + 1;elsej = mid - 1;}if (a[i] == k)b[q] = i + 1;elseb[q] = -1;}for (i = 0; i < m - 1; i++)printf("%d ", b[i]);printf("%d\n", b[i]);return 0;
}