总结的常见错误列表，欢迎大家补充！！

1、 两个int相乘，50%几率会爆了int。（不开long long见祖宗）

2、 无向图邻接表的边表忘了 $\times$ 2，这是心口永远的痛；

3、 线段树数组开小是 $\times$ 4（乘4有时候不够）

4、 调用多个函数不仅容易tle，还会mle

5.关于SPFA,它死了；

6.注意数组空间,(开了long long见祖宗)

7.永远不要把n和m打错.

8.多次查询记得清空数组

9.STL函数的区间大多是左闭右开

10、long long类型printf("%d",*).

11 要查反边的时候邻接表要从2开始存、

12 高级编译器不会查出void函数不打void的错误。=

1. 返回函数值一定要写return,windows下会自动return某一值（比如说并查集）。

2. 函数参数为数组时不能用memset和memcpy操作这个数组，必须for循环

3. 多组输入数据时记得初始化

4. strlen是O(n)的(别放在while里面）

5. Yes！=YES No!=NO,请尽量复制样例里的输入输出。。。

6. Ctrl+z悠着点按，版本问题很致命。。。

7. 分数比较要除法改乘法（并开long long）

8. const int N=1e5+10; int p[N]; for(int i=1;i<=N;++i) p[i]=... 然后你人没了。。。

9. freopen记得在对拍的时候如果改了一定要改回来。。。

10. 双斜杠。。。

11. 记得取模！！！

12. 小心别把提交文件夹的-打成下划线。。。

13. 看清楚模数是什么。。。

14. 千万别再没调出正解的情况下把暴力删了。。。

15. 多组数据注意每次输出的换行，多用文件调试。。。

16. 千万不要和那些大佬一样每次取模都是+和-mod，经本人多次试验， 很多时候他操作完两个数之后只+或-一个mod根本不够。。。

17. 函数里定义变量要初始化

18. 变量不要取重复

19. 除法取模要逆元（逆元要保证模数是质数）

20. 调用cmath库的函数注意浮点

21. 对于xxx.cpp,永远不要加入system("xxx.exe")

22. 不记得运算符号优先级就一定要加括号

23. 链表模拟一定要用数组，不要用指针极容易re（卡常大佬请忽视）

24. 用数组最好从1开始用

25. 多%几次总是好的

26. 手写栈或者队列什么的，把指针清空

27. 模数不是质数，Exgcd走起

28. 浏览全局数据，数据范围最大的不一定是最后一个点

29. 不要直接复制freopen

30. 快速幂指数不要%

31. 有向边与无向边

32. 某些位运算符优先级低于比较符

33. 数组空间尽量不要开成2的次幂,最好是奇数

34. 注意重边和自环

35. 复制粘贴细节没有改

36. const int twx=+100;数组没开，小数据过了，成功爆蛋

37. int N=1e6;
    int a[N];
    for(int i=1;i<=N;i++)
    {
    a[i]=....;
    }
    恭喜爆蛋！

38. getchar() Linux下两个空格你不配！！！！！！

39. 1<<n-1是2^(n-1)而不是2^n-1

40. 不会的题就猜吧

41. 删除打表

42. 树状数组防止出现<=0的下标233

43. 不会写高级数据结构想想代替的

44. 数组空间不能压线

45. 常数太大的时候尽量少使用STL，每年都会有题目5-10分卡常，想象如何代替

46. 文件名千万不要手打，一定要复制，尽管文件名特别容易。如果PDF不能复制， 用样例的名称去复制即可（考试是由样例文件的）

47. 不写万能头的dalao一定要记住不要忘记cstdio和cstring

48. 注意输出格式 ： 有时候输出两个数， 你至少要看清这两个数字之间输出的是空格还是换行。

49. 考前复习什么什么就不考

50. 能写多简单的数据结构就多简单，能用值域树状数组上倍增找k大就不要用平衡树.

51. 处理阶乘（fac）及其逆元（inv）要注意0的处理 当然组合数计算有特判的大佬就不需要管辽

52. 全世界只有我把1e9+7打成10e9+7的嘛

53. 快读别打错

54. 堆优化DJ的make_pair以第一关键字比较，不能反过来

55. 还有把1e9+7打成1e9+9的

56. multiset删除一个元素x要写：s.erase(s.find(x))而不是s.erase(x)

57. 如果递归变量每层都不一样，要在递归里申请

第一个结论：

$x + y = (x \& y)*2 + (x \quad xor \quad y)$

感性证明一下：

证明：a xor b是不考虑进位时加法结果。当二进制位同时为1时，才有进位，因此 (a&b)<<1是进位产生的值，称为进位补偿。将 两者相加便是完整加法结果。

第二个结论：

$(x \& y) \& (x \quad xor \quad y)=0$

自己先理解一下。

$s = a*2 + (x \quad xor \quad y)$

所以 $s-2*a \ge 0$ 必须满足

且$(s-2*a ) \& a $ 必须为0

本题主要利用了xor的特性，对于连续的数字，做xor运算，有特殊的性质。

比如 $2 \quad xor \quad 3 =1$ ，$4 \quad xor \quad 5 =1$

所以，以某个偶数开头的连续数字，每4个的xor值为0。

根据这个特性，我们可以分情况讨论：

如果$a$是奇数，先把$a$ 和 $ans$做异或。

$a+1$必然是偶数，让a++，保证区间起点是偶数

这时我们可以讨论$[a,b]$的长度，如果长度为奇数，即$b$为偶数，让ans再与$b$做异或，且$b--$。

这样就保证了$[a,b]$的长度为偶数。

这时根据长度来判断，如果长度是4的倍数，区间$[a,b]$的异或值为0，否则为1。

一眼看到这道题，一个DFS的思路来了，但是本蒟蒻连普及都没有考，水平很低，大佬们的记忆化搜索都不会。。

好了，先说一下思路，本蒟蒻外面用一个for循环来代表选取材料的数量，将这个数量当做参数。

然后，说一下坑点：

这个题目要看清了，我们知道它们各自的酸度S和甜度B。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的甜度为每一种配料的甜度的总和。

然后，我们必须添加至少一种配料。。

下面，看代码（逃）

#include<bits/stdc++.h>
using namespace std;
//n为配料个数，minn为最小值，x为酸度（注意声明=1啊），y为甜度
int n,minn,x=1,y;
//a存储酸度，b存储甜度
int a[11],b[11];
//用来标记用过的数
int book[11];
//传的参数代表选配料的个数，刚才忘了说了
void dfs(int c){
    //如果c是0，代表选完了，那么寻找最小值，并返回到上一次查找
    if(c==0){
        minn=min(minn,abs(x-y));
        return;
    }
    //从1到n查找
    for(int i=1;i<=n;i++){
    //是否使用过，没有使用过，即可使用
        if(book[i]){
        //将book[i]改为0，避免重复使用
            book[i]=0;
            //x增加
            x=a[i];
           //y增加
            y+=b[i];
            //剩余寻找次数减少
            c--;
            //继续搜索
            dfs(c);
            //别忘记恢复现场啊，否则答案是错误的
            c++;
            x/=a[i];
            y-=b[i];
            book[i]=1;
        } 
    }
}
int main(){
   //输入不解释
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    //选择所有配料的情况
    for(int i=1;i<=n;i++){
    //注意乘法
        x=a[i];
       //加法
        y+=b[i];
    }
    //abs是取绝对值，大家都知道吧，例如（-2）的绝对值是2
    minn=abs(x-y);
    //只选择一种配料的情况
    for(int i=1;i<=n;i++)
    //min方法取最小值，这样可以将最小值复制给minn
        minn=min(minn,abs(a[i]-b[i]));
        //选2~n中一种配料的情况
    for(int i=2;i<n;i++){
    //初始化不解释
        memset(book,1,sizeof(book));
      //别忘了重新初始化
        x=1;
        y=0;
        //神深搜
        dfs(i);
    }
    //输出
    cout<<minn;
    return 0;
}

最后，有几个方法给初学者讲一下：

1、ios::sync_with_stdio(false);这个方法还是要解释一下的

在某些题目中，我们使用普通的cin和cout会超时，所以我们每次只能打scanf和printf，然后一堆的占位符巨麻烦），为什么cin和cout比scanf和printf用的时间多？ 这是因为C++中，cin和cout要与stdio同步，中间会有一个缓冲，所以导致cin，cout语句输入输出缓慢，这时就可以用这个语句，取消cin，cout与stdio的同步，说白了就是提速，效率基本与scanf和printf一致。

2、abs绝对值

abs 是 absolute value （绝对值）缩写。c++ 中的一个数学函数，计算整型量的绝对值。要头文件 #include <cmath> 或 #include <math.h>

算例：
int x=16, y= -6;
cout << abs(x) << endl;
cout << abs(y) << endl;
输出：
16
6

但是注意浮点数要使用fabs

3、min取最小值

例如：

int a=10,b=8;
cout<<min(a,b);

则这段代码会输出8

4、memset

memset是计算机中C/C++语言初始化函数。作用是将某一块内存中的内容全部设置为指定的值， 这个函数通常为新申请的内存做初始化工作。

例如：

int a[100001]={1,43,3,2,3,5};
memset(a,0,sizeof(a));

那么a数组所有位置都为0

编程语言 C++ 代码长度 906B 用时 424ms 内存 668.00KB

有帮助的，记得点个赞哈！！

让我们首先关注预测高速公路末端（N英里）可能的交通量范围。为此，我们从一个较大的可能范围[a，b]开始（最初设置为[-999999999，+999999999]），并在扫描1…N英里的不同高速公路组件时缩小/修改它。每次我们看到传感器直接从高速公路读取数据时，这会将可能的范围[a，b]剪辑到传感器给定的范围。每当我们看到范围为[a′，b′的入口匝道时，可能的交通流的新范围为[a+a′，b+b′。类似地，当我们看到范围为[a′，b′的出口匝道时，可能的交通流值的新范围为[a-b′，b-a′（在这次更新之后，如果范围的下限变为负值，我们将其设置为零，因为我们不能有负的交通流速率）。

预测可能的初始流量范围是相似的，并且基本上是对称的，我们向后扫描并跟踪一个工作范围[a，b]，该工作范围被每个公路特征适当地缩小/修改。

T1 矩形

认真审题，

如果红色被蓝色遮住的部分为整个长或整个宽，那么新矩形面积肯定就是剩下的红色举行面积。

否则输出整个红色矩形的面积

T2 三个数

数学题

7个数排一下序，你可以用任何的方法来排序。

最小的为x， 第二小的为y。 最大的为 x+y+z.

本题得到解决。

第三小的不一定是z，有可能是x+y

T3 区间

用两重循环 来 枚举所有区间，i枚举起点，j枚举终点

​ 可以用第三重循环求区间平均值

​ 再用一重循环来查找是否有数是平均值

这样我们用三重循环来解决，本题可以得到完美解决。

另外，思考一下，如果数据量扩大到5000，如何做？

T4 咒语

本题，如果枚举找$j-i\neq k-j$ 三元组，必然需要三重循环，必然超时。

本着正难则反的原则，我们考虑没有条件约束的所有三个颜色不同的三元组的个数

    for(int i=0;i<n;++i){
        if(s[i]=='R') r++;
        else if(s[i]=='G') g++;
        else b++;
    }
r*g*b 就是所求sum

然后再找出$j-i= k-j$ 符合条件的三元组个数为cnt。因为间距相等，我们只需要枚举i，再枚举j，即可求出。

    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            int k=j+(j-i);
            if(k>n-1) break;
            if(s[i]!=s[j] && s[j]!=s[k] && s[i]!=s[k]) cnt++;
        }
    }

最后 sum-cnt 就是所求。 时间复杂度为 $O(n^2)$

T5 排课

观察数据规模，本题显然需要枚举所有的方案。

每个人 有3个班级可以选择，一共有$N$ 个人，时间复杂度为 $O(3^N)$ 之后再验证是否存在矛盾

当然，更高效的是，当枚举到第$i$ 个人所属的班级，我们让其与前$i-1$的方案进行判断，看是否出现矛盾，这就是搜索中的可行性剪枝。

学过递归的同学，应该要能写出基础$dfs$框架。

猴子选大王题解：

猴子大王是最后剩余两只猴子中选，我们需要模拟猴子退出的过程。

开一个bool 数组 a[1010] 来标记猴子是否退出。 我们要开一个计数器来记录 mark来记录当前还有多少只猴子。

    cin>>n;
    mark=n;
    for(int i=1;i<=1010;i++) a[i]=true;

然后模拟整个过程即可。

具体模拟时，我们开一个计数器来记录是第几次开始重新找，如果次数为奇数，就从头到尾找要退出的猴子，如果为偶数就是从尾到头找要退出的猴子

具体代码：

    while(mark>2)
    {
       if(j%2) counta();
       else countb();
       j++;
    }

counta 为从头到尾找要退出的猴子：

void counta()
{
    int i=1,k=0;
    for(int i=1;i<=n;i++)
    if(a[i]) if(++k==3) { a[i]=false; k=0; mark--;}
}

countb 只需要改一下循环的顺序即可。

最后 while(mark>2) 循环结束后，表明现在只有两只猴子

  if(j%2)  从1到n找第一个没退出的猴子
  else     从n到1找第一个没退出的猴子

输出即可。

T1 最大连续和

三重循环 可以拿20~~30分

如果知道前缀和，可以优化到二重循环

仔细思考，如果当前累加和为负数，只会让后边的累加和变小。

所以，利用这个思路，可以一重循环解决。

10^8

int s=0,maxx=-100000000;
for (int i=1;i<=n;i++)
{
    cin>>x;
    s+=x;
    if (s>maxx) maxx=s;
    if (s<0) s=0;    
}

T2

字符串读入，根据要求判断即可。

需要熟悉字符串的读入和基本操作。

T3 卡牌游戏

贪心，我们显然尽量让乘的数越大越好。

所以，开个结构体，按照魔法值从大到小排序。

排序后，魔法值从大到小枚举，前i个最小的魔法值必然是第i个。

所以只需要累加前i个能量值，乘 第i个魔法值，得到一个方案的值。

最终n个方案中的最大值，必然是要求的。

T4 字母游戏

显然要枚举所有的方案

考虑用递归回溯。我们演示一下代码。

void dfs(int x,int y,int s){    
    if(s>ans) ans=s;    
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];    
        if(xx<1||xx>r||yy<1||yy>c||f[a[xx][yy]]) continue;        
        f[a[xx][yy]]=1;
        dfs(xx,yy,s+1);
        f[a[xx][yy]]=0;
    }
}