在大部分oier看来，只要有高精度的题就是毒瘤题（雾），之前的我遇到高精度的题就直接弃疗了，但是如果考试考到，这些分就白丢了，所以说抽出时间整理了一下高精度模板，主要包括：高精加，高精减，高精乘，高精除单精 先说说如何定义： struct bigint{ int s[10100]; int len; bool zf; bigint() { memset(s,0,sizeof(s)); len=0; zf=0; } void init() { len=strlen(ch); if (ch[1]=='-') { zf=1; for (int i=2;i<=len;i++) s[i]=ch[l...

传送门（codeforces GYM）  题意：  给你一个n*m的矩形，对其进行上色，要求每个2*2的小正方形中的颜色不能相同，求方案数模p。（n<=10100,m<=5,p<=10000） Solution:  看到计数题，首先考虑组合数或者dp，组合数发现行不通，考虑dp，发现m非常小，说明可以状压，又发现n非常大，说明一定是可以用矩阵乘法的，我们很快可以想出一个状态：f[i][S]表示第i列的状态为S的方案数，我们可以预处理出S可以由哪些状态转移过来，假设a[i][j]表示i和j是否可以合法的拼在一起，那么转移方程为：     f[i][S]=∑T=0T<(1≪...

权限题。 题意： 给一个n × m的01矩阵，求一个最大的全1矩阵，输出答案 × 3。（n,m≤1000） Solution： 非常经典的一个模型，有两种方法，一种是贪心一种是dp， 这里介绍一种dp方法——悬线法（安利王知昆dalao论文《浅谈用极大化思想解决最大子矩形问题》） 悬线法的本质是dp：用 h [ i ] [ j ] h[i][j] h[i][j]表示第i行第j个数往上数，最早遇到的0的位置， l [ i ] [ j ] l[i][j] l[i][j]表示最多能往左扩展多少， r [ i ] [ j ] r[i][j] r[i][j]表示最多能往右扩展多少。大家可以思考一下为什么...

bzoj 1101[POI2007]Zap-莫比乌斯反演 题意：T组数据，每组给出m，n，d 求 ∑ni=1∑nj=1[gcd(i,j)==d](T≤50000,n,m,d<=50000)  Solution: 首先大家要记住一些结论：   μ∗1=[n==1]   类似地，    φ∗1=n    这些结论是莫比乌斯反演的精髓 然后我们就开始化简式子（一定要克服公式恐惧症啊QwQ）    N=nd,M=md    ans=∑ni=1∑nj=1[gcd(i,j)==d]   =∑Ni=1∑Mj=1[gcd(i,j)==1] （这一步大家自己yy一下吧）  =∑Ni=1∑Mj=1∑d|gc...

传送门  题意：中文题。 Solution：  因为这道题每个工人可以维修多个汽车，所以说没法直接用费用流，我们先想一个简单的贪心思路：假如说我们考虑一个工人的情况，那么他修车所需的时间为：     t1+(t1+t2)+(t1+t2+t3)+…+(t1+…+tn)    变形一下该式：     n∗t1+(n−1)∗t2+…+tn    容易看出，我们修车的顺序一定是从耗时小的开始，看到数据范围是50，所以说我们可以试试拆点：一个工人的维修情况可以看成多个只能维修一辆车的工人的维修情况，只不过他们各自需要1-N倍的时间，经过这次拆点，我们就可以把问题转化成普通的费用流了。  这道题的建图非常...

传送门 题意：  给一个字符串和m个操作，每次给出l,r,c，把字符串中l-r这段区间的字符为c的字符删掉，求最后的字符串。（n,m<=2e5） Solution：  此题显然不能离线搞，那么有什么动态的优秀的数据结构呢？我们一定会先想到线段树，我们可以维护每个区间剩余字符的个数siz和区间中每个字符的个数num，通过siz来求出每个l,r对应的在线段树上的l,r。  PS：因为字符串一定是不断减少的，所以说每个字符最多被删除一次，复杂度最多为O（mlogn），打标记也就没有意义了。 代码： #include<cstdio> #include<iostream> ...

CRT在算法竞赛中算是一个比较重要的模块，他的基本形式如下：  给出n个式子：     x≡a1 mod p1  x ≡ a 1   m o d   p 1       x≡a2 mod p2  x ≡ a 2   m o d   p 2       x≡a3 mod p3  x ≡ a 3   m o d   p 3       …  …        x≡an mod pn    x   ≡    a   n   <mtext>   </mtext>  m   o   d  <mtext>   </mtext>   p   n      求x...

题意：  给出n个齿轮的半径和n个齿轮之间的关系（角速度相等或线速度相等），两种操作，第一种操作：修改一个齿轮的半径，第二种操作：给一个齿轮角速度，输出最大的角速度，答案取ln（自然对数）。  Solution：  我们随意画一个图感受一下：   （粗边表示角速度相等，细边表示线速度相等，图中维护的是每个点的角速度和 w1 的关系）  我们可以发现一个规律：如果修改的点的父亲边是线边，那么到他线边所连的儿子的值是不包含这个点的半径的，也就是说，修改这个点的半径不会影响这个点线边所连的儿子，只会影响角边所连的儿子及儿子所在的子树；如果修改的点的父亲边是角边，那么只会影响这个点线边所连的儿子及儿子...

题意：  给你一棵树，m个条件，每个条件给出a,b,c,d,w，表示a到b和c到d路径上的点互相到达需要w的代价，现求从1号点出发能到达哪些点以及最小代价。 Solution：  不难发现这是要构造一颗最小生成树，把w按照从小到大排一遍序，对于每个条件，求出a,b的LCA和c,d的LCA，把经过他们的点都加入一个并查集中（类似Kruskal），但是暴力跳路径会T掉，所以我们就再引入一个并查集：up[i]表示从i节点往上跳最早深度最小的不在同一个联通块的点，这样路径压缩一下复杂度就很优秀了。 代码： #include<cstdio> #include<iostream> ...

题意： 给你一个数组，找一段区间使得区间内不同数的个数与区间长度的比值最小。 Solution： 这是一道经典的分数规划题，考虑二分答案k，那么我们的目标就是找一段区间使得val/len<=k，val是区间内不同的数的个数，len是区间长度，转化一下可以得到val-k*len<=0，我们可以利用线段树达到快速查询的效果：维护区间最小值，pre[a[i]]记录上一个值为a[i]的数出现的位置，每次把[pre[i]+1,i]这段区间+1，[1,i]这段区间-k，每次操作完后求[1,i]区间的最小值，如果小于0那么说明符合条件。 代码： #include<cstdio> #i...

传送门  题意： ​ 给出 k,p1,p2  k , p 1 , p 2 ，一开始串为空，每次有 p1p1+p2  p 1 p 1 + p 2 的概率在串中加一个a， p2p1+p2  p 2 p 1 + p 2 的概率在串中加一个b，当串中有k个为ab的子序列停止加字符，求停止加字符后串中为ab的子序列的个数的期望，假设结果为最简分数 ans1ans2  a n s 1 a n s 2 ,输出 ans1∗ans−12mod(1e9+7)  a n s 1 ∗ a n s 2 − 1 m o d ( 1 e 9 + 7 ) 。 Solution： ​ 明显是一道dp题，因为长度可以无穷大，所以...

传送门  题意：看原题吧，想不出比原题更好的描述了- -  Solution：  一开始思考过用网络流，但是想不出如何建图，最后还是去看了题解QwQ，建图思路很妙啊，我们先把每个点拆成四个小点，分别对应上，下，左，右，然后对应每种水管在点内分别建图（细节大家可以结合代码思考一下），由于这是一个二分图（拆点之前），所以说我们对每个点进行黑白染色，这样便可以确定每个点是连向T还是从S连过来，点与点之间都要建流量为1，费用为0的边，最后跑费用流即可，注意这里我们的流量表示的是“最大能匹配到的水管数量”，同时注意我们连边的顺序。 代码： #include<cstdio> #include&...

题意：  维护一个序列，支持单点修改，区间查询第k小。 Solution（普通的主席树相信大家都会，如果没学过建议先去学学再来看这篇文章）：  我们回忆一下不带修改的主席树是怎么求出答案的：每一棵主席树维护是前缀和，然后左右端点的主席树差分一下就能求出排名。对于这个问题，我们可以先考虑如何维护一个支持修改的前缀和，显然一个树状数组就可以做到，那么我们类比一下，在主席树上套一个树状数组（即第i棵主席树维护的是(i-lowbit(i),i]这一段区间），就可以达到我们的目的了，注意要先进行离散化。 #include<cstdio> #include<iostream> #i...

传送门  题意：  给定一个长度为n的串s，一个长度为m的串t。  有k次询问，每次给定l,r，在[1,l]中随机一个整数i，在[r,n]中随机一个整数j，问t在s[1…i]+s[j…n]中的出现次数。  n,k<=100000，m<=100 Solution：  答案可以分成三部分  1. t包含在s[1…i]内  2. t包含在s[j…n]内  3. t的前缀在s[1…i]内，t的后缀在s[j…n]内  1和2都很好处理，3看起来不是很好处理，其实很简单：枚举前缀长度k，pre[i][j]表示前缀在s串的结尾为i，前缀长度为j是否能匹配，后缀操作类似，最后求一遍前缀和即可，至于...