Jacky's Blog Jacky's Blog
  • 首页
  • 关于
  • 项目
  • 大事记
  • 留言板
  • 友情链接
  • 分类
    • 干货
    • 随笔
    • 项目
    • 公告
    • 纪念
    • 尝鲜
    • 算法
    • 深度学习
  • 6
  • 1

OJ 感想

Jacky
20 6 月, 2020
目录
  1. 一、基本知识
    1. 1. 基本框架
    2. 2. 代码标准
    3. 3. 输入与输出
    4. 4. t 组测试数据
    5. 4. EOF
    6. 5. 整形的自增与自减
  2. 二、基本操作
    1. 1. 冒泡排序
    2. 2. 比较两个浮点数相等问题
    3. 3. 数字分解
    4. 4. 闰年
    5. 5. 回文数
    6. 6. 素数
    7. 7. 因子
    8. 8. 完数
    9. 9. 递归
    10. 10. 动态规划
    11. 11. 格式化输出
    12. 12. ctype.h
    13. 13. string.h
    14. 14. limits.h
    15. 15. while (1)
    16. 16. 强制类型转换
    17. 17. 常用输入写法
  3. 三、进阶操作
    1. 1. 插入排序
    2. 2. 动态矩阵(指针与堆内存的分配)
    3. 3. 不使用临时变量在两个变量之间互相交换值
    4. 4. 碰撞检测
    5. 5. switch
    6. 6. 实现 string.h 内部分函数
    7. 7. 指针
    8. 8. 函数指针
    9. 9. 利用整形数组的键作为标记元素
    10. 10. 结构体
    11. 11. 十六进制转十进制
  4. 四、常见错误
  5. 五、特别注意
  6. 六、后记与总结
  7. 七、参考资料与文献

在家上网课的前三周,我把这个学期的OJ题都做完了。然后这两个月就没写过几行 C,再过几周就要期末考试了,所以打算做个总结。由于本人水平有限,解题所用的方法不是最优。

一、基本知识

1. 基本框架

#include<stdio.h>

int main() {
    printf("Hello World!");
    return 0;
}

2. 代码标准

C99 标准,需要注意的是这个标准是支持在 for 循环内初始化变量的。

for (int i = 0; i < t; i++) {};

但是在某些编辑器(比如 Dev-C++)没设置好代码标准会报错

'for' loop initial declarations are only allowed in C99 or C11 mode

则应该代码标准或者修改代码,在循坏外部初始化变量。

int i;
for (i = 0; i < t; i++) {};

3. 输入与输出

你的程序应该从标准输入 stdin(‘Standard Input’)获取输出 并将结果输出到标准输出 stdout(‘Standard Output’).例如,在C语言可以使用 ‘scanf’ ,在C++可以使用’cin’ 进行输入;在C使用 ‘printf’ ,在C++使用’cout’进行输出.

深圳技术大学在线判题教学平台 Online Judge FAQ

4. t 组测试数据

#include<stdio.h>

int main() {
    int t;
    scanf("%d", &t);
    while (t--){
        // your code
    }
    return 0;
}
#include<stdio.h>

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++){
        // your code
    }
    return 0;
}

下面我们来一个题的输入输出

输入
测试次数T
每组测试数据为15位身份证号
输出
对每组测试数据,给出升位后的18位身份证号。
样例输入
2
530102200508011
432831641115081
样例输出
53010219200508011X 
432831196411150810

初学的时候我就碰到这个问题,输出是在每个测试实例结束前输出,还是所有输入数据都输入结束之后输出?

OJ 感想-Jacky's Blog
每个测试实例结束前输出
OJ 感想-Jacky's Blog
全部数据输入完成后输出

经过测试,上述两种方法都可以顺利通过OJ

OJ 感想-Jacky's Blog
OJ 感想-Jacky's Blog

以下为测试时使用的代码

//
//  main.c
//  身份证升位(字符串)
//
//  Created by Jacky on 2020/3/17.
//  Copyright © 2020 Jacky. All rights reserved.
//

