C语言期中考前复习

语法基础我不打算再重复写了，杜学长的串讲已经很全了，请大家一定要认真看一下他的讲解提纲。

gitee代码仓库传送门，串讲回放传送门

另外，杜学长的仓库里边还有历次上机的题解和一些代码，这个仓库是个好东西，大家一定要认真看认真复习。

关于语言基础的一些补充

输入输出

多组数据

还是要提醒一下多组数据这件事。通常来说，很多题目是每组输入数据对应一个输出，当前的这组数据不需要留到下次（用完即扔）。这时就没有必要去用数组将所有组数据全存起来。

例：多组输入的a + b，每组数据一行两个整数a,b。

样例输入

1 2
3 4
11 22

样例输出

3
7
33

示例代码

// 这是好的
int a, b;
while (scanf("%d%d", &a, &b) != EOF) 
{
    printf("%d\n", a + b); // 一定要换行
}
// 这是不好的
int a[1005], b[1005], n = 0;
while (scanf("%d%d", &a[i], &b[i]) != EOF) n++;
for (i = 0; i < n; i++)
{
    printf("%d\n", a[i] + b[i]);
}

但还有一种情况是这些多行输入要在最后统一处理，例如E1-I 成绩统计2，这时就需要用数组来存储了。并且要边输入边计数。

另外还有一种情况是首先输入一个整数表明测试数据的组数，这种情况不需要EOF，但是也遵循"输入一组处理一组"的原则，用完即扔，不要用不必要的数组.

例：一共q组的a + b. 先输入q，然后q行输入，每行两个整数。

输入样例

5
1 2
3 4
5 6
7 8
9 10

输出样例

3
7
11
15
19

示例代码

int q, a, b;
scanf("%d", &q);
while (q--) // 这里的写法可以记住，不需要用for也不用浪费一个循环变量i
{
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
}

变量的初始化问题

多组数据题中如果有涉及到用来求和，计数，求最大/小值，标记的变量或者数组，一定要在每次循环的最开始进行初始化。

如果是变量的话，就给他赋初始值（比如求和一般是s = 0，计数就是cnt = 0，最大值max = 0，最小值min = 0x7FFFFFFF等等）

如果是数组的话，用下面的代码可以迅速将数组a的所有元素清零.

#include <string.h> 
// memset函数要包含string.h头文件
memset(a, 0, sizeof(a)); 
// a可以是别的数组名，第二个参数不要乱改，只能用0或者-1！

不清零造成的后果就是上一组数据的中间结果会累加到下一组数据中，造成错误。(例如E1-J 数学家的浪漫用来求真因子和的累加变量)

输入输出的数据类型

int: %d， 
long long: %lld;  
double: 输入用%lf输出用%f。保留两位小数: %.2f。 
char： %c，字符串: %s。

注意：输入输出long long型变量千万别忘了%lld，明明看出来题目考数据范围，很机智地用了long long结果输出的时候忘了，等于白给，非常可惜。

结束输入的标志

scanf, getchar: EOF;   gets, fgets: NULL

while (scanf("%d", &n) != EOF) {}
while ((ch = getchar()) != EOF) {} // 赋值运算参与复杂表达式必须加括号
while (gets(txt) != NULL) {}
while (fgets(txt, 1005, stdin) != NULL) {}

遇到空白符的处理

读取字符串

scanf+%d或%s: 前面的空白符会被吃掉(跳过、忽略)，遇到后面的第一个空白符停止.
特别注意：scanf("%s", s)只能读取不带空格的一段字符串(比如单词,整数等)

要读取整行的字符串(如英文的句子),可以用gets或者fgets。

gets(txt);
fgets(txt, 10005, stdin); // 第二个参数是最大接受的输入长度，填的比题目中给的字符串最大长度大一些就行

细微的区别：这二者都会将要读取的这行字符串末尾的换行符读掉，但gets不会将\n存入字符数组txt而fgets会。
例如输入一行hello，用gets读取结果是"hello"，fgets读取结果是"hello\n"。

使用gets或fgets应当心的坑：\r。windows系统的文本文件以\r\n换行(在windows系统下你注意不到，\r\n会被当做一个\n)。但在linux下文本换行符只有一个\n。因此如果在linux系统下运行代码读取windows系统下制作的文本文件，则会多读到一个\r，这个\r可能会导致一些奇怪的错误(比如字符串子串匹配)，需特别留心一下。(这次期中不知道有没有这种字符串题,如果有的话就留意一下，如果没有就权当是对期末的补充)
// 没事的时候尽量不要用gets/fgets，除非题目有要求按行读入含空格的句子。

还有个细节，如果是第一行输入了整数，而后输入带空格的句子，务必要过滤掉第一行行尾残留的换行符，否则下一个gets进来的可能是空串!

3
This is an apple.
I like apples.
Apples are good for our health.

char text[10005]; // 这个数组是全局的
int n;
scanf("%d", &n);
while (getchar() != '\n'); // 这行必须有，否则第一个gets读入的是空串
while (n--)
{
    gets(text);
    // ......
}

读取单个字符

1. getchar()和scanf("%c", &c)会将空白符和可见字符同等对待，空格' '，制表符'\t'，换行符'\n'等都会被原样读入。
2. 如果不想读入空白符，只读入可见字符，请使用scanf(" %c", &c)读入，即%c前面有个空格。

The C Programming Language

char c;
/* 以下示例代码中两行while循环头请任选一个执行，另一个注释掉即可 */
// while (scanf("%c", &c) != EOF)  // 1
while (scanf(" %c", &c) != EOF)  // 2
{
    putchar(c);
}

