const int MAX_N=300010; int dat[2*MAX_N-1]; int n; #define maxn 0x3f3f3f3f void init(int _n){ n=1; while(n<_n) n<<=1; for(int i=0;i<2*n-1;i++) dat[i]=maxn; } void update(int k, int a){ //将位置k的值改为a k+=n-1; //从n-1处开始存放单个元素的值 dat[k]=a; whil...

单调队列是一种在直觉上很容易想到的数据结构。有一个经典例子是滑动窗口问题，对于一串数字（长为n），存在一个在其上滑动的矩形窗（长为k），要求线性时间内求出每个窗口中的最大值。我们可以想见在窗口的每次右移后，新的最大值与原最大值会具有很密切的关系。我们可以设置一个单调减队列q，添加元素时从队尾添加，遇到比这个元素小的，全部剔除，因为这些元素既没有新元素大，位置又靠前，它们已经失去了“出场机会”。如果发现队首元素已不在窗中（入队过早），则将其弹出。 在牛客2019暑期多校第三场中，F题运用了这一算法。 牛客暑期训练样题 #include<bits/stdc++.h> using...

题目链接 官方给的题解是这样的： 直接从别的博客复制过来了，有几点需要补充解释一下： d为满足  的最小正整数，求它的目的是为了更方便的去求 ，因为它一定是d的倍数。   求g的时候，指数向上取整是为了保证j次方之后一定为d的倍数，当然大概率是会多乘几个质因数   强调k<=30这个界限是因为，在 的极限情况下，k最多不会超过30，2^30=1073741824。而在这之上时k/j向上取整只能为1，所以在这之后所加的值一定相同 贴代码：  #include<bits/stdc++.h> using namespace std; ty...

字符串哈希： 讲解 大意就是将字符串视为一个多位的数，用unsigned long long 保存，溢出可以视为对2^64取模。 回文树：  博客 另一篇博客 推荐配合OIWiki上的图食用 每个节点代表当前前缀的最大回文串后缀，next指向的是代表[通过前后加上一个新字符能得到的新回文串]的节点，suffix指向的是加入新字符后，该回文串的最大的回文后缀。有两个根，最终节点数-2就是回文串总数。 后缀自动机： 讲解和应用直接推荐OIwiki了，传送门 这篇作为补充https://oi.men.ci/suffix-automaton-no...

const int N=2e4+10; int n,sa[N],rnk[N],height[N]; char s[N]; //sa数组表示字典序为i的后缀是谁，rnk数组表示某个后缀的排名 void buildSA(int m=128){ int cnt[N],rnk1[N],rnk2[N],tmpSA[N]; //cnt[i]用来记录rnk小于等于i的子串已经有多少个了，这样可以直接用cnt[rnk[i]]更新sa //n=strlen(s)+1; //s[n]=0; 存疑 fill(cnt,cnt+m,0); for(int i=0;i...

