QeuroIzoのBlog

hello world

0%

112. 程序设计

发表于

  1. 程序设计返回结果

    1. Accepted: 通过
    2. Wrong Answer: 答案错误
    3. Runtime Error: 表示程序因为非法访问或未处理异常而结束。
    4. Memory Limit Exceeded: 表示程序因为使用的内存超过规定的内存限制。
    5. Presentation Error: 表示虽然程序输出的答案是对的，但是换行或空格等不符合输出格式要求
    6. Time Limit Exceed: 超时
    7. Output Limit Exceeded: 表示程序输出了过多的内容。
    8. Compile Error: 表示所提交的源代码没能通过编译，不符合语法规定。
    9. System Error, Validator Error: 表示系统发生错误无法正常判题。
    10. Segmentation Fault: 段错误：访问的内存超过了系统所给这个程序的内存空间

  2. 状态

    例子：找最短路径的问题中，状态仅仅是目前所在位置的坐标。

    当状态更加复杂是，就需要封装成一个类来表示转态了。

  3. 状态转移、转移的方式

    例子：同1中的例子，转移的方式为4个方向移动

    又如：八连通（$P_{32}$），8个方向共对应了8种状态转移。

  4. next_permutation 函数使用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int a[4] = {1, 5, 4, 3}, i;
        sort(a, a + 4); //在使用全排列函数之前，一定要先将数组中的数排序哦(不排序好像也可以)
        do {
            for (i = 0; i < 4; i++) cout << a[i] << " ";
            cout << endl;
        } while (next_permutation(a, a + 3));

        for (i = 0; i < 4; i++) cout << a[i] << " ";
        return 0;
    }

    使用 next_permutation 后，原数组的不变。

  5. 贪心算法

    贪心算法就是遵循某种规则，不断贪心地选取当期那最优策略的算法设计方法。

    如果我们不慎重地选择一个正确的规则，就会得到错误的算法。

    如果问题能够用贪心算法来求解的话，那么它通常是非常高效的。

    1. 区间问题：在可选工作中，每次都选择结束时间最早的工作。
    2. 字典序比较类型的问题经常用得上贪心法

  6. 动态规划

    1. 记忆化搜索

      在需要剪枝的情况下，可能会把各种参数都写在函数上，但是这种情况下会让记忆化搜索难以实现，需要注意

    2. def

      一步步按顺序求出问题的解的方法。

  1. memset 初始化数组

    语法： memset(<数组名>, <初始化的值>, <数组的大小>)

    虽然 memset 按照1字节为单位对内存进行填充，-1的每一位二进制位都为1，所以不可以像0一样用 memset 进行初始化。通过使用 Memset 可以快速地对高维数组等进行初始化，但是需要注意无法初始化成1之类的数值。

  2. 移位运算

    1. $1 << n = 2^n$
    2. $n << 1 = 2n$
    3. $n >> 1 = \lfloor{\frac{n}{2.0}}\rfloor$

  3. $a^b算法$

    求a的b次方对p取模的值，其中 $1 \leq a, b, p \leq 10^9$

    1
    2
    3
    4
    5
    6
    7
    8
    int power(int a, int b, int p) {
       int ans = 1 % p;
       for (; b; b >>= 1) {
          if (b & 1) ans = 1ll *ans * a % p;
          a = 1ll * a * a % p;
       }
       return ans;
    }

  4. $a * b % p$

    求a乘b对p取模的值，其中 $1 \leq a, b, p \leq 10^{18}$

    1. 方法一
      1
      2
      3
      4
      5
      6
      7
      8
      long long mul(long long a, long long b, long long p) {
         long long ans = 0;
         for (; b; b >>= 1) {
            if (b & 1) ans = (ans + a) % p;
            a = a * 2 % p;
         }
         return ans;
      }
    2. 方法二 ($P_6$)
      1
      2
      3
      4
      long long mul(long long a, long long b, long long p) {

      }

  5. 二进制状态压缩

    操作 运算
    取出整数n在二进制表示下的第k位 (n >> k) & 1
    取出整数n在二进制表示下的第0 ~ k - 1位（后k位） n & ((1 << k) - 1)
    把整数n在二进制表示下的第k位取反 n xor (1 << k)
    对整数n在二进制表示下的第k位赋值为1 n | (1<<k)
    对整数n在二进制表示下的第k为赋值为0 n & (~(1 << k))