其他

scanf千万别忘了加&！！！！！！！！

scanf("%d%d", a, b); // 这个代码是错的
printf("%d\n", a + b); // 在本地可能会看到程序没输出，实际上已经发生了内存访问错误，如果提交到OJ上则会REG。

数据类型与范围

大概没啥好说的，看清楚是浮点数还是整数，然后看清数据范围。如果对于求和，求方法数等涉及到累加累乘的题目，如果用int没通过，试试long long。（题干中的数据范围不是白给的，可以事先自己估计一下结果的范围）

typedef

嫌敲long long太长太费劲？把这个代码贴到#include下面即可。（根据具体所需的数据类型自取，第一行最常用）

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;

数据类型与数学运算

经典的1.0*a/b不用细说了。这里稍微提一下乘法和位运算。E1-D aikx解方程这道题如果用int存储a,b,c的话会发现delta在运算过程中可能会超过int范围。

long long delta = b * b - 4 * a * c; // wrong
long long delta = 1LL * b * b - 4LL * a * c; // correct

用long long定义delta是没错的，但是a,b,c本身是int，所以乘法运算也是按照int来乘的，先按int乘完(此时已经发生了溢出)，再转化成long long。而期望的运算顺序应该是先转成long long再乘法。所以用一个long long型的1去参与乘法运算，会自动将b转化为long long去乘。

数据类型与位运算

然后就是位运算，也是要注意类型。左移的时候注意基数的类型(比如说你写long long a = 1<<31;肯定不对，应该是1U<<31或者1LL<<31)，右移的话要区分有符号和无符号(逻辑右移，算术右移)。

几个常见的不同类型的常量1：unsigned int: 1U;   long long: 1LL;   unsigned long long: 1LLU。

浮点数判断相等(以等于零为例)

#include <math.h>
#define EPS 1e-7
if (fabs(x - y) < EPS) // fabs函数位于math.h中 
    printf("Equal\n");

整数的乘幂

尽量不要用math.h里的pow，因为他是浮点数，用它来计算整数的幂有可能损失精度。对于2的幂，推荐使用位运算，$2^{10}$=1<<10，$2^{31}$=1U<<31，$2^{60}$=1LL<<60。
对于给定模数要求结果取余的话，建议照抄E4-L的带余快速幂模板。

数组

这部分，简单直接，请将以下指示当成强制性的命令来做！

1. 所有大数组(长度超过100的就算)一律全局！
2. 数组长度不要正正好好等于数据个数，一律多几个！(比如n<=10000则数组定义可以是int a[10005];) 多五六个或者十个二十个都行，至少多1个！

流程控制

if,for,while的后面不要多写分号(不然真正的分支块or循环体没执行)

for (i = 0; i < n; i++); // 这行末尾的分号是错的，应该去掉
{
    scanf("%d", &a[i]);
}

如果分支或者循环体内有多条语句，务必加大括号！只有一条语句也可以加大括号，以免出错！！！！！

举个嵌套if的易错点：

// 以下代码是不对的
if (/* condition A */) 
    if (/* contidion B */)
        // do something
else
    // do something

这个else会自动匹配if B而不是if A，解决方案是把if A的分支加上大括号。

// 这样写才对
if (/* condition A */) {
    if (/* contidion B */)
        // do something
}
else
    // do something

当然，所有的大括号全加上也没错，更保险。

switch每个case后面必须有break。

语言基础部分我能想到的易错点补充大概就这样，后面的才是重头戏。

后续的易错点以及一些常见的代码套路，我会结合题目来给大家讲解。

上机题补充讲解

注意 && 说明：

这部分内容和历次上机的题解会有一些重合，但目的不是重复题解，我会将每道题的知识点和易错点打碎拆分成一些点，相当于一个强化的提醒，供大家加深理解和记忆，一些有坑的点希望大家在考试的时候不要反复犯。

有必要放完整代码的我会放上来，如果没必要的话我可能不会贴完整的代码，只贴一部分或者不贴代码。如果我没贴代码，请参考代码仓库里的官方题解。

这里我贴的代码均为本人编写，并非复制官方题解的代码。

E1 第一次上机

题解传送门

E1-A 字符的秘密

这题没啥讲的，看题解就行。

E1-B 代码表情

考察转义字符。

这里我个人比较喜欢的做法是，"用代码生成代码"，用一份工具代码帮助你完成对字符画的转义。这个操作需要利用到文件读写的知识，应该在第四讲PPT的末尾有一点提及。用代码生成代码不仅高效率而且可以防止自己手动操作由于粗心而导致的错误。

传送门，请认真阅读使用说明。

E1-C 令人期待的上机

看清题目！！！一定要认真读题！

帮你们画出重点：$0\le a \le 6$；包括当天。

E1-D aikx解方程

这道题的细节非常非常多。

复习这道题建议一定要自己读题自己重新写一遍。

多组输入 记模板 
数据类型 整数与浮点数，int与long long (当然也可以直接用double)
浮点数判断相等
边界情况一定要特判！

示例代码