/*
 题目描述
 第一代身份证十五位数升为第二代身份证十八位数的一般规则是:
 第一步,在原十五位数身份证的第六位数后面插入19 ;
 第二步,按照国家规定的统一公式计算出第十八位数,作为校验码放在第二代身份证的尾号。
 校验码计算方法:
 将身份证前十七位数分别乘以7、9、10、5、8、4、2、1、6、3、7、9、10、5、8、4、2,
 将这十七位数字和系数相乘的结果相加,用加出来的和除以11,看看余数是多少。
 余数只可能有0、1、2、3、4、5、6、7、8、9、10这十一个数字,其分别对应的最后一位身
 份证的号码为1、0、X、9、8、7、6、5、4、3、2,
 这样就得出了第二代身份证第十八位数的校验码。
 输入15位身份证号,对其升位,输出升位后的18位身份证号。
 
 输入
 测试次数T
 每组测试数据为15位身份证号
 输出
 对每组测试数据,给出升位后的18位身份证号。
 
 样例输入
 2
 530102200508011
 432831641115081
 样例输出
 53010219200508011X
 432831196411150810
 */

#define OLD 15
#define NEW 18
#include <stdio.h>

int main() {
    int t, d[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2}, tmp = 0;
    char input[OLD+1], id[NEW+1], verify_code[] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'};
    
    scanf("%d", &t);
    while (t--) {
        tmp = 0;
        scanf("%s", input);
        for(int i = 0; i < 6; i++) {
            id[i] = input[i];
        }
        // 第7, 8位
        id[6] = '1';
        id[7] = '9';
        for(int i = 6; i < OLD; i++) {
            id[i+2] = input[i];
        }
        
        for (int i = 0; i < NEW - 1; i++) {
            tmp += (id[i] - '0') * d[i];
        }
        tmp = tmp % 11;
        id[17] = verify_code[tmp];
        // don't forget \0
        id[18] = '\0';
        printf("%s\n", id);
    }
    
    return 0;
}
//
//  main.c
//  身份证升位(字符串)
//
//  Created by Jacky on 2020/3/17.
//  Copyright © 2020 Jacky. All rights reserved.
//

/*
 题目描述
 第一代身份证十五位数升为第二代身份证十八位数的一般规则是:
 第一步,在原十五位数身份证的第六位数后面插入19 ;
 第二步,按照国家规定的统一公式计算出第十八位数,作为校验码放在第二代身份证的尾号。
 校验码计算方法:
 将身份证前十七位数分别乘以7、9、10、5、8、4、2、1、6、3、7、9、10、5、8、4、2,
 将这十七位数字和系数相乘的结果相加,用加出来的和除以11,看看余数是多少。
 余数只可能有0、1、2、3、4、5、6、7、8、9、10这十一个数字,其分别对应的最后一位身
 份证的号码为1、0、X、9、8、7、6、5、4、3、2,
 这样就得出了第二代身份证第十八位数的校验码。
 输入15位身份证号,对其升位,输出升位后的18位身份证号。
 
 输入
 测试次数T
 每组测试数据为15位身份证号
 输出
 对每组测试数据,给出升位后的18位身份证号。
 
 样例输入
 2
 530102200508011
 432831641115081
 样例输出
 53010219200508011X
 432831196411150810
 */

// 测试用
#define OLD 15
#define NEW 18
#include <stdio.h>
#include <string.h>
int main() {
    int t, d[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2}, tmp = 0;
    char input[OLD+1], id[NEW+1], verify_code[] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'}, ans[100][NEW+1];
    
    scanf("%d", &t);

    for (int i = 0; i < t; i++) {
        tmp = 0;
        scanf("%s", input);
        for(int i = 0; i < 6; i++) {
            id[i] = input[i];
        }
        // 第7, 8位
        id[6] = '1';
        id[7] = '9';
        for(int i = 6; i < OLD; i++) {
            id[i+2] = input[i];
        }
        
        for (int i = 0; i < NEW - 1; i++) {
            tmp += (id[i] - '0') * d[i];
        }
        tmp = tmp % 11;
        id[17] = verify_code[tmp];
        // don't forget \0
        id[18] = '\0';
        strcpy(ans[i], id);
        //printf("%s\n", id);
        
    }
    
    for (int i = 0; i < t; i++) {
        printf("%s\n", ans[i]);
    }
    
    return 0;
}

因此,可以推断 OJ 在判题的时候比对的是程序最后输出的结果,为了简化程序,每次测试实例结束后就可以打印出答案。

4. EOF

文件结尾(英语:End of File,缩写为EOF),是操作系统无法从数据源读取更多数据的情形。数据源通常为文件或流。[1]

