Qeuroal's Blog

静幽正治

发表于 更新于 分类于

无穷大

0x3f3f3f3f

freopen()

头文件

stdio.h 或者 cstdio (如果是C11，iostream似乎已经包含了，若是C98需要加上 #include <cstdio>)

声明

  
1
FILE *freopen(const char *filename, const char *mode, FILE *stream)

参数

  - filename -- 文件名，用于存储输入输出的自定义文件名。
  - mode -- 文件打开的模式。和fopen中的模式（如: `r` -- "只读访问"、`w` -- "只写访问"、`a` -- "追加写入"）相同。
  - stream -- 一个文件，通常使用标准流文件。如：`stdin` -- 标准输入、`stdout` -- 标准输出、`stderr`(一般不用) -- 标准错误
  1. 模式
  2. 功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。
  3. 实例

    1. stdout 到一个文本文件的重定向，即：把输出到屏幕的文本输出到一个文本文件中

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      #include <iostream>
      #include <cstdio>
      using namespace std;

      int main()
      {
         if(freopen("./output.txt","r",stdout)==NULL)
             fprintf(stderr,"error redirecting stdout\n");

         for(int i=0;i<10;i++)
             printf("%3d",i);

         printf("\n");
         fclose(stdout);

         return 0;
      }

    2. 从文件 in.txt 中读入数据，打印到屏幕上

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      #include <iostream>
      #include <cstdio>
      using namespace std;

      int main()
      {
          int a, b;
          freopen("./in.txt", "r", stdin);
          // freopen("out.txt", "a", stdout);
          while (cin >> a >> b)
              cout << a + b << endl;
          fclose(stdin);
          fclose(stdout);

          return 0;
      }

    3. 从文件 in.txt 中读入数据，计算加和输出到 out.txt 中

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      #include <iostream>
      #include <cstdio>
      using namespace std;

      int main()
      {
          int a, b;
          freopen("./in.txt", "r", stdin);
          freopen("out.txt", "a", stdout);
          while (cin >> a >> b)
              cout << a + b << endl;
          fclose(stdin);
          fclose(stdout);

          return 0;
      }
> Note: 一般常用的是 `6.2`，因为有些比赛的命令行不能粘贴，一个个的打又太麻烦了，这样就会方便很多

导入全部头文件

1
#include <bits/stdc++.h>

发表于 更新于 分类于

友情提示

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 $10^7$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

  1. n ≤ 30 => 指数级别, dfs+剪枝，状态压缩dp
  2. n ≤ 100 => O(n3)O(n3)，floyd，dp
  3. n ≤ 1000 => O(n2)O(n2)，O(n2logn)O(n2logn)，dp，二分
  4. n ≤ 10000 => O(n∗n√)O(n∗n)，块状链表
  5. n ≤ 100000 => O(nlogn)O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、dijkstra+heap、spfa、求凸包、求半平面交、二分
  6. n ≤ 1000000 => O(n)O(n), 以及常数较小的 O(nlogn)O(nlogn) 算法 => hash、双指针扫描、kmp、AC自动机，常数比较小的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
  7. n ≤ 10000000 => O(n)O(n)，双指针扫描、kmp、AC自动机、线性筛素数
  8. n ≤ $10^9$ => O(n√)O(n)，判断质数
  9. n ≤ $ 10^{18} $ => O(logn)O(logn)，最大公约数

发表于 更新于 分类于

位运算：

& （与）

eg: 

1
2
3
1 0 1 
0 0 1 
0 0 1

| （或）

eg: 

1
2
3
1 0 1 
0 0 1 
1 0 1

^ （异或）

运算规则：（不进位加法）

1
2
3
4
0 &nbsp; &nbsp; &nbsp;  &nbsp; 0 ——> 0  
1 &nbsp; &nbsp; &nbsp;  &nbsp; 0 ——> 1
0 &nbsp; &nbsp; &nbsp;  &nbsp; 1 ——> 1  
1 &nbsp; &nbsp; &nbsp;  &nbsp; 1 ——> 0

不进位的加法

1 ^ 1 ==> 0 正常的话：1 + 1 = 20b,但是只看个位, 因此, 取0

运算法则：

  1. 交换律

  2. 结合律

    即$(a^b)^c == a^{b^c}$

  3. 对于任何数x, 都有

    $x^x=0, x^0=x$

  4. 自反性：

    A XOR B XOR B = A xor 0 = A

~ （取反）

  • 把 0 变成 1
  • 把 1 变成 0

<< （左移）

eg:

1
2
1101 << 1 ===> 11010
1 << n  <==>    2^n （向上取整）

>> （右移）

eg:

  • 1101 >> 1 <==> 110

  • n >> x <==> $n \over 2^x$(向下取整)

技巧：

x + (-x)

经验：

  • 将数组无穷大：memset(nums, 0x3f, sizeof(nums))
  • 竞赛中少使用 #include <bits/stdc++.h> // 原因：编译的时间过长,时间会超时
  • 转化成 long long 的形式：乘以 1ll,例子见——>快速幂算法模板—求 $a^b%p$
  • 将大数组放到全局变量中

快速幂算法模板

求 $a^b$

1
2
3
4
5
6
7
8
9
10
11
long long quickPower(int a, int b)
{
    long long res = 1;
    while(b) {
        if(b & 1)
            res *= 1ll * a;
        a *= a;
        b >>= 1;
    }
    return res;
}

求 $a^b%p$

1
2
3
4
5
6
7
8
9
10
11
12
int quickPowerMod(int a, int b, int p)
{
    int res = 1 % p;
    while(b) {
        if(b & 1)
            res = res * 1ll * a % p;
        a = a * 1ll * a % p;
        b >>= 1;
    }
    return res;
}

模运算法则

1
2
3
4
5
6
7
(a + b) % p = (a % p + b % p) % p

(a - b) % p = (a % p - b % p) % p 

(a * b) % p = (a % p * b % p) % p 

(a^b) % p = ((a % p)^b) % p

位运算常用技巧

用异或来实现配偶

1
2
3
4
5
0, 1
2, 3
4, 5
6, 7
……

即(把每个整数异或一个1, 就可以得到他的配偶)

1
2
3
4
0 ^ 1 = 1,            1 ^ 1 = 0
2 ^ 1 = 3,            3 ^ 1 = 2
……
2k ^ 1 = 2k + 1,    (2k + 1) ^ 1 = 2k

用法

一般在图论里面, 写最小费用流时, 我们会存一个编的正向编和反向编, 会需要快速求出来一个数的反向编是什么

lowbit运算(树状数组的基础)

定义

快速的求出来整数n, 在二进制表示里面, 最低的一位1是哪个(或者说：n的二进制表示中最右边一个1)

效果

lowbit(1110011000) ——> 1000

实现

1
2
3
4
5
首先, 假设n的二进制是1110011000
然后, 对n取反, 得到：~n = 0001100111
接着, ~n+1  ===>  0001101000
紧接着, (~n + 1) & n ===> 0000001000 ===> 1000
最后, 由于-n = ~n + 1,所以lowbit就是：(-n) & n

代码实现

1
2
3
4
int lowbit(int n)
{
    return (-n) & n;
}

拓展

  1. 复杂度和1的个数有关和

  2. 可以快速求出来一个整数里面有多少个1

  3. 求n是2的整次方幂

    解析:
    $$
    2^n == 1 << n
    $$

    $$
    n & (-n) == n
    $$

    $$
    otherwise, n & (-n) < n
    $$

原码、反码、补码

正数

原码, 反码, 补码均相等。

负数

  • 反码求法：
    1. 符号位不变。
    2. 其他位取反。
  • 补码求法：
    1.符号位不变。
    2.其他位取反。
    3.最后一位加1。

例子

以123和-123为例：

  • [123] 原码：01111011。 反码：01111011。 补码：01111011。
  • [-123]原码：11111011。 反码：10000100。 补码：10000101。

二进制转换成10进制

  1. 如果为正数, 则直接求即可
  2. 如果为负数, 取反+1, 然后求出数值前面加个负号。

发表于 更新于 分类于

题目

解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0   0000
1   0001
2   0010 
3   0011
4   0100
5   0101
6   0110
7   0111
8   1000
9   1001
10  1010
11  1011
12  1100
13  1101
14  1110
15  1111

  1. 假设求r[i]

  2. r[i - 1] + 1 ，如果进位，那么r[i]就和r[i - 1] 没有关系了，如果没有进位，那么，r[i] = r[i - 1] + 1

  3. 接着，看进位的情况：如果 i & (i - 1) ，那么就会把i和 i - 1 的最低位去掉，即变为0；

    Ps: 最低位是指，从左面第0位开始，一直往右数，直到遇到两个数不一样的位置，那么后面的数（包括不一样的数）不管相不相同，都为最低位（例：9 和 10：从左面第0位开始，到第2位不同，那么第2、3位即为最低位）

  4. 显而易见，i & (i - 1)得到的数就是去掉最低位之后的数，那么，由于进位了，所以，r[i] = r[i & (i - 1)] + 1

代码

1
2
3
4
5
6
7
8
vector<int> countBits(int num) {
    vector<int> r(num + 1);
    r[0] = 0;
    for(int i = 1; i <= num; i++) {
        r[i] = r[i & (i - 1)] + 1;
    }
    return r;
}
# n&(n-1)的妙用

判断一个数是否是2的方幂

  1. 方法：n > 0 && ((n & (n - 1)) == 0 )

  2. 解释：
    ((n & (n-1)) == 0)：

    如果A&B==0，表示A与B的二进制形式没有在同一个位置都为1的时候。

    不妨先看下n-1是什么意思。

    令:n=1101011000(二进制,十进制也一样)，则

    n-1=1101010111。

    n&(n-1)=1101010000

    由此可以得出，n和n-1的低位不一样，直到有个转折点，就是借位的那个点，从这个点开始的高位，n和n-1都一样，如果高位一样这就造成一个问题，就是n和n-1在相同的位上可能会有同一个1，从而使((n & (n-1)) != 0),如果想要((n & (n-1)) == 0)，则高位必须全为0，这样就没有相同的1。

    所以n是2的幂或0

求某一个数的二进制表示中1的个数

1
2
3
4
while (n >0 ) {
      count ++;
      n &= (n-1);
}

计算N!的质因数2的个数

  1. N!质因数2的个数 = [N / 2] + [N / 4] + [N / 8] + ….

  2. 过程：
    下面通过一个简单的例子来推导一下过程：N = 10101(二进制表示）

    现在我们跟踪最高位的1，不考虑其他位假定为0，

    则在

    [N / 2]    01000

    [N / 4]    00100

    [N / 8]    00010

    [N / 8]    00001

    则所有相加等于01111 = 10000 - 1

    由此推及其他位可得：(10101)!的质因数2的个数为10000 - 1 + 00100 - 1 + 00001 - 1 = 10101 - 3(二进制表示中1的个数)

    推及一般N!的质因数2的个数为N - （N二进制表示中1的个数）

    n&(-n)在树状数组中lowbit出现   用来求 t 中的因子中形如2^k的数为多少     用来取得n最右边的1，可以知道其因子中有几个2

    10:  0000 1010

    -10: 1111 0110

    10&(-10)为 0010  =  2  所以10的因子中为2的有一个，$2^k$ 的形式的为 $2^1$

    8&(-8) = [1000] = 8   所以8的因子中为2的有3个，$2^k$ 的形式为 $2^3$

0%