#include <stdio.h>
#include <math.h>
typedef long long ll;
#define EPS 1e-8
int main()
{
    int a, b, c;
    while (scanf("%d%d%d", &a, &b, &c) != EOF)
    {
        ll delta = 1LL * b * b - 4LL * a * c;
        if (a == 0 && b == 0)
            printf("NO Solution\n"); // 别忘了\n
        else if (a == 0)
            printf("%.2f\n", -1.0 * b / c);
        // 前面是方程退化的情况，从后面开始才是解二次方程
        else if (delta < 0)
            printf("NO Solution\n");
        else if (delta == 0)
            printf("%.2f\n", -0.5 * b / c); // 写成b / (2.0 * c)也可，但2.0写成2不对
        else {
            double sqd = sqrt(1.0 * delta);
            double x1 = (-1.0 * b + sqd) / (2.0 * c); // 1.0 2.0同理别写成整数
            double x2 = (-1.0 * b - sqd) / (2.0 * c);
            // solve"-0.00"
            if (x1 <= 0 && fabs(x1) < EPS)x1 = 0.00;
            if (x2 <= 0 && fabs(x2) < EPS)x2 = 0.00;
            // 由于c的正负不知道，因此对于x1 x2的相对大小不要想当然
            if (x1 < x2)
                printf("%.2f %.2f\n", x1, x2);
            else
                printf("%.2f %.2f\n", x2, x1);
        }
    }
    return 0;
}

一些点：

这道题特别容易情况考虑不全，题干只说了c != 0但没说a,b，所以必须讨论a,b为零的情况。

用int存储a,b,c没问题，注意delta是long long，或者用double存也行。
（用double的话判断方程退化或者delta == 0的情况要用EPS，并且delta先处理等于零再处理正和负）

有一段标记有solve -0.00的代码，这个代码在本题中是否有用尚属未知，但是处理浮点数题的话稍微留心一点总是好的。所谓的-0.00实际上是一个很小很小的负数，例如-0.000000114514，由于保留位数的原因使得小数部分无法体现在输出中，这时应当输出0.00。

E1-E 听说出成绩了

每个人的总成绩要用double，不要用int，因为0.2 * x + 0.8 * y不一定是整数。

E1-F 响应净网号召

这道题的做法之一是直接按行读入字符串再进行转化，这里我提供另一种解法。

读完题之后发现其实不用管有多少行，可以把所有的输入当成一个整体(包括中间的换行)，只需将这个整体里边的字母进行大小写翻转即可。

所以做法就是直接逐个字符读入，逐个字符处理(是字母就翻转大小写，否则原样输出)，逐个字符输出。这种做法在本地调试时，输入完第二行密码后需用Ctrl+Z结束输入查看输出结果.

#include <stdio.h>
#include <ctype.h>
int main()
{
    char ch;
    while ((ch = getchar()) != EOF) // 直接读字符就行，换行符也是字符，会直接被原样输出回去
    {
        if (isupper(ch)) putchar(tolower(ch));
        else if (islower(ch)) putchar(toupper(ch)); // 这行的else不可缺少，想想为什么? (key: 折腾过去又被折腾回来)
        else putchar(ch);
    }
    return 0;
}

一些注意：
1. 头文件ctype.h及其库函数的应用（PPT有介绍）
2. 我发现很多同学只将大写转了小写，或者只将小写转了大写，你们没发现样例都不对吗？读题的重要性啊！！！

逐个字符读入操作
ctype.h的应用

E1-G 火仙草数

这题没啥好说的，循环做就行

这里有个小知识点：截断整数的数位。做法就是利用整除和取模。

相关题目：E4-F Zeller公式求星期

prefix = i / 100; // 前两位
suffix = i % 100; // 后两位

E1-H You underestimate my power!

两种做法。

// 法一
cnt = 0;
for (i = 0; i < 6; i++) {
    if (obi[i] < ana[i]) cnt++;
}
// 法二
cnt = 0;
for (i = 0; i < 6; i++) {
    cnt += (obi[i] < ana[i]);
}

这题本意是让你对符合条件的情况进行计数(法一)。法二是利用逻辑表达式真值为1，假值为0的特性，直接将所有为真的情况的1加起来。

数组的应用
基本的计数
逻辑表达式

E1-I 成绩统计2

这题代码稍微有点长，题解里应该也比较详细了。
我看大家做的情况非常好。这道题目可以说是细节非常非常多。回顾一下：

多行输入 用数组存，边输入边计数(因为最后还要用到)
判断整除 a % b == 0
两个int相除，实数商or取整商? (a / b) or (1.0 * a / b) ?

E1-J 数学家的浪漫

#include <stdio.h>
int main()
{
    int a, b, j, k, sum1, sum2;
    while (scanf("%d%d", &a, &b) != EOF)
    {
        sum1 = sum2 = 0; // 至关重要的初始化！
        for (j = 1; j < a; j++) // 这个for循环正在枚举a的因子
        {
            if ((a % j) == 0)
                sum1 = sum1 + j; // 满足条件下的求和
        }
        for (k = 1; k < b; k++) // 同样是枚举因子
        {
            if ((b % k) == 0)
                sum2 = sum2 + k;
        }
        if (a != 0 && b != 0 && a != b) // 读题要仔细
        {
            if (sum1 == b && sum2 == a)
                printf("Y\n");
            else
                printf("N\n");
        }
        else printf("N\n");
    }
}

首先这里给大家强调一下理解题意，题目给了亲密数的定义，亲密数一定是两个正整数。
但是输入数据只说了非负整数，意味着输入数据当中是有0的。注意：这里需要你自己去判断输入数据是否为0。(甚至可以出负数，如果这样则题面的输入数据说明也会相应告知)
所以你需要自己去用if判断输入数据是否为0，以及是否互异。如果不满足亲密数定义的前提条件，显然就输出N。

