时间轴

2025-03-04

  1. P1421

题单在这里：

洛谷题单广场

https://www.luogu.com.cn/training/list

P1421 小玉买文具

题目描述

班主任给小玉一个任务，到文具店里买尽量多的签字笔。已知一只签字笔的价格是 $1$ 元 $9$ 角，而班主任给小玉的钱是 $a$ 元 $b$ 角，小玉想知道，她最多能买多少只签字笔呢。

输入格式

输入只有一行两个整数，分别表示 $a$ 和 $b$。

输出格式

输出一行一个整数，表示小玉最多能买多少只签字笔。

输入输出样例 #1

输入 #1

1
10 3

输出 #1

1
5

说明/提示

数据规模与约定

对于全部的测试点，保证 $0 \leq a \leq 10^4$，$0 \leq b \leq 9$。

题解

没啥好说的，毕竟是入门题，简单的小学数学。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

#define PEN_PRICE 19

int main(){

  int a=0;
  int b=0;
  int pen_num = 0;

  scanf("%d %d",&a,&b);

  pen_num = (a*10+b)/PEN_PRICE;
  printf("%d",pen_num);


}

C 中常见整数的数据的范围

不过这里还是要记下 C 中常见整数的数据的范围：

数据类型 字节数 十进制取值范围 科学计数法表示（约）
char 1 -128 ~ 127 -1.28×10² ~ 1.27×10²
unsigned char 1 0 ~ 255 0 ~ 2.55×10²
short 2 -32,768 ~ 32,767 -3.28×10⁴ ~ 3.27×10⁴
unsigned short 2 0 ~ 65,535 0 ~ 6.55×10⁴
int 4 -2,147,483,648 ~ 2,147,483,647 -2.15×10⁹ ~ 2.15×10⁹
unsigned int 4 0 ~ 4,294,967,295 0 ~ 4.29×10⁹
long (Linux 64 位) 8 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 ±9.22×10¹⁸
unsigned long 8 0 ~ 18,446,744,073,709,551,615 0 ~ 1.84×10¹⁹
long long 8 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 ±9.22×10¹⁸
unsigned long long 8 0 ~ 18,446,744,073,709,551,615 0 ~ 1.84×10¹⁹
  • long 的字节数在 不同平台上可能不同，如在 64 位 Linux 系统上通常为 8 字节。
  • 实际大小和范围由编译器及目标平台的 data model 决定，如 LP64（Linux）/LLP64（Windows）

P1000 超级玛丽游戏

题目背景

本题是洛谷的试机题目，可以帮助了解洛谷的使用。

题目描述

超级玛丽是一个非常经典的游戏。请你用字符画的形式输出超级玛丽中的一个场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###            ###
                ...........               #...#          #...#
               ##*#######                 #.#.#          #.#.#
            ####*******######             #.#.#          #.#.#
           ...#***.****.*###....          #...#          #...#
           ....**********##.....           ###            ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################
#...#......#.##...#......#.##...#......#.##------------------#
###########################################------------------#
#..#....#....##..#....#....##..#....#....#####################
##########################################    #----------#
#.....#......##.....#......##.....#......#    #----------#
##########################################    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#
##########################################    ############

输入格式

无

输出格式

如描述。

题解

printf换行打印

这个题目有点搞笑了。
每行 printf 有点蠢，这里用 c 语言换行打印的一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
int main() {
    printf(
    "                ********\n"
    "               ************\n"
    "               ####....#.\n"
    "             #..###.....##....\n"
    "             ###.......######              ###            ###\n"
    "                ...........               #...#          #...#\n"
    "               ##*#######                 #.#.#          #.#.#\n"
    "            ####*******######             #.#.#          #.#.#\n"
    "           ...#***.****.*###....          #...#          #...#\n"
    "           ....**********##.....           ###            ###\n"
    "           ....****    *****....\n"
    "             ####        ####\n"
    "           ######        ######\n"
    "##############################################################\n"
    "#...#......#.##...#......#.##...#......#.##------------------#\n"
    "###########################################------------------#\n"
    "#..#....#....##..#....#....##..#....#....#####################\n"
    "##########################################    #----------#\n"
    "#.....#......##.....#......##.....#......#    #----------#\n"
    "##########################################    #----------#\n"
    "#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#\n"
    "##########################################    ############\n"
    );
    return 0;
}

B2005 字符三角形

题目描述

给定一个字符，用它构造一个底边长 $5$ 个字符，高 $3$ 个字符的等腰字符三角形。

输入格式

输入只有一行，包含一个字符。

输出格式

该字符构成的等腰三角形，底边长 $5$ 个字符，高 $3$ 个字符。

输入输出样例 #1

输入 #1

1
*

输出 #1

1
2
3
*
 ***
*****

说明/提示

对于 $100 \%$ 的数据，输入的字符是 ASCII 中的可见字符。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>


int main(){
  char ch;

  scanf("%c",&ch);

  printf(
    "  %c  \n"
    " %c%c%c \n"
    "%c%c%c%c%c\n"
    ,ch,ch,ch,ch,ch,ch,ch,ch,ch);

}