八数码问题，类似华容道，要求给出复位的操作序列。 康托展开用于解决排列相关问题，实现了一个排列到整数双射。因此我们可以用一个整数表示当前排列，便于进行搜索。以下是康托展开和逆展开的模板。 int cantor(int* st){ int x=0; for(int i=0;i<9;i++){ int smaller=0; for(int j=i+1;j<9;j++){ if(st[j]<st[i]) smaller++; } x+=fac...

这道题是牛客2019暑期多校第六场的C题，题目链接 大意是，给出一个字符串，对于它所有的回文子串，若其中某个是另一个的子串，则视其为一对，求总对数。 看到回文子串就想到了回文树。简单回顾一下，回文树每个节点代表以当前字符结尾的最长回文子串，next指向前后添上某个字符后更大的那个子串，fail（suffix）指向当前子串的最长回文后缀。初步的想法是，对于某个节点，它fail链上的所有节点以及反向next链上的所有节点，是它的所有回文子串，对于所有节点求出这个数量，并相加。可是实际操作中发现，fail链和反next链上的节点有重复，导致结果会重复计数某个节点。 于是考虑通过标记避免重复计数...

舞蹈链算法，用于求解精确覆盖或者重复覆盖问题，目的是保证每一列的值最后为1或大于1，搜索中选用某一行后就将这一行以及它所解决的所有列删去，最后如果发现有列无法删去则失败，回溯并将之前删去的都恢复；如果最后发现所有列都被删去了，则说明问题解决。 它首先可以用来解决数独问题：转化为每行，每列，每个宫都有1~9，每格只有一个数字这个条件。是精确覆盖问题。 HDU3111题目链接 #include<bits/stdc++.h> using namespace std; const int N=350; const int M=740; const int inf=0x3f3f3f...

本文着重介绍在项目开发过程中遇到的问题和解决方案。   1.数据库配置与连接 要求使用access数据库。首先，什么是数据源 讲解。我们可以直接在cmd中输入下列语句打开ODBC管理程序 %windir%\syswow64\odbcad32.exe 根据网上配置数据源的教程配置好数据源。之后就可以用这个数据源的名字快捷连接它。 连接的时候发现一直在报java.lang.ClassNotFoundException，查资料才发现jdk大于1.7的版本中，jdbc-odbc已被删去，之后发现了各种方法，参考了这个博客https://blog.csdn.net/weixin_4...

首先我们要对扫描线算法建立一个形象的认识，可以参考链接。大概就是，对于某个由多个矩形覆盖重叠形成的不规则几何体的面积，可以转化为从下往上一系列小矩形，有点像垒砖，层数为线段数-1，也就是矩形数*2-1。 在这个算法里，线段树维护整个区间被覆盖的，有效的“长”，它是由一小段一小段的线段组成，我们对于每条线段添加一个flag成员变量，当该线段被某矩形的下边包含，该线段flag+1，上边则-1。如果该线的flag大于0，则说明该线段在当前高度的有效的，就把它的len赋上它原本的长度，详细的可以看代码： #include <cstdio> #include <cstring&g...

转载邝斌的板子，这里稍微留一点讲解吧，万一之后用得着呢 1.米勒罗宾算法用到了费马小定理和二次探测定理，可以看这篇大佬博客。 2.Pollard_Rho算法可以看看这篇https://blog.csdn.net/doyouseeman/article/details/51204612 poj1811模板： #include<iostream> #include<cstdio> using namespace std; const int S=20;//随机算法判定次数，S越大，判错概率越小 long long mult_mod(long long a,lo...

最小路径算法解决以下问题：对于一个DAG，找到最少的路径（连续的若干边）条数（单个顶点也算一条路径），覆盖所有顶点。按路径可否相交分为两类。 首先是路径不相交的最小覆盖： 我们可以把每个顶点拆为出点和入点，这时每种路径安排都是一个二分图P'，问题转化为了求该二分图的最大匹配：如果在P'中增加一条匹配边pi'－－>pj'，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个。 求解二分图最大匹配用匈牙利算法。 依次遍历每个点尝试寻找增广路。一条增广路满足两端是非匹配点，这样的路径可以通过调整使得匹配数加一。 值得注意的...

众所周知，DP算法用于解决拥有最优子结构或者可记忆化搜索的问题。数位DP一般属于后者。 对于HDU2089这样的经典问题，我们可以看到，如果从0到1000000一个数字一个数字地去判断是否合***造成很多计算的浪费，譬如0~999这个区间有多少合法的值，其实是可以复用的。我们因此引入记忆化搜索来解决这个问题。 dp[pos][state];    //int dp[6][2]; 表示在0~10^pos-1区间上，状态为state时，满足要求的数字个数，本题中state只需表示前一位是否为6 接下来只需要按照逻辑dfs即可，详情参照https://blog.csdn.net/...

        可持久化线段树可以用来解决这个经典问题：对于给定数字序列，求出 [l, r] 区间中第K大的数。我们首先考虑这样一棵线段树i，它的每个节点对应一段值域，记录了数组中[1, i]区间中的数字有多少落在这个值域。如果我们能有n棵这样的线段树，那么对于区间第K大问题就可以通过搜索来解决，这个式子表示的就是对于i所代表的值域，[l,r]中有多少元素在此内。比如如果左区间的量为res小于k，那么就继续在右区间找第k-res大的值，最终l==r时寻找完毕。 但我们知道不可能建立n棵完整线段树，内存将会不够用，于是考虑相同的节点的复用问题。我们每加入一个节点，实际上只修改了logn个节点（...