另外代码中的两个for循环的作用是枚举a,b的因子。这个循环还有里面的if可以稍微记一下。枚举因子其实就是找能被自己整除的数。

for (i = 1; i <= n; i++){
    if (n % i == 0) { // n能被i整除 --> i是n的因数
        // do something
    }
}

通常来说枚举的范围是1到n，当然对于这道题而言要求的是小于自身(或者说 不包括自身)的因子，那么只需将i <= n改成i < n即可。
除此之外可能还会有其他的变形，比如说考察非1的因子，那就是循环从i = 2开始。
另外还有些情况可以关注一下，比如说如果要找出一个数所有的因数，由于因数是成对出现的，所以可以只枚举前一半(即在n的平方根之前)，然后n / i就是跟他相对应的因子。如果是完全平方数的话，其平方根只算一次。这样可以减少很多无用的循环次数。（详见题解中"一点小小的优化"）

然后就是对求和变量sum1,sum2的初始化，千万别再忘了！！！！！

循环枚举因数 (平方根优化)
多组数据注意求和变量初始化

E1-K 温度转换

这题没啥说的，循环就行。然后还是注意一下除法与数据类型的关系。

F = C * 9.0 / 5 + 32; // 如果C用int，注意9.0
C = 5.0 * (F - 32) / 9; // 如果F用int, 注意5.0

也可以直接用double去循环，但是double没有++，只能每次+=1

E1-L 小明的钟表问题

时钟时刻重合问题。如果考试遇到了，直接抄题解的代码就行。

一定要注意先算重合时间的取整，再比较。不要试图计算时分针相差的角度，因为这样误差很大(正负1分钟的话误差可能高达3°)。

然后就是过了11点以后的下一个重合时刻是12:00，要当成0点处理。另外不要解出类似于11:59:60这种解(不是说这道题，其他的时钟重合题可能遇到)

E2 第二次上机

题解传送门

E2-A 字节清零

位运算的基本应用，直接看题解就行。方法很多，可以每种都练一下，熟悉一下。

如果是最高字节，或者最低字节，又该怎么做?

一个字节其实就是连续的8位，可以用两位十六进制表示。比如说0xFF就是最低的八位全是1，其余位是0。0xFF00FF00这个数是最高字节和次低字节全是1，而其他位是0。

标答当中的n & 0xFFFF00FF，可以理解为0xFF000000 | 0x00FF0000 | 0x000000FF，相当于把这三个字节取出来，那没取出来的字节自然就没了。

这道题中涉及到的位运算基本操作：

取出某些位
在字节层面的操作(本质上还是位运算)
位运算操作数的十六进制表示(方便)

E2-B 最萌身高差

双重循环基本应用。这里边的数组下标建议从1开始用(数组长度开多点的重要性)

for (i = 1； i < n; i++){
    for (j = i + 1; j <= n; j++) {
        // ......
    }
}

注意内外层循环的上下界

E2-C 求阶乘

这道题引入了一个重要的知识点，涉及取模的操作。

通常来说，一些涉及到求和或计数的题目，由于答案往往特别特别大，所以只要求你输出对一个大数取模的结果。这里就是要记住关键：边加边取模，边乘边取模。一定要时刻提防可能出现的越界/溢出的风险。绝对不要等到最后再取模。

#define MOD 1000033 
// 建议将模数用#define设定为一个常量，增强代码可读性以及防止敲错
(a + b) % MOD = ((a % MOD) + (b % MOD)) % MOD;
(a * b) % MOD = ((a % MOD) * (b % MOD)) % MOD;
// 对于累加或者累乘
sum = (sum + a[i]) % MOD;
prod = (1LL * prod * a[i]) % MOD; // 这题不需要1LL，但是加上更保险

另外如果这道题是多组数据的话，有个预处理的小技巧可以不用每次输入n都循环算一遍阶乘：用一个数组和一个在输入之前执行的循环，提前算好各个数的阶乘并存起来.

int fact[22] = {1, 1};
for (i = 2; i <= 20; i++) {
    fact[i] = (1LL * fact[i - 1] * i) % MOD;
}
// 后续的scanf ......

结果带有取模的问题
预处理

E2-D 宋老师的进制转化2

重要知识点：进制转化。

进制转化是一个步骤相对比较套路但是涉及到的知识点比较多的操作。

由于L题也是进制转化，所以详细操作我留到L题再细讲。这题先摸了。

这道题需要注意的就是，用字符串存储三进制的结果，别想着用整数类型来存，可以很负责任地告诉你，unsigned long long是不够用的。

大体的步骤就是类似于数学里学过的"短除法"，先循环对n取余+除掉进制数，将每一步的余数存成数组，最后将数组反转。

循环取余，数组翻转 (都是重要操作，要掌握)

E2-E 统计单词数

首先先去看题解，先掌握题解里的方法(数空格)。

我给两种解法。

法一：单词的长度有限，可以用字符数组存。利用scanf("%s")遇到空格被截断的特性，循环读入并计数。而开头的空格(在读入第一个字母之前)会被scanf跳过。

char word[2005];
cnt = 0;
while (scanf("%s", word) != EOF) {
    if (word[0] != '.') cnt++;
}

scanf("%s")遇空格停止的特性

法二：单词的两边是非字母，所以我们判断单词个数其实就是判断字母和非字母的交界个数。这里计数的时候要统一，只看左边界或者只看右边界。这里我选择了看左边界，右边界的写法可以自己试试。

看边界其实就是比对连续的两个字符，在输入的时候不需要用数组，只需一个额外的变量保存"上一个输入的字符"即可。

