BzhH

P1707 刷题比赛 一道显而易见的矩阵加速题，只需要将转移矩阵按照题目的要求构建出来就行了。 状态矩阵 ∣ak+1bk+1ck+1akbkckk2kwkzk1∣\begin{vmatrix} a_{k+1}&b_{k+1}&c_{k+1}&a_k&b_k&c_k&k^2&k&w^k&z&k&1 \end{vmatrix}​ak+1​​bk+1​​ck+1​​ak​​bk​​ck​​k2​k​wk​z​k​1​​ 转移矩阵 ∣p11100000001u10100000011x00100000q00000000000v00000000000y00000000r0000010000t010002100001000000w00001000000z010200011001∣\begin{vmatrix}p&1&1&1&0&0&0&0&0&0&0\\1&u&1&0&1&0&0&am ...

对于题目给出的两个查询，我们我可以将它这样转换： 对于操作一，用dfs序将一个子树转化为一段连续的区间,然后根据dfs序建立一个trie树，那么查询一个子树即为查询一段区间 对于操作二，根据根到结点的路径建立一个trie树,同样也可以转化为一个区间查询 于是就可以建两个trie树,分别对应两个操作 结合代码理解 #include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N = 4e5 + 50, M = 32 * N;int tr1[M][2], root1[N], tot1, siz[N];int w[N], n, q, maxn[M], id[N], it[N];int head[N], ver[N], net[N], idx, cnt, root2[N];int tr2[M][2], dep[N], fa[N][25], maxd[M], tot2;void add(int a, int b){ net[idx] = head ...

例题Pollard-Rho算法 要求的是一个数的最大质因子，常规做法肯定是过不了的这个数据范围的 ##MillerRabin概率测素数法 根据两个定理 费马小定理:若ppp为质数,ap−1≡1(modp)a^{p-1}\equiv 1 \pmod{p}ap−1≡1(modp) 二次检查定理:若ppp为质数,x2≡0(modp)x^2 \equiv 0 \pmod{p}x2≡0(modp)的解为x1=1,x2=p−1x_1=1,x_2=p-1x1​=1,x2​=p−1 有了这两个定理,就可以开始MillerRabin算法了 通过费马小定理可知,如果一个数满足费马小定理,那么这个数很可能为素数,并不是一定. 对于一个素数 p,p−1p , p-1p,p−1 一定是偶数,那么不妨设 p−1=m×2qp-1=m \times 2^qp−1=m×2q 那么我们就可以通过一个数 ama^mam 不断自乘得到下面这个序列 am×2,am×22,...,am×2qa^{m \times 2},a^{m \times 2^2},...,a^{m \times 2^q}am×2,am×22,...,am× ...