printf

printf 函数详解：
下面是 printf() 函数的声明。

1
int printf(const char *format, ...)

参数

  • format — 这是字符串，包含了要被写入到标准输出 stdout 的文本。它可以包含嵌入的 format 标签，format 标签可被随后的附加参数中指定的值替换，并按需求进行格式化。
  • format 标签属性是
1
%[flags][width][.precision][length]specifier
格式字符 意义
a, A 以十六进制形式输出浮点数(C99 新增)。实例 printf(“pi=%a\n”, 3.14); 输出 pi=0x1.91eb86p+1。
d 以十进制形式输出带符号整数(正数不输出符号)
o 以八进制形式输出无符号整数(不输出前缀 0)
x,X 以十六进制形式输出无符号整数(不输出前缀 Ox)
u 以十进制形式输出无符号整数
f 以小数形式输出单、双精度实数
e,E 以指数形式输出单、双精度实数
g,G 以%f 或%e 中较短的输出宽度输出单、双精度实数
c 输出单个字符
s 输出字符串
p 输出指针地址
lu 32 位无符号整数
llu 64 位无符号整数
flags（标识） 描述
- 在给定的字段宽度内左对齐，默认是右对齐（参见 width 子说明符）。
+ 强制在结果之前显示加号或减号（+ 或 -），即正数前面会显示 + 号。默认情况下，只有负数前面会显示一个 - 号。
空格 如果没有写入任何符号，则在该值前面插入一个空格。
# 与 o、x 或 X 说明符一起使用时，非零值前面会分别显示 0、0x 或 0X。 与 e、E 和 f 一起使用时，会强制输出包含一个小数点，即使后边没有数字时也会显示小数点。默认情况下，如果后边没有数字时候，不会显示显示小数点。 与 g 或 G 一起使用时，结果与使用 e 或 E 时相同，但是尾部的零不会被移除。
0 在指定填充 padding 的数字左边放置零（0），而不是空格（参见 width 子说明符）。
width（宽度） 描述
(number) 要输出的字符的最小数目。如果输出的值短于该数，结果会用空格填充。如果输出的值长于该数，结果不会被截断。
* 宽度在 format 字符串中未指定，但是会作为附加整数值参数放置于要被格式化的参数之前。
.precision（精度） 描述
.number 对于整数说明符（d、i、o、u、x、X）：precision 指定了要写入的数字的最小位数。如果写入的值短于该数，结果会用前导零来填充。如果写入的值长于该数，结果不会被截断。精度为 0 意味着不写入任何字符。 对于 e、E 和 f 说明符：要在小数点后输出的小数位数。 对于 g 和 G 说明符：要输出的最大有效位数。 对于 s: 要输出的最大字符数。默认情况下，所有字符都会被输出，直到遇到末尾的空字符。 对于 c 类型：没有任何影响。 当未指定任何精度时，默认为 1。如果指定时不带有一个显式值，则假定为 0。
.* 精度在 format 字符串中未指定，但是会作为附加整数值参数放置于要被格式化的参数之前。
length（长度） 描述
h 参数被解释为短整型或无符号短整型（仅适用于整数说明符：i、d、o、u、x 和 X）。
l 参数被解释为长整型或无符号长整型，适用于整数说明符（i、d、o、u、x 和 X）及说明符 c（表示一个宽字符）和 s（表示宽字符字符串）。
L 参数被解释为长双精度型（仅适用于浮点数说明符：e、E、f、g 和 G）。

  • 附加参数

    根据不同的 format 字符串，函数可能需要一系列的附加参数，每个参数包含了一个要被插入的值，替换了 format 参数中指定的每个 % 标签。参数的个数应与 % 标签的个数相同。

  • 返回值

    如果成功，则返回写入的字符总数，否则返回一个负数。

P5708 三角形面积

题目描述

一个三角形的三边长分别是 $a$、$b$、$c$，那么它的面积为 $\sqrt{p(p-a)(p-b)(p-c)}$，其中 $p=\frac{1}{2}(a+b+c)$。输入这三个数字，计算三角形的面积，四舍五入精确到 $1$ 位小数。

输入格式

第一行输入三个实数 $a,b,c$，以空格隔开。

输出格式

输出一个实数，表示三角形面积。精确到小数点后 $1$ 位。

输入输出样例 #1

输入 #1

1
3 4 5

输出 #1

1
6.0

说明/提示

数据保证能构成三角形，$0\leq a,b,c\leq 1000$，每个边长输入时不超过 $2$ 位小数。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <math.h>

int main(){
  float a,b,c;
  float p = 0;
  float square = 0;

  scanf("%f %f %f",&a,&b,&c);
  p = (a+b+c)/2;
  square = sqrt((double)(p * ( p-a)*(p-b)* (p-c)));
  printf("%.1f",square);

}

没什么好说的，总结一下 c 语言 math 标准库吧

