Za
- 将满足某一性质的边长设为1，不满足的设为0，通过求最短路或者维护一个双端队列可以得到两点之间的满足该性质的边的最小值或最大值。
- 最大值最小/尽可能大/具有二段性的问题可以想想能否用二分。
- 具有结合律(1 + 1 + 1 + 1 == 1 + 3 == 2 + 2 -> 1 2 4 8)的性质，可以考虑倍增。
- 使用前缀和的时候，若用到-1，（j - i-1）考虑把所有的下标向后移一位
- 用Hash直接记不了pair 采用 LL 然后 x * 1e6 + y （看数据大小） 求这个hash值的时候1e6要转LL
- unsign int scanf(“%u”, &a), ull -> scanf(“%llu”, &b)
- 四舍五入, round(_double);
- 拓扑排序判断有无环: return tt == n - 1; [0, n - 1]
- 二维坐标化一维 x, y -> x * n + y(x, y [0, n - 1])
- 加法在mod 2 的意义上，相当于 ^ 运算（开始的值要mod 2后
- 多组数据时，存储图的边的idx = 0，ind = 0
- a xor b = c <-> a xor c = b; a xor 0 = a
- 位运算枚举一个集合T的子集: for(int S = T; S; S = T&(S-1))
- 血的教训, 滚动数组不要反复memset, 把它赋值回INF就好了. 用到上一层的[i, j]就把上一层的[i, j]赋值回INF!!!也建议在状态更新的最外层, 先判断上一层这个状态是否合法, 是否可以用于转移见测试
- memset结构体
- 单个 - memset(&Node,0,sizeof Node);
- 数组 - memset(Node,0,10*sizeof Node);
二分
- 小数点保留2位一般去4位(即比保留多两位即可)
- 实数二分[0, 1000], l 取不到 右端点, r 取不到 左端点, 虽然输出保留小数因为精度问题可能看不出来,还是要注意 是取不到的, 有时会有大问题.
卡常
#include <ctime>
int start = clock();
if(clock() - start >= CLOCKS_PER_SEC * 0.9)
{
cout << ... << endl;
exit(0);
}
注意
clock()函数很慢， 为了减少clock()的次数（控制在几百次可能），前面加上某个条件减少次数 如 i % 1000000 == 0
使用常量CLOCKS_PER_SEC，因为不同系统下可能常量不同
离散化
若不是unordered_map，可能还是保序的快 qwq详见
- 保序 - 排序，判重，二分 （离线操作，需要把所有需要离散化处理的数据都读入后再操作）
- 不要求保序 - map, hash （不要忘记n = 0; S.clear();）（在线离散化）
sort(id + 1, id + n + 1);
n = unique(id + 1, id + n + 1) - (id + 1);
int get_id(int x)
{
return lower_bound(id + 1, id + n + 1, x) - (id + 1) + 1; // 返回下标以1开始
}
并查集
不要忘了压缩路径 fa[x] = t;
int get_fa(int x)
{
if(fa[x] == x) return fa[x];
int t = get_fa(fa[x]);
return fa[x] = t;
}
常常用一维数组，所以常把二维化为一维
数组模拟队列
int hh = 0, tt = -1 / 0 // 根据初始有无元素
while(hh <= tt)
// 加入
q[++ tt] = i;
// 弹出
int t = q[hh ++];
数组模拟循环队列
用到的是[0, N - 1];
int hh = 0, tt = 0;
while(hh != tt)
// 加入
q[tt ++ ] = i;
if (tt == N) tt = 0;
// 弹出
int t = q[hh ++ ];
if (hh == N) hh = 0;
高精度
先写非高精，再改为高精。
void add(LL a[], LL b[])
{
static LL c[M];
memset(c, 0, sizeof c);
for(int i = 0, t = 0; i < M; i ++)
{
t += a[i] + b[i];
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}
void mul(LL a[], LL b)
{
static LL c[M];
memset(c, 0, sizeof c);
LL t = 0;
for(int i = 0; i < M; i ++)
{
t += a[i] * b;
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}
int cmp(LL a[], LL b[])
{
for(int i = M - 1; i >= 0; i --)
if(a[i] > b[i]) return 1;
else if(a[i] < b[i]) return -1;
return 0;
}
void print(LL a[])
{
int k = M - 1;
while(k && !a[k]) k --;
while(k >= 0) printf("%lld", a[k --]);
puts("");
}
整数类型转string 连接
inline string get_string(int x)
{
string res = "";
while(x) res = (char)(x%10+'0') + res, x /= 10; // + res!!!
return res;
}
表达式求值
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int N = 1e5 + 10;
stack<int> num;
stack<char> op;
inline int get_prior(char c)
{
if(c == '+' || c == '-') return 1;
if(c == '*' || c == '/') return 2;
}
inline void eval() // 用末尾的运算符操作末尾两个数
{
int b = num.top(); num.pop();
int a = num.top(); num.pop();
char c = op.top(); op.pop();
int x;
if(c == '+') x = a + b;
else if(c == '-') x = a - b;
else if(c == '*') x = a * b;
else x = a / b;
num.push(x);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string str;
cin >> str;
for(int i = 0; i < str.size(); i ++)
{
char c = str[i];
if(c >= '0' && c <= '9')
{
int x = 0, j = i;
while(j < str.size() && str[j] >= '0' && str[j] <= '9')
x = x * 10 + str[j ++] - '0';
num.push(x);
i = j - 1; // !!
}
else if(c == '(') op.push(c);
else if(c == ')')
{
while(op.top() != '(') eval();
op.pop();
}
else
{
// 不能取到左括号
while(op.size() && op.top() != '(' && get_prior(op.top()) >= get_prior(c)) eval();
op.push(c);
}
}
while(op.size()) eval();
cout << num.top() << endl;
return 0;
}
哈希
- 哈希不一定就一定一一对应，也可以是大致分类，然后在一个链表里寻找，是否有对应的值。例
- 常见哈希方式：和、积、和与积的和、所有距离之和
- 字符串哈希进制值可取131、13331较好。可以采用多哈希（不同的mod值，注意保成正数！！！
- 字符串的比较是$O(n)$，可以利用hash求出最大的相同前缀，然后比较下一位即可例
图论
- 符合拓扑序，不管边权正负。
- 一个的和/另一个的和 max -> 01分数规划 -> 二分一个定值 将不等式整理一下 重新定义点权或边权 再做一遍图论算法
- 正环（相当于最长路）spfa更新dist方式改变一下即可.
- 关于差分约束的问题（求最小解 最长路为例）
- 边权无限制，spfa - O(nm)
- 边权非负权（特殊），有向图tarjan，强连通分量 - O(n + m)
- 边权 > 0 拓扑排序 - O(n + m)
- 剪边若是左边的点集指向右边的点集，可以在两集合之间建一个虚拟点，边数n * m -> n + m，相当于找了个跳板 例，因使用拓扑排序涉及入度、出度时，要每次建立一个虚拟源点，可以采用n + i(i [1, m])，所以q[]大小 开N + M
- 拆点（在到一个点时，这个点的状态有多个的时候）
- 当一个图的出边最多只有一条时，可用dfs判环（1.走到终点没有出边（一条链） 2.基环树， used[]i是否被遍历过，cur[]，i是否在栈中） 搜的时候把used 和 cur都标记为true，出去cur[] false;, 在栈中&used 有环， 不在栈&used 另一条路径搜过了，无环
数学知识
- gcd(x, y, z) = gcd(x, y - x, z - y);
- 皮克定理(证明网上找吧qwq)例题
- S：多边形面积， a：内部整点数，b：边上整点数
- S = a + b / 2 - 1
- b = gcd(x, y)（把这条边一段移到原点）
- 两个正整数p, q互质，由p, q不能凑出的最大正整数为p * q - p - q或者写成(p - 1)(q - 1) - 1，对n个数仍成立。同时，当这两个不互质，那么没有凑不出的最大的数。（这里的凑指的是任意非负整数倍数的p和q相加）同时，令d = gcd(p, q)，能凑出的数必然是d的倍数，不是d的倍数的数一定不能凑出。对于多个数它所不能表示的数p < a1例题
DP
- 优化方式
- 推公式（类似完全背包的从状态表达式本身入手、滑动窗口（单调队列）
- 数据结构（线段树、树状数组、splay、
决策集合的元素只增多不减少的情况像LCIS一样采用维护一个变量来记录决策集合的当前信息.- 要取类似aabbbbb(左边都是a, 右边都是b(或者与a相关/与b相关), 理论上要枚举分割点*计算区间和$O(n^2)$实际上可以通过先计算b的前缀和变为$O(n)$)
(例如[l, r], ts[l-1] = 0, 再计算[l, r]的b的前缀和, 用ts[r]直接表示全选b的情况的答案(要更新进去!!!)之后从[l, r], 用sum数组记录前面选1~l-r+1个a的值, 用sum + ts[r] - ts[k]来更新答案)
- 解题经验
记录方案(决策)
开一个把dp状态的状态全部记录下的结构体,
用pre
注意while的结束要看什么时候是不用继续记录方案, 这里明显是前面没有选的个数的时候!
inline void Schprint(S t)
{
int i,j,l,r,z1,z2;
i = t.i, j = t.j, l = t.l, r = t.r, z1 = t.z1, z2 = t.z2;
while(j) //应当是看上一个的j的个数还有没有
{
for(int p = r; p >= l; p --)
ans.push_back(mkp(i, p));
t = pre[i][j][l][r][z1][z2];
i = t.i, j = t.j, l = t.l, r = t.r, z1 = t.z1, z2 = t.z2;
}
reverse(ans.begin(), ans.end());
for(int p = 0; p < ans.size(); p ++)
cout << ans[p].fi << ' ' << ans[p].se << endl;
}
在状态转移可以更新当前值的时候更新pre数组
inline void solve_print(int i)
{
if(!i) return;
solve_print(pre[i]);
cout << a[i] << ' ';
}
贪心
- 两个序列随机组成n对数的和的最大值最小是排序不等式,两个序列一个升序排,一个逆序排.
其他
<math.h>中有些常用值
#if !defined(__STRICT_ANSI__) || defined(_XOPEN_SOURCE) || defined(_GNU_SOURCE) || defined(_BSD_SOURCE) || defined(_USE_MATH_DEFINES)
#define M_E 2.7182818284590452354
#define M_LOG2E 1.4426950408889634074
#define M_LOG10E 0.43429448190325182765
#define M_LN2 0.69314718055994530942
#define M_LN10 2.30258509299404568402
#define M_PI 3.14159265358979323846
#define M_PI_2 1.57079632679489661923
#define M_PI_4 0.78539816339744830962
#define M_1_PI 0.31830988618379067154
#define M_2_PI 0.63661977236758134308
#define M_2_SQRTPI 1.12837916709551257390
#define M_SQRT2 1.41421356237309504880
#define M_SQRT1_2 0.70710678118654752440
#endif
