- 博客(162)
- 收藏
- 关注
RSS订阅
原创 【索引】CodeForces各类比赛、杂题索引
CodeForces比赛、杂题索引Part 1.CF比赛题解Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2)ABCD题题解Part 2.CF题目分类1.DPCodeForces 8C Looking for OrderCodeForces 10D LCISCodeForces 11D A Simp...
2018-10-05 17:58:08
848
原创 【索引】《算法竞赛入门经典（第二版）》第九章-例题及习题题目与部分题解
虽然题解很少（只占所有题的27%QAQ），但我会一直更新。例题9-1 UVa 1025-A Spy in the Metro 9-2 UVa 437-TheTower of Babylon 9-3 UVa 437-Tour 9-4 UVa 116-Unidirectional TSP 9-5 UVa 12563-Jin Ge Jin Qu [h]ao 9-6 UVa 11400...
2018-08-15 21:15:42
343
1
原创 【干货】Markdown语法实例（9000+请耐心阅读）
在CSDN上，写博客有两种编辑器，这里介绍Markdown编辑器用法。快捷键加粗——ctrl + B斜体——ctrl + I引用——ctrl + Q插入链接——ctrl + L插入图片——ctrl + G插入代码——ctrl + K提升标题——ctrl + H有序列表——Ctrl + O无序列表——Ctrl + U横线——ctrl + R撤销——ctrl + Z...
2018-02-11 21:24:05
8738
2
原创 [北理工乐学] NH-5 Probability
在斗角场在你偷偷下了注，赌赢了，获得了一个小游戏资格，能免费送棒棒糖！活动规则：在一个长度为N的数列的N个位置随机填入一个∈1MAX的数，一个免费获得的棒棒糖数记为∑i1N−1gcdaiai1aigcdaiai1ai表示如果aiai1的最大公因数等于ai，则gcdaiai1ai1，否则gcdaiai1ai0。
2023-04-25 12:54:45
302
原创 【CodeFroces】【DP】Maximum White Subtree
CodeForces 1324F Maximum White Subtree 题解
2023-02-07 12:11:10
316
原创 【CodeForces】【可持久化线段树】 Katya and Segments Sets
CodeForces 1080F Katya and Segments Sets题解
2023-01-02 17:09:24
344
原创 【CodeChef】【DP】Count Subsequences
CodeChef CSUBSQ Count Subsequences题目大意◇题目传送门◆如果一个整数序列的各元素之和可以被给定整数 KKK 整数，则称这个序列是好的。给定整数序列 A1,A2,…,ANA_1, A_2, \ldots, A_NA1,A2,…,AN。Hasan 想计算该序列有多少子序列是好的。不过这样的话问题就太简单了，因此 Hasan 决定再加一个限制。任意非空下标...
2020-01-10 14:08:10
193
原创 【DP】四边形不等式优化详解（二）
Part.3 如何证明 w(l,r)w(l, r)w(l,r) 满足四边形不等式其实四边形不等式优化的最重要、最关键、也是最开始的一步就是证明 w(l,r)w(l, r)w(l,r) 满足四边形不等式。我们发现直接用定义来证明来证某些 w(l,r)w(l, r)w(l,r) 其实是不好做的。推论： 若对于 a<ba < ba<b 有 w(a+1,b+1)+w(a,b)≤w...
2019-12-15 17:08:59
335
原创 【DP】四边形不等式优化详解（一）
Part.0 前置知识简单的 DP 方法；数学推理能力。Part.1 四边形不等式高能数学公式警告Part.1/1 四边形不等式的概念四边形不等式优化主要应用于区间 DP 的优化。一般来讲，四边形不等式可以用来优化形如下面的转移方式的 DP：f(l,r)=mink=lr−1{f(l,k)+f(k+1,r)}+w(l,r)f(l, r) = \min\limits_{k = l...
2019-12-15 14:29:52
1272
1
原创 【生成函数】五边形数定理与整数划分问题详解
Part 0. 前置知识简单的公式推导生成函数大量数学公式警告Part 1. 什么是五边形数五边形数看一张图吧：XP 系统带的画图真的挺好用！我们不难得出五边形数的数列：P={1,5,12,22,…}P = \{1, 5, 12, 22,\ldots\}P={1,5,12,22,…}再找一下规律，我们就可以得到五边形数的通项公式：Pn=n(3n−1)2P_n = \...
2019-12-07 17:50:33
2816
2
原创 【CodeForces】【单调队列优化DP】939F Cutlet
CodeForces 939F Cutlet题目大意有一块牛排需要两面都需要煎 NNN 秒，现仅有 KKK 个时间段 [Li,Ri][L_i, R_i][Li,Ri] 可以用来翻面，其中每秒只能够翻一次。问最少翻多少次使得牛排两面都煎了 NNN 秒。分析神奇的 DP。定义状态 f(i,j)f(i, j)f(i,j) 为在前 iii 个时间段中，当前朝上的那一面已经被烤了 jjj 秒...
2019-12-03 14:01:54
270
原创 【CSP-S2019】D2T3 树的重心
CSP-S2019 D2T3 树的重心题目题目描述小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：一个大小为 nnn 的树由 nnn 个结点与 n−1n − 1n−1 条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。对于一个大小为 n...
2019-11-23 16:53:41
1183
原创 【CSP-S2019】D1T3 树上的数
CSP2019 D1T3 树上的数题目题目描述给定一个大小为 nnn 的树，它共有 nnn 个结点与 n−1n - 1n−1 条边，结点从 1∼n1 \sim n1∼n 编号。初始时每个结点上都有一个 1∼n1 \sim n1∼n 的数字，且每个 1∼n1 \sim n1∼n 的数字都只在恰好一个结点上出现。接下来你需要进行恰好 n−1n - 1n−1 次删边操作，每次操作你需要选一条未被...
2019-11-23 12:25:04
1277
原创 【CSP-S2019】D2T2 划分
CSP-S2019 D2T2 划分题目题目描述2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 nnn 组数据，数据从 1∼n1 \sim n1∼n 编号，iii 号数据的规模为 aia_iai。小明对该题设计出了一个暴力程序，对于一组规模为 uuu 的数据，该程序的运行时间为 u2u^2u2。然而这个程序运行完一组规模为 uuu 的数据之后，它...
2019-11-23 09:28:19
1226
原创 【CSP-S2019】D2T1 Emiya 家今天的饭
CSP-S2019 D2T1 Emiya 家今天的饭题目题目描述Emiya 是个擅长做菜的高中生，他共掌握 nnn 种烹饪方法，且会使用 mmm 种主要食材做菜。为了方便叙述，我们对烹饪方法从 1∼n1 \sim n1∼n 编号，对主要食材从 1∼m1 \sim m1∼m 编号。Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 ai,ja_{i,...
2019-11-22 22:44:07
768
原创 【CSP-S2019】D1T1 格雷码 & D1T2 括号树 题解
CSP-S2019 D1T1 格雷码题目题目描述通常，人们习惯将所有 nnn 位二进制串按照字典序排列，例如所有 222 位二进制串按字典序从小到大排列为：000000，010101，111111，101010。格雷码（Gray Code）是一种特殊的 nnn 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。所有 2 位二进制串按格雷码...
2019-11-22 21:59:32
1120
1
原创 CSP-S 2019 爆炸记
CSP-S 2019 爆炸记Day -?最近学了一些新的东西。然后就是不断地写题。似乎并没有在意 CSP-S ，只觉得如果这次的难度和去年差不多的话那应该能够稳拿一等奖。Day -2教练列了一黑板的东西出来，我发现一堆东西没有复习。。。还有 vjudge 上的杂题没做完。不管了，先写版题再说。于是打开洛谷敲版题。。。我竟然写了 10 道版题？？？Day -1我竟然颓废了一整天。...
2019-11-20 16:32:16
342
1
原创 【洛谷】【差分】【LCA】P1600 天天爱跑步
洛谷 P1600 天天爱跑步题目大意◇题目传送门◆分析考虑如果直接模拟每个人的路径复杂度就会达到O(NM)O(NM)O(NM)级别，这样做肯定要爆炸。于是换个方向思考：我们以观察员的视角来解决这道题。即我们统计每个人对于每个观察员的贡献。对于第iii个人的行动，我们可以分成两部分来看：记uuu是s,ts,ts,t的最近公共祖先，d(u)d(u)d(u)为节点uuu的深度。当当前人是...
2019-11-14 20:42:53
146
原创 【数论】中国剩余定理与扩展中国剩余定理详解
Part. 0 前置知识扩展欧几里得算法；模运算相关知识。Part. 1 中国剩余定理中国剩余定理是用于求解形如：{x≡a1(mod m1)x≡a2(mod m2)…x≡an(mod mn)\begin{cases}x\equiv a_1(\mod m_1)\\x\equiv a_2(\mod m_2)\\\ldots\\x\equiv a_n(\mod m_n)\...
2019-11-14 16:04:39
409
原创 【洛谷】【扩展欧几里得算法】P4031 [Code+#2]可做题2
洛谷 P4031 [Code+#2]可做题2题目大意◇题目传送门◆给定一个广义斐波那契数列的第一项a1=ia_1=ia1=i，和第二项的范围a2∈[l,r]a_2\in [l,r]a2∈[l,r]，求满足ak≡m(mod p)a_k\equiv m(\mod p)ak≡m(modp)的数列的个数。分析先找一下aaa的规律，设a2=xa_2=xa2=x，则有：a1=i,a2=x,...
2019-11-14 11:52:30
189
原创 【CodeForces】【数学】【贪心】792E Colored Balls
CodeForces 792E Colored Balls题目大意将NNN个数中，每个数分成若干个数的和，要求必须由x,x−1x,x-1x,x−1构成。求出最少分出的集合个数。分析设我们最终从AiA_iAi分出的数的数量为kkk，分出的数为x,x−1x,x-1x,x−1。则我们可以 通过打表 得到：k≤Aik\le \sqrt{A_i}k≤Ai且有x≤Aix\le \sqrt{A_i...
2019-11-13 21:18:05
150
原创 【CodeForces】【生成树】【状压DP】1149D Abandoning Roads
CodeForces 1149D Abandoning Roads题目大意给定一张无向图，边权只有A,B(A<B)A,B(A<B)A,B(A<B)两种情况，要求求出在这张图上的所有最小生成树中，从111到iii的路径的最小值。分析结论（1）： 边权为AAA的边必须被选做生成树上的边。证明（1）： 根据 Kruskal 算法求解生成树的过程显然可得。这样一来整张图就被分...
2019-11-13 20:38:30
199
原创 【CodeForces】【中途相遇法】【二分答案】912E Prime Gift
CodeForces 912E Prime Gift题目大意给定有NNN个素数的集合(1≤N≤161\le N\le 161≤N≤16)，要求用集合内的素数通过乘法构造出一些数字，并输出这些数字中的第KKK大。注意一个素数可以多次使用，且答案不超过101810^{18}1018。分析注意到N≤16N\le 16N≤16，这意味着我们可以采用爆搜。但直接搜索似乎不太好做。考虑中途相遇法：...
2019-11-13 19:20:42
232
原创 【AtCoder】AGC038重练题解
AtCoder AGC038 题解A.01 Matrix题目大意要求构造一个N×MN\times MN×M的01矩阵，其中每行0或者1中较少者的数量恰好为AAA，每列0或1中较少者的数量恰好为BBB。求这样一个矩阵。分析按如下方法构造即可：参考代码#include <cstdio>#include <algorithm>using namespace s...
2019-11-13 15:49:46
331
原创 【CodeForces】【结论】444A DZY Loves Physics
CodeForces 444A DZY Loves Physics题目大意给定一张无向图，其中每个点有一个权值AuA_uAu，每条边有一个权值Bu,vB_{u,v}Bu,v，要求找出一个子图，使得子图连通且任意两点间存在边则一定要被选中。求出选出的子图中点权之和除以边权之和的最大值。分析结论： 这个子图中仅包含一条边和它的两个端点。然后就枚举一条边，计算它的答案。然后就完了。。。...
2019-11-13 15:45:39
171
原创 【HYSBZOJ】【AC自动机】【期望DP】1444 [Jsoi2009]有趣的游戏
HYSBZOJ 1444 [Jsoi2009]有趣的游戏题目大意◇题目传送门◆分析考虑我们已经得到了一个串，我们将这个串拿去和玩家的串匹配，最好的方法是用 AC 自动机：让这个串在上面跑，找到第一个有 endpos 标记的地方。那么动态的想法就是在 AC 自动机上，设f(i)f(i)f(i)在第iii个节点上停止的概率，通过 fail 指针和 Trie 树来转移，我们可以得到：f(u)...
2019-11-12 20:10:10
100
原创 【HYSBZOJ】【高斯消元】【期望DP】2337 [HNOI2011]XOR和路径
HYSBZOJ 2337 [HNOI2011]XOR和路径题目大意◇题目传送门◆分析我们先考虑将这个问题转化为一个期望 DP ，设f(i)f(i)f(i)为从iii走到NNN的异或和的期望值，并记节点iii的度数为d(i)d(i)d(i)，u,vu,vu,v之间的边权为vu,vv_{u,v}vu,v。则f(u)f(u)f(u)可以与它邻接的节点转移过来，所以不难得出：f(u)=1d(...
2019-11-12 19:42:52
114
原创 【CodeForces】【搜索】【思维】1218H Function Composition
CodeForces 1218H Function Composition题目大意给定一个长度为NNN的序列A(1≤Ai≤N)A(1\le A_i\le N)A(1≤Ai≤N)，现在定义一个函数如下：f(i,1)=Aif(i,1)=A_if(i,1)=Ai；f(i,m)=Af(i,m−1)f(i,m)=A_{f(i,m-1)}f(i,m)=Af(i,m−1)。给定m,ym,ym...
2019-11-11 21:27:38
300
原创 【CodeForces】【BFS】【状压】718E Matvey's Birthday
CodeForces 718E Matvey’s Birthday题目大意◇题目传送门◆今天与 CF 的连接怎么这么稳定？？？给定一个长度为NNN的字符串sss，字符集为小写字母aaa到hhh，我们可以按照如下方式构造出一个无向图：若∣i−j∣≤1|i-j|\le 1∣i−j∣≤1，则在点iii和点jjj之间连一条长度为111的边；若si=sjs_i=s_jsi=sj，则在点ii...
2019-11-11 20:15:13
138
原创 【HYSBZOJ】【哈希】【换根DP】4754 [Jsoi2016]独特的树叶
HYSBZOJ 4754 [Jsoi2016]独特的树叶题目大意◇题目传送门◆分析这道题显然考察的是树哈希。我这里采用的方法是：f(u)=1+∑v∈son(u)f(v)×Psizvf(u)=1+\sum_{v\in son(u)}f(v)\times P_{siz_v}f(u)=1+v∈son(u)∑f(v)×Psizv其中PPP表示质数序列，sizvsiz_vsizv表...
2019-11-11 11:27:48
143
原创 【洛谷】【状压DP】P2831 愤怒的小鸟
洛谷 P2831 愤怒的小鸟题目大意◇题目传送门◆分析看到NNN这么小，我们很容易想到状压或者是爆搜。。。设l(i,j)l(i,j)l(i,j)为经过猪iii和猪jjj的抛物线能够击中的猪的集合。设f(S)f(S)f(S)为击中SSS中的猪所需的最少的鸟的数量。则有以下两种转移：只发射击中猪iii的鸟：f(S∪{i})=min(f(S)+1)f(S\cup \{i\})=\min...
2019-11-11 10:24:20
106
原创 【HYSBZOJ】【搜索】[Hnoi2019]校园旅行
HYSBZOJ 5492 [Hnoi2019]校园旅行题目大意◇题目传送门◆分析首先我们不难发现，一个回文串去掉首尾之后一定是一个回文串。所以我们可以根据这个性质来做：假设(x,y)(x,y)(x,y)是一对可以通过回文串相互到达的点对，那么我们可以枚举xxx的邻接点uuu，yyy的邻接点vvv，当u,vu,vu,v同色时，它们就可以通过回文串相互到达。然后我们按照 BFS 顺序转移即...
2019-11-11 09:12:23
120
原创 【洛谷】【博弈搜索】P4363 [九省联考2018]一双木棋chess
洛谷 P4363 [九省联考2018]一双木棋chess题目大意◇题目传送门◆分析根据题目所给定的规则，可以发现对于每一行，其下面一行上放的棋子数目不可能多于上面的一行。所以我们可以将每行上已经用了的棋子个数记录下来，这样就能够很轻松的表示出一个棋盘了。如果直接暴力加上 alpha - beta 剪枝的话显然会直接 T 飞。同时我们发现随着步数的增加，棋子也会越来越多，换句话说这东西...
2019-11-09 17:41:47
174
原创 【CF-GYM】【状压DP】100837F Controlled Tournament
CF-GYM 100837F Controlled Tournament题目大意有NNN个人参加比赛，其中你是比赛的组织者，你必须帮助第MMM个人使他获胜。求让比赛轮数最小时的方案数。分析看到了这么小的NNN，我们很容易往状压 DP 上想。考虑状态f(i,S,d)f(i,S,d)f(i,S,d)表示当前参加的人为SSS，我们想让第iii个人胜出且经过ddd层的方案数。转移就枚举SSS的...
2019-11-07 22:30:21
175
原创 【CodeForces】【状压DP】1155F-Delivery Oligopoly
CodeForces 1155F Delivery Oligopoly题目大意给定一个已经是边双联通分量的图，要求删掉最多的边，使得最终得到的图是也是一个边双联通分量。输出保留的边。分析考虑我们如何构造出一个边双联通分量。我们发现最终的答案一定是一个环带上一个环的样子（有点像糖葫芦）。于是考虑强制以111为起点，每次向上面加上一条链。考虑如何按照这样的方式来计算答案。首先预处理一个...
2019-11-07 21:37:11
272
原创 【二分图】二分图的关键点和关键边
二分图的关键点二分图中的关键点是指，若去掉这个点，使得二分图上的最大匹配变小的方案数。算法考虑枚举一个点，将它删去后所产生的影响。设mx(i)mx(i)mx(i)为XXX部中的点所匹配到的YYY部中的点。考虑枚举iii，若mx(i)=−1mx(i)=-1mx(i)=−1显然这是个非关键点。否则我们就沿着iii去找一条增广路，若找到了这么一条增广路，就说明这个点是非关键点。那么剩下的点就...
2019-11-07 21:21:25
565
原创 【POJ】【二分图】3487 The Stable Marriage Problem
POJ 3487 The Stable Marriage Problem题目大意◇题目传送门◆有NNN个男人向NNN个女人求婚。每个男人会从他最喜欢的女人开始一个一个地求婚。每个女人对男人也有不同的喜欢程度，当有某个女人有更喜欢的求婚者来求婚时，她会拒绝掉之前来求婚的男人。求最终哪些男人和女人会结成一对。分析这是一个稳定匹配的模板题考虑这样一个算法：我们进行第一轮的求婚：每个男人会选...
2019-11-07 19:51:39
234
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人