math.h

错误状态宏定义

在 <math.h> 中，有一些宏用于表示数学函数的错误状态：

宏 描述
HUGE_VAL 当函数结果溢出时返回的值（正无穷大）。此宏代表一个非常大的双精度浮点数，通常用来作为某些数学函数在结果超出可表示范围时的返回值。当一个函数的结果太大以至于无法用正常的浮点数表示（即发生上溢）时，会设置 errno 为 ERANGE（范围错误），并返回 HUGE_VAL 或其负值（对于负无穷大）。
HUGE_VALF 当函数结果溢出时返回的值（正无穷大，浮点型）
HUGE_VALL 当函数结果溢出时返回的值（正无穷大，长双精度）
INFINITY 正无穷大
NAN 非数字值（Not-A-Number）
FP_INFINITE 表示无穷大
FP_NAN 表示非数字值
FP_NORMAL 表示正常的浮点数
FP_SUBNORMAL 表示次正规数
FP_ZERO 表示零

库函数

下面列出了头文件 math.h 中定义的函数：

函数 描述
double acos(double x) 返回以弧度表示的 x 的反余弦。
double asin(double x) 返回以弧度表示的 x 的反正弦。
double atan(double x) 返回以弧度表示的 x 的反正切。
double atan2(double y, double x) 返回以弧度表示的 y/x 的反正切。y 和 x 的值的符号决定了正确的象限。
double cos(double x) 返回弧度角 x 的余弦。
double cosh(double x) 返回 x 的双曲余弦。
double sin(double x) 返回弧度角 x 的正弦。
double sinh(double x) 返回 x 的双曲正弦。
double tanh(double x) 返回 x 的双曲正切。
double exp(double x) 返回 e 的 x 次幂的值。
double frexp(double x, int *exponent) 把浮点数 x 分解成尾数和指数。返回值是尾数，并将指数存入 exponent 中。所得的值是 x = mantissa * 2 ^ exponent。
double ldexp(double x, int exponent) 返回 x 乘以 2 的 exponent 次幂。
double log(double x) 返回 x 的自然对数（基数为 e 的对数）。
double log10(double x) 返回 x 的常用对数（基数为 10 的对数）。
double modf(double x, double *integer) 返回值为小数部分（小数点后的部分），并设置 integer 为整数部分。
double pow(double x, double y) 返回 x 的 y 次幂。
double sqrt(double x) 返回 x 的平方根。
double ceil(double x) 返回大于或等于 x 的最小的整数值。
double fabs(double x) 返回 x 的绝对值。
double floor(double x) 返回小于或等于 x 的最大的整数值。
double fmod(double x, double y) 返回 x 除以 y 的余数。
函数名 作用 向哪边取整
round() 四舍五入 到最近整数
floor() 向下取整（不大于原数的最大整数） 向 -∞
ceil() 向上取整（不小于原数的最小整数） 向 +∞
trunc() 去除小数部分（直接截断） 向 0

常用数学常量

以下是 <math.h> 中定义的一些常用数学常量：

常量 值 描述
M_PI 3.14159265358979323846 圆周率 π
M_E 2.71828182845904523536 自然对数的底数 e
M_LOG2E 1.44269504088896340736 log2(e)
M_LOG10E 0.43429448190325182765 log10(e)
M_LN2 0.69314718055994530942 ln(2)
M_LN10 2.30258509299404568402 ln(10)
M_PI_2 1.57079632679489661923 π/2
M_PI_4 0.78539816339744830962 π/4
M_1_PI 0.31830988618379067154 1/π
M_2_PI 0.63661977236758134308 2/π
M_2_SQRTPI 1.12837916709551257390 2/√π
M_SQRT2 1.41421356237309504880 √2
M_SQRT1_2 0.70710678118654752440 1/√2

P5707 上学迟到

题目描述

学校和 yyy 的家之间的距离为 $s$ 米，而 yyy 以 $v$ 米每分钟的速度匀速走向学校。

在上学的路上，yyy 还要额外花费 $10$ 分钟的时间进行垃圾分类。

学校要求必须在上午 $\textrm{8:00}$ 到达，请计算在不迟到的前提下，yyy 最晚能什么时候出门。

由于路途遥远，yyy 可能不得不提前一点出发，但是提前的时间不会超过一天。

输入格式

一行两个正整数 $s,v$，分别代表路程和速度。

输出格式

输出一个 $24$ 小时制下的时间，代表 yyy 最晚的出发时间。

输出格式为 $\texttt{HH:MM}$，分别代表该时间的时和分。必须输出两位，不足前面补 $0$。

输入输出样例 #1

输入 #1

1
100 99

输出 #1

1
07:48

说明/提示

对于 $100\%$ 的数据，$1 \le s,v \le 10^4$。

题解

这题有两个点需要注意：

  1. 使用 ceil 函数时，s/v 是两个正整数相除，如果将结果再放入 ceil 中，相当于 ceil 什么也没做
  2. 考虑凌晨
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <math.h>