P1221 最多因子数 根据唯一分解定理 m=p1a1×p2a2×...×pkakm=p_1^{a_1}\times p_2^{a_2} \times ... \times p_k^{a_k}m=p1a1​​×p2a2​​×...×pkak​​. 那么 mmm 的约数个数就为 (a1+1)(a2+1)...(ak+1)(a_1+1)(a_2+1)...(a_k+1)(a1​+1)(a2​+1)...(ak​+1). 并且观察数据范围, n≤5×104n \le 5 \times 10^4n≤5×104. 那么可以得出 k≤16k \le 16k≤16 ,因为 216≥5×1042^{16} \ge 5 \times 10^4216≥5×104. 所以接下来就可以直接通过搜索枚举前16个质数的幂次方 aaa 就行了. 但是由于答案可能很大,所以要用高精,但如果每一次更新答案都用一次高精,很明显会超时. 根据小学知识 lg⁡(x×y)=lg⁡x+lg⁡y,lgxy=y×lg⁡x\lg(x\times y)=\lg{x}+\lg{y},lg{x^y}=y\times \lg{x}lg(x×y ...

CF1077F2 Pictures with Kittens (hard version) 题解里好像没有和我做法一样的 (指状态不一样)，那我就来发一篇，定义状态fi,jf_{i,j}fi,j​表示当前选了iii个数字,在第jjj个数字时的和的最大值 那么很容易可以想出转移方程 fi,j=max⁡0≤u<j1≤i≤x,0≤j≤nfi−1,u+ajf_{i,j}=\max\limits_{0\le u<j}\limits^{1\le i \le x,0\le j\le n}f_{i-1,u}+a_jfi,j​=0≤u<jmax1≤i≤x,0≤j≤n​fi−1,u​+aj​ 很显然直接O(n3)O(n^3)O(n3)转移是不行的,只能过24个点,别问我为什么知道,那么就可以考虑优化,去掉一维,仔细观察发现似乎可以用单调队列优化第三维,那么就可以用O(n2)O(n^2)O(n2)成功转移了 代码 #include<iostream>#include<cstdio>#include<cstring>using namespace std; ...

P1772 [ZJOI2006]物流运输 看完这道题，很容易想到需要用最短路，但是只用最短路显然是不行的，因为运输路线不止一条， 所以如果每一天都选择最短的路线答案可能并不是最优，所以这时候就需要考虑DP， 刚开始我想的是用状态压缩把所有可能的路线算出来，但很快就被我否决了，因为时间复杂度显然超了，所以考虑其他方法 观察样例得出，有可能一段时间内的最短路是一样的，所以考虑定义一个数组disi,jdis_{i,j}disi,j​表示第iii天到第jjj天都可以走的最短的路线, 然后就可以定义状态fif_ifi​表示前iii天的最短花费,考虑将n天划分成若干段进行转移即可 得出状态转移方程 fi=min⁡0≤j<ifj+(i−j)∗(disj+1,i)+kf_i=\min\limits_{0\le j <i}f_j+(i-j) * (dis_{j+1,i})+kfi​=0≤j<imin​fj​+(i−j)∗(disj+1,i​)+k 代码 #include<iostream>#include<cstdio>#include<queue> ...

P3354 [IOI2005]Riv 河流 这是一道比较好的树型DP，在参考了网上的一些题解后，蒟蒻终于把它给做了出来 可以看到这道题如果只用二维表示状态明显是不够的 所以设状态fi,j,kf_{i,j,k}fi,j,k​表示iii为根节点,jjj为它的一个建有伐木场的父节点,kkk为iii与它的子树共建的伐木场的数量 考虑再开一个数组gi,j,kg_{i,j,k}gi,j,k​表示iii这个点建了伐木场,状态含义同fff 状态转移方程结合代码讲解 #include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N = 105, M = 205;int n, k, siz[N], f[N][N][N], g[N][N][N], sum[N], stk[N];int head[N], ver[M], net[M], edge[M], w[N], idx, top;void add(int a, int b, int c){ ver[idx] ...

读完这到题，感觉上像是一道二分图匹配得问题，但是它对于每一个点又有一些限制，所以可以考虑拆点，将男生和女生都拆成两个点，并连一条容量为k的边 对于一对相互喜欢的男女，在男l与女r之间连一条容量为1的边，如果不喜欢那么就在男r与女l之间连一条容量为1的边，枚举可以有和舞曲数量m，在S与男l，女r与T之间连一条容量为m的边，如果该流网络存在满流的最大流，那么这个答案就是合法的，因为此题答案并不大，所以可以直接枚举 代码 #include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N = 1005, M = 1e5 + 5, INF = 1e8;int n, k, idx, S, T;int head[N], ver[M], net[M], cpt[M];int d[N], cur[N], q[N];void add(int a, int b, int c){ net[idx] = head[a], ver[idx] = b, cpt[i ...

CF149D Coloring Brackets 一道很有意思的区间DP 我们用0表示不染色,1表示红色,2表示蓝色 定义状态fi,j,k,uf_{i,j,k,u}fi,j,k,u​表示将合法序列[i,j]染色且i染为k,j染为ui染为k,j染为ui染为k,j染为u的方案数 那么序列就可以分为三种情况 1°:() fi,j,0,1=fi,f,1,0=fi,j,0,2=fi,j,2,0f_{i,j,0,1}=f_{i,f,1,0}=f_{i,j,0,2}=f_{i,j,2,0}fi,j,0,1​=fi,f,1,0​=fi,j,0,2​=fi,j,2,0​ 2°:((…)) fi,j,0,k=∑u=0u≤2∑v=0v≤2,v≠kfi+1,j−1,u,vf_{i,j,0,k}=\sum\limits_{u=0}^{u \le 2} \sum\limits_{v=0}^{v \le 2,v \ne k}f_{i+1,j-1,u,v}fi,j,0,k​=u=0∑u≤2​v=0∑v≤2,v=k​fi+1,j−1,u,v​ fi,j,k,0=∑u=0u≤2,u≠k∑v=0v≤2fi+1,j−1,u ...

P4056 [JSOI2009]火星藏宝图 这道题很容易想到O(n2)O(n^2)O(n2)的暴力做法,但仔细思考一下,可以发现对于每一列的可转移的岛,行数大的一定比行数小的更优. 不妨假设这两个岛的坐标为(x1,y),(x2,y)(x1<x2≤x)(x_1,y),(x_2,y)(x_1 < x_2 \le x)(x1​,y),(x2​,y)(x1​<x2​≤x),当前的岛的坐标为(x,y)(x,y)(x,y) ∵(x1−x2)2+(x2−x)2−(x1−x)2\because (x_1-x_2)^2+(x_2-x)^2 - (x_1-x)^2∵(x1​−x2​)2+(x2​−x)2−(x1​−x)2 =2x22−2x1x2−2xx2+2xx1=2(x2−x1)(x2−x)<0=2x_2^2-2x_1x_2-2xx_2+2xx_1=2(x_2-x_1)(x_2-x)<0=2x22​−2x1​x2​−2xx2​+2xx1​=2(x2​−x1​)(x2​−x)<0 ∴(x1−x2)2+(x2−x)2<(x1−x)2\therefore (x_1-x ...