112. 程序设计
程序设计返回结果
Accepted: 通过Wrong Answer: 答案错误Runtime Error: 表示程序因为非法访问或未处理异常而结束。Memory Limit Exceeded: 表示程序因为使用的内存超过规定的内存限制。Presentation Error: 表示虽然程序输出的答案是对的，但是换行或空格等不符合输出格式要求Time Limit Exceed: 超时Output Limit Exceeded: 表示程序输出了过多的内容。Compile Error: 表示所提交的源代码没能通过编译，不符合语法规定。System Error, Validator Error: 表示系统发生错误无法正常判题。Segmentation Fault: 段错误：访问的内存超过了系统所给这个程序的内存空间
状态
例子：找最短路径的问题中，状态仅仅是目前所在位置的坐标。
当状态更加复杂是，就需要封装成一个类来表示转态了。状态转移、转移的方式
例子：同1中的例子，转移的方式为4个方向移动
又如：八连通（$P_{32}$），8个方向共对应了8种状态转移。next_permutation函数使用1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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后，原数组的不变。贪心算法
贪心算法就是遵循某种规则，不断贪心地选取当期那最优策略的算法设计方法。
如果我们不慎重地选择一个正确的规则，就会得到错误的算法。
如果问题能够用贪心算法来求解的话，那么它通常是非常高效的。- 区间问题：在可选工作中，每次都选择结束时间最早的工作。
- 字典序比较类型的问题经常用得上贪心法
动态规划
- 记忆化搜索
在需要剪枝的情况下，可能会把各种参数都写在函数上，但是这种情况下会让记忆化搜索难以实现，需要注意
- def
一步步按顺序求出问题的解的方法。
- 记忆化搜索
memset初始化数组语法：
memset(<数组名>, <初始化的值>, <数组的大小>)
虽然memset按照1字节为单位对内存进行填充，-1的每一位二进制位都为1，所以不可以像0一样用memset进行初始化。通过使用Memset可以快速地对高维数组等进行初始化，但是需要注意无法初始化成1之类的数值。移位运算
- $1 << n = 2^n$
- $n << 1 = 2n$
- $n >> 1 = \lfloor{\frac{n}{2.0}}\rfloor$
$a^b$ 算法
求a的b次方对p取模的值，其中 $1 \leq a, b, p \leq 10^9$
1
2
3
4
5
6
7
8int 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;
}$a * b % p$
求a乘b对p取模的值，其中 $1 \leq a, b, p \leq 10^{18}$
- 方法一
1
2
3
4
5
6
7
8long 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;
} - 方法二 ($P_6$)
1
2
3
4long long mul(long long a, long long b, long long p) {
}
- 方法一
二进制状态压缩
操作 运算 取出整数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))