// 10 min to sort trash
#define OFFSET 10
// timeline is 8:00
#define TIMELINE 480


int main(){
  int s,v;
  int duration;
  // start timeline
  int timeline;


  scanf("%d %d",&s,&v);
  // 这里不能用s/v，因为s,v都是整数，是整数除法，直接舍去小数的
  duration = (int)ceil((double)s/v);
  // 总共需要的时间
  duration += OFFSET;

  timeline = TIMELINE - duration;
  // 考虑凌晨
  if(timeline < 0){
    timeline += 60*24;
  }

  int hour = timeline / 60;
  int minutes = timeline % 60 ;
  printf("%02d:%02d",hour,minutes);

}

P1424 小鱼的航程（改进版）

题目描述

有一只小鱼，它平日每天游泳 $250$ 公里，周末休息（实行双休日)，假设从周 $x$ 开始算起，过了 $n$ 天以后，小鱼一共累计游泳了多少公里呢？

输入格式

输入两个正整数 $x,n$，表示从周 $x$ 算起，经过 $n$ 天。

输出格式

输出一个整数，表示小鱼累计游泳了多少公里。

输入输出样例 #1

输入 #1

1
3 10

输出 #1

1
2000

说明/提示

数据保证，$1\le x \le 7$，$1 \le n\le 10^6$。

题解

用模拟是最简单的但是这里用了边界计算+通用部分计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#define SPEED 250

int main() {
  int x, n, workday=0,distance=0;

  scanf("%d %d", &x, &n);

  if(x+n-1<=7){ // 只有一周
    if(x>5){
      printf("0");
    }else if(x+n-1<=5){// 1<=x<=5
      workday += n;
    }else if(x+n-1>5){
      workday += 5 - x + 1;
    }
    distance += workday* SPEED;
    printf("%d",distance);
    return 0;
  }


  // 两周以上
  // 先算第一周，从周 x 开始
  if (x <= 5) {
    workday += 5 - x + 1;
  }else{
    workday += 0;
  }
  // 减去第一周的所有天数
  n = n - (7 - x + 1);
  // 之后的完整周数
  workday += (n / 7) * 5;
  // 最后一周是否满
  if (n % 7 > 0 && n % 7 < 5) {
    workday += n % 7;
  } else if (n % 7 >= 5) {
    workday += 5;
  }
  distance = workday *SPEED;
  printf("%d",distance);
}

P1055 [NOIP 2008 普及组] ISBN 号码

题目描述

每一本正式出版的图书都有一个 ISBN 号码与之对应，ISBN 码包括 $9$ 位数字、$1$ 位识别码和 $3$ 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 - 就是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言，例如 $0$ 代表英语；第一个分隔符 - 之后的三位数字代表出版社，例如 $670$ 代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以 $1$ 加上次位数字乘以 $2$ ……以此类推，用所得的结果 $ \bmod 11$，所得的余数即为识别码，如果余数为 $10$，则识别码为大写字母 $X$。例如 ISBN 号码 0-670-82162-4 中的识别码 $4$ 是这样得到的：对 067082162 这 $9$ 个数字，从左至右，分别乘以 $1,2,\dots,9$ 再求和，即 $0\times 1+6\times 2+……+2\times 9=158$，然后取 $158 \bmod 11$ 的结果 $4$ 作为识别码。

你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出 Right；如果错误，则输出你认为是正确的 ISBN 号码。

输入格式

一个字符序列，表示一本书的 ISBN 号码（保证输入符合 ISBN 号码的格式要求）。

输出格式

一行，假如输入的 ISBN 号码的识别码正确，那么输出 Right，否则，按照规定的格式，输出正确的 ISBN 号码（包括分隔符 -）。

输入输出样例 #1

输入 #1

1
0-670-82162-4

输出 #1

1
Right

输入输出样例 #2

输入 #2

1
0-670-82162-0

输出 #2

1
0-670-82162-4

说明/提示

2008 普及组第一题

题解

这题也没啥好说的，主要注意字符串分割函数 strtok 的用法吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <string.h>


int main(){
  // 9位数字，1位识别码，3个分隔符
  char input[14];
  char ISBN[14];
  char array[11] = "";
  char *token;
  int index = 0, num = 0;

  scanf("%s",input);
  strcpy(ISBN,input);

  token = strtok(ISBN, "-");
  while(token!=NULL){
    strcat(array,token);
    token = strtok(NULL, "-");
  }
  // 9是识别码,10是\0
  for(int i=0;i<9;i++){
    num += (array[i]-'0')*(i+1);
  }
  num %= 11;

  if((array[9]-'0')==num || (num ==10 && array[9]=='X')){
    printf("Right");
  }else{
    if(num==10){
      input[12] = 'X';
    }else{
      input[12] = '0'+num;
    }
    printf("%s",input);
  }

}

strtok

1
char *strtok(char *str, const char *delim)