在C语言中,EOF不是特殊字符,而是一个定义在头文件stdio.h的常量,一般等于-1。在Linux系统之中,EOF根本不是一个字符,而是当系统读取到文件结尾,所返回的一个信号值(也就是-1)

stdio.h 内有 define

#define EOF (-1)

Linux 中,在新的一行的开头,按下 Ctrl-D,就代表 EOF(如果在一行的中间按下 Ctrl-D,则表示输出”标准输入”的缓存区,所以这时必须按两次 Ctrl-D);Windows 中,Ctrl-Z 表示 EOF。[2]

来一道开心猫的例题

//
//  main.c
//  开心猫的字符串(字符串)
//
//  Created by Jacky on 2020/3/17.
//  Copyright © 2020 Jacky. All rights reserved.
//

/*
 题目描述
 开心猫在喵星小学终于以优异的成绩考取了喵星加力顿中学,从此开始学习地球传统猫咪们的叫声,然而开心猫的野心不只是在地球做一只温顺的猫咪,他决定学会人类的语言然后攻打地球。
 正在深圳大学计软楼239学习的噗噗猫觉得他怕是失了志,为此开心猫很不服气,头很铁得打开了噗噗猫得笔记本,他发现本子上有很多“szu”和“SZU”的字符串,并觉得前者相比与后者十分的不合适。
 于是开心猫很皮,把本子上所有的“szu”都改成了“SZU”,现给定本子上所有的字符串,问经过开心猫“一顿操作”之后的字符串是什么。
 
 要求自定义函数实现字符串中szu改SZU的功能。
 
 输入
 每行输入一串字符串,字符串的长度小于等于60;
 输入结束标志为文件结束符(EOF)。
 
 输出
 输出一行字符串代表修改后的字符串。
 
 样例输入
 szuacm
 Szuu
 abc
 样例输出
 SZUacm
 Szuu
 abc
 */

#define N 60
#include <stdio.h>

int main() {
    char input[N], a;
    while (scanf("%s", input) != EOF) {
        a = 0;
        while (input[a] != '\0' && a + 2 < N) {
            if (input[a] == 's' && input[a+1] == 'z' && input[a+2] == 'u') {
                input[a] = 'S';
                input[a+1] = 'Z';
                input[a+2] = 'U';
            }
            a++;
        }
        printf("%s\n", input);
    }
    return 0;
}

5. 整形的自增与自减

int i = 0, a;
a = i++; // a = 0;
i = 0;
a = ++i; // a = 1;

即先取值后自增自减或者先自增自减再取值的区别

二、基本操作

1. 冒泡排序

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。[3]
for (int a = 0; a < length - 1; a++) {
            for (int b = 0; b < length - 1 - a; b++) {
                if (input[b] > input[b+1]) {
                    tmp = input[b+1];
                    input[b+1] = input[b];
                    input[b] = tmp;
                }
            }
}

2. 比较两个浮点数相等问题

两个浮点数由于计算机内部表示的原因可能略有微小的误差,不能用==判定相等。浮点数判定相等用 |a-b| < e , e为足够小的数。

这个 e 在 float.h, double.h 内分别被定义为 FLT_EPSILON 和 DBL_EPSILON,如果题目给定了 e 为 0.01

则可以在代码开头 #define e 0.01,下面为示例函数

#define EPSILON 0.01

int isEqual(double a, double b) {
    if (fabs(a-b) < EPSILON) {
        return 1;
    }
    return 0;
}

3. 数字分解

以三位数为例,得到百位直接/100,得到十位用/10,得到个位 %10

#include <stdio.h>

int main() {
    int a, b, c, input;
    
    scanf("%d", &input);
    
    a = input / 100;
    b = input / 10;
    c = input % 10;
    
    printf("%d%d%d\n", c, b, a);

    return 0;
}

4. 闰年

可以被4整除同时不能被100整除(普通闰年)或者能被400整除(世纪闰年)

int isLeapYear(int y) {
    return (y % 4 == 0 && y % 100 != 0 ) || y % 400 == 0;
}

5. 回文数

从左到右读这个数与从右到左读这个数是一样的。例如12321、1221都是回文数。

下面是判断回文数的代码,从整形的角度解,如果用字符串应该也是可以的。

int d(int n) {
    int d = 1;
    while (n >= 10) {
        d *= 10;
        n /= 10;
    }
    return d;
}