char prev = 0, ch;
int cnt = 0;
while ((ch = getchar()) != EOF){
    if (!isalpha(prev) && isalpha(ch)) cnt++;
}

这里让prev=0是为了记上首次出现的单词，强行给首个单词的首字母之前脑补一个非字母的字符，这样首个单词就可以被计入了(如果句子开头有空格也没影响)。

逐个字符读入处理
相邻字符比较 - 存储上一个字符
ctype.h应用

E2-F 超大统计

没啥好说的，long long求和就行。这个多行输入也不用数组存，输入一个累加一个就行了。

E2-G W位数

这题其实要细说的话挺复杂的，我懒得写了，大家仔细去看看题解就可以。

如果考场上想不出来，当然也可以用数组去暴力做，先把a+b转成二进制(存成数组)，然后再去截断，截断完了再恢复回来。

做这道题一定要了解什么是符号位，什么是补码，负数的补码怎么算。(不清楚的，去补PPT)

最精简的核心代码在此

long long a, b, w, sum;
sum = a + b;
sum = (sum << (64 - w)) >> (64 - w); // 移过去再移回来

解释一下：第一个左移，利用溢出，将高于w的位直接怼出去；第二个右移是利用了有符号整型的"算术右移"(即补符号位)。
可以自己写几个例子验证一下，把一个32位int整数赋值给long long，然后看看他们的二进制。正负都试一下，可以发现long long的高32位跟int的符号位是一样的，w位数同理，高于w的位就都是符号位。

移位运算的应用：
左移 - 溢出
右移 - 算术右移和逻辑右移
熟悉一下原码反码补码

然后再看看题解里边用mask的方法，这个mask实际值是(1LL<<w) - 1，可以通过&mask取出后w位。

E2-H 弹反

基本操作；整数的反转
循环取余，循环*10+个位

看清数据范围，有的数翻转之后就不再是int了(比如说2147483647)

long long x, ret = 0;
while (x) {
    ret = ret * 10 + (x % 10);
    x /= 10;
}

E2-I A op B Problem

这题怎么做，请看题解。

然后注意一下提示里边的1U，可以试试1<<31和1U<<31的区别。

按位与&：取出某位的值或将某位清零；按位或|：向某位加载一个1。

无符号整型
位运算 - 取出位，加载位

E2-J 求相反数

这道题环节比较多，按环节讲一下。

1. 判断0verf1ow!，即不能用补码表示其相反数的数

很显然，-128, -32768, -2147483648这样的数不能表示其相反数。这类数的补码形式也很统一，都是10...0(首位是1，其他位是0)。注意全零并不是overflow，零的相反数的补码还是零。

方法：标记变量(flg)

用一个标记变量(如果不知道叫什么的话就叫flg或者flag)跟随循环，如果出现符合(或不符合)的情况，就修改标记变量，根据标记变量的不同值来判定结果。

这道题当中，overflow也就是判断首位为1，其他位为0，判断非首位时，如果有一位不是0，则整个数不是overflow，否则这个数就是。
所以如果首位是1，标记变量初始值即设为1，然后后续的位有一个不是0，标记即为零。最后标记为1的，是overflow。

int flg = (a[0] == '1');
for (i = 1; i < len; i++) {
    if (a[i] == '1') flg = 0;
}
if (flg == 1) puts("0verf1ow"); //用puts自动加换行，防止自己忘了
else // 后续操作...

2. 逐位取反

这步没啥好说的，循环就行。

这一步的循环和上一步的循环可以合并成一个循环，提高效率。

3. 反码加一

这一步其实就是一个对(二进制加法)连续进位的处理。

遇到0之后把0变1然后要break出来。

for (i = len - 1; i >= 0; i--) {
    if (b[i] == '1') b[i] = '0';
    else {b[i] = '1'; break;}
}

可以想想十进制大整数加法(就是用数组存数的每一位)怎么连续进位?

这一步居然有同学完全没有考虑进位，这不好。

如果一直WA的话，可以自己尝试去构造一些边界数据，比如说10000000, 01111111, 00000001, 00000010, 00000011, 11111111等，看看有没有哪个数据和预期的不一样。

E2-K 我家大小姐不想让我告白

循环移位:

利用移位来取得高位(<<)和低位(>>)
位拼接(&)

其实就是把最高的n位和最低的32-n位交换个位置。
用a<<n把右边32-n位移到左边，同时留出n个空位；
用a>>(32-n)将原来的高n位移到低位去。
用按位或|运算拼接起来。

另外还是mask，由于题目里的N不见得是32,64之类的，利用不到自然溢出，因此最后的运算结果需要&((1<<N)-1)，否则原来的最高n位没有被顶掉，而是待在了这个int的更高位。(int永远是32位，不会受N影响的)

E2-L TaoFu算进制转换

进制转换模板，一共分两步。

<1> 循环求余

char res[10005];
int a, k;
int l = 0; // l记录k进制数的长度
if (a == 0) res[0] = '0'; // 这行如果不加的话输入0会没输出
while (a) {
    res[l++] = (a % k >= 10) ? (a%k-10+'a') : (a%k+'0');
    a /= k;
}
// 或者用do-while
do {
    res[l++] = (a % k >= 10) ? (a%k-10+'a') : (a%k+'0');
    a /= k;
}while (a);

<2> 反转结果

数组的翻转/逆序

