#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=3e5+4; struct Palindromic_Tree{ int next[maxn][26]; int fail[maxn]; int cnt[maxn]; //表示每个回文串出现的次数 int num[maxn]; //表示有多少回文串和[i节点表示的回文串]有共同的结尾(i节点回...

HDU4283 题目中的小黑屋就是一个栈，因此在处理区间时要考虑栈的特点，即“区间嵌套性”。我们令dp[i][j]代表区间[i , j]的最小代价，注意这里是单看这一个区间，即a[i]为首元素。接下来讨论a[i]的出现次序，设第k个出现，则[i+1, i+k-1]元素必将在第1~k-1个次序出现，因为a[i]入栈后在栈底，第k个出现则意味着之前k-1个元素即使入栈，也早已出栈，可视为同结构的子状态；而之后的[k+1,j]元素面对的是一个空栈，也是一个子状态。所以 这里注意对于区间DP，遍历的时候要按照区间长度从小到大遍历。其他遍历方式会影响结果。 #include<...

题目连接 题目大意：定义一种 o n e − a n d − h a ...

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick Start Create a new post 1 $ hexo new "My New Post" More ...

npm 安装 nodejs安装在了D盘，同时npm安装目录也设在了D盘，按照博客上教的方法设置即可 由于官网速度慢，想按照网友的方法设置镜像下载源，需要nrm这个工具，但由于某些原因npm安装一直卡在checking安装状态这一步（***中）。这个时候从网上查到了一个方法：删掉C盘Roaming目录下的npm和npm-cache文件夹，但是可能是我更改了默认安装目录的原因，并未找到这两个文件夹。 最后的解决方法是，使用–registry=https://registry.npm.taobao.org先临时使用镜像站下载该工具，然后按照其他教程设置默认下载源为taobao即可 he...

例题洛谷一道题 线段树的讲解推荐博客 这道题唯一难点在于lazy标记的处理，因为涉及加和乘两种区间修改，需要考虑运算顺序。 板子： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 7...

模板题 树剖模板 这个题的需求是给定一棵树，操作支持区间修改和点查询，我们一样用线段树维护区间和实现区间查询。 三种操作I、D、Q分别是对于一条路径上的点增/减和询问某个点的当前值 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 6...

[toc] A Blank Blank 计数dp，长为n的数列，每个位置上四种数字选择，题目会给出m个限制条件，每个条件要求在[l,r]范围内有且仅有几种数字。要求给出所有合法方案数。 我们可以用dp来对每种数字上次出现的位置做情况讨论，例如用dp[x][y][z][w][len]来表示0123上次出现位置分别在xyzw、当前读取到第len个字符时共有多少种方案数。然后对于r=len的限制条件，我们查看在l之后出现过的数字种数是否符合要求，即xyzw中大于等于l的有几个。 优化：由于四个位置中必定有一个等于len，所以我们可以减少一个维度，令dp[x][y][z]表示较远出现...

​ 线性基类似于线性代数中的基向量，我们找一个整数集的线性基，实际上是找这样一个集合P，使得P中的元素互相异或运算得到的结果集和原集合相等。从二进制上看，最终我们期望得到 ​ 1—– ​ 01— ​ 001- 这样的集合，同时也可以进一步将低位的0消去。 向原集合插入一个新数字 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void inst(ll a){ for(int i=61;i>=0;i--){ if(a&(1ll<<i)){ ...

题目链接 给一个无向图，含边权，并定义这样一种三元组(u, v, t)满足：从u到v有一条路径且路径上的边权异或和为t。求所有三元组的t的和 我们对它逐步拆解分析，先考虑最简单的情况——如果这个图是一棵树。首先我们发现由于异或的特殊性，经过相同的边两次等价于没有经过，所以对于所有的点对(u, v)它有唯一的异或和dis(u, v) 且等于dis(u, root) ^ dis(v, root)，因为路径上重合的部分被异或掉了。这样的关系给了我们一个启示：可以一次计算出所有点到根的异或和（用dfs）。然后再用它来求两点间的异或和。 接下来我们向图中加入环，我们知道如果在一条...

题目给出一个有向图，要求阻挡其中的一些边，使得从1到n的最短路径变长，阻挡一条边的代价是这条边的长度。 问题其实就转化为，找到从1到n的所有最短路，并在这些路中找到能阻挡最短路的一些边且边权和最小——也就是找到最短路构成图的最小割。 找所有最短路可以贪心地去找合适的边，什么样的边(u, v)是合适的呢？从1到u，从v到n的最短距离之和等于整体最短路减去这条边权时，意味着这条边可以放在一条最短路中。我们就把它加入新图的集合。 然后对新图求最大流即可。Dinic算法，正常复杂度为$n^2m$，在求解二分图最大匹配时复杂度是$m\sqrt{n}$ 1 2 3 ...

C++标准模板库（STL）封装了大量十分有用的数据结构和算法，熟练使用STL将会使我们的程序编写如虎添翼。接下来会介绍几种在程序竞赛中常用到的STL类。如果想了解更多，推荐直接访问官方文档搜索查阅 [TOC] bitset 可以理解为bit这个数据类型的数组（即取值只为0/1），大多数情况下，每个元素所占内存确实只有1bit，是bool类型的1/8。方便各种位操作的进行。 构造方法 都需要在定义时指明长度 1 2 3 4 5 6 7 8 默认： std::bitset<16> foo; //填充0 整数： std::bi...

点、线段 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 const double eps=1e-8; inline int sgn(double x){ if(fabs(x)<eps) return 0; else if(x<0) return -1; else return 1...

题目 题目给出一个点集，要求其中选三个点能构成的最大三角形的面积。 我的方法是O(n^2)，似乎能通过二分降成nlogn，不过好在这题数据不大可以过。 可以证明这三个点必在凸包点中，如果说存在一个面积更大的三角形而它有的点不在凸点上，那么必定可以在凸点上找到一点，使得（替换后）三角形面积更大。 我们先求出凸包，然后在凸点上寻找这三个点即可。寻找过程运用了旋转卡壳思想，固定一条边的跨度，然后寻找最高的顶点。 #include<iostream> #include<cmath> #include<cstdio> #include<algorit...