int isPalindrome(int n, int div) {
    int a, b;
    while (n != 0) {
        a = n / div;
        b = n % 10;
        if (a!=b) {
            return 0;
        }
        // 掐头去尾
        n %= div;
        n /= 10;
        div /= 100;
    }
    return 1;
}

6. 素数

一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。

#include <math.h>

int isPrimeNumber(int n) {
    int flag = 1;
    if (n > 1) {
        for (int i = 2; i <= sqrt((double)n); i++) {
            if (n % i == 0) {
                flag = 0;
                break;
            }
        }
    } else {
        flag = 0;
    }
    return flag;
}

7. 因子

假如整数n除以m,结果是无余数的整数,那么我们称m就是n的因子。 需要注意的是,唯有被除数,除数,商皆为整数,余数为零时,此关系才成立。反过来说,我们称n为m的倍数。[4]

8. 完数

一个数如果恰好等于它的因子之和,这个数就称为”完数”。 例如,6的因子为1、2、3,而6=1+2+3,因此6是”完数”。

/*
 题目描述
 一个数如果恰好等于它的因子之和,这个数就称为"完数"。 例如,6的因子为1、2、3,而6=1+2+3,因此6是"完数"。 编程序找出N之内的所有完数,并按下面格式输出其因子:
 输入
 N
 输出
 ? its factors are ? ? ?
 样例输入
 1000
 样例输出
 6 its factors are 1 2 3
 28 its factors are 1 2 4 7 14
 496 its factors are 1 2 4 8 16 31 62 124 248
 */
#include <stdio.h>

int main() {
    int n, sum, a, factor[10000] = {0};
    scanf("%d", &n);
    for (int i = 6; i <= n; i++) {
        // 后面的数因子肯定比前面多,不用清零数组
        sum = 0;
        a = 0;
        for (int j = 1; j <= i / 2; j++) {
            if (i % j == 0) {
                sum += j;
                factor[a++] = j;
            }
        }
        if (i == sum) {
            printf("%d its factors are ", i);
            for (int k = 0; k < a; k++) {
                printf("%d ", factor[k]);
            }
            printf("\n");
        }
    }
    return 0;
}

9. 递归

递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。[5]

下面是一个算斐波那契数列(递归)的函数。

int f(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return f(n-1) + f(n-2);
}

10. 动态规划

动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。[6]

这批OJ题涉及到的动态规划比较入门,算斐波那契数列(动态规划),下面是代码。

