- 博客(121)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 浮点数陷阱
浮点数陷阱猜猜结果是什么#include<cstdio>using namespace std;int main() { for(double i = 0; i != (double)1.0; i+=0.1) printf("%.1lf ", i); return 0;}结果是刷屏…
2016-08-06 11:22:10
429
1
原创 回归帖
回归帖掐指算来，距离上次写博客已经是一年多的时间了。去年省选结束我就退出了奥赛，全身心投入文化课了。虽然经历了很多坎坷，但最终还是收获了不错的高考成绩，裸分全校第一，一批次被上海交通大学电子信息系录取。在本科一批报名前我纠结了很长时间，清华国防生、港科大、上交，到底该去争取哪一个。最后还是选择了相对自由而又不至于太昂贵的上海交通大学。一个很重要的原因就是上交保证了我可以学电子信息专业。上交大类招生，
2016-07-25 08:53:45
519
2
原创 算法学习-莫比乌斯反演
写在前面必须把更多的精力放在文化课上了, 所以这段时间的学习和数学相关的比较多, 希望可以对文化课有帮助.莫比乌斯反演公式g(n)=∑d|nf(d)⇒f(n)=∑d|nμ(d)g(nd)g(n)=\sum_{d|n}f(d)\Rightarrow f(n)=\sum_{d|n}\mu(d)g(\frac n d)基础知识μ\mu函数 f(n)=⎧⎩⎨1,(−1)k,0,n=1n=p1∗p
2015-04-30 17:44:05
1789
1
原创 BestCoder-Round#38
1001描述给出四个三维坐标下的点, 判定是否为正方形.分析用向量的数量积来判定是否垂直, 再判断长度.我是在纸上画出了A(3,2)=6A(3,2)=6 种情况然后暴力枚举判断是否为正方形. 组合数的意义表示在 2、3、4 三个点中有序选出两个点和 1 相邻.我写了一百多行的代码, 看了看别人简洁的代码, 发现可以直接用STL的 next_permutation 来生成下一个排列, 把排列
2015-04-19 08:35:22
1079
原创 COGS-363-土地购买-斜率优化
描述有 n(≤50000) 块 (Xi*Yi) 的土地. 一些土地的购买价格是这些土地中长的最大值乘宽的最大值 (长宽不可颠倒). 求购买所有土地的最小花费.将 n 个二元组 (x, y) 分组使每个组中的 max{x}*max{y} 的和最小.分析这里土地的顺序是无所谓的, 所以凭直觉先按 x 升序排序. 然后去除无用的土地, 即如果一块土地可以完全包含在另一块土地里, 这一块土地就不需
2015-04-18 16:27:59
891
原创 省选归来
准备二轮省选其实可以考得更好的, 但我没有安心写暴力, 结果Day1写了四个小时的树链剖分还没过样例, Day2最后一题直接最小生成树就40分结果状压动规爆零. 同时也暴露了学过的算法还是不熟练, 以为考前看一眼然后考场上就可以凭印象写出, 但是实践证明如果算法学的不扎实, 那么考场上是绝对写不出来的, 写出来也会出BUG或者调不出来.因为一轮考的不太好, 所以二轮希望不太大了, 但我还是希望用
2015-04-18 10:17:19
791
3
原创 考场计划
马上要考试了前 30 分钟之内看完题.然后不到一个半小时做一道题(顺序不一定是按原顺序), 做不出来就半小时打暴力.估计 应该全是 暴力...分块 和 莫队 和 整体二分|CDQ分治, 如果能用上的话调试还是很方便的.想 DP 或 记忆化搜索的思路.遇到需要数学推导的题目不要慌, 慢慢推, 别出错, 自己推不出来别人也不一定能推出来.计算几何慎做...
2015-04-11 06:52:40
614
原创 COGS-257-动态排名系统-树状数组+主席树
描述给定一个长度为N的已知序列A[i](11、查询A[i],A[i+1],A[i+2],...,A[j](12、修改A[i]的值为j。分析用了很长时间理解树状数组+主席树的做法这里先有一个正常的线段树,
2015-04-08 23:21:39
1030
5
原创 BZOJ-2038-小Z的袜子hose-莫队
描述每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。分析区间无修改的题目, 只需要求出各种颜色的数量即可, 所以可以用莫队.如果一种颜色 i 在区间 [L, R] 内的数目是 c[i], 那么随机抽出两只袜子颜色相同的概率等于 ΣC(c[i], 2) / C(R-L+1, 2).发现组合数的 m 位置都
2015-04-07 19:11:33
693
原创 BZOJ-3190-赛车-JLOI2013-暴力枚举
描述这里有一辆赛车比赛正在进行，赛场上一共有N辆车，分别称为个g1，g2……gn。赛道是一条无限长的直线。最初，gi位于距离起跑线前进ki的位置。比赛开始后，车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖，而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度，你的任务
2015-04-07 17:36:46
838
原创 BZOJ-2002-Bounce弹飞绵羊-分块
描述Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。分析分块, 维护
2015-04-07 17:28:52
751
原创 模板-数据结构
数据结构相关模版, 可能有错误, 省选前持续更正中重要的不是模版内容, 而是提供算法的实现思路.#define M (L+R>>1)// 删除标记线段树struct SegmentTree { int y1, y2; int sumv[maxn<<2], addv[maxn<<2]; bool clr[maxn<<2]; voi
2015-04-06 12:31:51
892
原创 模板-计算几何
图论算法相关模版, 可能有错误, 省选前持续更正中重要的不是模版内容, 而是提供算法的实现思路.struct Point { double x, y; Point(double x = 0, double y = 0): x(x), y(y) {}};typedef Point Vector;Vector operator + (Vector A, Ve
2015-04-06 12:30:10
818
原创 模板-图论
图论算法相关模版, 可能有错误, 省选前持续更正中重要的不是模版内容, 而是提供算法的实现思路.struct SPFA { int n, m, s, t; int d[maxn]; bool ban[maxn], inq[maxn]; vector edges; vector G[maxn]; void init(int n, int s, int t) {
2015-04-06 12:28:36
831
原创 模版-数学
数学算法相关模版, 可能有错误, 省选前持续更正中重要的不是模版内容, 而是提供算法的实现思路.// 扩展欧几里德算法void gcd(lli a, lli b, lli&d, lli&x, lli&y) { if(!b) d = a, x = 1, y = 0; else gcd(b, a%b, d, y, x), y -= x*(a/b);}// 逆
2015-04-06 12:27:16
795
原创 CODEVS-1082-线段树练习3-splay
描述区间修改, 区间求和分析想练练splay打标记.因为splay不支持永久标号, 所以pushdown后必须把标记清掉.第一次打上标记后要立刻让标记生效.需要注意的地方是pushdown必须让子结点的标记生效.#include using namespace std;typedef long long int lli;c
2015-04-05 18:08:27
1259
原创 BZOJ-2618-凸多边形-CQOI2006
描述给一些多边形求重叠面积分析半平面交的模版注意别少加了直线#include #include #include #include using namespace std;struct Point { double x, y; Point(double x=0, double y=0):x(x),y(y) { }};
2015-04-05 15:43:51
665
原创 CODEVS-1074-食物链-并查集
描述三种动物 A吃B, B吃C, C吃A.1, a, b 表示a,b同类2, a, b 表示a吃b判断假话个数分析NOIp前看过, 当时不会, 现在理解起来也有点抽象.按权值合并的并查集能确定关系的 x, y 的find到的祖先相同.pa[x] 是 x 的祖先, r[x] 是 x 到祖先的距离, 有三种, 0, 1, 2. 0
2015-04-05 13:36:25
1713
原创 总结-计算几何
计算几何做的题目很少, 而且模版也不熟. 所以还有这几天的时间, 把几个经典的算法弄熟弄懂, 模版能打出来就行了吧.1. 凸包2. 旋转卡壳3. 半平面交题目:1. [codevs 1249] 多边形的面积 求多边形面积, 要理解叉积的意义.2. [codevs 1298] 凸包周长 [codevs 3201] 奶牛代理商 XI 凸包周长3. [codevs 1
2015-04-05 10:45:32
963
原创 总结-图论
图论1. 与动态规划结合1. BZOJ-1003-物流运输trans-ZJOI2006-SPFA+DP2. BZOJ-1880-Elaxia的路线-SDOI2009-SPFA+拓扑排序2. 其他算法1. [CODEVS 1173] 最优贸易 民间解法spfa*2, 标解的拓扑排序dp现在想想可以用队列递推实现3. 网络流1. [BZOJ
2015-04-04 21:43:15
527
原创 总结-分治
分治分治法是一种效率很高的算法, 往往带有一个log级的复杂度.1. CDQ分治CDQ分治可以应用到带有修改操作的题目中, 对操作进行分治, 通过考虑前一半操作对后一半操作的影响达到分治的目的.应用的条件比较苛刻BZOJ-1492-货币兑换cash-NOI2007-CDQ分治 优化dpBZOJ-2716-天使玩偶angel-CDQ分治 能这样做还得益
2015-04-04 21:11:15
770
原创 总结-数学
数学比较害怕数学题, 因为数学题一般代码比较短, 一旦想到正解往往就能AC, 但是我数学水平很洼, 知道的东西也比较少. 感觉写写暴力拿部分分比较现实. 毕竟不是每个人都能找到正解.1. 组合数一般用阶乘计算, 需要求逆元. 可以用lucas定理优化时间复杂度.组合类的问题就要考虑组合数1. BestCoder-Round#33 第二题是组合数的题目2. BZOJ-10
2015-04-04 18:12:29
549
原创 总结-数据结构
数据结构1. 树状数组写起来很方便, 用的比较多, 比线段树更实用吧. 虽然原理到现在不太清楚...往往没有裸树状数组的题目, 往往和其他算法相结合.单次修改或查询: O(logn)1. BZOJ-2716-天使玩偶angel-CDQ分治 cdq分治2. BZOJ-1878-HH的项链-SDOI2009 离线处理, 求种数3. BZOJ-3289-Mato的文件
2015-04-04 17:19:02
561
原创 CODEVS-1758-维护数列-NOI2005-splay
描述要求支持区间插入、区间修改、区间翻转、区间删除、区间求和 和求和最大的子列.分析从最开始学完splay做了翻转区间后就想做这个题目, 结果WA了N次后失去调试的信心, 40分收场(这题暴力30分)快省选了想拿出来再做一下, 因为splay的区间操作这个题算是最全的了, 不做一下的话总担心模版是错的.然后做了好长时间...终于不耐烦了拿HZWER的改了改, 直到改到所
2015-04-04 16:52:53
1178
原创 BZOJ-3289-Mato的文件管理-莫队+树状数组
描述给定一段 n(n≤50000) 个数的序列, m(m≤50000) 次询问 [L, R] 区间内相邻元素两两交换使得序列不降的最少次数.分析首先转化为一个逆序对的问题, 最少交换的次数就是逆序对的个数. 后面的证明说的不严谨甚至可能是错的, 不过可以作为启发和参考吧 : 对于序列中的一个元素x, 其后面比它小的元素有c个, 讨论它后面第一个元素y的值, 如果y比x小
2015-04-04 10:35:03
1102
原创 BZOJ-2588-Count-on-a-tree-SPOJ10628-LCA+主席树
描述给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。分析想用树链剖分但是发现不知道怎么套主席树.正解是LCA, 只要维护根节点到每个结点u的权值线段树. 因为主席树求第k大支持减法, 所以最终答案就
2015-04-03 23:28:17
851
原创 BZOJ-1878-HH的项链-SDOI2009
描述有n个位置(n ≤ 50000), 每个位置有一个颜色(颜色数 ≤ 200000).询问[L, R]区间的颜色种数.分析两种解法都做了一下1. 离线树状数组统计HZWER:将所有询问按照左端点进行排序, 将所有颜色的第一个点x, 将a[x]++, 然后从左往右扫, 扫到一个点x, 将a[next[x]]++, 碰到一个询问l,r输出sum[r]-su
2015-04-02 23:15:11
1072
原创 BZOJ-1951-古代猪文-SDOI2010-费马小定理+欧拉函数+lucas定理+中国剩余定理
描述=>G∑(ni),i|nmodP=>G^{\sum {{n\choose i}\text{,i|n}}} modP分析k=∑Cin,i|n(modP)k=\sum {C_n^i , i|n}\pmod PGϕ(P)≡1(modP),ϕ(p)=p−1G^{\phi(P)}\equiv1\pmod P,\quad \phi(p)=p-1 P′=P−1P'=P-1=>GP′≡1(modP)=>G
2015-04-01 23:24:25
902
原创 BZOJ-1875-HH去散步-SDOI2009-矩阵乘法
描述无向图边长均为1, 求从给定地点A走到给定地点B共有多少条长度为 t 的路径(不能连续走重复的边). 模45989.分析f[i][k] : 当走到边 i 的终点的时候路径长度为 j 的方案数量f[i][k] : 可以由 f[j][k-1] 转移来的条件是边 j 的终点是i的起点那么就可以构造矩阵来解了...不用矩阵是不是也能解？代码{CS
2015-04-01 17:47:40
1075
原创 BZOJ-2326-数学作业-HNOI2011-矩阵乘法
描述分析如果用 f[i] 表示 i 时 Concatenate(1 .. i) Mod M 的值, 如果 i 是个 k 位数, 则 f[i+1] = f[i] * (10^k) + i+1, (i != 10^k-1)所以可以建立一个按 i 的位数分段的动态规划解法 -> f[n]n ≤ 10^18, 所以要用矩阵乘法优化然后就是矩阵的选取了, 我首先考虑的 2×2
2015-04-01 17:05:36
831
原创 CODEVS-2018-反病毒软件-线段树
描述两种操作:1. (1, x, y) 表示 x 点权值增加 y2. (2, x, y) 表示求 [x, y] 区间的最大值与次大值的差.分析可以采用线段树对于操作1, 就是单点修改操作2, 先找到区间最大值, 然后把这个点清零, 再求一遍区间最大值. 相减输出. 最后单点修改改回原状态.有许多细节需要注意.代码{CSDN:CODE:6319
2015-03-30 23:15:00
667
原创 算法复习计划
写在前面随着四月的到来, 离省选越来越近了.从NOIP到现在, 学到了很多很多东西, 有的学的比较深入, 有的只是略知一二从明天开始, 进行针对省选的算法复习计划. 省选前完成.重点是对算法的理解和应用, 还会注重模板习惯的养成计划内容1. 数据结构一直觉得我数据结构学的还可以, 不过列出来发现会的也没多少.少就少吧, 省选够用就行...线段
2015-03-29 21:39:54
623
1
原创 COGS-930-找第k小的数-HNOI2012-主席树
描述静态区间第k小值分析改了一个主席树的模板, 改成了数组版.感觉数组的要简洁好多.主席树的讲解：http://hi.baidu.com/lov_zyf/item/87b578342e73fc83f5e4ad3d感觉写的特别好.代码#include #include using namespace std;const int
2015-03-28 17:19:05
697
原创 BZOJ-2716-天使玩偶angel-CDQ分治
描述先给出n个点, 然后有m个操作, (1, x, y) 表示查询离(x, y)最近点的曼哈顿距离, (2, x, y) 表示插入点 (x, y).分析不会做... 又照着别人的代码打了一遍... CDQ分治总想不到思路比较关键的几个地方是 : 1. 坐标的范围是小于1000000的所以可以用树状数组维护. 2. 距离点(x, y)最近的点和x的方位有四种, 左下左上右
2015-03-28 14:45:37
6490
原创 BZOJ-2001-city城市建设-HNOI2010-CDQ分治
描述给出有n个点, m条边的无向图, 每次修改一条边的权值, 求修改后的最小生成树的大小. 修改次数 ≤ 50000.分析还是CDQ分治, 但是有点特殊. 目前的CDQ分治还是停留在看题解看别人代码才理解的层面.有一些边一定在部分修改后的最小生成树中, 这是优化的中心思想吧.然后一个减少边的操作, 一个减少点的操作. 看课件吧.减少点的方法是缩点, 用并查集.一开始想用
2015-03-28 09:57:10
2555
原创 BZOJ-1492-货币兑换cash-NOI2007-CDQ分治
描述分析CDQ分治的例题, 具体怎么分析看当时的课件.DP优化, 维护凸线, 斜率递增.说白了就是一个分治memcpy 不比 for 循环快函数参数加引用比不加引用还慢了自己推了一遍分析过程, 放代码后面了代码#include #include #include using namespace std;const int maxn = 1000
2015-03-27 13:23:24
1208
原创 BZOJ-3110-K大数查询-ZJOI2013-整体二分
描述有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。分析今天终于看懂了一个整体二分的题目. 发现这真是一种很BT的做法.二分答案区间(L, R), 判断中间值M = L+(R-L)/2. 每次清空线段树(直接在根节点
2015-03-24 19:43:29
857
原创 BZOJ-2705-Longge的游戏-SDOI2012-欧拉函数
描述求Σgcd(i, n), 0分析直接求是不行的, 可以分析满足gcd(i, n) = j 的 i 有多少个, 再用 j 乘上这个个数.如果gcd(i, n) = j, 那么gcd(i/j, n/j) = 1, 又由于i≤n, 所以gcd(i/j, n/j) = 1的个数就是不超过n/j并与n/j互质的数的个数, 即φ(n/j).所以Σgcd(i, n) = j *
2015-03-23 21:30:32
807
原创 BZOJ-1880-Elaxia的路线-SDOI2009-SPFA+拓扑排序
描述就是求两对点之间 (s1,t1 和 s2,t2) 最短路的最长重合距离分析首先要有可以快速判断一条边是否在最短路上的方法, 可以用SPFA分别跑出以s1, t1, s2, t2四个点为起点的单源最短路, 判断时例如如果 d_s1[u] + d_t1[e.to] + e.dist == d_s1[t1], 那么边就在s1, t1的最短路上.确定一些在最短路上的
2015-03-23 16:44:23
771
原创 BZOJ-1406-密码箱-AHOI2007-数学
描述在一次偶然的情况下，小可可得到了一个密码箱，听说里面藏着一份古代流传下来的藏宝图，只要能破解密码就能打开箱子，而箱子背面刻着的古代图标，就是对密码的提示。经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数与密码的关系。假设这个数是n，密码为x，那么可以得到如下表述： 密码x大于等于0，且小于n，而x的平方除以n，得到的余数为1。 小可可知道满足上述条件的x可能不止一个，所以一定要
2015-03-22 20:48:11
839
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人