- 博客(45)
- 收藏
- 关注
RSS订阅原创 Codeforces gym 101675B Cactusophobia
题面：2016 Russian Code Cup (RCC 16), Final Round B.Cactusophobia题意：给定一棵边仙人掌（每条边最多在一个环内），每条边有一种颜色。现要删除一些边，使得边仙人掌变成一棵树，且剩下边的颜色种类最多。求最大的剩下边的颜色种类。题解：点双连通分量 + 最大流求边仙人掌的点双连通分量。对于每个点双连通分量内边的数量，如大于111，则说明是一个环；否则为一个点及一条边。对于大小大于111的点双连通分量， 需删去一条边；否则保留此边。将源点与每个点双连
2020-08-13 16:49:56
195
原创 重回算法竞赛
高考结束，被交大录取，为参加ACM做准备。最近又开始打训练赛，明显感觉水平下降，代码功底退化严重。训练的题也比较难，做不出来是常见的事情。从今天开始继续在博客更新题解，主要以补难题为主。加油！！！...
2020-08-12 22:40:56
194
2
原创 Luogu3826 NOI2017 蔬菜
题面：luogu3826题意：有nnn种蔬菜，第iii种初始有cic_ici个，每卖出一个获得aia_iai的收益，卖出的第一个有额外sis_isi的收益，每天会腐烂xix_ixi个。每天最多卖mmm个蔬菜。给出kkk个询问，问卖pip_ipi天蔬菜最多能获得多少收益。题解：蔬菜减少很不好处理，考虑按天数从后往前做，每天多xix_ixi个蔬菜。因为每种蔬菜不会减少，如果往前一天来...
2019-07-08 15:28:41
156
原创 Luogu3825 NOI2017 游戏
题面：luogu3825题意：nnn场比赛，三种车型A,B,CA, B, CA,B,C。每场比赛规定不能使用一种车型或是无限制，另有mmm条限制如果第iii场使用hih_ihi车型，那么第jjj场必须使用hjh_jhj车型。输出一个比赛车型的合法方案，或−1-1−1。n≤5×104n \le 5 \times 10^4n≤5×104，m≤105m \le 10^5m≤105，无限制场数≤8\...
2019-07-08 12:21:21
91
原创 Luogu3824 NOI2017 泳池
题面：luogu3824题意：宽为nnn米，高为100110011001米的长方形网格，每个格子有qqq的概率是安全的。问以最下面一行为底边的最大的安全子矩阵的大小恰好为KKK的概率。n≤109n \le 10^9n≤109，k≤1000k \le 1000k≤1000题解：首先转化问题为求矩阵大小小于等于KKK的概率。答案即为≤K\le K≤K减去≤K−1\le K - 1≤K−1设dp[...
2019-07-07 22:24:14
174
原创 Luogu3823 NOI2017 蚯蚓排队
题面：luogu3823题意：nnn只蚯蚓，每只蚯蚓有一个≤6\le 6≤6的长度，初始时每只蚯蚓一支队伍。给出mmm个操作。三种操作：将以iii结尾的队伍和以jjj开头的队伍合并，且iii的队伍在前。将iii和iii后面一只蚯蚓处断开，分为两支队伍。定义以第xxx只蚯蚓开始的长度为kkk的数字串为：从xxx开始的连续kkk只蚯蚓，它们的长度数字连成的字符串。定义给定一个字符串sss和...
2019-07-07 12:20:05
197
原创 Luogu3822 NOI2017 整数
题面：luogu3822题意：有一个二进制整数初始为000。两种操作：加a⋅2ba \cdot 2^ba⋅2b；询问二进制下第kkk位的值。操作数n≤106n \le 10^6n≤106，∣a∣≤109|a| \le 10^9∣a∣≤109，0≤b,k≤30n0 \le b, k \le 30n0≤b,k≤30n题解：对加和减(对应aaa的正负)分别维护二进制数，记做incincinc和dec...
2019-07-07 10:41:14
116
原创 Luogu4774 NOI2018 屠龙勇士
题面：luogu4774题意：有nnn条龙，初始生命值aia_iai，恢复能力pip_ipi，生命值为负时会恢复，当它生命值恰好为000时死亡。初始有mmm把剑，每把剑有攻击力。每次会选择攻击力≤\le≤龙初始生命值且攻击力最大的剑，若不存在则选择攻击力最小的剑。当击杀一条龙时，使用的剑会消失，同时会奖励一把新的剑。现在按照1→n1 \to n1→n的顺序杀龙，固定对每条龙攻击xxx次，求最...
2019-07-05 18:52:35
144
原创 Luogu4770 NOI2018 你的名字
题面：luogu4770题意：给定一个串SSS。每次询问给出一个字符串TTT，问TTT有多少个不同的子串使得其也不是S[l…r]S[l … r]S[l…r]的子串。∣S∣≤5×105|S| \le 5 \times 10^5∣S∣≤5×105，q≤105q \le 10^5q≤105，∑∣T∣≤106\sum |T| \le 10^6∑∣T∣≤106题解：首先考虑部分分l=1,r=∣S∣l =...
2019-07-05 18:36:38
174
原创 Luogu4769 NOI2018 冒泡排序
题面：luogu4769题意：给定一个排列ppp。求字典序严格大于ppp，且冒泡排序交换次数=∑i=1n∣i−pi∣= \sum _{i = 1} ^n |i - p_i|=∑i=1n∣i−pi∣的排列个数。n≤6×105n \le 6 \times 10^5n≤6×105题解：整理自luogu题解可以证明该问题等价于最长下降子序列的长度不能超过2。因为如果长度大于2，那么中间的元素会被...
2019-07-05 16:39:20
230
原创 Luogu4768 NOI2018 归程
题面：luogu4768题意：给定一张nnn个点mmm条边的无向连通图，每条边有长度和海拔。给qqq个询问，强制在线，每次询问指定一个水位线ppp和出发点vvv，能够从vvv开始无代价走过若干条海拔大于ppp的边到达v′v'v′后，再从v′v'v′花路线长度的代价走到111号节点。求最小代价。n≤2×105,m≤4×105,q≤4×105n \le 2 \ti...
2019-07-05 16:21:48
142
原创 扩展卢卡斯ExLucas
扩展Lucas定理用于求：(nm)mod  p\binom n m \mod p(mn)modp，其中ppp不一定为素数求法首先对ppp进行素因数分解：p=∏ipikip = \prod _i p_i ^{k_i}p=∏ipiki显然pikip_i^{k_i}piki之间两两互素，因此如果能求出(nm)mod&Th...
2019-06-20 19:54:22
206
原创 uoj455 雪灾与外卖
题面：uoj455题意：有nnn只老鼠和mmm个洞，每个洞有容量限制和一个费用。要求每只老鼠进一个洞，使所有老鼠的移动距离和加进洞费用和最小。题解：模拟费用流(贪心+反悔)将所有的老鼠和洞按位置排序。考虑先让老鼠向左边的洞匹配。维护老鼠和洞两个堆：MMM，HHH。老鼠移动的距离为右减左。当前是老鼠：坐标为xxx，从洞堆HHH中取出最优解vvv，则代价为x+vx+vx+v，这样只考虑了向左...
2019-06-10 20:59:38
516
原创 bzoj3456 城市规划
题面：bzoj3456题意：求nnn个点的简单无向连通图的方案数题解：设g(n)g(n)g(n)为简单无向图的方案数，f(n)f(n)f(n)为简单无向连通图的方案数g(n)=2Cn2g(n) = 2^{C_n^2}g(n)=2Cn2枚举111号点的连通块大小：g(n)=∑i=1nCn−1i−1f(i)g(n−i)g(n) = \sum _{i=1} ^n C_{n-1} ^{i-1} ...
2019-06-10 09:10:34
142
原创 bzoj3625 小朋友和二叉树
题面：bzoj3625题意：一棵带点权的树的权值为所有点的权值和。给定mmm，求点权在给定集合中的权值为s(1≤s≤m)s(1 \le s \le m)s(1≤s≤m)的二叉树的个数。题解：设f(i)f(i)f(i)为权值为iii的二叉树个数，c(i)c(i)c(i)为集合中数的生成函数。f(n)=∑i=1nc(i)∑j=0if(j)∗f(n−i−j)f(n) = \sum _{i=1} ^...
2019-06-09 22:07:01
128
原创 多项式除法
设AAA为nnn次多项式，考虑AR(x)=xnA(1x)A_R(x) = x^n A(\frac 1 x)AR(x)=xnA(x1)AR[i]=A[n−i]A_R[i] = A[n - i]AR[i]=A[n−i]F(x)=Q(x)∗G(x)+R(x)F(x) = Q(x) * G(x) + R(x)F(x)=Q(x)∗G(x)+R(x)F(1x)=Q(1x)∗G(1x)+R(1x)F...
2019-06-09 13:05:50
1400
原创 多项式求逆
设AAA为原多项式，所求为多项式BBB即有A×B≡1mod  xnA \times B \equiv 1 \mod x^nA×B≡1modxn设A×B′≡1mod  xn2A \times B' \equiv 1 \mod x^{\frac n 2}A×B′≡1mo...
2019-06-09 11:01:52
138
原创 bzoj5093 图的价值
题面：bzoj5093题意：定义一个带标号的图的价值为每个点度数的kkk次方的和 mod 998244353998244353998244353。求nnn个点带标号的简单无向图的价值和。n≤109n \le 10^9n≤109，k≤200000k \le 200000k≤200000题解：枚举每个点连多少条边：∑i=0n−1(in−1)⋅ik⋅2n(n−1)2−(n−1)\sum _{i=0}...
2019-06-09 10:28:26
169
原创 bzoj4555 Tjoi2016&Heoi2016 求和
题面：bzoj4555题意：求∑i=0n∑j=0iS(i,j)⋅j!⋅2j\sum _{i=0} ^n \sum_{j=0} ^i S(i, j) \cdot j! \cdot 2^j∑i=0n∑j=0iS(i,j)⋅j!⋅2j mod 998244353998244353998244353，其中S(i,j)S(i,j)S(i,j)是第二类斯特林数。题解：第二类斯特林数S(i,j)S(i,...
2019-06-08 17:12:01
114
原创 FFT快速傅里叶变换
前言FFT(Fast Fourier Transfromation)，快速傅里叶变换，用于加速多项式乘法。朴素乘法：O(n2)O(n^2)O(n2)。FFT：O(nlogn)O(nlogn)O(nlogn)多项式的系数表示法与点值表示法系数表示法一个n−1n-1n−1次nnn项多项式f(x)f(x)f(x)可以表示为f(x)=∑i=0n−1aixif(x) = \sum _{i = 0...
2019-06-04 20:07:05
278
原创 后缀自动机
后缀自动机基本描述后缀自动机：对于一个字符串SSS，它对应的后缀自动机是一个最小的确定有限状态自动机，接受且仅接受SSS的后缀。栗子：对于字符串S = “aabbabd”，它的后缀自动机：其中红色状态是终结状态。对于SSS的后缀，都可以从SSS状态出发沿着字符标识路径转移，最后到达终结状态。特别的，对于SSS的子串，最终会走到一个合法状态；若不是SSS的子串，最后会无路可走。后缀自动...
2019-05-29 08:36:18
277
原创 bzoj3512 DZY Loves Math IV
题面：bzoj3512题意：求∑i=1n∑j=1mφ(ij)\sum _{i=1} ^n \sum _{j=1} ^m \varphi (ij)∑i=1n∑j=1mφ(ij)，1≤n≤1051 \le n \le 10^51≤n≤105，1≤m≤1091 \le m \le 10^91≤m≤109题解：nnn范围比较小，枚举nnn。即求S(n,m)=∑i=1mφ(ni)S (n, m) ...
2019-05-20 13:59:55
132
原创 bzoj4916 神犇和蒟蒻
题面：bzoj4916题意：求∑i=1nμ(i2)\sum _{i=1} ^n \mu (i^2)∑i=1nμ(i2)和∑i=1nφ(i2)\sum _{i=1} ^n \varphi (i ^2)∑i=1nφ(i2)，膜109+710^9+7109+7。n≤109n \le 10^9n≤109题解：第一个式子∑i=1nμ(i2)\sum _{i=1} ^n \mu (i^2)∑i=1n...
2019-05-20 10:46:22
117
原创 bzoj3529 Sdoi2014 数表
题面：bzoj3529题意：求∑i=1n∑j=1mσ(gcd(i,j))\sum _{i=1} ^n \sum _{j=1} ^m \sigma (gcd (i, j))∑i=1n∑j=1mσ(gcd(i,j))，σ(gcd(i,j))≤a\sigma (gcd (i, j)) \le aσ(gcd(i,j))≤a。其中σ(x)\sigma (x)σ(x)表示xxx的约数和。题解：先不管a...
2019-05-20 09:53:38
125
原创 bzoj3309 DZY Loves Math
题面：bzoj3309题意：设f(n)f(n)f(n)表示nnn所含质因子的最大幂指数。求∑i=1a∑j=1bf(gcd(i,j))\sum _{i=1} ^a \sum _{j=1} ^b f (gcd (i, j))∑i=1a∑j=1bf(gcd(i,j))题解：ans=∑i=1a∑j=1bf(gcd(i,j))=∑d=1af(d)∑i=1a∑j=1b[gcd(i,j)=d]=∑d=...
2019-05-20 09:40:07
157
原创 bzoj4652 Noi2016 循环之美
题面：bzoj4652题意：对于1≤x≤n1 \le x \le n1≤x≤n，1≤y≤m1 \le y \le m1≤y≤m，有多少个在kkk进制下数值互不相等的纯循环小数xy\frac x yyx。1≤n,m≤1091 \le n, m \le 10^91≤n,m≤109，2≤k≤20002 \le k \le 20002≤k≤2000题解：首先考虑10进制下的纯循环小数，一定可以表示成...
2019-05-19 19:47:32
219
原创 bzoj4816 Sdoi2017 数字表格
题面：bzoj4816题意：求∏i=1n∏j=1mf[gcd(i,j)]\prod _{i=1} ^n \prod _{j=1} ^m f[gcd (i, j)]∏i=1n∏j=1mf[gcd(i,j)]，其中f[i]f[i]f[i]表示第iii项斐波那契数列。膜109+710^9+7109+7题解：ans=∏i=1n∏j=1mf[gcd(i,j)]=∏d=1n∏i=1n∏j=1m[gc...
2019-05-19 17:59:29
151
原创 bzoj4815 Cqoi2017 小Q的表格
题面：bzoj4815题意：有一个矩阵始终满足f(a,b)=f(b,a)f(a,b) = f(b,a)f(a,b)=f(b,a)b∗f(a,a+b)=(a+b)∗f(a,b)b * f(a, a + b) = (a + b) * f (a, b)b∗f(a,a+b)=(a+b)∗f(a,b)有两个操作：修改一个格子的数；询问∑i=1k∑j=1kf(i,j)\sum _{i=1} ^k ...
2019-05-19 17:41:57
139
原创 bzoj4407 于神之怒加强版
题面：bzoj4407题意：求∑i=1n∑j=1mgcd(i,j)k\sum _{i=1} ^n \sum _{j=1} ^m gcd (i, j) ^k∑i=1n∑j=1mgcd(i,j)k，mod(109+7)mod (10^9+7)mod(109+7)题解：即求∑d=1ndk∑i=1n∑j=1m[gcd(i,j)=d]\sum _{d = 1} ^n d^k \sum _{i=1} ...
2019-05-19 17:03:07
149
原创 bzoj3994 SDOI2015 约数个数和
题面：bzoj3994题意：设d(x)d(x)d(x)是xxx的约数个数，求∑i=1n∑j=1md(ij)\sum _{i=1} ^n \sum_{j=1} ^m d (ij)∑i=1n∑j=1md(ij)题解：d(ij)=∑x∣i∑y∣j[gcd(x,y)=1]d(ij) = \sum _{x \mid i} \sum_{y \mid j} [gcd (x, y) = 1]d(ij)=∑...
2019-05-19 16:40:19
121
原创 bzoj3930 CQOI2015 选数
题面：bzoj3930题意：从[L,H][L,H][L,H]选出nnn个数，使它们的最大公约数为kkk的方案数，对1e9+71e9+71e9+7取模。1≤n,k,L,H≤1091 \le n, k, L, H \le 10^91≤n,k,L,H≤109，H−L≤105H-L \le 10^5H−L≤105题解：即求∑a1=LH∑a2=LH…∑an=LH[gcdi=1n(ai)=k]\sum ...
2019-05-19 16:25:09
171
原创 bzoj2440 中山市选2011 完全平方数
题面：bzoj题意：求第kkk个不含平方因子的数。题解：二分答案xxx。xxx以内不含平方因子的数的个数cnt=x−一个质数平方数的倍数+两个质数积的平方数的倍数−...cnt=x - 一个质数平方数的倍数 + 两个质数积的平方数的倍数 - ...cnt=x−一个质数平方数的倍数+两个质数积的平方数的倍数−...发现μ(3)=−1\mu(3)=-1μ(3)=−1，μ(6)=1\mu (6)...
2019-05-19 15:58:26
157
原创 bzoj2301 HAOI2011 Problem b
题面Description对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。Input第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、kOutput共n行，每行一个整数表示满足要求的数对(x,y)的个数Sample Input22 5 1 5 11 5 1 5 2...
2019-05-19 11:42:23
165
原创 bzoj2005 NOI2010 能量采集
题面Description栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第...
2019-05-19 11:31:55
131
原创 莫比乌斯反演、杜教筛
莫比乌斯反演莫比乌斯反演基本形式：对于一个函数f(x)f(x)f(x)设g(x)=∑x∣df(d)g(x)=\sum _{x \mid d} f(d)g(x)=∑x∣df(d)，那么f(x)=∑x∣dμ(dx)⋅g(d)f(x)=\sum _{x \mid d} \mu(\frac {d} {x}) \cdot g(d)f(x)=∑x∣dμ(xd)⋅g(d)111：f(x)=1f(...
2019-05-19 11:20:49
192
原创 整体二分
《浅谈数据结构题的几个非经典解法》中的介绍：所谓整体二分，需要数据结构题满足以下性质：询问的答案具有可二分性修改对判定答案的贡献相对独立，修改之间互不影响效果修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值贡献满足交换律，结合律，具有可加性题目允许离线操作询问的答案有可二分性质显然是前提，我们发现，因为修改对判定标准的贡献相对独立，且贡献的值（如果有的话）与判定标准无...
2019-05-15 11:17:17
645
原创 带修改莫队
普通的莫队：对询问分块，计算相邻两个询问差距对答案的影响，统计答案。O(nn)O(n\sqrt n)O(nn)带修改莫队：记录当前进行了几次修改。如果当前修改比询问时的修改数少，就向前修改；如果当前修改比询问时的修改数多，就改回来。时间复杂度引用自洛谷题解原版莫队是将区间(l,r)(l,r)(l,r)视为点(l,r)(l,r)(l,r)，带修改的即加一维时间轴(l,r,t)(l,r,t...
2019-05-14 19:51:49
270
原创 Link-Cut Tree动态树
把树边划分为实边和虚边，用Splay来维护若干实边连成的实链。Link-Cut Tree支持：查询修改链上信息；换根；动态加边、删边。性质：每棵SplaySplaySplay维护一条从上到下深度严格递增的链，SplaySplaySplay的中序遍历得到的深度序列递增。每个节点包含且仅被包含在一棵SplaySplaySplay中边分为实边和虚边。实边存在SplaySplaySp...
2019-05-14 17:08:12
111
原创 后缀数组
后缀数组是处理字符串的有力工具。实现方法主要是两种：倍增法O(nlogn)O(nlogn)O(nlogn)和DC3法O(n)O(n)O(n)本文主要介绍倍增法。倍增法定义第iii个后缀：s[i…n]s[i…n]s[i…n]。它的后缀位置为iii定义变量：sss：原字符串。s[i]s[i]s[i]：原字符串的第iii个字母。nnn：字符串长度mmm：字符集大小sa[i]sa[i]...
2019-05-13 10:56:04
130
原创 树链剖分
树链剖分（重链剖分）中的一些概念：重儿子：所有儿子中子树节点数量最多的儿子。轻儿子：除重儿子外的儿子。重边：父亲和重儿子的边。轻边：父亲和轻儿子的边。重链：重边连成的链。轻链：轻边连成的链。为什么要使用树链剖分？树链剖分后有一条重要的性质：从根节点到任意节点的路径经过的轻重链数量小于lognlognlogn剖分后使重链上节点的dfsdfsdfs序连续，使链上的操作转换为区间操作，即...
2019-05-13 07:25:26
143
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人