int fib(int n) {
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

11. 格式化输出

格式字符说明
d, i十进制,整数(负数输出符号)
o八进制,整数(无前导0)
x, X十六进制,整数,无符号(无前导0x)x输出小写字母,X输出大写字母
u十进制,无符号,整数(unsigned)
c一个字符
s字符串
ffloat, double
e, E指数形式输出实数,e(1.2e+02),E(1.2E+02)
g, G指数形式输出实数,g(1.2e+2),G(1.2E+2)
printf 函数中用到的格式字符[7]

12. ctype.h

ctype.h 是 C 标准函数库的头文件,定义了一些字符串的函数可以方便解题。

函数描述
isalpha(x)x 是否为字母
isalnum(x)x 是否为“字符数字”e.g. ‘1’, ‘0’
isspace(x)x 是否是空格
islower(x)x 是否小写
isupper(x)x 是否大写
isdigit(x)x 是否为十进制数字 e.g. 1, 0
tolower(x)将 x 转换为小写
toupper(x)将 x 转换为大写
ctype.h 常用函数

13. string.h

函数描述
strlen(x)返回字符串 x 的长度
strcmp(x, y)比较字符串 x, y 是否相等相等时返回 0
strcat(x, y)将字符串 y 追加到 x 后面
strcpy(x, y)将字符串 y 拷贝到 x
string.h 常用函数

14. limits.h

宏值描述
INT_MAX32768整型最大值
INT_MIN-32768整型最小值
limits.h 常用宏

15. while (1)

一个无限循环,如果需要跳出循环,在满足条件后 break; 即可

16. 强制类型转换

转换变量的类型

float a = 1;
int b;
b = (int) a;

17. 常用输入写法

输入一个整数 scanf(“%d”, &t);

输入一个字符 scanf(“%c”, &c);

输入一个不带空格的字符串 scanf(“%s”, input);

输入一个带空格的字符串 gets(a);

模拟 gets 函数

char a[10000];
while ((t = getchar())!= '\n') {
   a[i++];
}

三、进阶操作

1. 插入排序

// N 为数组长度
int *sort(int array[]) {
    int p, c;
    for (int i = 1; i < N; i++) {
        p = i - 1;
        c = array[i];
        while ( p >= 0 && array[p] > c) {
            array[p + 1] = array[p];
            p--;
        }
        array[p + 1] = c;
    }
    return array;
}

2. 动态矩阵(指针与堆内存的分配)

利用 (int *)malloc(n * sizeof(int)) 可以定义一个长度为 n 的 int 一维数组。

(int **)malloc(n * sizeof(int)) 可以定义一个长度为 n 的 int 二维数组。

free(x) 将数组 x 的内存释放。

/*
 题目描述
 未知一个整数矩阵的大小,在程序运行时才会输入矩阵的行数m和列数n
 要求使用指针,结合new方法,动态创建一个二维数组,并求出该矩阵的最小值和最大值,可以使用数组下标法。
 不能先创建一个超大矩阵,然后只使用矩阵的一部分空间来进行数据访问、
 创建的矩阵大小必须和输入的行数m和列数n一样
 
 输入
 第一行输入t表示t个测试实例
 第二行输入两个数字m和n,表示第一个矩阵的行数和列数
 第三行起,连续输入m行,每行n个数字,表示输入第一个矩阵的数值
 依次输入t个实例
 
 输出
 每行输出一个实例的最小值和最大值
 
 样例输入
 2
 2 3
 33 22 11
 66 88 55
 3 4
 19 38 45 14
 22 65 87 31
 91 35 52 74
 样例输出
 11 88
 14 91
 */

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

int main() {
    int t, m, n, **p, min, max;
    scanf("%d", &t);
    while (t--) {
        min = INT_MAX;
        max = INT_MIN;
        scanf("%d %d", &m, &n);
        p = (int **)malloc(m * sizeof(int));
        for (int i = 0; i < m; i++) {
            p[i] = (int *)malloc(n * sizeof(int));
            for (int j = 0; j < n; j++) {
                scanf("%d", &p[i][j]);
                if (p[i][j] > max) {
                    max = p[i][j];
                }
                if (p[i][j] < min) {
                    min = p[i][j];
                }
            }
        }
        
        printf("%d %d\n", min, max);
        
        for (int i = 0; i < m; i++) {
            free(*(p + i));
        }
    }
    return 0;
}

3. 不使用临时变量在两个变量之间互相交换值

/*
 题目描述
 输入三个整数,然后按照从大到小的顺序输出数值。
 
 要求:用三个指针分别指向这三个整数,排序过程必须通过这三个指针来操作,不能直接访问这三个整数
 
 输出时,必须使用这三个指针,不能使用存储三个整数的变量
 
 输入
 第一行输入t表示有t个测试实例
 
 第二行起,每行输入三个整数
 
 输入t行
 
 输出
 每行按照从大到小的顺序输出每个实例
 
 在每行中,每个数据输出后都带有一个空格,即使该行最后一个数据输出后也要再输出一个空格
 
 样例输入
 3
 2 4 6
 88 99 77
 111 333 222
 样例输出
 6 4 2
 99 88 77
 333 222 111
 */

#include <stdio.h>

void f(int *x, int *y) {
    if (*x < *y) {
        *x = *x + *y;
        *y = *x - *y;
        *x = *x - *y;
    }
}

int main() {
    int t, a, b, c, *x = &a, *y = &b, *z = &c;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d", x, y, z);
        f(x, y);
        f(x, z);
        f(y, z);
        printf("%d %d %d \n", *x, *y, *z);
    }
    return 0;
}

4. 碰撞检测

 一般规则的物体碰撞都可以处理成矩形碰撞,实现的原理就是检测两个矩形是否重叠。

 矩形1的参数是:左上角的坐标是(x1,y1),宽度是w1,高度是h1;

 矩形2的参数是:左上角的坐标是(x2,y2),宽度是w2,高度是h2。

 在检测时,数学上可以处理成比较中心点的坐标在x和y方向上的距离和宽度的关系。

 即两个矩形中心点在x方向的距离的绝对值小于等于矩形宽度和的二分之一,同时y方向的距离的绝对值小于等于矩形高度和的二分之一。

 x方向:| (x1 + w1 / 2) – (x2 +w2/2) | <= |(w1 + w2) / 2|

 y方向:| (y1 + h1 / 2 ) – (y2 + h2/2) | <= |(h1 + h2) / 2 |

