字符串哈希 AcWing841. 字符串哈希 #include<iostream> #include<cstdio> #include<queue> #include<string> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #def...

AcWing 835. Trie字符串统计 #include<iostream> using namespace std; typedef long long ll; typedef pair<int, int> PII; const int N = 1e5 + 10; int son[N][26],cnt[N],idx; char str[N]; void insert(char str[]){  int p =0; for(int i = 0;str[i];++i){  int u = str[i] - 'a'; if(!son[p]...

AcWing 846. 树的重心 给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。 请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。 输入格式 第一行包含整数n，表示树的结点数。 接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。 输出格式 输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。 数据范围  输入样例 9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6  输出样例： 4  代码 #incl...

A - Minimal Square 题意 给两个完全一样的矩形(平行且不重叠) 求能覆盖两个矩形的最小正方形的面积 思路 只有两种摆放方式 将两个矩形上下并列或者左右并列 得到的新图形 长或者宽是之前的二倍 判断一下并排之后的图形长和宽的最小值即可 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 ...

区间问题 区间选点 给定 N N N个闭区间 [ a i , b i ] [ai,bi] [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数N，表示区间数。 接下来 N N N行，每行包含两个整数 a i , b i ai,bi ai,bi，表示一个区间的两个端点。 输出格式 输出一个整数，表示所需的点的最小数量。 数据范围  1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1≤N≤105  − 1 0 9 ≤ a i ≤ b i ≤ 1 0 9 -10^{...

Busy Robot 题意 机器人初始在一数轴上的原点 某时刻接受命令 并朝命令方向前进 每秒前进1距离 在未到达当前命令的终点时 忽略当前时刻的其他命令 若机器人在  [ t i , t i + 1 ] [t_i,t_{i+1}] [ti​,ti+1​] 时间内移动到  x i x_i xi​ 位置 视为完成一次指令 (被忽略的命令可能会成功执行) 给出一系列的指令问机器人能完成多少次 思路 记录每次指令的起点  s t st st 和终点  e d ed ed 下一次停止的时间  n e t net net 上一次接收到可执行命令的时刻  l a s las las 遍历每个指令 如果当前...

离散化 ①：要求保序 排序、判重、二分 vector<int>alls; int find(int x){  //二分 int l = 0, r = alls.size(); while(l < r){  int mid = l+ r >> 1; if(alls[mid] >= x)r = mid; else l = mid + 1; } return r + 1; } sort(alls.begin(),alls.end()); //排序 alls.erase(unique(alls.begin(),alls.end()),alls.end()); //判...

线段树基本操作 query() int query(int u, int l, int r) {  //查询操作 if (tr[u].l >= l && tr[u].r <= r)return tr[u].v; //树中节点已经被完全包含在[l,r]中 int mid = tr[u].l + tr[u].r >> 1; int v = 0; if(l > mid)return query(u << 1 | 1,l,r); else if(r <= mid)return query(u << 1,l,r); else{ ...

组合数定义  C a b = a ! b ! ( a − b ) ! C^{b}_{a} = \frac{a!}{b!(a-b)!} Cab​=b!(a−b)!a!​ 带模数 数据范围(a 、b较小)  1 ≤ n ≤ 10000 1≤n≤10000 1≤n≤10000,  1 ≤ b ≤ a ≤ 2000 1≤b≤a≤2000 1≤b≤a≤2000  m o d = 1 e 9 + 7 mod = 1e9+7 mod=1e9+7  C i j = = C i − 1 j + C i − 1 j − 1 C^{j}_{i} == C^{j}_{i-1} + C^{j-1}_{i-1} Cij​...

FloodFill AcWing1097. 池塘计数 农夫约翰有一片  N ∗ M N∗M N∗M 的矩形土地。 最近，由于降雨的原因，部分土地被水淹没了。 现在用一个字符矩阵来表示他的土地。 每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。 现在，约翰想知道他的土地中形成了多少片池塘。 每组相连的积水单元格集合可以看作是一片池塘。 每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。 请你输出共有多少片池塘，即矩阵***有多少片相连的”W”块。 输入格式 第一行包含两个整数 N 和 M。 接下来 N 行，每行包含 M 个字符，字符为”W”或”...

多源BFS AcWing173. 矩阵距离 给定一个N行M列的01矩阵A， A [ i ] [ j ] A[i][j] A[i][j] 与  A [ k ] [ l ] A[k][l] A[k][l] 之间的曼哈顿距离定义为：  d i s t ( A [ i ] [ j ] , A [ k ] [ l ] ) = ∣ i − k ∣ + ∣ j − l ∣ dist(A[i][j],A[k][l])=|i−k|+|j−l| dist(A[i][j],A[k][l])=∣i−k∣+∣j−l∣ 输出一个N行M列的整数矩阵B，其中： B [ i ] [ j ] = m i n 1 ≤ x ≤ N ...

两种算法解决从起点到终点状态过多的问题（BFS剪枝） 双向广搜 双向广搜实际是 B F S BFS BFS的一种剪枝形式 实现方式是 <mark>同时从起点和终点搜索到相遇为止</mark> AcWing190. 字串变换 已知有两个字串  A A A,  B B B 及一组字串变换的规则（至多6个规则）:  A 1 − > B 1 A_{1} -> B_{1} A1​−>B1​  A 2 − > B 2 A_{2} -> B_{2} A2​−>B2​ … 规则的含义为：在  A A A 中的子串  A 1 A_{1} A1​ 可以变...

连通性 Acwing 1112. 迷宫 一天 E x t e n s e Extense Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。 同时当 E x t e n s e Extense Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上， E x t e n s e Extense Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。 如果起点或者终点有一个不能通行(为#)，则看成无法办到。 注意：A、B不一定是两个不同的点...

常用的几种剪枝策略 1.优化搜索顺序 大部分情况下 我们应该优先搜索分支较少的节点 例如 分组问题 可以先从花费较大的元素搜索 可以减少状态分支 2.排除等效冗余 如果不考虑顺序的话 尽量用组合的方式搜索 即与组内元素顺序无关 3.可行性剪枝 在搜索过程中已经检测到不合法 可以提前退出 4.最优性剪枝 在搜搜过程中 已经检测到当前答案大于最优解 可以提前退出 5.记忆化搜索(DP) AcWing165. 小猫爬山 翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。 经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。 翰翰和达达只好花钱让它们坐索道...