高精度运算 高精度加法： int main() { scanf("%s%s",&a1,&b1); if(a1[0] == '0' && b1[0] == '0') { cout << "0"; return 0; } for(int i = 0;i < strlen(a1);++i) a[strlen(a1) - i - 1] = a1[i] - '0'; for(i…
动态规划 维基百科上给出的动态规划的定义是：动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 动态规划和递推有些相似，而递推求出的是数据，所以只是针对数据进…
数据结构 树状数组，堆 线段树 单点，区间 动态开结点 并查集 加了路径压缩之后不能随便撤销 使用启发式合并复杂度是 O(n log n)，按秩合并是 O(nα(n))。 平衡树 treap 比较好写 splay 比较难写， noip 也不会考这么高级的东西 只能说 (开了 O2 的)set 秒杀一切 dfs 序与树链剖分 非传统方法 点事件 分块 cdq 分治 树状数组 具体思想就是要维护一个序列 a 的前缀和，我们可以维护一个辅助序列 s，使得 si = ∑j2(i-lowbit(i);i] aj，然后我们发…
模板 #define lowbit(x) x & -x //1D void add(int x,int t) { while(x <= n) { v[x] += t; x += lowbit(x); } } int query(int x) { int res = 0; while(x) { res += v[x]; x -= lowbit(x); } return res; } //2D n * m void add(int x,int y,int t) { while(x <= n) { f…
洛谷：P3366 ，和Dijkstra堆优化模板差不多 题目描述 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz 输入输出格式 输入格式： 第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000） 接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi 输出格式： 输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz 输入输出样例 输入样例#1： 4 5 1 2 2 1 3 2 1 4 …