//
//  main.c
//  碰撞检测(循环)
//
//  Created by Jacky on 2020/3/12.
//  Copyright © 2020 Jacky. All rights reserved.
//

/*
 游戏中需要检测元素是否碰撞到一起,比如打飞机游戏,没躲避炮弹就算碰撞,检测出来,游戏game over。假设将游戏中的元素当作矩形,当两个矩形有重合点,则认为它们发生碰撞。
 
 设屏幕左上角坐标为(0,0),x轴向右,y轴向下,屏幕上的点用(X,Y)坐标表示。
 
 屏幕中的矩形用其左上角和右下角坐标标识。分别输入两个矩形的左上角和右下角坐标,检测其是否碰撞。
 
 输入
 测试次数T
 
 每组测试数据两行:
 
 第一行,矩形1的左上角坐标,右下角坐标
 
 第二行,矩形2的左上角坐标,右下角坐标
 
 输出
 对每组测试数据,输出碰撞检测结果,YES(碰撞)或NO(无碰撞)
 
 样例输入
 3
 0 0 10 10
 11 11 20 20
 10 10 15 15
 8 13 13 20
 4 4 20 20
 20 20 30 30
 样例输出
 NO
 YES
 YES
 */

/*
 一般规则的物体碰撞都可以处理成矩形碰撞,实现的原理就是检测两个矩形是否重叠。
 
 矩形1的参数是:左上角的坐标是(x1,y1),宽度是w1,高度是h1;
 矩形2的参数是:左上角的坐标是(x2,y2),宽度是w2,高度是h2。
 
 在检测时,数学上可以处理成比较中心点的坐标在x和y方向上的距离和宽度的关系。
 
 即两个矩形中心点在x方向的距离的绝对值小于等于矩形宽度和的二分之一,同时y方向的距离的绝对值小于等于矩形高度和的二分之一。
 
 x方向:| (x1 + w1 / 2) – (x2 +w2/2) | <= |(w1 + w2) / 2|
 y方向:| (y1 + h1 / 2 ) – (y2 + h2/2) | <= |(h1 + h2) / 2 |
 */

#include <stdio.h>
#include <math.h>

int main() {
    int t, x1, y1, x2, y2, x3, y3, x4, y4, w1, h1, w2, h2;
    
    scanf("%d", &t);
    
    for (int i = 0; i < t; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        scanf("%d %d %d %d", &x3, &y3, &x4, &y4);
        h1 = y2 - y1;
        h2 = y4 - y3;
        w1 = x2 - x1;
        w2 = x4 - x3;
        
        if (fabs((double) ((x1 + w1 / 2 ) - (x3 + w2 / 2))) <= fabs((double) ((w1 + w2) / 2)) &&
            fabs((double) ((y1 + h1 / 2 ) - (y3 + h2 / 2))) <= fabs((double) ((h1 + h2) / 2))) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
        
    }

    return 0;
}

5. switch

case 结束之后要 break,当然不 break 的话可以拿来干一些骚操作。

6. 实现 string.h 内部分函数

/*
 题目描述
 企业发放的奖金根据利润提成,如下规则
 
 利润≤10000元时,奖金可提10%;
 
 10000<利润≤20000时,低于10000元的部分按10%提成,高于10000元的部分,可提成 7.5%;
 
 20000<利润≤40000时,低于20000元部分仍按上述办法提成,(下同),高于20000元的部分按5%提成;
 
 40000<利润≤60000元时,高于40000元的部分按3%提成;
 
 60000<利润≤100000时,高于60000元的部分按1.5%提成;
 
 利润>100000时,超过100000元的部分按1%提成
 
 注意奖金是整数,无小数
 
 输入
 第一行输入T表示有T个测试实例
 
 第二行起,每行输入一个数据(正整数且小于10的10次方)表示利润,连续输入T行
 
 输出
 每行输出应得的奖金
 
 样例输入
 3
 5000
 36000
 120000
 样例输出
 500
 2550
 4150
 */

#include <stdio.h>

