日常标题 直达链接：https://waifulabs.com/ 或许是用的英伟达那个算法？
高精度运算 高精度加法： 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…
洛谷：https://www.luogu.org/problemnew/show/U50167 Description 给定一个非降序的由 n 个整数构成的序列以及 q 个由整数i 和 j 构成的询问。对于每一个询问，输出在 a[i],a[i+1], ... ,a[j-1],a[j]里面出现次数最多的那个(些)整数出现的次数。 Input 第一行包含两个整数， n 和 q。第二行包括 n 个整数 a[1],a[2], ... ,a[n]，由空格分开。以下 q 行每一行包括一个询问，一个询问由两个整数 i 和 j 构…
动态规划 维基百科上给出的动态规划的定义是：动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 动态规划和递推有些相似，而递推求出的是数据，所以只是针对数据进…
洛谷：P3386 题目背景 二分图 题目描述 给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数 输入输出格式 输入格式： 第一行，n,m,e 第二至e+1行，每行两个正整数u,v，表示u,v有一条连边 输出格式： 共一行，二分图最大匹配 输入输出样例 输入样例#1： 1 1 1 1 1 输出样例#1： 1 邻接矩阵（老码风） #include <cstdio> #include <iostream> #include <algorithm> #include &…
数据结构 树状数组，堆 线段树 单点，区间 动态开结点 并查集 加了路径压缩之后不能随便撤销 使用启发式合并复杂度是 O(n log n)，按秩合并是 O(nα(n))。 平衡树 treap 比较好写 splay 比较难写， noip 也不会考这么高级的东西 只能说 (开了 O2 的)set 秒杀一切 dfs 序与树链剖分 非传统方法 点事件 分块 cdq 分治 树状数组 具体思想就是要维护一个序列 a 的前缀和，我们可以维护一个辅助序列 s，使得 si = ∑j2(i-lowbit(i);i] aj，然后我们发…
搜索问题 搜索是玄学，最稳定的应用是写暴力 or 骗分。 一个搜索问题的基本模型有以下几个要素： 状态：表示当前搜索到的局面。一般用x,y,z表示。一开始我们处于初始状态。 代价：表示对当前状态好坏的一个衡量。一般用f(x),g(x)表示，指代状态代价。 扩展（转移）：表示从当前状态出发，我们再进行一步搜索的过程。在扩展过程结束以后，我们可能会转移到若干个新的状态。一步转移也会带来代价，称为转移代价。 搜索问题可以分为两类：可行性搜索与最优性搜索。 在可行性搜索问题当中，目标是搜索到某些给定状态，问是否能够从初始状…
笔记 1、出度：以顶点v为起点的弧的数目 入度：顶点v为终点的弧的数目 2、如果在有向图G中，有一条<u，v>有向道路，则v称为u可达的，或者说，从u可达v。 3、强连通图：若有向图G的任意两个顶点都互相可达，则称图 G是强连通图，如果有向图G存在两顶点u和v使得u不能到v，或者v不能到u，则称图G是强非连通图。 4、强连通分量：如果有向图G不是强连通图，他的子图G2是强连通图，点v属于G2，任意包含v的强连通子图也是G2的子图，则称G2是有向图G的极大强连通子图，也称强连通分量。 5、极大强连通子图（…
裴蜀定理 在数论中，裴蜀等式是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a,b和m，关于未知数 x和y的线性丢番图方程（称为裴蜀等式）：ax+by=m 有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 x、y都称为裴蜀数，可用扩展欧几里得算法求得。 就是关于 x, y 的不定方程 ax + by =c 有整数解的充要条件是 gcd(a,b)∣c 。 题目见洛谷:P4549 模板 #include <cstdi…
简介 Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 无优化复杂度：O(n ^ 2) 那么有O（km）的Spfa算法我们为什么需要Dijkstra算法呢？ 因为某些毒瘤出题人会专门设计网格图来卡Spfa算法，使其变为O（m ^ 2）如下方提到的落谷题目。 洛谷：P3371（弱化版） Spfa能过 P4779（标准版）卡S…