// 基本代码，a可以换成别的数组名
char tmp;
for (i = 0, j = l - 1; i < j; i++, j--) {
    // 中间这三行是用来交换a[i]和a[j]
    // 交换两个变量x,y的基本操作：t=x; x=y; y=t;
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

以上代码中的i和j是要翻转的起点和终点。从0到l-1可以实现整个数组的翻转。
这个代码还可以翻转数组当中的一个区间，只需将i,j的初始值分别设定为待翻转区间的起点和终点(包括自己)即可。

E3 第三次上机

题解传送门

E3-A 小明的压岁钱

这个题代码看题解就行，提两个点。

1. 每行的第一个数前面的符号其实无需用char去存储，直接输入%d就行，毕竟一个数可以是带符号的。在算钱的时候也不用判断是正还是负，一律用加法即可(初中学过"代数和")。
2. 记录利率最大值的变量，不要忘了每轮循环前要初始化。

E3-B Switch真香

switch-case多路分支的基本操作 - 开关语句。

这题的输入不需要你去解析字符串，直接scanf("%lf%c%lf")就可以按照指定的格式去提取输入。

另外有的同学没读清题，把%lf写成%d(当成了整数)，评测结果有可能出现TLE。如果是这种情况的话，可以试试输入1+1.0，scanf首先按照%d%c%d格式读入了一个1，一个+号，一个1；然后输入区还残留着.0，下一组输入的时候第一个%d由于被小数点.挡住，导致输入无法继续进行(被卡住)，从而死循环。

E3-C Random Star

图形的输出都没啥问题，就是注意一下"每两个图形之间以空行隔开"的空行。

这个空行一定是一个多余的空行，而绝不是最后一行末尾自带的'\n'。最后一行末尾自带的换行只是让下一个图形从下一行开始输出，并不是空行。

更不要觉得在本地手动多敲一个Enter就以为是空行了，实际上在评测机当中输入和输出是分开的，不会像本地调试一样全挤在一个黑框框中。

注意输出格式问题

E3-D 小胖吃自助

同样这题细节有点多。简单回顾一下：

首先是判断是否全负，这里可以采用flag的方法，首次循环遍历时带着标记变量去判断一下(题解里边的nega就是标记变量)。
如果不想判断的话那就把最大值maxS的初始值设成-1而不是0。

然后中间的主体，嵌套的for循环里边有个级联的if加if嵌套，注意嵌套if为了避免出最好加大括号。

if (sum > maxS) {
    // 更新最大值和始末位置......
}
else if (sum == maxS) {
    if (j - i > end - start) {
        // 更新始末位置......
    }
}

最后是输出，输出这里坑太多了。。。

1. printf("I\'m hungry!")，没换行的(这种输出一行固定信息建议puts)
2. 输出maxS没有用%lld的，即使maxS定义成了long long也没体现在输出，功亏一篑。

另外再次强调一下多组数据，每次输入n之后要重新初始化maxS, nega(如果有)。

E3-E 人肉指南针

数学公式，级联if判断。

为了防止浮点误差建议用整数输入坐标，先判断原点和坐标轴，再划分象限。在象限里边再转浮点数。

整数绝对值用abs(在stdlib.h中)，浮点数绝对值用fabs(在math.h中)。

E3-F 拔剑吧少年

注意到这个泰勒只有奇数次项，所以展开到偶数($2k$)阶的结果和$2k-1$阶应该是一样的。

同样这道题可以预处理，因为n<=20所以可以提前算好展开第1到20阶的结果。

E3-G 质量弹簧阻尼

就是迭代。迭代不需要用数组，就是用变量记录当前状态，循环根据当前状态计算出下一个时刻的状态，然后将下一时刻更新为当前时刻即可。

x = x0; z = 0;
for (i = 1; i <= n; i++) {
    xx = x + h * z; // 下一时刻的x
    zz = z - (h / m) * (b * z + k * x); // 下一时刻的z
    x = xx, z = zz; // 更新状态，下一时刻变成当前时刻
}

E3-H 找零件

这个题可以专门记住。利用a^a=0，以及异或运算的交换律。出现偶数次的数在求异或和的过程中会相互抵消，最后只剩下奇数次的。

这道题不要用数组，否则会超时。

E3-I jqe的卡组1

这道题的正解是对1到n以及输入的数据分别求和或者求异或和，然后对两个和相减或者将两个异或和再取异或。（求和用等差数列公式，求异或和用循环）

还有一种暴力的方法，即用数组来计数。(思想有点像散列表)
用cnt[i]表示数字i在输入序列中出现了几次。最后从1到n扫描一遍，遇到次数大于1的就输出。

for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    cnt[x]++;
}
for (i = 1; i <= n; i++) {
    if (cnt[i] > 1) {
        printf("%d\n", i);
        break;
    }
}

E3-J 1992年9月29日

整数的数位拼接：y * 10000 + m * 100 + d

判断有没有2和9：用循环取余的方法，每次取出个位判断，然后将个位砍掉。

闰年：((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0))

E3-K 摔跤比赛

这道题里边的最大公约数牵扯到了0和负数，比较麻烦。

先给大家一个比较正常的最大公约数的计算函数，用辗转相除法。