参数
str: 要分割的字符串。在第一次调用时，传入要分割的字符串；后续调用时，传入 NULL，表示继续分割同一个字符串。
delim: 分隔符字符串。strtok() 会根据这个字符串中的任意一个字符来分割 str。

返回值
返回指向下一个标记的指针。如果没有更多的标记，则返回 NULL。

1
2
3
4
5
6
7
8
9
/* 获取第一个子字符串 */
token = strtok(str, s);

/* 继续获取其他的子字符串 */
while( token != NULL ) {
   printf( "%s\n", token );

   token = strtok(NULL, s);
}

注意事项

  1. 修改原字符串: strtok() 会修改传入的字符串，将分隔符替换为 \0（空字符）。因此，原始字符串会被破坏。
  2. 不可重入: strtok() 使用静态缓冲区来保存状态，因此它不是线程安全的。如果在多线程环境中使用，可以考虑使用 strtok_r()（可重入版本）。
  3. 连续分隔符: 如果字符串中有连续的分隔符，strtok() 会忽略它们，并返回下一个有效的标记。

可重入版本：strtok_r()
strtok_r() 是 strtok() 的可重入版本，它允许你在多线程环境中安全地使用。它的原型如下：

char strtok_r(char str, const char delim, char **saveptr);
saveptr: 是一个指向 char 的指针，用于保存分割的状态。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <string.h>

int main() {
    char str[] = "This is a sample string";
    char *token;
    char *saveptr;

    // 第一次调用 strtok_r，传入要分割的字符串
    token = strtok_r(str, " ", &saveptr);

    // 继续调用 strtok_r，直到返回 NULL
    while (token != NULL) {
        printf("%s\n", token);
        token = strtok_r(NULL, " ", &saveptr);
    }

    return 0;
}

P1009 阶乘之和

题目描述

用高精度计算出 $S = 1! + 2! + 3! + \cdots + n!$（$n \le 50$）。

其中 ! 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如，$5! = 5 \times 4 \times 3 \times 2 \times 1=120$。

输入格式

一个正整数 $n$。

输出格式

一个正整数 $S$，表示计算结果。

输入输出样例 #1

输入 #1

1
3

输出 #1

1
9

说明/提示

【数据范围】

对于 $100 \%$ 的数据，$1 \le n \le 50$。

【其他说明】

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 $n \le 20$，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

NOIP1998 普及组 第二题

题解

经典高精度计算，思路就是通过数组存放每一位，然后计算，如果采用直接定义静态数组的方式会更简便，不用考虑 realloc，速度应该也会更快，这里为了熟悉堆内存分配 API 还是用了堆内存方式处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <stdlib.h>
// num * right 结果存放在num中，返回num的长度len
int high_accuracy_multiply(int **num, int len, int right) {
  int carry = 0, i = 0, temp = 0;
  int *new_arr;
  while (1) {
    if (i <= len - 1) {
      temp = ((*num)[i] * right + carry) / 10;
      (*num)[i] = ((*num)[i] * right + carry) % 10;
      carry = temp;
      i++;
    } else if (i == len && carry != 0) {  // 最高位有进位但是没有容量了
      new_arr = (int *)realloc(*num, (len + 1) * sizeof(int));
      if (new_arr == NULL) {
        perror("realloc error");
        free(*num);
        exit(-1);
      } else {
        *num = new_arr;
      }
      len++;
      (*num)[i] = carry % 10;
      carry = carry / 10;
      i++;
    } else if (i == len && carry == 0) {
      break;
    }
  }
  return len;
}

// num1+num2结果存在res中,返回res的长度len
int high_accuracy_add(int num1[], int len1, int num2[], int len2, int **res) {
  int carry = 0, temp = 0;
  int *left, llen;
  int *right, rlen;
  int *new_arr;
  int *result;
  /**
   * find the longer one and name it as left ,the other as right
   */
  if (len1 >= len2) {
    left = num1;
    llen = len1;
    right = num2;
    rlen = len2;
  } else {
    left = num2;
    llen = len2;
    right = num1;
    rlen = len1;
  }

  result = (int *)malloc(llen * sizeof(int));

  /**
   * calcualte
   */
  for (int i = 0; i < llen; i++) {
    if (i < rlen) {
      temp = right[i];
    } else {
      temp = 0;
    }
    result[i] = (left[i] + temp + carry) % 10;
    carry = (left[i] + temp + carry) / 10;
  }
  if (carry != 0) {  // 最高位有进位
    new_arr = (int *)realloc(result, (llen + 1) * sizeof(int));
    if (new_arr == NULL) {
      perror("realloc error\n");
      free(result);
      exit(-1);
    } else {
      result = new_arr;
      llen++;
      result[llen - 1] = carry;
    }
  }

  if (*res == num2) {
    free(num2);
  } else if (*res == num1) {
    free(num1);
  }
  *res = result;
  return llen;
}

