- 博客(38)
- 收藏
- 关注
RSS订阅原创 博客搬家公告
鉴于CSDN对博客的个性化不是很支持，所以我选择转移… 新博客地址为 http://www.cnblogs.com/yearwhk/ http://www.cnblogs.com/yearwhk/ 但是cnblogs对Markdown编辑器的支持不如CSDN，因为它不支持预览。所以，我现在用本地Markdown编辑器写博客代码，然后拷贝到cnblogs上去。不得不说…cnblogs的确要美观一些
2016-01-11 19:26:28
500
1
原创 BZOJ 1588 - 二叉搜索树
本题是Treap/Splay的模板题了… 也可以用set或者双向链表实现。 （其实这题是在NOIP2012 Day1 T3的一部分啊。。 由于我懒，所以只码了Treap。还有很多模板题，先把这几种数据结构刷熟再说。 平衡树上找一个元素的前缀/后缀只要脑补一下，左左右右地走一走就行了。 第一次码，出现了不少问题，也从各种千奇百怪的模板中学到了不少。详见代码注释。// BZOJ 1588#inc
2016-01-10 00:37:59
724
原创 BZOJ 1968 - 枚举约数
枚举1..n的每个数x，加上它对答案的贡献n/x即可。// BZOJ 1968#includeusing namespace std; int n, ans; int main(){ scanf("%d", &n); for(int i=1; i<=n; i++) ans+=n/i; printf("%d\n", ans); return 0;
2016-01-07 23:32:57
707
原创 BZOJ 1010 - 斜率优化
比较裸的DP+斜率优化啦…… 让窝又想到了BZOJ上A的第一道有意义的题1597…… 作为第27个A的题也让我颇有感触…… 设前ii个玩具放置到jj个盒子里所需的最小费用为f[i][j]f[i][j]。由于连续的玩具必须放到一个容器里，所以我们有：f[i][j]=f[k][j−1]+cost[k+1][i]f[i][j]=f[k][j-1]+cost[k+1][i]其中k为我们枚举的上一个容器的末
2016-01-07 23:14:10
439
原创 BZOJ 1015 - 变删点为加点 + 并查集维护
题意：给出一张无向图，每次删去其中一个点，每删一次就输出当前连通块的数量。 首先要明确一点：删去一个点，同时也删去了和这个点有关联的边集。但无论如何，删点并不好搞，所以我们可以考虑倒着来，加点，用并查集维护。具体来说，每次加上一个点xx，如果一个点是被第一次删去的（一个点可能被删去多次）（然而数据中并没有这种情况），那么就将连通块数加1；否则不考虑。然后依次添上它的每一条相邻边，并查集维护之即可。
2016-01-07 18:45:03
743
原创 BZOJ 3875 - SPFA处理带环的DP
本题的DP思路很好想：设f[i]f[i]为第ii个怪兽被消灭所需要的最小代价，那么，f[i]=min{spl[i],ori[i]+∑j∈App[i]f[j]}f[i]=min\{spl[i], ori[i]+\sum_{j∈App[i]}{f[j]}\}然而，由于f[j]f[j]有可能也要依赖f[i]f[i]，所以这个DP会带环。啊，那该怎么办呢？遇到这类问题，我们常常用SPFA来处理。怎么处理呢
2016-01-06 22:20:30
773
原创 BZOJ 2705 - 经典问题 欧拉函数
题意：求∑ni=1gcd(i,n)\sum_{i=1}^{n}gcd(i,n) 首先，gcd(i,n)gcd(i,n)肯定是nn的约数。所以我们可以考虑枚举每个nn的约数dd，然后看有多少个gcd(i,n)=dgcd(i,n)=d。这个式子又可以化成gcd(i/d,n/d)=1gcd(i/d, n/d)=1。而它，就相当于ϕ(n/d)\phi(n/d)。所以，答案就是∑d|nϕ(n/d)\sum_
2016-01-06 00:12:28
731
原创 BZOJ 1030 - AC自动机 + DP
1009那题仍然记忆犹新…… 首先说一下1009的拓展：如果有多个串，则需要建立AC自动机，状态也需要改成：设f[i][j]f[i][j]为考虑到长度为ii的字符串，匹配到AC自动机的jj号节点的方案数，同样地道理构造出矩阵即可，只不过这里f[i][j]f[i][j]为0的条件变为j号节点是单词节点。 然后看这道题，它的要求是相反的：给定一堆字符串，统计长度为m的至少包含一个给定字符串的文本串的长
2016-01-05 19:41:05
257
原创 BZOJ 2301 - 莫比乌斯反演 + 前缀和 + 分块计算
题意：对于给出的nn个询问，每次求有多少个数对(x,y)(x,y)，满足a≤x≤b，c≤y≤da \le x≤b，c≤y≤d，且gcd(x,y)=k(x,y) = k。 首先用容斥原理将一个询问拆成4个。然后，一种可行的转化是求一种可行的转化是先令k=1k=1，即求1≤floor(x/k)≤n1 ≤ floor(x/k) ≤ n 且 1≤floor(y/k)≤m1 ≤ floor(y/k) ≤ m
2016-01-05 19:24:31
377
原创 BZOJ 1009 KMP思想 + DP + 矩阵快速幂
第一次用MarkDown和LaTex，写得有点丑……本题的坑爹历程给了我一个血的教训：没有真正搞清楚做法之前，不要瞎BB地写题解。不然会造成深陷坑中的严重后果。题意简述：给定一个字符串s，求出长度为n的不含字串s的字符串t的数量。这道题是一个非常经典的模型，DP之： 设 f[i][j]\ f[i][j]为前i个t字符，匹配到s的第 j\ j位（强制选 i\ i）的方案数，则有ans=Σ( f[n]
2016-01-03 23:05:30
276
原创 BZOJ 1257 - 数学题 乱搞
先看一个乱搞的题解（但是很有启发性...）：首先是一个有趣的发现：当 i 增长很小时，k/i 值是不变的！比如，在 i∈[l, r]的时候，商不变，那么在这个区间内，k modi 的值将是一个公差为1的等差数列！所以，我们枚举商，统计答案就行了！好吧。。我们来一个严谨一点的方法。。题目要求的是 ans = Σ(k mod i) = Σ(k-k div i * i) = n*
2015-12-29 22:10:58
365
原创 BZOJ 1003 - 最短路 + DP
从这篇开始换字体。。数据范围很小。。直接暴力DP之即可。。感觉跟之前做的1597的DP很像，都是基于连续区间的DP，应该也可以用斜率优化。。还感觉跟某次CodeVS模拟赛的题的一道变态题（多面体原谅我。。）很像。。只不过那道题最后是二分图匹配。。题解详见代码注释。。我只想吐槽。。窝一遇到什么n m d k p都出来的题，就很容易打错变量名（又因为这WA了三四次！。。这回我一开始就写
2015-12-29 22:10:32
313
原创 BZOJ 1002 - 奇妙的题目 + 高精度
这道题有很多奇妙的方法可以搞。。最科学的当然是基尔霍夫矩阵（按照传统，“我也不知道是什么东西”），详见VFK教主的博客；还有乱七八糟的找规律，网上遍地都是。。我就把这题当作高精度练习题了。。
2015-12-29 00:10:35
449
原创 BZOJ 2190 - 欧拉函数的应用（数据范围不同 -> 做法不同 -> 启示）
用欧拉函数解决问题满足(x, y)=1 (x<=n, y<=n) 的数对的个数UVa 10214数据范围不同 -> 做法不同 -> 启示
2015-12-28 23:12:05
376
原创 BZOJ 1036 - 树链剖分 模板题
今天终于入手了期盼已久的Macbook Pro，十分高兴。。然而这道题对着黄学长的代码码的，还是打错了一个变量名，查了半个小时，羞耻MAX。。第一次A了之后遵循了VFK的神谕和bkq的忠告，按照自己的理解重新码了一遍，感觉效果好了很多。。这种方法对之后的学习仍然适用~// BZOJ 1036// Tree Chain Spilt#include #include #inc
2015-12-27 00:07:57
449
原创 BZOJ 1053 - 反素数（搜索）
一个写过的题还搞了半个多小时。。羞耻MAX。。求反素数的核心思想是“用大的（质数）不如用小的”。一个数的约数个数等于其各质因子的次数加1后的乘积，因此可以从小到大考虑每个质数，枚举其次数，DFS之即可。具体细节详见代码。// BZOJ 1053#include #include #include using namespace std; typedef long long L
2015-12-24 19:40:42
301
原创 BZOJ 1415 - 利用定义计算期望 + DP
本题是我第一道A掉的NOI题~ 啪啪啪。。参考了tky的论文，他的题解很详尽易懂，下面对这个经典题目的经典解法作个推导和总结。第一个拦路虎是如何求出鼠和猫的位置为(a,b)时猫的下一步行动。我们设p[a][b]为猫位于a，鼠位于b时猫下一步走到的节点。由于这个图没有边权，所以这个p是可以通过n次BFS预处理出来的（这个BFS的细节需要特别注意，详见代码）。然后我们考虑枚举所有情况来计算
2015-12-23 00:33:54
589
原创 白书动态规划例题和习题简解
Pre言：本文的题解原题均来源于白书，题号：UVa 10859, 11825, 11584, 10534, 11552, 11404, 11795, 10564.LA 3983, 4794, 4256, 4731, 4727, 2038, 4394, 4015.一直觉得自己的基础DP不是很扎实，所以就花了一节晚自习+半个上午的时间阅读和解决了上述大部分题目，少数几道习题查了题解之后
2015-12-21 20:20:05
409
原创 BZOJ 1266 - 最短路 + 最小割
裸题。。第一问最短路，第二问最小割。。先求一发最短路树，然后建图，容量均为1，然后Dinic最大流即可。。
2015-12-17 19:57:46
275
原创 BZOJ 1001 (UVa1376, LA3661 ) - 平面图最大流（对偶图 -> 最短路）
直接套Dinic妥妥地TLE。。怎么办呢。。这是一个平面图。。有一些很好玩的性质。。利用这些性质，我们可以做一些奇妙的转化，把流量转化为边的长度，然后跑一遍最短路即可。。这个转化，就是对偶图。。理论依据详见2008年国家集训队周冬的论文《两极相通——浅析最大—最小定理在信息学竞赛中的应用》、
2015-12-17 19:16:27
429
原创 UVa 11178 - 计算几何初步
本题直接计算即可，“主要是看你会不会算”。。抄了一通Rujia Liu的代码。。同样地。。方便好记然而效率比较低。。所以先用着。。用熟了再参考黄学长的模板。。// UVa 11178#include #include #include using namespace std; int T; #define rep(i,a,b) for (int i=a; i<=b;
2015-12-17 19:10:06
288
原创 BZOJ 1787 裸LCA
一个求树上LCA的裸题。。WC（伪。。）里想出来的。。题目大意：给出树上的三个点，要求确定一个集合点，使得这三个点到集合点的路径权值和最小。所有边权均为1。先考虑两个点A、B的情形。。显然这两个点间路径上的任何一点都可以作为集合点。。然后再加入第三个点C。。画个图不难证明此时最优集合点应是LCA(A, B)。但是A、B、C分别是哪些点呢？。。枚举取最优解。。但看了黄学长博客
2015-12-16 21:22:45
718
原创 BZOJ 1045 (UVa 11300) 数学分析 + 结论
这道题在白书上题解相当详细了。。作个总结。。令传递是单向的。。（传递的糖果数量可正可负）然后列出了n-1个方程。。然后一些奇怪的方程加减消元。。转化成了单变量的极值问题。。是这样的。。令Ci=Ai-M（M为最终每个人手中的糖果数量，Ai为初始糖果数量）于是ans=|x1| + |x1-C1| + |x1-C2| ... + |x1-C(n-1)|注意它的几何意义。。在数
2015-12-16 21:15:12
289
原创 NOIP 2012 Day1 T3 - set + 树上倍增
这道题NOIP之前没码完。。身败名裂。。很明显的树上倍增啦。。但有一个问题是如何快速获得每个点的两个最近和次远。。用set。。完了。。细节见代码。。// NOIP2012 Day1 T3#include #include #include #include #include using namespace std; typedef long long LL;
2015-12-16 19:44:23
339
原创 BZOJ 2561 - 最小生成树 + 最小割
本题需要用一点M(in & ax)ST的性质。。以MinestST（这英语也是十级水平。。）为例。。假设加入边(u, v)，边权为L。然后我们把所有边权小于L的边都取出来单独看。这些边不能连通u, v，否则(u,v)边绝无可能在MST中——因为在加入它之后形成的这个环中，如果去掉它，显然是最优的。所以以u、v为s、t，每条边权小于L的边容量置为1、跑一遍无向图最小割即可。。Maxest
2015-12-16 00:04:02
364
原创 UVa 11082 - 最大流 基础建模
一道很基础的网络流建模。。本题输入的是前缀和，先用它们求出每行、每列的元素和然后将每一行看作一个节点（记作Xi），每一列看作一个节点（记作Yi），并新增源点S、汇点T。S往Xi连边，容量为这一行的元素和减1；Yi往T连边，容量同上。每个Xi往每个Yj连边，容量为20-1=19。之所以要将容量都减1，是因为边权要在1~20之间，有下界，但并不需要用到专门的有下界最大流算法，可
2015-12-15 23:52:43
278
原创 OI? OI!
最近有点不顺心。。时间安排上有点奇怪，然后很奇怪地每天只能睡五六个小时。。天天被某人D啊。。OI之路漫漫，我还是太弱太弱。以后做题准备纸笔。。题量以及一些常识积累不够的情况下，空想只会让效率低下。看了一个zj神犇的博客，然后感叹了一番强省弱省差距之大后，也应该庆幸。。一些基础内容并不熟练，先得把它们写熟再说。。某(wu)人(shen)说得对，我还是 NOIP选手。。不能急于
2015-12-15 23:42:09
428
1
原创 BZOJ 1406 - 伪数论
本来以为用一些奇妙的枚举顺序可以直接卡过去，然后弃疗。。由题意可得 x^2 = 1 (mod n) ==> x^2 = k*n+1 ==> (x+1)(x-1) = k*n ==> n | (x+1)(x-1)然后枚举n的约数。设n=a*b (aa），再判断它+2是否能被a整除。反过来再判断一次。如果(x+1)和(x-1)分别获得a、b中的因子，那么一定也会被其他情况枚举到，即做到了不
2015-12-14 20:07:39
658
原创 BZOJ 1264 动态规划 + 树状数组
“很难想的一道题不过不难写”—— Po姐 这道题窝的思考过程十分坎坷。 首先想着纯DP，类似于NOIP Day2T2的方法搞。 设f[i][j]为强制将A[i]与B串中第j个相同字符匹配的LCS，s[i][j]为考虑到A[i]与B串中第j个相同字符匹配（且强制不允许选这个字符之后）的LCS。 从这个状态设计就可以看得
2015-12-14 19:22:11
367
原创 递推专题 - 两种状态互推问题：经典问题 打砖块 + NOIP2015 Day2 T2
例1：打砖块这道题的一个非常重要的细节是：只要子弹打光，就必须结束，无论是否还有可以打到的有奖励子弹的砖块。也就是说，有奖励子弹的砖块不等价于不耗费子弹就能获得分数。就是因为这个细节，我们需要双重递推。设f[i][j]表示第i列打j下能获得的分数，g[i][j]表示第i列打j下且第j下不能接着打有奖励子弹的砖块能获得的分数。这个是可以在O(mk)时间内预处理出来的。然后进行DP
2015-12-11 23:09:22
789
原创 UVa 1232 / LA 4108 线段树
这题就是个裸的线段树。。但细节容易想错。。 题意：一个全0的序列，m次操作，每次给出一个区间[l,r)和一个值v，将该区间内所有小于等于v的数全部修改为v。求总的修改次数。 怎么做呢？一开始我是这么做的：开一个线段树，每个节点维护一个值：该区间内的元素的值——如果该区间内元素值不同，则置为-1，然后直接统计。（而且一开始我居然把1-4*maxn内的所有点
2015-12-11 22:46:39
885
原创 LA 4329 树状数组入门
本题是一道树状数组的入门题。直接统计比赛场数并不好办，我们采用枚举裁判的方法。考虑从左到右第i个人当裁判的情形，需要统计的是前i-1个人和后n-i个人中能把第i个人的技能值“夹”在中间的情况数。注意可能是前大后小，也可能是前小后大。由于这些选手的技能值各不相同，所以我们在从左到右扫描的过程中，可维护布尔型数组f[max_Ai]表示第i个人之前技能值的“占用情况”，c[i]表示前面的人中技能值小于a
2015-12-11 22:34:53
472
原创 BZOJ 4352 预处理 + DP
题目链接 ： http://www.lydsy.com/JudgeOnline/problem.php?id=4352一道SB题。。先把所有积木的长度从小到大排序。设前i块积木的摆放方案为f[i]。先考虑第i块摆在最下面的情况。显然合法，且方案数为f[i-1]。然后对于前i-1块的每一种摆放方案，都可以把第i块摆在s[i]块之上，其中s[i]为可以被第i块摆在上面的积木块数，可以O(n
2015-12-10 21:17:28
1014
原创 BZOJ 1954 (POJ 3764) Trie的经典应用 求树上最大异或值
题目链接： http://www.lydsy.com/JudgeOnline/problem.php?id=1954 （然而这是权限题…… 所以还是看POJ 3764吧）感谢黄学长。。涨姿势了。。树上路径问题，xor运算满足分配率交换律，先求出每个节点到根节点的路径权值，这样就转化为从一堆值中选出两个xor起来最大的。于是把这一堆值（不足30位的补到30位）一一插入一颗Trie
2015-12-10 20:55:39
382
原创 BZOJ 1597 斜率优化
题目链接： http://www.lydsy.com/JudgeOnline/problem.php?id=1597 作为一个非权限狗，我抱着侥幸心理在BZOJ上搜了一发USACO，结果发现了这道题。。然后想出了一个DP，然而超时。。然后就百度一下，于是被安利了一个DP的经典优化技巧——斜率优化 完整题解如下：① 注意到有一些土地是可以被其他土地无代价地“带掉”的。
2015-12-10 20:46:27
466
原创 BZOJ 1965 快速幂 + 拓展欧几里得
题目链接： http://www.lydsy.com/JudgeOnline/problem.php?id=1965AHOI2005 Day1是一道找规律题… 不难发现初始为x的牌在经过m轮洗牌之后的位置为x*(2^k) % (n+1)。然后就是一个二元线性不定方程，拓欧解之即可。方程为： (2^k)%(n+1)*x + (n+1)*y = L// BZOJ 1965#inc
2015-12-10 20:37:56
453
原创 新博客开张，欢迎前来吐槽~
一直觉得用OneNote管理笔记太乱，而且没有代码整理功能。自己搭博客又没有money，于是想到了CSDN。。 CSDN也不是sb专用啊。。巨多神(tou)犇(lan)也在这里写啊。。——回应一些品味很高的人（雾。。 好啦…… 这段时间就开始把博文搬家咯。。 开博大吉~ #include #include using namespace std;int main(){ puts("H
2015-12-10 19:59:29
251
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人