int gcd(int a, int b) { // a >= b
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

题本身的做法看题解就成。核心部分可以用四重循环，也可以直接枚举一下n=4的全排列，都可以找遍所有的对应关系。对于每种对应关系，依次检查是否有互质即可。

E3-L 卖口罩

优先找2元钱。找一个5块可以是2+2，2+1+1，1+1+1+1。
找钱之后别忘了钱数的计数变量要减掉。

另外这里有一个大坑，由于是多组数据，因此在含有输入数据的循环不要有break，必须执行完。否则会给下一组数据带来问题(这组数据有没读到的，残留在输入区里)。
解决方法：

1. 先循环输入，再循环模拟收钱找钱过程。这样在第二个循环如果发现找不开零钱就可以break
2. 边输入边模拟找钱，此时千万不要break，如果找不开零钱了可以利用标记变量flg处理。

另外就是记录各种面额纸币数量的计数器要每次清零(多组数据)

E4 第四次上机

题解传送门

E4-A 签到之GPA计算

就是加权平均数。注意用float。

E4-B 简单的三角形面积

三种方法都在题解里边。

E4-C SIR模型算感染人数

又是一个迭代法的题。

for (i = 1; i <= n; i++) {
    // 计算下一时刻的状态，即S(n+1), I(n+1), R(n+1)
    SS = S - beta * S * I / N;
    II = I + beta * S * I / N - gamma * I;
    RR = R + gamma * I;
    S = SS, I = II, R = RR; // 将下一时刻更新为当前时刻
}

注意这里不要用递归，不要一看这节课是讲递归的就想当然地用递归了。递归的缺点在于大量的重复计算。而且这道题涉及到三个函数，这种多个函数耦合的递归写起来更麻烦而且非常容易写错。所以不如递推或者迭代。

E4-D 求阿克曼函数

直接照着翻译就行。判断边界情况，然后递归计算。

E4-E 小明又去春游

经典的计算组合数。在后面的G题当中也有一些方法用到了组合数，所以在这个题里我稍微强调一下组合数的计算方法。

常见的组合数的计算方法除了PPT上的$C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$以外，还可以利用阶乘直接计算。即$C_{n}^{m} = \frac{n!}{m!(n-m)!} = \frac{n\cdot (n-1)\cdots(n-m+1)}{m!}$。

对于第一种方法，可以直接抄课件，但是课件上的纯递归的代码有一点小小的坏处，就是如果程序不是只计算一次组合数，而是大量计算很多个组合数的话，纯递归很容易造成大量的重复运算而TLE。这里可以采用记忆化的手段去优化。

int comb[105][105];
int comb_num(int n, int m) {
    if (comb[n][m]) return comb[n][m]; // 如果已经求过C n m，直接返回，无需重复计算。
    if (m == n || m == 0) return (comb[n][m] = 1);
    if (m == 1) return (comb[n][m] = n);
    return (comb[n][m] = comb_num(n-1, m) + comb_num(n-1, m-1));
}

说明：comb数组用来记录已经求过答案的组合数。在没有求之前所有的comb[n][m]都是零。在递归函数comb_num中，所谓的记忆化其实就是在算出某个$C_{n}^{m}$的结果时将其存入数组。在代码中我利用了赋值表达式的特性，一次性完成了赋值和返回两件事。然后在递归的过程中，如果遇到了先前求过答案的C(n,m)则不需要重新递归计算，直接返回答案即可。

利用阶乘分式直接计算时也有一些细节需要注意，直接看代码：

int comb_num(int n, int m) {
    int res = 1;
    for (int i = 1; i <= m; i++) {
        res *= n + 1 - i;
        res /= i;
    }
    return res;
}

举个例子：$C_{8}^{3} = \frac{8 \times 7 \times 6}{1\times 2 \times 3}$，我们采取的运算顺序是*8 /1 *7 /2 *6 /3，通过这种运算顺序可以及时避免由于阶乘迅速增长而溢出int范围。并且这样的运算顺序一定能保证任何一步都是整数，所有的除法都一定整除。（原因解释起来真的太直接了，因为$C_{8}^{1}, C_{8}^{2}$都是整数。以上的代码循环到i的res就是$C_{n}^{i}$）

不要试图分别算好分子分母再相除，否则的话分子很有可能会越界的。不信的话算一个$C_{20}^{10}$试试，结果在int范围内，但是运算过程如果不控制就惨了(分子溢出)。

E4-F Zeller求星期

还是分割数位，把一个8位的日期分割成世纪数c，年代数y，月份数m和日期数d。

// 直接把年拆开
int c = date / 1000000;
int y = (date / 10000) % 100;
// 或者先提取出年份再拆
int yr = date / 10000;
int c = yr / 100, y = date % 100;
// 月份和日期
int m = (date / 100) % 100; 
int d = date % 100;

然后注意读清题，对于1月2月，将其当做上一年的13,14月。很多同学只处理了月份，却忘了同步处理年份。这样造成的后果是2月最后一天和3月第一天的星期是断开的，因为一个是明年的一个是今年的。
这一步处理时，如果拆年份用的第一种方法，除了y--之外还要判断一下是否需要"借位"，即if (y < 0) y += 100, c--;（这里不借位也可能能过，不知道是测试数据没卡还是确实没影响）
如果用第二种方法的话，先year--然后再拆c和y。

E4-G 这个勇者确实很菜所以过分慎重

推荐写成递推形式而不要写递归。题解当中也提到了"重复计算"这件事。

结果要求余，依旧是一边计算(加，乘)一边取余。比较保险的写法：

f[i] = (f[i - 1] + (2 * f[i - 2]) % MOD) % MOD;

同样这道题可以先预处理出全部的结果：

for (i = 2; i <= 20; i++)
    f[i] = ...
// 预处理完再开始接受输入，不用重新算，直接输出就行
while (scanf("%d", &n) != EOF) {
    // ...
}

代码很好写，关键是要能够从题目中分析出来递推关系，找到公式。

可以从一天前直接加一个1         -->     f[i - 1]
或者从两天前来一套2 3或者3 2    -->     f[i - 2] * 2

还有一种用排列组合的写法，不在这里细讲了，那种方法太麻烦，仅供感兴趣的同学去思考。传送门

E4-H 甄医生找工作牌

对于解这道题本身，题解已经帮着分析了，看出规律之后其实就是a*b*c。

这里我想强调一下vis数组的使用。(题解代码里用的是visited，命名其实没关系，重点在于知道数组可以这么用)

vis / visited数组

也是一句话的事，用数组来记录某个数是否被访问过，也是散列表思想。用vis[i] = 1表示i被访问过了，vis[i] = 0表示i没被访问。
除了用0和1表示是否访问过以外，还可以直接用整数记录访问的次数。（每访问一次i，执行vis[i]++，则vis[i]表示i被访问过的次数，起到计数作用，0表示从未访问过）

这个数组的名字叫什么无所谓，重点在于学会散列的思想。常见的应用可以有分类计数（统计一篇英语文章中每个字母出现多少次，给一堆数找到出现次数最多的数(众数)）等。

E4-I 置换的分解

for (i = 1; i <= n; i++) {
    if (trans[i] == i) continue;
    for (j = i; !vis[j]; j = trans[j]) {
        vis[j] = 1;
        printf("%d ", j);
    }
    printf("\n");
}

核心代码是内层的for j循环，最关键的一步是j = trans[j]，这个循环大家可以稍微记住一下，它在做的事就是模拟一个元在不断的变换。在这道题当中同样要用数组记录某个数是否被遍历过。

E4-J Four Pegs Hanoi

这题没啥好说的，直接看题解就行。

不要直接递归，推荐记忆化递归或者直接递推。并且注意一下"剪枝"操作，如果F3[N - x]太大了，那么很明显这个x对应的F4[x] + F3[N - x]一定不会是最小值，不可能是F4[N]的答案，所以这样的x直接跳过(continue)即可。

E4-K 水水の多项式加法

还是散列思想，读到一项，直接把系数加到次数对应这项的总系数里，体现了"合并同类项"思想。

int coe[10005]; // coe[i]表示所有x的i次方项的系数和
// read c, u, p
coe[p] += c;

细节：
1. 直接scanf("%d%c%d")读入一项，系数的正负号直接会算在第一个%d里，作为整数的一部分出现，而不要把它当成一个单独的字符。第一行行尾的换行符没影响，会被第二行第一项的第一个%d直接跳过。
2. 注意long long，提示的神必代码是告诉你在%和d之间写一加号可使得输出带符号，但这个%+d还是有一定迷惑性，因为这道题实际上用的是%+lld。每项的系数已经给了是int范围，不超过10000项。如果所有项都是同一个指数，系数加起来就超过int了。因此注意看范围。

E4-L 原根

题解写的很清楚。

• Phi函数只调用一次，用变量把结果存起来
• flag标记变量的应用

很多同学没有读明白题啊，第三个条件说的是使得那个同余式成立的最小正整数是Phi(p)(即phi)，这个"最小"有两层意思，首先phi自身得满足，其次任何比phi小的数都不满足。很多同学写的代码是验证不到"比phi小的数都不满足"这个条件的。

附一个稍加修改过的快速幂模板（把一部分变量改成了long long类型）

typedef long long ll;
ll PowMod(ll a, int t, int p){
    ll ret = 1;
    while(t){
        if(t & 1) ret = ret * a % p;
        a = a * a % p;
        t >>= 1;
    }
    return ret;
}

最后的一点小提醒

• 一定一定一定一定要认真读题，认真审题！
• 数据范围！输入输出！代码里的小细节！
• 善用调试
• 对于情况比较多的题，不要只满足于通过样例，一定要自己去尝试造一些简单的各种情况的测试数据去测试你的程序。

另外就是前几次上机大家也都有目共睹，咱们的OJ平台比较卡，对于用OJ考试也是有几点小建议：

• 千万不要挤到最后再提交，尽量做一题就交一题，以免最后交不上。
• 点了提交之后一定要及时检查提交状态！
  在比赛界面题目的右侧有个提交记录，一定要看到提交记录变了（第一行多了一条记录）才算提交成功。
• 如果实在OJ比较卡，一时半会提交不上，不要干等着！考试时间是你自己的，如果现在交不上可以先自己做下一道题，等网好了再一块交。（千万别交串题号！）
• 不要过度依赖评测结果！
  在OJ非常卡的时候一道题可能要评测很久才能给出反馈，甚至在考试快结束的提交高峰期，可能考试已经结束了，提交的代码还没有判完。
  要提交就尽量交有把握的代码(如果WA了会增加罚时，影响排名)
• 点击网页最左边的"我的提交"可以查看自己的提交记录，鼠标指在红色提交的反馈类型上(比如Wrong Answer)，可以查看详细错误信息(一共多少个测试点，对了多少个测试点，错了多少个测试点……)。如果是编译错误(Compile Error)则会显示编译器输出的errors。
• 如果自己的代码TLE了，并且确定自己的算法没问题（保证代码中没有死循环，多组输入的循环控制正确 能通过Ctrl+Z正确结束程序，没有过深的递归或者复杂度过高的嵌套循环），可以尝试重交一遍，有可能是评测机卡了>_<

最后祝大家都能AC，远离WA,TLE,REG,REP……
然后敲代码手速快点，两个小时做对10道题还是很可能的，冲击AK吧！