int main() {
  int n = 0;
  int *result, len;
  int *S, slen;

  scanf("%d", &n);

  /**
   * 计算阶乘并保存到factorial数组中，长度保存在lens中
   */
  result = (int *)malloc(sizeof(int));
  len = 1;
  result[0] = 1;

  S = (int *)malloc(sizeof(int));
  slen = 1;
  S[0] = 1;

  for (int i = 1; i < n; i++) {
    len = high_accuracy_multiply(&result, len, i + 1);
    slen = high_accuracy_add(result, len, S, slen, &S);
  }

  for (int i = slen - 1; i >= 0; i--) {
    printf("%d", S[i]);
  }
  return 0;
}

P1217 回文质数

题目描述

因为 $151$ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 $151$ 是回文质数。

写一个程序来找出范围 $[a,b] (5 \le a < b \le 100,000,000)$（一亿）间的所有回文质数。

输入格式

第一行输入两个正整数 $a$ 和 $b$。

输出格式

输出一个回文质数的列表，一行一个。

输入输出样例 #1

输入 #1

1
5 500

输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
5
7
11
101
131
151
181
191
313
353
373
383

说明/提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自 NOCOW。

USACO Training Section 1.5

产生长度为 $5$ 的回文数：

1
2
3
4
5
6
7
8
for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

题解

说明和提示里提示很明白了，要先找回文数再判断是不是质数，因为质数判断比回文数判断要耗时的多，不过直接暴力枚举好像也能过，只要跳过奇数就行

下面是 38ms 的解法, 注意检查质数时只需要判断到 sqrt(i)就行了(包括 sqrt(i))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

bool in(int left, int right, int num) { return num >= left && num <= right; }

bool is_prime(int num) {
  if (num <= 0 || num == 1) {
    return false;
  }
  // 只检查到sqrt(num)
  for (int i = 2; i * i <= num; i++) {
    if (num % i == 0) {
      return false;
    }
  }

  return true;
}

int main() {
  int a, b;
  int a_digit = 0, b_digit = 0, temp;
  // 5≤a<b≤100,000,000
  scanf("%d %d", &a, &b);

  /**
   * 十进制视角下的位数
   */
  temp = b;
  while (temp != 0) {
    temp /= 10;
    b_digit++;
  }
  temp = a;
  while (temp != 0) {
    temp /= 10;
    a_digit++;
  }
  /**
   * 生成a_digit~b_digit位的回文数
   */
  // 质数必定是奇数

  for (int i = a_digit; i <= b_digit; i++) {
    switch (i) {
      case 1:
        for (int d = 5; d <= 9; d += 2) {
          if (in(a, b, d) && is_prime(d)) {
            printf("%d\n", d);
          }
        }
        break;
      case 2:
        for (int d1 = 1; d1 <= 9; d1 += 2) {
          temp = d1 * 10 + d1;
          if (in(a, b, temp) && is_prime(temp)) {
            printf("%d\n", temp);
          }
        }
        break;

      case 3:
        for (int d1 = 1; d1 <= 9; d1 += 2) {
          for (int d2 = 0; d2 <= 9; d2++) {
            temp = d1 * 100 + d2 * 10 + d1;
            if (in(a, b, temp) && is_prime(temp)) {
              printf("%d\n", temp);
            }
          }
        }
        break;

      case 4:
        for (int d1 = 1; d1 <= 9; d1 += 2) {
          for (int d2 = 0; d2 <= 9; d2++) {
            temp = d1 * 1000 + d2 * 100 + d2 * 10 + d1;
            if (in(a, b, temp) && is_prime(temp)) {
              printf("%d\n", temp);
            }
          }
        }
        break;

      case 5:
        for (int d1 = 1; d1 <= 9; d1 += 2) {
          for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
              temp = d1 * 10000 + d2 * 1000 + d3 * 100 + d2 * 10 + d1;
              if (in(a, b, temp) && is_prime(temp)) {
                printf("%d\n", temp);
              }
            }
          }
        }
        break;

      case 6:
        for (int d1 = 1; d1 <= 9; d1 += 2) {
          for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
              temp = d1 * 100000 + d2 * 10000 + d3 * 1000 + d3 * 100 + d2 * 10 +
                     d1;
              if (in(a, b, temp) && is_prime(temp)) {
                printf("%d\n", temp);
              }
            }
          }
        }
        break;

      case 7:
        for (int d1 = 1; d1 <= 9; d1 += 2) {
          for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
              for (int d4 = 0; d4 <= 9; d4++) {
                temp = d1 * 1000000 + d2 * 100000 + d3 * 10000 + d4 * 1000 +
                       d3 * 100 + d2 * 10 + d1;
                if (in(a, b, temp) && is_prime(temp)) {
                  printf("%d\n", temp);
                }
              }
            }
          }
        }
        break;

      case 8:
        for (int d1 = 1; d1 <= 9; d1 += 2) {
          for (int d2 = 0; d2 <= 9; d2++) {
            for (int d3 = 0; d3 <= 9; d3++) {
              for (int d4 = 0; d4 <= 9; d4++) {
                temp = d1 * 10000000 + d2 * 1000000 + d3 * 100000 + d4 * 10000 +
                       d4 * 1000 + d3 * 100 + d2 * 10 + d1;
                if (in(a, b, temp) && is_prime(temp)) {
                  printf("%d\n", temp);
                }
              }
            }
          }
        }
        break;

      default:
        break;
    }
  }
}

