青烟绕指柔

分类

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

全部文章（共382篇）

游走配对

很裸的费用流。会费用流应该都会做。因为我们是选择每个x去匹配y。然后我们可以直接源点S到x，y到汇点T。然后点权会变，我们直接拆点，并且把两点之间拆成q条边即可。 AC代码： #pragma GCC optimize("-Ofast","-funroll-all-lo...

2020-06-12

1 544

简单瞎搞题

显然可以dp。 dp[i][j] 为前i个数字能否构成j。怎么状态转移呢？每次第i个数有一个对应区间，我们直接尝试加入区间的每一个数字，和前i-1个数能构成的数字去匹配。我们就可以发现这样复杂度是：1e6 * 100 * 100为1e10，不过我们只需要知道能否构成，所以可以状态压缩，然后用bi...

2020-05-19

0 984

换个角度思考

显然是可以离线之后fenwick维护。因为不喜欢离线，所以直接主席树了。每次找到对应区间，然后相当于就是区间sum的问题了。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=N*40; i...

2020-04-29

4 1264

迷宫

先跑出起点到每个点的最短路，然后每个点到终点的最短路。如果d==0，那么直接特判，否则使用一定是最优的。枚举每个点，到能到的最小到终点的最短路，其实就是矩形查询min。直接ST表维护即可。 AC代码： #pragma GCC optimize("-Ofast","...

2020-04-18

2 456

Shortest Path

其实我们画画图就可以发现，如果把边全部选完，那么一定是有解的。所以，我们就是删除权值和最多的边，使得原问题还有解。什么是无解呢？就是某个边删除之后，连通块个数为奇数了，那么就不行。所以直接dfs一次即可，如果当前子树点的个数为偶数个，直接删除即可。 AC代码： #include<bits...

2020-04-03

2 896

激光炸弹

激光炸弹 *一种新型的激光炸弹，可以摧毁一个边长为 R 的正方形内的所有的目标。现在地图上有 N 个目标，用整数Xi,Yi表示目标在地图上的位置，每个目标都有一个价值Wi。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个边长为 R 的正方形的边必须和x，y轴平行。 ...

2019-12-27

0 624

a^b%p

a^b 求 a 的 b 次方对 p 取模的值。输入格式三个整数 a,b,p ,在同一行用空格隔开。输出格式输出一个整数，表示a^b mod p的值。数据范围 1≤a,b,p≤1e9 输入样例： 3 2 7 输出样例： 2 时/空限制： 1s / 32MB 这道题刚看会发现诶，直...

2019-12-27

0 532

康拓展开与康拓展开的逆

康托展开康拓展开一般是用于计算一个全排列数字排在所有全排列的大小位置。那么到底怎么计算呢？敲重点 X=a[n]∗(n-1)!+a[n-1]∗(n-2)!+…+a[i]*(i-1)!+…+a[2]*1!+a[1]*0![1] 从第一个数字开始到倒数第二个数字，计算需要计算的那个数字之后...

2019-12-27

0 530

数字的全排列

数字的全排列直接上代码 #include<bits/stdc++.h> using namespace std; int n,p[10],vis[10]; void dfs(int x)//x为当前的枚举位置 { if(x==n+1)//如果位置都枚举完毕了，就打印出来 {...

2019-12-27

0 456

编辑距离

编辑距离这是一个典型的动态规划问题问题就是给你两个字符串a,b，有三种操作增加一个字符删除一个字符改变一个字符问通过上述的操作，最少多少步，能把a变为b 直接上代码 #include<bits/stdc++.h> using namespace ...

2019-12-27

0 514