int main() {
    int t, profits, bonus = 0;
    
    scanf("%d", &t);
    
    for (int i = 0; i < t; i++) {
        scanf("%d", &profits);
        bonus = 0;
        
        switch (profits / 10000) {
            default:
            case 10:
                bonus += (profits - 100000) / 100;
                profits = 100000;
            case 9:
            case 8:
            case 7:
            case 6:
                bonus += 3 * (profits - 60000) / 200;
                profits = 60000;
            case 5:
            case 4:
                bonus += 3 * (profits - 40000) / 100;
                profits = 40000;
            case 3:
            case 2:
                bonus += (profits - 20000) / 20;
                profits = 20000;
            case 1:
                bonus += 3 * (profits - 10000) / 40;
                profits = 10000;

            case 0:
                bonus += profits / 10;
                break;
        }
        

        printf("%d\n", bonus);
        
    }

    return 0;
}

7. 指针

定义一个整型指针 int *p;

p 为指针 p 的地址

*p 为指针 p 的值

*p = 1; 赋值

8. 函数指针

/*
 题目描述
 定义并实现三个函数:
 第一个函数是整数函数,返回类型为整数,参数是一个整数变量,操作是求该变量的平方值
 第二个函数是浮点数函数,返回类型为浮点数,参数是一个浮点数变量,操作是求该变量的平方根值。求平方根可以使用函数sqrt(浮点参数),将返回该参数的平方根,在VC中需要头文件cmath。
 第三个函数是字符串函数,无返回值,参数是一个字符串指针,操作是把这个字符串内所有小写字母变成大写。
 要求:定义三个函数指针分别指向这三个函数,然后根据调用类型使用函数指针来调用这三个函数。不能直接调用这三个函数。
 如果类型为I,则通过指针调用整数函数;如果类型为F,则通过指针调用浮点数函数;如果类型为S,则通过指针调用字符串函数
 
 输入
 第一行输入一个t表示有t个测试实例
 每行先输入一个大写字母,表示调用类型,然后再输入相应的参数
 依次输入t行
 
 输出
 每行输出调用函数后的结果
 
 样例输入
 5
 S shenzhen
 I 25
 F 6.25
 I 31
 S China
 样例输出
 SHENZHEN
 625
 2.5
 961
 CHINA
 */

#define N 100
#include <stdio.h>
#include <math.h>

int sq(int n) {
    return n * n;
}

float _sqrt(float n) {
    return sqrt(n);
}

void capital(char *p) {
    int i = 0;
    while (*(p + i) != '\0') {
        if (*(p + i) >= 97 && *(p + i) <= 122) {
            *(p + i) = *(p + i) - 32;
        }
        i++;
    }
}

int main() {
    int t, a, (*I)(int) = sq;
    float b, (*F)(float) = _sqrt;
    char type, input[N];
    void (*S)(char *) = capital;
    
    scanf("%d", &t);
    getchar();
    while (t--) {
        scanf("%c", &type);
        getchar();
        switch (type) {
            case 'S':
                scanf("%s", input);
                getchar();
                (*S)(input);
                printf("%s\n", input);
                break;
            case 'I':
                scanf("%d", &a);
                getchar();
                printf("%d\n", (*I)(a));
                break;
            case 'F':
                scanf("%f", &b);
                getchar();
                printf("%.1f\n", (*F)(b));
                break;
        }
    }
    return 0;
}

9. 利用整形数组的键作为标记元素

整型数组的键是 int,默认值为 0,因此可以用这个键来作为标记,再循环中判读这个整型内存的是 0 还是 1,作相应的操作。

10. 结构体

定义一个长度为 N 的 Student 结构体数组,或者一个名为 tmp 的 Student 结构体。

struct Student {
    char id[10];
    char name[20];
    int s1;
    int s2;
    int s3;
} student[N], tmp;

student[i].id 可用于取 i 号 Student 结构体数组元素的 id

&student[i].id 可用于取 i 号 Student 结构体数组元素的 id 的地址

/*
 题目描述
 有N个学生,每个学生的数据包括学号、姓名、3门课的成绩,从键盘输入N个学生的数据,要求打印出3门课的总平均成绩,以及最高分的学生的数据(包括学号、姓名、3门课成绩)
 输入
 学生数量N占一行每个学生的学号、姓名、三科成绩占一行,空格分开。
 输出
 各门课的平均成绩 最高分的学生的数据(包括学号、姓名、3门课成绩)
 样例输入
 2
 1 blue 90 80 70
 b clan 80 70 60
 样例输出
 85 75 65
 1 blue 90 80 70
 */

#define N 100
#include <stdio.h>