P1075 质因数分解

题目描述

已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

输入一个正整数 $n$。

输出格式

输出一个正整数 $p$，即较大的那个质数。

输入输出样例 #1

输入 #1

1
21

输出 #1

1
7

说明/提示

$1 \le n\le 2\times 10^9$

NOIP 2012 普及组 第一题

题解

这题也是判断质数的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

bool is_prime(int num) {
  if (num <= 0 || num == 1) {
    return false;
  }
  // 只检查到sqrt(num)
  for (int i = 2; i * i <= num; i++) {
    if (num % i == 0) {
      return false;
    }
  }

  return true;
}

int main() {
  int n, temp;
  scanf("%d", &n);

  for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
      temp = n / i;
      if(is_prime(temp)){
        printf("%d",temp);
        return 0 ;
      }
    }
  }
}

P1427 小鱼的数字游戏

题目描述

小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字 $a_i$（长度不一定，以 $0$ 结束），记住了然后反着念出来（表示结束的数字 $0$ 就不要念出来了）。这对小鱼的那点记忆力来说实在是太难了，你也不想想小鱼的整个脑袋才多大，其中一部分还是好吃的肉！所以请你帮小鱼编程解决这个问题。

输入格式

一行内输入一串整数，以 $0$ 结束，以空格间隔。

输出格式

一行内倒着输出这一串整数，以空格间隔。

输入输出样例 #1

输入 #1

1
3 65 23 5 34 1 30 0

输出 #1

1
30 1 34 5 23 65 3

说明/提示

数据规模与约定

对于 $100\%$ 的数据，保证 $0 \leq a_i \leq 2^{31} - 1$，数字个数不超过 $100$。

题解

注意双指针的判断条件，如果用 lptr==rptr，则偶数个元素时会直接错过，必须用 lptr < rptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <stdlib.h>

int main() {
  int *arr, *new_arr;
  int capacity = 2;
  int temp;
  int index = 0;

  arr = (int *)malloc(capacity * sizeof(int));

  while (scanf("%d", &temp)) {
    if (temp == 0) {
      break;
    }

    // 超过arr存储的范围
    if (index == capacity) {
      capacity = capacity + 10;
      new_arr = (int *)realloc(arr, capacity * sizeof(int));
      if (new_arr == NULL) {
        perror("realloc error");
        free(arr);
        return -1;
      } else {
        arr = new_arr;
      }
    }

    arr[index++] = temp;
  }
  if (index == 0) {
    return 0;
  }

  capacity = index;
  new_arr = (int *)realloc(arr, capacity * sizeof(int));
  if (new_arr == NULL) {
    perror("realloc error");
    free(arr);
    return -1;
  } else {
    arr = new_arr;
  }

  int *lptr = arr, *rptr = arr + capacity - 1;

  while (lptr < rptr) {
    temp = *lptr;
    *lptr = *rptr;
    *rptr = temp;
    lptr++;
    rptr--;
  }

  for (int i = 0; i < capacity; i++) {
    printf("%d ", arr[i]);
  }
  free(arr);
  return 0;
}

P1320 压缩技术（续集版）

题目描述

设某汉字由 $N \times N$ 的 $\texttt 0$ 和 $\texttt 1$ 的点阵图案组成。

我们依照以下规则生成压缩码。连续一组数值：从汉字点阵图案的第一行第一个符号开始计算，按书写顺序从左到右，由上至下。第一个数表示连续有几个 $\texttt 0$，第二个数表示接下来连续有几个 $\texttt 1$，第三个数再接下来连续有几个 $\texttt 0$，第四个数接着连续几个 $\texttt 1$，以此类推……

例如: 以下汉字点阵图案：

1
2
3
4
5
6
7
0001000
0001000
0001111
0001000
0001000
0001000
1111111

对应的压缩码是： $\texttt {7 3 1 6 1 6 4 3 1 6 1 6 1 3 7}$ （第一个数是 $N$ ,其余各位表示交替表示 0 和 1 的个数，压缩码保证 $N \times N=$ 交替的各位数之和）

输入格式

汉字点阵图（点阵符号之间不留空格）。

输出格式

输出一行，压缩码。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
0001000
0001000
0001111
0001000
0001000
0001000
1111111

输出 #1

1
7 3 1 6 1 6 4 3 1 6 1 6 1 3 7

说明/提示

