- 博客(255)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 Codeforces 1231E Middle-Out 题解
博客观赏效果更佳：githubcnblogs题意简述（qqq 组数据）你有两个串，sss 和 ttt，长度都是 nnn。现在你可以对 sss 做若干次操作：选择某一个字符，把它移到最前面或者最后面（二选一）。你现在要把 sss 变成 ttt，请问最少需要多少步操作。不行输出 −1-1−1。1≤q,n≤1001\le q,n\le1001≤q,n≤100。思路先放结论：求出最长的串 ...
2020-05-02 21:20:43
275
原创 cdq分治 笔记
博客观赏效果更佳：githubcnblogs算法讲解这个算法用于解决三维偏序问题。三维偏序：给定 nnn 个三元组： (ai,bi,ci)(a_i,b_i,c_i)(ai,bi,ci)，求同时满足满足 ai≤aj,bi≤bj,ci≤cja_i\le a_j,b_i\le b_j,c_i\le c_jai≤aj,bi≤bj,ci≤cj 的 (i,j)(i,j)(i,j) ...
2020-05-02 18:27:23
310
原创 线段树优化建图 笔记
博客观赏效果更佳githubcnblogs算法讲解其实不用讲，看标题就知道这大概是一个什么样的算法了。它用来解决这样类型的问题：你要支持，从一个点往一个区间中的所有点连一条边，或者一个区间中的所有点连一条边（有向）。然后你就要进行一些 最短路/强连通分量/最大流 等图论基本操作了。那么这个咋整呢（⊙.⊙）假设我们现在是从第 ⑨ 个点向 [3,6][3,6][3,6] 区间中的所有点...
2020-04-19 22:28:13
302
原创 bzoj 4962 简单的字符串 题解
博客观赏效果更佳githubcnblogs题意简述给你一个长度为 nnn 的数组 aaa，问你有多少个区间，满足：长度为偶数前一半和后一半循环同构n≤5000,ai≤5000n\le 5000,a_i\le 5000n≤5000,ai≤5000思路两个串 a,ba,ba,b 循环同构 ，那么一定可以把 aaa 分成两个串 u,vu,vu,v 接起来，然后把 bbb 表示成 ...
2020-04-19 20:50:25
462
原创 libreoj 6192 「美团 CodeM 复赛」城市网络 题解
博客观赏效果更佳githubcnblogs题意简述有 nnn 个城市，组成一张树形网络。第 iii 个城市售卖价值为 aia_iai 的珠宝。zps 的父母计划了 qqq 次行程。每次先带上价值为 ccc 的珠宝，从城市 uuu 走到城市 vvv （保证 vvv 在 uuu 到 111 的路径上）。如果当前的城市售卖的珠宝比手头的贵（严格大于，等于不行），那么 zps 的父母会买入这个珠...
2020-04-19 02:46:15
280
原创 莫比乌斯容斥 笔记
博客观赏效果更佳：cnblogsgithub算法讲解（本篇文章假设您学过莫比乌斯反演 (〃‘▽’〃)我们知道莫比乌斯函数有一个性质： ∑d∣nμ(d)=[n=1]\sum\limits_{d|n} \mu(d)=[n=1]d∣n∑μ(d)=[n=1]根据这条性质，我们写出一个类似筛的东西：一个数组，初始都是 000。 第 iii 轮，将 iii 的倍数都加上 μ(i)\mu(i)μ(...
2020-04-18 22:43:16
534
2
原创 洛谷 4247 bzoj 2962 [清华集训2012]序列操作
博客观赏效果更佳：cnblogsgithub题意简述给一个长度为 nnn 的序列 aaa，支持 qqq 个操作：I l r x 区间元素整体 +x+x+x。R l r 区间元素整体 ×(−1)\times (-1)×(−1)Q l r x 询问：从 [l,r][l,r][l,r] 中选择 xxx 个数的积的所有方案的和， mod 19940417\bmod 19940417mod1...
2020-04-11 21:46:10
203
原创 洛谷 4492 [HAOI2018] 苹果树 题解
博客观赏效果更佳：githubcnblogs先膜一发 shadowice1984的题解，太神了！题意简述你有一个 nnn，表示你的二叉树将要有 nnn 个节点。然后每次你的树会等概率选择某个点的还没长过的儿子，在这里长一个儿子。容易证明，这样有 n!n!n! 种方案。（第一次有一种方案，第二次两种，第三次三种…一共就是 n!n!n! 种）然后你要输出树上路径和的期望值乘以 n!n!n...
2020-04-11 20:26:25
320
原创 洛谷 5295 [北京省选集训2019]图的难题 题解
博客观赏效果更佳：githubcnblogs题意简述给你一个 nnn 个点 mmm 条边的无向图，判断是否能将一些边染色为白色，其它的染成黑色，并且没有一个纯色的环。n≤501,m≤2nn\le 501,m\le 2nn≤501,m≤2n思路一张图有 EEE 条边，VVV 个点。那么，它要满足没有纯色的环，EEE 最大值为 2(V−1)2(V-1)2(V−1)（此时的情况就是白色和黑...
2020-04-11 19:54:05
254
原创 libreoj 6270 数据结构板子题 题解
博客观赏效果更佳题意简述给定 nnn 个区间 [li,ri][l_i,r_i][li,ri]，和 QQQ 个询问，每次给你三个整数 [l,r,k][l,r,k][l,r,k]，求被 [l,r][l,r][l,r] 完全包含且长度 ≥k\ge k≥k 的区间数量。注：定义一个区间 [l,r][l,r][l,r] 的长度是 r−lr-lr−l。n,q≤106n,q\le 10^6n,q≤...
2020-04-06 11:35:58
210
1
原创 bzoj 5102 [POI2018]Prawnicy 题解
博客观赏效果更佳题意简述给你 nnn 个区间 [li,ri][l_i,r_i][li,ri]，选出 恰好 kkk 个，使得交集最大。输出最长的长度和方案。注：区间 [l,r][l,r][l,r] 的长度被定义为 r−lr-lr−l。1≤k≤n≤1051\le k\le n\le 10^51≤k≤n≤105。思路框架若干的区间的交集，显然，左端点是所有左端点的最大值，右端点是所有右端...
2020-04-06 10:27:38
222
原创 扩展卢卡斯定理 笔记
博客观赏效果更佳先问一个简单的问题，求：Cnm(modq)C_{n}^{m}\pmod {q}Cnm(modq)不保证 qqq 是质数。1≤q≤106,1≤m≤n≤10181\le q\le 10^6,1\le m\le n\le 10^{18}1≤q≤106,1≤m≤n≤1018。（原题：洛谷上的板子）这很毒瘤了！我们平常熟知的几个方法，预处理阶乘和阶乘逆元，或者是 Lucas ...
2020-03-27 11:50:59
367
4
原创 libreoj 10051「一本通 2.3 例 3」Nikitosh 和异或
博客观赏效果更佳题意简述给一个长度为 nnn 的序列 a1,a2...ana_1,a_2...a_na1,a2...an，求两个区间 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2][l1,r1],[l2,r2]，使得两端区间不相交，且两端区间的异或和加起来最大。n≤105n\le 10^5n≤105，每个 ai≤109a_i\le 10^9ai≤109。...
2020-03-26 22:11:25
376
原创 主席树 笔记
看起来需要建 n 颗线段树，但是实际上每次修改只改了 log 条链！快用「 可持久化」 把空间优化成 nlogn！让我们灵活运用 n 颗线段树，解决各种各样的问题吧！
2020-03-25 00:58:34
220
11
原创 洛谷 3831 [SHOI2012]回家的路 题解
博客观赏效果更佳题意简述nnn 行 nnn 列的矩阵上，只有 mmm 个“关键点”处（在第 xxx 行 yyy 列）才能拐弯。从格子到上下左右四个相邻格子花费 222，转弯花费 111。 求从某个位置走到另一个位置的最小花费。无解输出 −1-1−1。思路新建两个点 SSS 和 TTT 表示起点。 然后把所有点 AAA（包括关键点和 S,TS,TS,T） 拆成两个点 A1A_1A1 和 A...
2020-03-21 23:35:56
231
1
原创 libreoj 10067 「一本通 3.1 练习 2」构造完全图 题解
博客观赏效果更佳题意简述给定一个树 TTT ，求一个完全图 GGG 使得 TTT 是 GGG 的最小生成树，并且 GGG 的边权和最小。求出这个最小的边权和。TTT 的点数 n≤105n\le 10^5n≤105，每个边权 w≤105w\le 10^5w≤105思路我们把 TTT 中的边权排一下序，反向推一下 Kruskal 算法的步骤。我们每次考虑到第 iii 条边 (u,v,w)(u...
2020-03-21 23:22:16
662
2
原创 洛谷 1117 libreoj 2083 优秀的拆分 题解
博客观赏效果更佳题意简述一个字符串是“优秀”的，定义为：存在两个非空的字符串 A,BA,BA,B，满足这个字符串 S=AABBS=AABBS=AABB，那么这个 SSS 就是优秀的。给定一个串，计算它有多少子串是“优秀”的。相同的子串出现在不同的位置也被算两次。长度 ≤3e4\le 3e4≤3e4思路对于每个位置，我们维护 pre[i]pre[i]pre[i] 表示以 iii 结尾的 ...
2020-03-17 21:45:28
245
1
原创 Codeforces 1235E Ehab's REAL Number Theory Problem 题解
博客观赏效果更佳考场上想出了思路，但是没能写出来代码，实在可惜题意简述有 n≤1e5n\le 1e5n≤1e5 个正整数，每个数值域都是 [1,106][1,10^6][1,106]，并且最多有 777 个因数。 请你求出最少选多少个数能使得乘积是平方数。思路最多 777 个因数 ↔\leftrightarrow↔ 最多两个质因数而且对于一个质因数，显然我们还可以把它的指数膜个 222...
2020-03-17 21:08:30
283
1
原创 51nod 1238 最小公倍数之和 V3 题解
博客观赏效果更佳题意简述∑i=1n∑j=1nlcm(i,j)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \operatorname{lcm}(i,j)i=1∑nj=1∑nlcm(i,j)n≤1010n\le 10^{10}n≤1010 （简短题意，恶臭规模）思路总的来说，就是先把式子变一变，然后巧妙的用欧拉函数 φ\varphiφ 加上杜教...
2020-03-17 21:03:28
253
2
原创 libreoj 137 最小瓶颈路 加强版 题解
博客观赏效果更佳题意简述给定 nnn 个点 mmm 条边的无向连通图，边带权。qqq 次询问，每次问你 u,vu,vu,v 之间的所有路径中，边权最大值最小是多少。n≤7×104,m≤105,q≤107n\le 7\times10^4,m\le 10^5,q\le 10^7n≤7×104,m≤105,q≤107（询问会用种子生成方式给你，具体见原题，不会影响输入时间）思路首先跑一遍 K...
2020-03-15 04:37:58
269
原创 洛谷 5308 [COCI2019] Quiz 题解
博客观赏效果更佳题意简述有 nnn 个人，kkk 轮比赛。每次如果淘汰了 xxx 个人，还剩下 mmm 个人，得分增加 xm\dfrac{x}{m}mx 的奖金。。假设你能控制每次淘汰多少人，最大化得分。思路设 dp[i]dp[i]dp[i] 表示现在还剩下 iii 个人的最优方案 （先不考虑轮数）。那么 dp[i]=max(dp[j]+i−ji)dp[i]=max(dp[j]+\df...
2020-03-15 04:16:16
257
原创 Codeforces 1252K Addition Robot 题解
博客观赏效果更佳题意简述你有一个字符串，仅由 A,B 两种字符构成。长度 n≤105n\le 10^5n≤105。维护 QQQ 次操作，格式为：1 L R 区间 [L,R][L,R][L,R] 中，AAA 变成 BBB，BBB 变成 AAA。2 L R A B 你有两个数，初始是 AAA 和 BBB。从 LLL 遍历到 RRR ，如果这一位是字符 A，那么 A=A+BA=A+BA=A+B...
2020-03-15 04:06:44
203
原创 libreoj 10069 「一本通 3.1 练习 4」Tree 题解
博客观赏效果更佳题意简述一个图有 nnn 个点 mmm 条边，每个边是白色或黑色。生成一棵树使得白边的数量恰好是 kkk，并且边权和最小。输出最小的边权和。1≤n,m≤1051\le n,m\le 10^51≤n,m≤105，边权在 [1,100][1,100][1,100] 之间思路我们在跑朴素的 Kruskal 的时候，把每个白边都调的贵一点，或者便宜一点。把白边弄便宜的时候，就会多...
2020-03-15 03:51:04
388
原创 codeforces 916E Jamie and Tree 题解
题意简述给定一个 n≤105n\le 10^5n≤105 个点带权的树，初始根为 111。支持三种操作：1 r 把根换成 rrr2 u v x 把 LCA(u,v)LCA(u,v)LCA(u,v) 的子树整体加 xxx3 u 查询 uuu 的子树点权和操作数≤105\le 10^5≤105。每个点权 ≤108\le 10^8≤108 。思路如果没有 111 操作，那 2,32,32,...
2020-03-15 01:52:46
187
原创 libreoj 125 除数函数求和2 题解
博客观赏效果更佳题意简述给定 nnn，求 ∑i=1n2σ2(i)+3σ1(i)+5σ0(i)\sum\limits_{i=1}^{n} 2\sigma_2(i)+3\sigma_1(i)+5\sigma_0(i)i=1∑n2σ2(i)+3σ1(i)+5σ0(i)n<=1e9n<=1e9n<=1e9其中 σk(x)=x\sigma_k(x)=xσk(x)=x 所有...
2020-03-14 21:30:58
260
7
原创 noi.ac 357 partner 题解
博客观赏效果更佳题意简述（数据结构做傻了系列）给你一列数，求有多少对(i,j)(i,j)(i,j)满足 0.9aj≤ai≤aj0.9a_j\le a_i\le a_j0.9aj≤ai≤aj。思路框架显然先排序，设 bi=0.9aib_i=0.9a_ibi=0.9ai （double型即可），然后每次 lower_boundlower\_boundlower_bound找一下即珂...
2020-03-03 19:17:53
238
5
原创 洛谷 2472 [SCOI2007]蜥蜴 题解
博客观赏效果更佳题意简述有一个 n×mn\times mn×m 的矩阵，其中一些位置上有蜥蜴。每个位置上有一个石柱，给你他们初始的高度 ai,ja_{i,j}ai,j。一个蜥蜴可以从一个石柱，跳到直线距离 ≤k\le k≤k 的另一个石柱上。当一只蜥蜴从一个石柱上离开的时候，这个石柱的高度就会减少 111 。如果蜥蜴跳到了矩阵外面，就是逃离了。请你求最少有多少只不能逃离（其实就是最多能逃离几...
2020-03-02 00:43:33
240
原创 洛谷 5242 [USACO19FEB]Cow Dating P 题解
博客观赏效果更佳题意简述Bessie要找 nnn 头奶牛约会，第 iii 头奶牛同意的概率是 pi106\dfrac{p_i}{10^6}106pi。Bessie 会对一个连续区间的所有奶牛邀请约会，但是她只希望恰好一个同意来约会。请求出所有区间中，恰好只有一个奶牛同意约会的概率的最大值。输出这个最大的概率乘以 10610^6106 后下取整的结果。n<=106n<=10^6...
2020-03-02 00:12:22
279
原创 noi.ac 41 最短路 题解
博客观赏效果更佳题意简述给你一个 nnn 个点的边带权的树，还有 mmm 个新增的修建计划，以及 QQQ 个询问。每一个询问的格式是：给定 s,t,l,rs,t,l,rs,t,l,r ，问你，如果动用 [l,r][l,r][l,r] 之间的修建计划，从 sss 到 ttt 的路径中，边权异或和最小是多少？询问之间是独立的，在某一个询问里加入的修建计划，询问完就会拆掉。并且修建计划保证不是树上...
2020-02-27 21:53:18
236
原创 洛谷 3073 [USACO13FEB]Tractor S 题解
博客观赏效果更佳题意简述给定一个 n×nn\times nn×n 的矩阵 aaa，两个相邻的格子之间的代价，就是两个格子 aaa 值之差的绝对值。请你找到一个联通块，使得它格子数超过 ⌊n22⌋\lfloor \dfrac{n^2}{2} \rfloor⌊2n2⌋ ，并且最大的边权最小。思路框架比较基础的问题，首先“最大值最小”想到二分，然后对于相邻的两个格子，如果 aaa 值之差的绝对...
2020-02-27 21:42:14
223
原创 noi.ac 405 bzoj 4403 序列统计 题解
博客观赏效果更佳题意简述noi.ac再次蒯题，实锤了…请你求长度在 [1,n][1,n][1,n] 范围内，值域在 [l,r][l,r][l,r] 范围内的序列中，不下降序列有多少个。答案对 100000310000031000003（是质数）取膜。多组数据，数组组数 T≤100T\le 100T≤100 ，每组数据 n,l,r≤1e9n,l,r\le 1e9n,l,r≤1e9 ，并且保...
2020-02-27 21:13:51
157
原创 noi.ac 716 答案是整数 题解
博客观赏效果更佳题意简述求∑i=1n∑j=1nijgcd(i,j)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\dfrac{ij}{\gcd (i,j)}i=1∑nj=1∑ngcd(i,j)ij。对 998244353998244353998244353 取模。n<=107,m<=1014n<=10^7,m<=10^{...
2020-02-27 21:10:41
230
1
原创 Codeforces 1304E 1-Trees and Queries 题解
博客观赏效果更佳题意简述nnn 个节点的树，每天边权都是 111。有 qqq 个询问，每次给定 x,y,a,b,kx,y,a,b,kx,y,a,b,k，表示你在树上加一条边 <x,y><x,y><x,y> ，并求从 aaa 到 bbb 走 kkk 条边的最短路。其中每条边和点都允许重复经过。求完询问后，把 <x,y><x,y><...
2020-02-21 09:24:45
207
2
原创 Codeforces 1169E And Reachability 题解
博客观赏效果更佳题意简述给定nnn个数a1,a2...ana1,a2...ana1,a2...an。如果i<ji<ji<j且a[i]&a[j]a[i]\&a[j]a[i]&a[j]（&\&& 是按位与运算）非零，则i→ji\rightarrow ji→j连一条有向边。qqq次询问，每次给定xixixi和yiyiyi，查询xixi...
2020-02-16 14:59:44
213
原创 洛谷 3660 bzoj 4994 Why Did the Cow Cross the Road III 题解
博客观赏效果更佳题意简述（bzoj，十分简洁，直接蒯来了）给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数n<=1e5。思路相当于有nnn个区间ai,bia_i,b_iai,bi，求相交的区间对数。那么我们把它转化为，对于每个ai,bia_i,b_iai,bi，统计区间里面包含多少其...
2020-02-16 14:55:45
168
原创 bzoj 4373 洛谷 5728 算术天才⑨与等差数列 题解
博客观赏效果更佳题意简述给定给一个序列，每次支持：单点修改询问一段区间是否能排列成一个公差为ddd的等差数列（强制在线）区间长度3e53e53e5，其它的值域都在[0,1e9][0,1e9][0,1e9]之间。思路框架维护区间和？显然能构造出一种情况卡掉。那怎么办？维护区间平方和！然后看看是否和等差数列的平方和相等即珂。和很容易相等，但是平方和在1e91e91e9的范围内，就...
2020-02-16 14:38:29
249
原创 codeforces 1304C Air Conditioner 题解
博客观赏效果更佳题意简述你有一个空调（承太郎），初始温度为mmm，有nnn个客人。第iii个客人会在tit_iti的时间过来，适应的温度在[li,ri][l_i,r_i][li,ri]之间。每一个时刻，空调珂以让气温升高111（制热），减少111（制冷），或者不变（关掉空调）。请问你能否满足所有顾客的适应温度？输出YES/NOYES/NOYES/NO。n<=1e6n<=1...
2020-02-16 14:25:43
349
原创 noi.ac 34 洛谷 4656 libreoj 2484 [CEOI2017]Palindromic Partitions
博客观赏效果更佳（noi.ac题面被改过了，题意是一样的）题意简述给你一个字符串SSS，长度1e61e61e6。SSS的一个kkk个串的划分a1,a2...aka_1,a_2...a_ka1,a2...ak，满足：对于任意的iii，ai=ak−i+1a_i=a_{k-i+1}ai=ak−i+1，这就是SSS的一个“回文划分”，它被分成了kkk块。请你求SSS中被分成的块数最多的...
2020-02-16 13:53:36
191
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人