保研考研机试攻略（满分篇）：第一章——技巧之巅（1）

从这章开始，我们就告别满分篇进入满分篇啦~

这一章，我们一起来领略技巧的极致魅力，包括：输入输出加速外挂、调试技巧、位运算技巧、考试最佳策略、预处理与打表技巧、对数器技巧等内容。

目录

1.1 输入输出加速外挂

1.2 调试技巧

说一些我常用的调试位置：

1.3 位运算技巧

速度比较

异或运算的特殊性

例题：DreamJudge 1506

常见位运算问题

1. 位操作实现乘除法

2. 取相反数

3. 判断奇偶性

4. 不用临时变量交换两个数

5. 统计二进制中 1 的个数

练习题目：

DreamJudge 1118 将军的书

1.1 输入输出加速外挂

有的时候题目的输入数据量比较大，比如要输入 10W 和数字进行排序，这个时候，如果我们直接使用 C++的 cin 和 cout 函数进行输入输出，有很大的概率会超出题目的时间限制。

在这种情况下，需要的优化的就不再是算法过程，而是读写数据的速度优化。

使用 cin 和 cout 函数进行输入输出时，在 main()里首先写入下面两行代码：

ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

如果题目的输入量巨大，比如要输入 100W 个数字，这个时候我们最好使用 C 语言的 scanf 和 printf 语句进行输入输出：

//适用于正负整数
template <class T>
inline bool scan_d(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0; //EOF
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
inline void out(int x) {
    if(x>9) out(x/10);
    putchar(x%10+'0');
}

加速外挂原理： getchar 的速度 快于 scanf 的速度

速度比较：

getchar > scanf > cin

putchar > printf > cout

// 求 1 + n 的和
#include <bits/stdc++.h>
using namespace std;
//适用于正负整数
template <class T>
inline bool scan_d(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0; //EOF
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
inline void out(int x) {
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
// 请注意只有在大量输入或大量输出的时候才能看出时间的区别
int main() {
    int n;
    scan_d(n); //加速输入
    long long sum = 0;
    for (int i = 1; i <= n; i++)
    sum += i;
    out(sum); //加速输出
    return 0;
}

1.2 调试技巧

调试是我们在编写程序时不得不经历的过程，这一节我们来学习快速定位错误的调试技巧。

不太建议使用断点调试，虽然这是很常用的一种方法，但是我们的机试往往有一些特殊的情况：

1、机试的代码往往很短，几行到几十行不等。

2、比赛中争分夺秒，我们对调试时间要求更为迫切。

3、我们的错误往往是由于代码细节没考虑周全导致的。

所以，断点调试更适于项目代码中且对时间的迫切度没有那么高的情况。

接下来，我们来学习一种超级棒的调试方法：输出调试

简言之，就是通过输出一些数据或标志来进行调试。

说一些我常用的调试位置：

1. 在for循环和while循环中输出一个自定义的字符串，比如yes、no等，可以判断是否陷入死循环；
2. 在if语句大括号内加入一个输出字符串，可以判断是否按规则进入我们指定的代码区域；
3. 在某些部分输出数组数据，可以判断某一时刻的数据处理是否正确……

教程中提到了下边的定位方法，说实话，我没看懂，懂的宝子欢迎评论区告诉我们：

大部分没有足够调试经验的同学使用输出调试的时候，不知道应该如何使用输出调试。如果从前往后逐条语句输出调试去排查错误，那么很容易要找很久。反之从后往前逐条语句输出调试去排查错误，那么也很容易要找很久。其实，观察上面两种方法，我们发现就是顺序查找的方法。那么，与此对应的就应该是二分查找的方法。

使用二分查找的思想来调试定位错误，可以更快，更节约时间。

特别注意：输出调试完成之后提交代码之前一定要删除或注释掉调试信息。

1.3 位运算技巧

速度比较

我们之所以要进行位运算优化，是因为：取模时间 > 四则运算时间 > 位运算时间

所以对于一个语句

if (a % 2 == 1) {
    a /= 2;
}

可以优化为：

if (a & 1 == 1) {
    a >>= 1;
}

异或运算的特殊性

异或同一个数 2 次或者偶数次，那么本身的值不变。

例如：

a^b^b = a

x^y^y^y^y = x

这是一个很好用的性质，接下来我们来看一下它的应用：

例题：DreamJudge 1506

由于本题要求我们以尽量小的空间来解决问题，所以我们不能够使用数组来存储每一个数。那么我们应该怎么办呢？这个时候可以想到异或运算的特殊技巧，同一个数异或两次那么就会消除，如果我们提前将 1 到 N 的所有数字进行异或处理，然后再去异或输入的N-1个数，那么答案就是缺失的那个数。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, x;
    scanf("%d", &n);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum ^= i;
    }
    for (int i = 1; i < n; i++) {
        scanf("%d", &x);
        sum ^= x;
    }
    printf("%d\n", sum);
    return 0;
}

常见位运算问题

1. 位操作实现乘除法

数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2

int a = 2;
a >> 1; ---> 1
a << 1; ---> 4

2. 取相反数

思路就是取反并加 1，也即~n + 1 或者(n ^ -1) + 1。 相当于补码

3. 判断奇偶性

/* 判断是否是奇数 */
bool is_odd(int n)
{
    return (n & 1 == 1);
}

4. 不用临时变量交换两个数

a ^= b;
b ^= a; // 相当于 b = b ^ ( a ^ b );
a ^= b; 

5. 统计二进制中 1 的个数

count = 0
while(a){
    a = a & (a - 1);
    count++;
}

练习题目：

DreamJudge 1118 将军的书

//摘自N诺用户：滴滴答答
#include<bits/stdc++.h>
using namespace std;
int main()
{
	bitset<22>num;
    long N,res;
    while(cin>>N)
    {
        N=(1<<N)-1;//左移N位，也就是连续N次乘2
        for(int i=res=0;i<N;i++)
        {
            cin>>num;
            res^=num.to_ulong();//该函数将bitset对象中的二进制位转换为一个unsigned long类型的整数
        }
        cout<<res<<endl;
    }
    return 0;
}

创作不易，点个赞吧~点赞收藏不迷路，感兴趣的宝子们欢迎关注该专栏~

勤奋努力的宝子们，学习辛苦了！宝子们可以收藏起来慢慢学哦~休息下，我们下部分再见( •̀ ω •́ )~