数据保证，$3\leq N\leq 200$。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define _GNU_SOURCE
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int main() {
  char *str = NULL;
  size_t len = 0;
  ssize_t nread;
  int type = 0;
  int tmp = 0;
  int N;

  nread = getline(&str, &len, stdin);
  // len = 8, 7个字符+\n
  if (nread != -1) {
    // 去掉换行符
    str[strcspn(str, "\n")] = '\0';
  } else {
    perror("geline failed\n");
    exit(-1);
  }
  N = strlen(str);
  printf("%d ", N);

  // 处理第一行
  for (int j = 0; j < N; j++) {
    if (str[j] - '0' == type) {
      tmp++;
    } else {
      type = type ^ 1;
      printf("%d ", tmp);
      tmp = 1;
    }
  }

  for (int i = 1; i < N; i++) {
    nread = getline(&str, &len, stdin);
    if (nread != -1) {
      // 去掉换行符
      str[strcspn(str, "\n")] = '\0';
    } else {
      perror("geline failed\n");
      exit(-1);
    }
    for (int j = 0; j < N; j++) {
      if (str[j] - '0' == type) {
        tmp++;
      } else {
        type = type ^ 1;
        printf("%d ", tmp);
        tmp = 1;
      }
    }
  }
  printf("%d ", tmp);
  return 0;
}

getline

getline() 的返回值是读取的字符数(包括换行符)

参数 含义
char **lineptr 指向一个 char* 指针（用来存储读入的字符串，函数内部会自动分配/扩展内存）
size_t *n 指向缓冲区大小（初始为 0），函数根据需要动态分配/扩展内存
FILE *stream 输入流，例如 stdin、文件句柄等

返回值

  • 成功：返回读取到的字符数（包括换行符 \n，但不包括终止符 \0）
  • 失败：返回 -1，并设置 errno

使用 getline 需要包含 GNU 扩展定义的 和 ，但更关键的是在 某些非 POSIX 平台（如 Windows 或老标准 C 编译器） 中，getline() 并不是标准 C 函数。
综合解决方法（适用于 Linux/GCC 环境）：
确保你包含了以下头文件：

1
2
3
4
5
6
7
8
9
10
11
12
// 可选：启用 GNU 扩展
#define _GNU_SOURCE

#include <stdio.h>
#include <stdlib.h>

// 使用strcspn
#include <string.h>

// 定义了 ssize_t 类型（带符号的 size_t），常用于 read, write, getline, readlink 等函数的返回值
// 是 POSIX 标准的一部分，不是 C 标准库的一部分，所以在 GNU/Linux 平台使用 POSIX API 时必须包含
#include <unistd.h>

strcspn

strcspn 是 C 标准库 中的一个字符串处理函数，用于查找目标字符串中第一个匹配指定字符集合的字符的位置。

  • 函数原型
1
2
3
#include <string.h>

size_t strcspn(const char *s, const char *reject);
  • 功能说明

它返回字符串 s 中第一个包含 reject 中任意字符的位置（索引），如果 s 中不包含 reject 中的任何字符，就返回 strlen(s)。

💡 “cspn” 全称是 complement span，意思是：返回“不是 reject 的最长前缀”长度

  • 示例
1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <string.h>

int main() {
    char str[] = "hello, world!";
    size_t pos = strcspn(str, ",!");

    printf("第一个 ',' 或 '!' 的位置是：%zu\n", pos);  // 输出 5
    return 0;
}

strspn

strspn 是 C 语言标准库 中的函数，用来计算一个字符串开头有多少字符全部属于指定的字符集合。
strspn 这个函数名来自 “string span” 的缩写，意思是“字符串的跨度”或“字符串中连续满足条件的前缀长度”。

对比 strcspn

函数名 含义说明
strspn span of characters in accept
strcspn span of characters not in reject

也就是说：

  • strspn(s, accept)：从开头开始，统计多少字符在 accept 中

  • strcspn(s, reject)：从开头开始，统计多少字符不在 reject 中

  • 函数原型

1
2
3
#include <string.h>

size_t strspn(const char *s, const char *accept);
  • 功能说明

strspn(s, accept) 会返回字符串 s 开头连续有多少个字符，全部都出现在 accept 中。

  1. 它不会跳过字符，也不会检查整个字符串；
  2. 一旦遇到一个不属于 accept 的字符，就停止统计；
  3. 返回值是一个 size_t 类型（即无符号整数），表示匹配的长度。
  • 示例
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <string.h>

int main() {
    const char *s = "abcabc123";
    const char *accept = "abc";

    size_t len = strspn(s, accept);
    printf("前缀长度为：%zu\n", len);  // 输出 6
    return 0;
}

  • ✨ 分析：
    字符串 s = “abcabc123”
    以 “a”, “b”, “c” 开头，刚好连着 6 个字符都在 “abc” 中
    第 7 个字符是 ‘1’，不在 “abc” 中 → 统计停止
    所以返回 6

  • 应用场景
    📌 检查字符串开头是否只包含某些字符

1
2
3
if (strspn(s, "0123456789") == strlen(s)) {
    printf("s 是纯数字\n");
}

📌 跳过前缀中所有合法字符

1
2
3
char *s = " \t\n hello";
s += strspn(s, " \t\n");  // 跳过所有空白字符
printf("剩下：%s\n", s);  // 输出 "hello"