struct Student {
    char id[10];
    char name[20];
    int s1;
    int s2;
    int s3;
} student[N], max;

int sum(struct Student s) {
    return s.s1 + s.s2 + s.s3;
}

int main() {
    int n, s1 = 0, s2 = 0, s3 = 0;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%s %s %d %d %d", student[i].id, student[i].name, &student[i].s1, &student[i].s2, &student[i].s3);
        s1 += student[i].s1;
        s2 += student[i].s2;
        s3 += student[i].s3;
    }
    s1 /= n;
    s2 /= n;
    s3 /= n;
    max = student[0];
    for (int i = 1; i < n; i++) {
        if (sum(student[i]) > sum(max)) {
            max = student[i];
        }
    }
    printf("%d %d %d\n", s1, s2, s3);
    printf("%s %s %d %d %d\n", max.id, max.name, max.s1, max.s2, max.s3);
    return 0;
}

11. 十六进制转十进制

/*
 题目描述
 以字符形式逐个读入十六进制数的每一位。边读入边计算,将十六进制数转为10进制。假设数据不含小数。
 
 输入
 测试次数T
 
 每组测试数据一行,为十六进制数。数据以#结束。
 
 输出
 对每组测试数据,输出转换后的十进制数字。
 
 样例输入
 3
 1AE#
 -123#
 BC89#
 样例输出
 430
 -291
 48265
 */

#include <stdio.h>
#include <math.h>
#include <ctype.h>

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int ans = 0, a = 0, b = 0, length = 0, s = 0;
        char o[10] = {'\0'}, *p = o;
        scanf("%s", o);
        while (*p != '#') {
            p++;
            length++;
        }
        int j = length;
        while (j--) {
            if(isalpha(o[j])) {
                b = o[j] - 55;
            } else if (o[j] == '-') {
                s = 1;
                break;
            } else {
                b = o[j] - '0';
            }
            ans += b * pow(16, a);
            a++;
        }
        
        if (s) {
            printf("-");
        }
        printf("%d\n", ans);
    }
    return 0;
}

四、常见错误

OJ 感想-Jacky's Blog

%c %s 交叉 scanf 需要用 getchar 来清空缓存。

scanf 里忘记写 &

printf 里写 &

printf 的时候格式化字符跟变量类型不对应e.g. %d 然后变量类型是 float

五、特别注意

代码化格式,看得更清晰,更容易查出语法错误,给 TA debug 的时候更尊重TA。

六、后记与总结

注意身体

本文出现的例题代码在 https://github.com/0xJacky/c-oj

七、参考资料与文献

  1. 《文件结尾》https://zh.wikipedia.org/wiki/文件结尾
  2. 《EOF是什么?》http://www.ruanyifeng.com/blog/2011/11/eof.html
  3. 《冒泡排序》https://jackyu.cn/algorithm/c-bubble-sort/
  4. 中国社会科学院语言研究所词典编辑室.现代汉语词典(第6版):商务印书馆,2012
  5. 递归.https://zh.wikipedia.org/wiki/递归
  6. 动态规划.https://zh.wikipedia.org/wiki/动态规划
  7. C程序设计,谭浩强,2019

文章最后修订于 2020年8月29日

6
本文系作者 @Jacky 原创发布在 Jacky's Blog。未经许可,禁止转载。
修改 macOS LaunchPad 图标行数与列数
上一篇
Windows 强制刷新打印机状态
下一篇

评论 (1)

再想想
  • Bunny

    沙发

    5 年前

近期评论

  • Jacky 发表在《Nginx UI》
  • kim 发表在《Nginx UI》
  • Jacky 发表在《留言板》
  • 菜鸟 发表在《留言板》
  • merlin 发表在《留言板》
1 6
Copyright © 2016-2025 Jacky's Blog. Designed by nicetheme.
粤ICP备16016168号-1
  • 首页
  • 关于
  • 项目
  • 大事记
  • 留言板
  • 友情链接
  • 分类
    • 干货
    • 随笔
    • 项目
    • 公告
    • 纪念
    • 尝鲜
    • 算法
    • 深度学习

搜索

  • Mac
  • Apple
  • OS X
  • iOS
  • macOS
  • Linux
  • 阿里云
  • WordPress
  • 运维
  • macOS Sierra

Jacky

Go Python C C++ | 弱冠之年 | 物联网工程
183
文章
193
评论
267
喜欢