- 博客(106)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 整洁即是正义
序 读到这句话往往有两个原因：1.你是一个程序员，2.你想成为更好的程序员。 ——《代码整洁之道》马金(美)原则命名无论是在现实世界还是在代码中，命名都是一件令人头疼的事情。在现实世界，人们往往基于其特征与人们对其寄予的期望对某事某物或者其他人命名，而在代码中，命名的原则与现实世界相同——也就是“见名知意”。但是与现实世界稍有不同的是，代码中的命名还要考虑命名冲突的问题。见名知意，
2017-06-21 20:03:14
877
2
原创 阿里笔试题解（2020.4.17场）
题目一题干给定n，构造长度为n的排列，使得满足i<j<ki<j<ki<j<k的ai,aj,aka_i,a_j,a_kai,aj,ak，不出现ak+ai=aj∗2a_k+a_i=a_j*2ak+ai=aj∗2的情况。题解暴力解法得到n=3n=3n=3到n=8n=8n=8部分的答案，观察可知，奇数部分和偶数部之间不会互相干扰（因为当aia_iai...
2020-04-17 10:15:07
3840
5
原创 ZeroMQ源码阅读阶段性总结
文章目录Data Structor —— ZMQ的最快底层Own tree —— ZMQ的安全销毁机制own_t 基类参考资料Command Flow —— ZMQ如何实现内部的命令传递序：ZMQ中command与message的区别基类：command_t —— 真正的命令mailbox_t的前置技能：mutex_t（同步锁）mailbox_t的前置技能：signaler_t（信号机）核心类：m...
2019-02-22 18:45:55
1007
原创 【多变量线性回归】学习记录
序由于最近时间比较紧，要学的东西也比较多，所以这篇文章会写得比较粗略，主要目的也是保存自己的代码，以及方便自己日后回忆。思路J 函数首先我们将要定义一个 JJJ 函数，意在表达当前函数与训练数据间的差异值，JJJ 函数的值越大，表示在参数为 θ\thetaθ 时当前函数 hθ(x)h_{\theta}(x)hθ(x) 与训练数据 yyy 的拟合程度越差。下面给出 JJJ 函数的定义式：...
2018-11-27 15:56:58
298
原创 【Google Kickstart Round_H】解题报告
序虽然做了一个多小时，但是还是想说这场好水啊。链接：https://code.google.com/codejam/contest/3324486/dashboardProblem A. Big Buttons题意一个长度为 nnn 的 01串，该字符串有 mmm 个不能出现的前缀，问这样的字符串有多少种？题解由于 n,mn,mn,m 的范围很小，直接建一棵表示前缀限制条件的字典树...
2018-11-19 19:57:33
615
原创 【HDU 1010】顺序刷题 Tempter of the Bone （dfs 奇偶剪枝）
题目大意给出一张 n∗mn*mn∗m 的图，图中标有起始点 SSS，终点 DDD，和不能走的墙 XXX。问是否可以恰好走 k 步 从起点走到终点（不能走重复的点）。解题思路一开始以为是 bfs，但是这个就算地图状态可以状压，状态数也还是太多了，所以广搜明显是不行的。后来转到 dfs， 考虑剪枝。最基础的可行性剪枝 -> 如果现在剩余的可走步数已经严格小于当前位置和终点位置的曼哈顿距...
2018-11-13 21:51:41
346
原创 【HDU 6410】序列期望 百度之星复赛B （数学期望）
题目大意有n个随机变量x1,x2,…,xn。给定区间[l1,r1],…,[ln,rn]，变量xi的值会等概率成为区间[li,ri]中的任意一个整数。显然这n个随机变量的值会有一共∏ni=1(ri−li+1) 种情况，且每种情况出现的概率为 ∏ni=1ri−li+1∏i=1nri−li+1∏^{n}_{i=1}r_i−l_i+1 。对于某种情况，令h=max{x1,x2,…,xn}，定义...
2018-08-20 11:18:48
483
原创 【HDU 6395】暑期多校day7 Sequence （除法分块、矩阵快速幂）
题目大意求 Fn ，（n<=1e9）。 ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪F1=AF2=BFn=Fn−2∗C+Fn−1∗D+⌊Pn⌋{F1=AF2=BFn=Fn−2∗C+Fn−1∗D+⌊Pn⌋\begin{cases}F_1=A \\\\F_2=B \\\\F_n=F_{n-2}*C+F_{n-1}*D+ \lfloor \frac {P}{n} \rfloor \\\\...
2018-08-14 20:52:19
189
原创 【HDU 6393】暑期多校day7 Traffic Network in Numazu （基环树、树链剖分）
题目大意给出一棵基环树，有两种操作：1）修改一条边的边权，2）查询一个点到另一个点的最小距离。解题思路基环树其实可以形象的理解为一个长了好几棵树的环，那么，取两个点共有以下两种情况： 1. 两点在同一棵树上； 2. 两点在不同根的两棵树上；对于在同一棵树上的两个点，问题就是简单的树链剖分；对于在不同树上的两个点，距离可以转化为“两结点到根节点的距离+环上两个根节点的距...
2018-08-14 18:03:47
220
原创 【HDU 6394】暑期多校day7 Tree （LCT、倍增LCA）
题目大意给出一个有根树，每一个结点有一个值 ki ，表示到达这个点的的石子可以向根跳 ki 步，现在有两种操作：1）改变一个点的 ki 值，2）查询向一个点丢石子时，石子弹几次才会走出树。解题思路这道题其实就是弹飞绵羊那道题的升级版，两种操作可以分别被理解为：改变某个节点的父节点，查询某个结点到根节点的距离。感觉当场只有100人过掉有点少了吧。代码#include &l...
2018-08-13 21:28:56
213
原创 【HDU 6365】暑期多校day6 Shoot Game （区间dp）
题目大意在二维平面的第一象限和第四象限上有 n 条线段表示 n 堵墙，每堵墙有一个坚固度 wi ，表示只有不小于 wi 的能量才能摧毁并贯穿它。你只能从原点向任意方向发射任意能量，问至少需要发射多少能量才能把所有的墙都摧毁。解题思路在考试的时候一直都想偏了，一直在考虑各个墙之间的遮挡关系，甚至画出了拓扑图。由于这道题的线段都是在二维平面上，这就很烦，所以考虑降维。虽然发射能量的...
2018-08-09 11:03:36
460
原创 【HDU 6370】暑期多校day6 Werewolf （推理 基环树）
题目大意有 n 个人在玩只有狼人和村民两种身份的狼人杀，他们在互相指认，形式为“ x 是狼人/村民”。限制：1）每个人都不能指认自己，2）村民必须说真话，3）狼人可能说谎。对于每组测试数据，要求输出一定为村民的玩家数目，一定为狼人的玩家数目。 http://acm.hdu.edu.cn/showproblem.php?pid=6370解题思路根据题意可知，村民只能说实话，而狼人既...
2018-08-09 09:22:42
347
原创 【Nowcoder】暑期多校day6 Team Rocket （线段树 细节）
题目大意有 n 条线段，分别对 m 个点进行操作，每次操作时删除包括这个点的所有线段，每个线段至多被删除一次。问每个操作删除的线段数，以及每个线段被消灭的最早一次操作。解题思路考虑把每个区间当做平⾯上的⼀个点 (l, r)，每次操作相当于是删去所有的满⾜ (l <= x <= r) 的点，相当于是把横坐标 <= x 的所有纵坐标 >= x 的点删去。离散...
2018-08-08 10:18:06
170
原创 【Nowcoder】2018 ACM-ICPC 上海大都会赛 A Simple Problem with Integers （线段树 思维）
题目大意对于一个序列，进行以下两种操作：1）将区间 [li,ri] 内的数字平方后 mod 2018，2）求不取模的平方和。解题思路由于模数很小，所以可以从这里下手。打一个表之后可以发现，每个数都将在进行几次 mod 2018 意义下的平方运算之后进入一个长度很小的循环节，且所有循环节长度的 lcm 为 6。而且可以发现，每个数字经过不超过 5 次运算都可以进入循环节，所以在某个数...
2018-08-06 09:41:41
253
原创 【Nowcoder】2018 ACM-ICPC 上海大都会赛 Matrix Game （网络流 最大流）
题目大意给定一个 n*m 的矩阵 (n,m<=20)，保证矩阵内的元素 Ai,j<=20，每次操作可以对矩阵内的数进行 +1/-1。问至少需要多少次操作，可以使矩阵内行与行的和相同，列与列的和相同。 链接：https://www.nowcoder.com/acm/contest/163/I解题思路看了一个非官方的题解是用 mcmf 解决的，而且还要对结果进行三分，...
2018-08-05 20:41:05
589
1
原创 【Nowcoder】暑期多校day6 Generation I （组合数学）
题目大意有 n 个编号分别为 1~n 的集合（无重复元素），下面对这 n 个集合进行 n 次操作，第 i 次操作为：向编号为 i~n 的集合中分别插入一个 ai ∈ [1,m]。经过 n 次操作后，问这些集合有多少种终态？解题思路在编号从 1~n 的 n 个集合中，集合内元素的个数随集合编号的增加而不降：也就是说，当进行第 i 次操作时，要么加入了一个之前已经被加入过的“旧数”...
2018-08-04 21:21:21
145
原创 【Nowcoder】暑期多校day5 Take （数学期望 树状数组）
题目大意有 n 个箱子，每打开一个箱子有 pi 的概率出现一个大小为 di 的钻石。以 1~n 的顺序打开箱子，每开到比手里的钻石更大的钻石就把手里的钻石换掉，求期望交换次数。 https://www.nowcoder.com/acm/contest/143/F解题思路基于期望的线性性，分别求出第 i 个箱子的钻石被交换的概率 p = p（第 i 个箱子前面的所有钻石尺寸大于等于...
2018-08-03 18:03:28
187
原创 【Nowcoder】暑期多校day5 VCD （思维 树状数组）
题目大意Kanade has an infinity set H:{{(a,b)&amp;nbsp;|&amp;nbsp;a≥x,b∈[y1,y2]}&amp;nbsp;&amp;nbsp;|&amp;nbsp;&amp;nbsp;y1∈R,y2∈R,x∈R,y1≤y2}H:{{(a,b)&amp;nbsp;|&amp;nbsp;a≥x,b∈[y1,y2]}&
2018-08-03 10:40:25
203
原创 【Nowcoder】暑期多校day5 GPA （01分数规划）
题目大意共有 n 个对象，每个对象有两个属性值 si ci，至多可以删去 k 个对象，求右式的最大值：∑ni=1s[i]∗c[i]∑ni=1s[i]∑i=1ns[i]∗c[i]∑i=1ns[i]\frac{\sum_{i=1}^{n}s[i]*c[i]}{\sum_{i=1}^{n}s[i]}。解题思路01分数规划的经典问题。二分答案解决问题，当我们检查二分到的值 D 是否可以达到...
2018-08-03 10:28:49
113
原创 【HDU 6341】暑期多校day4 Let Sudoku Rotate （搜索）
题目大意原有一个16×16的数独，这个数独的某些宫（粗黑线划分的区域）被逆时针的旋转了未知次，给出某个数独被操作后的终态，求从原始状态到终态的最小操作次数。详见 http://acm.hdu.edu.cn/showproblem.php?pid=6341 题目样例，解释很详细。解题思路直接进行枚举状态的搜索虽然加上优化可以过，但是考试的时候还是不太愿意写这种可能被强数据强行卡掉...
2018-08-02 10:09:32
237
原创 【HDU 6326】 暑期多校day3 Monster Hunter （贪心）
题目大意给定一棵 n 个点的树，除 1 外每个点有一只怪兽，打败它需要先消耗 ai 点 HP，再恢复 bi 点 HP。 求从 1 号点出发按照最优策略打败所有怪兽一开始所需的最少 HP。 (2≤n≤105)(2≤n≤105)(2 ≤ n ≤ 10^5)解题思路以 1 为根将树转化成有根树，那么每只怪兽要在父亲怪兽被击败后才能被击败。 考虑简化版问题：忽略父亲的限制，求最优...
2018-08-02 00:25:33
451
原创 【HDU 6331】暑期多校day3 Walking Plan （分块 矩阵乘法 × Floyd）
题目大意给定一个 n 个点，m 条边的有向图，q 次询问 u 到 v 经过至少 k 条边的最短路。 (2≤n≤50,1≤m,k≤104,1≤q≤105)(2≤n≤50,1≤m,k≤104,1≤q≤105)(2 \leq n \leq 50 , \quad 1 \leq m,k \leq 10^4, \quad 1 \leq q \leq 10^5)解题思路注意题目中n的范围很小，...
2018-08-01 10:48:38
218
原创 【HDU 6327】 暑期多校day3 Random Sequence （妙妙dp）
题目大意给定一个正整数序列 a[1..n]a[1..n]a[1..n]，每个数在 [1,m][1,m][1, m] 之间，有些数已知，有些数未知。 在未知数在 [1,m][1,m][1, m] 之间随机的情况下，求以下值的期望： ∏i=1n−3v[gcd(ai,ai+1,ai+2,ai+3)]4≤n≤100,1≤m≤100∏i=1n−3v[gcd(ai,ai+1,ai+2,ai+3)]4≤...
2018-07-31 17:49:47
175
原创 【HDU 6319】 暑期多校day3 Ascending Rating （双端单调队列）
题目大意给定一个序列 a[1..n]，对于每个长度为 m 的连续子区间， 求出区间 a 的最大值以及从左往右扫描该区间时 a 的最大值的变化次数。(1≤m≤n≤107)(1≤m≤n≤107)(1 \leq m \leq n \leq 10^7)解题思路今天上午的时候刚帮高中教练验了一道几乎一样的题，只不过是双权值，而且数据范围兹磁时间复杂度 O(nlogn)O(nlogn)O...
2018-07-31 09:07:06
159
1
原创 【Nodecoder】 暑期多校day4 Chiaki Sequence Reloaded （二进制树）
题目大意求f(n)f(n)f(n)，共有10510510^5组询问： an=⎧⎩⎨⎪⎪⎪⎪1,a⌊n2⌋+(−1)n∗(n−1)2,n=1n≥2f(n)=∑i=1n|ai|an={1,n=1a⌊n2⌋+(−1)n∗(n−1)2,n≥2f(n)=∑i=1n|ai|a_n=\begin{cases}1,&\text{$n=1$}\\\\a_ {\lfloor \frac{n}{2} \rfloo...
2018-07-29 17:43:08
296
原创 冲刺NOI2017 (24) A （后缀数组 回滚莫队）
题目大意给出一个长度为nn的字符串ss，提出qq个询问，对于每个询问要求回答：右端点在区间[l,r][l,r]的所有前缀，最长公共后缀最长的一对前缀的最长公共后缀的长度是多少。题解因为要在原串的前缀上分析后缀十分的别扭，所以对这个问题略作转化：将原串翻转过来，求左端点在区间[l,r][l,r]内的后缀的lcp（最长公共前缀）。同时不要忘记把询问也翻转到同样的姿势。问题已经转化为了：左端点在区间[l,
2017-06-22 23:04:09
638
原创 BZOJ4241 历史研究 （分块 回滚莫队-教程向）
题目大意给定一个长度为nn的序列，并提出qq个询问，每次询问要求回答区间 [l,r][l,r] 内所有的权值与其出现次数的积的最大值。题解看见这种xjb询问的题当然是要下意识地用分块来搞一搞的，又因为只有询问，且题目没有要求强制在线，所以就可以理所应当地“分块+莫队”来搞这道题了。对于这道题，莫队的加入操作是很好实现的，只要增加一下被加入区间的权值的出现次数并同时更新一下答案就可以了，但是删除操作却
2017-06-20 23:01:45
1752
2
原创 冲刺NOI2017 (22) 养猫 （线性规划方程转网络流）
题目大意你养了一只猫，为了让它快乐地成长，你需要合理地安排它每天的作息时间。假设一天分为nn个时刻，猫在每个时刻要么是吃东西，要么是睡觉。在第ii个时刻，假如猫是去吃东西，那么它能获得愉悦值eie_i，假如是去睡觉，那么能获得的愉悦值为sis_i。猫要成长，不仅仅需要快乐，还需要健康的作息。经过研究，对于每一个连续的长度为kk的作息时间，即所有的时刻区间[i,i+k−1],1≤i≤n−k+1[i,i
2017-06-17 22:43:04
1366
原创 冲刺NOI2017 (20) 距离 （可持久化树链剖分）
题目大意给定一棵nn个点的边带权的树，以及一个排列pp，有qq个询问，给定点 l,r,kl,r,k，希望你求出： ∑点j∈l到r的最短路径dis(p[j],k)\sum_{点j\in{l到r的最短路径}}dis(p[j],k) 其中dis(u,v)dis(u,v)表示在树上uu到vv的最短路径的长度。数据范围：(n,p<=2∗105)(n,p<=2*10^5 )题解我们先抛开这个道题不谈，讨论另
2017-06-16 17:20:34
887
原创 冲刺NOI2017 (20) 苹果树 （矩阵树定理 容斥原理 Meet in middle）
题目大意给定nn个苹果，对于苹果ii，其甜度为cic_i，cic_i>=-1。假如cic_i=-1，代表苹果ii是坏的，否则它是好的。现在要用n−1n-1条线把这n个苹果连成一个联通块，也就是一棵树，定义树上一个苹果是有用的，当且仅当它是一个好苹果，且与至少一个好苹果直接相连。一棵树的权值定义为树上的有用的苹果的甜度之和。给定limitlimit，问有多少种不同的生成树，满足其权值小于等于limit
2017-06-14 14:46:28
811
翻译 Z-function/Z Algorithm的构造与应用
Z-function 定义一个函数z()，z(i)是指由s[i]开始的字串，与s[0]开始的字串可以匹配到多长。也就是说 s[0 ... z(i)-1] = s[i ... i+z(i)-1]。
2017-06-02 15:07:00
1967
原创 一点杂谈
200元左右请考虑 “Switch 超级炸弹人R” 300元左右请考虑“Switch ARMS” 500元左右请考虑“战地1 豪华版” 600元左右请考虑“战地1 终极版” 700元以上我收不起谢谢dalao…
2017-05-27 12:23:53
540
原创 【正解】Openjudge 至少有多少只恼人的大青蛙 （dfs 剪枝 好题）
题目大意http://cxsjsx.openjudge.cn/2015finalpractice/43/ 讲真这题的大意我真的真的概括不来，各位看官老爷还是直接在原题目上看吧，顺便给出一个提交的链接。题解作为一道擅长屎题 向往屎题 热爱屎题的选手，不得不说，这道题确是一道搜索好（shi）题，所考察的搜索剪枝相关的知识点也是非常的全面。没有比较就没有差距，首先我放上一份无脑而又暴力的代码上来。暴力代
2017-05-18 10:44:20
1594
原创 BZOJ3676 回文串 （回文树）
题目大意考虑一个只包含小写拉丁字母的字符串ss。我们定义ss的一个子串tt的“出 现值”为tt在ss中的出现次数乘以t的长度。请你求出ss的所有回文子串中的最 大出现值。 题解回文树裸题，但是这里要注意一定要在最后统一推标记，否则全1串的时候一定会TLE。 这里附上一个写得很好的回文树讲解 回文树介绍(Palindromic Tree)代码#include <cstdio>#inclu
2017-05-01 10:05:24
748
原创 （模板）中国剩余定理 重学笔记 POJ1006
资料推荐有很大帮助的博客 ——（本文多处引用其中金句，特此注明出处并鞠躬感谢博主。）主要定理定理一： 几个数相加，如果任何一个数不能被div整除，那么这几个数的和一定不能被div整除。定理二： 两数不能整除，若除数扩大（或缩小）了几倍，而被除数不变，则其商和余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。主要步骤求出各个除数(div)的最小公倍数(lcm)。求出各个除数的基础数(b
2017-04-24 15:13:30
831
1
原创 BZOJ4327 玄武密码 （AC自动机）
题目大意给出一个母串和一些特征串，询问字串能在母串中匹配的最长的前缀的长度。题解将特征串一一插入AC自动机并构建fail指针，这样母串匹配的时候走过的路径上的点所代表的前缀就都是可匹配的了。所以把所有的特征串插入AC自动机后构造fail树，然后把母串在AC自动机上跑一下并在可匹配的点上留下标记就可以了，这里要注意标记一定要顺着fail指针传上去一并打上标记，否则可能会遗漏。然后对于每一个特征串，从叶
2017-04-20 16:11:22
1191
原创 BZOJ2251 外星联络 （Trie树）
题目大意给出一个01串，要求按照字典序输出在串中出现两次以上的子串的出现次数。题解我是在hzwer学长的后缀数组专题中看到这道题的，但是我并没有很理解黄学长的暴力是怎么思考的…于是我在另一个地方得到了另一种思路。首先要知道字串的性质：一个串的所有字串都可以表示为这个串某个后缀的某个前缀。换句话说，就是一个串的所有后缀的所有前缀都与这个串的子串一一对应。利用这个性质，这道题就可以写得很简短。所以，这道
2017-04-17 19:00:51
625
原创 BZOJ4429 Elementary Math小学数学 （二分图匹配）
题目大意给出n个数对，支持加减乘三种操作，输出一种方案使每一个式子的结果各不相同。如果没有方案的话输出impossible。题解因为每个方案中，每一个式子都能且只能对应一个值，所以说式子和值的关系是一一对应的。有因为每一个式子最多只能对应3个值，所以说空间和时间复杂度都允许。代码#include <cstdio>#include <iostream>#include <algorithm>us
2017-04-17 14:27:45
777
原创 BZOJ3307 雨天的尾巴 （树链剖分 线段树合并 dfs相关）
题目大意N个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。题解看到这道题之后我本能的想法就是位置线段树套权值线段树的，但是看了一下，这道题的时间限制和空间限制卡得都比较近，树套树卡起来应该是十分的困难的。这道题虽然是处理树上问题，但是我们先考虑如何处理这样的区间问题。 如果所有的操作和询问都是
2017-04-17 13:44:32
1211
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人