- 博客(34)
- 收藏
- 关注
RSS订阅
原创 【HEOI 2015】兔子与樱花
有一棵 n 个节点组成的有根树，根节点是编号为 0 的节点，每个节点有一个权值，这棵树必须保证每个节点上的权值与其子节点的个数之和均不超过 m。你可以选择将一个节点删除，一个节点删除后其子节点全部变为其父节点的子节点，且该节点的权值也累加进其父节点中，求最多能删除多少个节点。n≤2000000。
2018-08-08 22:59:20
419
原创 【POJ 3666】Making the Grade
给定一个长度为 n 的序列 A，要求构造一个单调不上升或单调不下降的序列 B 使得 ∑|ai-bi| 的值最小，输出这个最小值。1≤n≤2000。
2018-08-06 21:13:38
213
原创 【POJ 2279】Mr. Young's Picture Permutations
有 1～N 共 N 个数字，让你排成 k 排，要求第 i 排有 Ai 个数字，同时满足每排上的数字单调递增，每列上的数字单调递增，求合法的方案数。N≤30,k≤5。
2018-08-06 18:03:38
250
原创 【CH 3301】同余方程
题目描述求关于 xxx 的同余方程 ax≡1(modb)ax≡1(modb)ax\equiv1(\mod b) 的最小正整数解.算法分析将同余方程转化为二元一次方程的形式，即由 ax≡1(modb)ax≡1(modb)ax\equiv1(\mod b) 转化为 ax−by=1ax−by=1ax-by=1。使用扩展欧几里得算法求解：当 b=0b=0b=0 时要满足 ax−by...
2018-08-03 22:02:57
221
原创 【POJ 1845】Sumdiv（逆元解法）
题目描述求 ABABA^B 的所有约数之和 mod9901mod9901\mod 9901。1≤A,B≤5×1071≤A,B≤5×1071≤A,B≤5\times10^7。算法分析根据之前博客的题解，ABABA^B 的约数之和为 (p00+p10+...+pc0B0)×(p01+p11+...+pc1B1)×...×(p0n+p1n+...+pcnBn)(p00+p01+...+p...
2018-08-03 21:25:10
264
原创 【POJ 2482】Stars in Your Window
平面上有 n 个点，每个点 (x,y) 有一个权值 c，计算用长为 w，宽为 h 的矩形所能覆盖点的最大权值和。
2018-08-02 14:13:59
209
转载 OIer
来源：《膜你抄》屏幕在深夜微微发亮 思想在那虚树路径上彷徨 平面的向量交错生长 织成，忧伤的网剪枝剪去我们的疯狂 SPFA告诉我前途在何方 01背包装下了忧伤 笑颜，洋溢脸庞键盘微凉，鼠标微凉 指尖流淌，代码千行 凸包周长，直径多长 一进考场，全都忘光你在OJ上提交了千百遍 却依然不能卡进那时限 双手敲尽代码也敲尽岁月 只有我一人写的题解 凋零在OJ里面...
2018-08-02 13:11:52
792
原创 【COGS 2965】简单题233
题目描述有一个 n×m(1≤n,m≤300000)n×m(1≤n,m≤300000)n\times m(1≤n,m≤300000) 的网格，求从左上角第一个格子走到右下角最后一个格子的方案数（由于方案数过大，请余除23333333），只能选择向下走或向右走。算法分析由于只能向左走或向右走，总步数固定为 n+m−2n+m−2n+m-2，向下走的步数固定为 m−1m−1m-1，则答案就...
2018-07-30 21:26:21
219
原创 【POJ 3090】Visible Lattice Points
题目描述一个 n×n(1≤n≤1000)n×n(1≤n≤1000)n\times n(1≤n≤1000) 的平面直角坐标系，输出从原点向第一象限看去，能够看到多少个钉子。算法分析对于一个点 (x,y)(x,y)(x,y)，它能够被看到仅当 gcd(x,y)=1gcd(x,y)=1gcd(x,y)=1。将平面直角坐标系分成左上和右下两部分，由于两部分能看到的钉子个数相同，我们选择...
2018-07-29 11:21:31
204
原创 【CH 3201】Hankson的趣味题
题目描述已知正整数 a0,a1,b0,b1a0,a1,b0,b1a_0,a_1,b_0,b_1，设某未知正整数 xxx 满足：1、xxx 和 a0a0a_0 的最大公约数是 a1a1a_12、xxx 和 b0b0b_0 的最小公倍数是 b1b1b_1请求解满足条件的 xxx 的个数。算法分析xxx 一定是 b1b1b_1 的约数，则 b1b1b_1 分解质因数的结果一定...
2018-07-29 10:12:05
337
原创 【POJ 2182】Lost Cows
题目描述有 n(n≤8000)n(n≤8000)n(n≤8000) 头奶牛，它们的身高为 1～n1～n1～n 的一种全排列，已知第 2～n2～n2～n 头牛比它矮的牛的数量为给定的数组 AAA，求每头牛的身高。算法分析比第 nnn 头牛矮的牛的数量为 aaa，那么它的身高为 a+1a+1a+1，由此倒序枚举。用树状数组维护每种身高的使用情况，在树状数组上二分即可求出每头牛的具体...
2018-07-28 17:42:06
230
原创 【POJ 1733】Parity game
题目描述有一个长度为 N(N≤109)N(N≤109)N(N≤10^9) 的 010101 序列，共给你 M(M≤10000)M(M≤10000)M(M≤10000) 条信息，每条信息给出 [l,r][l,r][l,r] 中 111 的个数的奇偶性，但只有前 kkk 条信息是正确的，请输出 kkk 的值。算法分析将信息拆成前缀和的形式，即 sumr−suml−1sumr−suml−...
2018-07-28 14:35:43
236
原创 【BZOJ 1257】余数之和
题目描述给出正整数 nnn 和 kkk，计算 (kmod1)+(kmod2)+(kmod3)+…+(kmodn)(kmod1)+(kmod2)+(kmod3)+…+(kmodn)(k\mod1)+(k\mod2)+(k\mod3)+…+(k\mod n) 的值。1≤n,k≤1091≤n,k≤1091≤n,k≤10^9。算法分析将取模运算变换形式：kmodi=k−⌊ki⌋×ikmod...
2018-07-27 19:19:52
254
原创 【BZOJ 1053】反素数
题目描述对于任何正整数 xxx，其约数的个数记作 g(x)g(x)g(x)。例如 g(1)=1g(1)=1g(1)=1，g(6)=4g(6)=4g(6)=4。如果某个正整数 xxx 满足：对于任意的 0<i<x0<i<x0g(x)>g(i)g(x)>g(i)g(x)>g(i)，则称 xxx 为反质数。例如，整数 1,2,4,61,2,4,61,2,4,6...
2018-07-27 18:28:26
248
原创 【CH 3101】阶乘分解
题目描述给定整数 N(1≤N≤106)N(1≤N≤106)N(1≤N≤10^6)，试把阶乘 N!N!N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pipip_i 和 cicic_i 即可。算法分析一个一个分解显然不可行，我们考虑对于每个质数，计算它在 1×2×...×N1×2×...×N1\times2\times...\times N 中每个数分解质因数后对应的指数和...
2018-07-27 11:11:58
1054
原创 【POJ 2689】Prime Distance
题目描述给定两个整数 L,U(1≤L≤U≤231,U−L≤106)L,U(1≤L≤U≤231,U−L≤106)L,U(1≤L≤U≤2^{31},U-L≤10^6)，求闭区间 [L,U][L,U][L,U] 中相邻两个质数的差最大是多少，最小是多少，输出对应的质数。算法分析首先使用线性筛筛出所有在 [2,⌊U‾‾√⌋][2,⌊U⌋][2,\lfloor\sqrt U\rfloor] ...
2018-07-27 10:14:05
166
原创 【POJ 2018】Best Cow Fences
题目描述求一个长度为 NNN 的序列中长度不超过 FFF 的子段，使得这个子段的平均值最大，输出这个平均值的 100010001000 倍。算法分析最大化平均值，二分答案，将序列中的每个元素减去当前判断的平均值，则当前判断的结果就是是否存在一个新序列中的子段，使得这个子段的和不小于 000。将子段拆成前缀和的形式，枚举右端点，由于可选范围递增，再维护一个变量用来储存当前可选范围...
2018-07-26 16:42:34
353
1
原创 【POJ 3889】Fractal Streets
题目描述请求出一个等级为 nnn 的分形图中，编号为 SSS 的格子到编号为 DDD 的格子的直线距离。城市的规划在城市建设中是个大问题。不幸的是，很多城市在开始建设的时候并没有很 好的规划，城市规模扩大之后规划不合理的问题就开始显现。而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示: 当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域...
2018-07-26 15:40:39
625
1
原创 【POJ 1845】Sumdiv
题目描述求 ABABA^B 的所有约数之和 mod9901mod9901\mod 9901。1≤A,B≤5×1071≤A,B≤5×1071≤A,B≤5\times10^7。算法分析将 AAA 分解质因数得 A=pc00pc11...PcnnA=p0c0p1c1...PncnA=p_0^{c_0}p_1^{c_1}...P_n^{c_n}，则 AB=pc0B0pc1B1...PcnB...
2018-07-26 12:14:41
139
原创 【POJ 3263】Tallest Cow
题目描述有 NNN 头牛站成一行。两头牛能够相互看见，当且仅当它们中间的牛身高都比它们矮。现在，我们只知道其中最高的牛是第 III 头，它的身高是 HHH，不知道剩余 N−1N−1N-1 头牛的身高，但是，我们还知道 RRR 对关系，每对关系都指明了某两头牛 AiAiA_i 和 BiBiB_i 可以相互看见。求每头牛的身高最大可能是多少。1≤N,R≤1041≤N,R≤1041≤N,R≤10^4...
2018-07-26 10:26:08
285
原创 【POJ 1985】Strange Tower of Hanoi
题目描述解出 nnn 个盘子 444 座塔的 HanoiHanoiHanoi（汉诺塔）问题最少需要多少步？算法分析回顾一下 333 座塔的汉诺塔问题：f[n]=2f[n−1]+1f[n]=2f[n−1]+1f[n]=2f[n-1]+1。先将 n−1n−1n-1 个盘子从 AAA 柱移动到 BBB 柱，再将第 nnn 个盘子从 AAA 柱移到 CCC 柱，最后再将 n−1n−1n...
2018-07-26 10:01:35
144
原创 【CH 0102】64 位整数乘法
题目描述求 aaa 乘 bbb 对 ppp 取模的值，其中 1≤a,b,p≤10181≤a,b,p≤10181≤a,b,p≤10^{18}。算法分析【算法一】快速乘 仿照矩阵快速幂，b=c0×20+c1×21+...+ck×2kb=c0×20+c1×21+...+ck×2kb=c_0\times2^0+c_1\times2^1+...+c_k\times2^k，将 a×ba×ba\t...
2018-07-26 10:00:10
342
原创 所以
所以，我选择 CSDN 博客。Hexo 独立博客界面太“软”了，而且还要编译什么的不太方便。 cnblogs 上写吧，虽然能屏蔽广告，但是编辑器什么的显然不够方便，会分散自己的注意力。 至于 简书 和 知乎，由于用户群体的原因不在考虑的范围之内。UOJ 太多大佬了，不敢在上面瞎写……CSDN 上广告不少，用 Adblock Plus 屏蔽掉就好。以后就在这里安家了，其它博客不想...
2018-07-21 18:12:28
171
原创 NOI 2018 网络同步赛 总结
本来写了一大长篇，但是我不太想放出来……应该得到的分数：55+8+28+60+15+20=186分 实际得分：45+8+20+50+0+0=123分 加上笔试才过 Cu 分数线……第一场发挥得勉强还行，但时间安排并不好，第二场就彻底崩了，以后还是要打一些模拟赛，练练时间安排和比赛策略。其实题目都有深入思考，但是感觉学的还是不够用啊，后面应该要把基础打打多学东西。比较遗憾的是今年...
2018-07-21 13:02:47
595
原创 Codeforces 进阶计划：从 Specialist 到 Expert
训练计划：做 Codeforces Round (Div. 3)、Codeforces Round (Div. 3) 和 Educational Codeforces Round 通过人数少于 1000 人的题目。 目前做了 3 题。Codeforces Round #490 (Div. 3)D. Equalize the Remainders 给定两个整数 n,mn,...
2018-06-26 12:13:18
620
1
原创 信息学竞赛开发环境快速入门：Vim、G++和GDB
原文链接：信息学竞赛开发环境快速入门：Vim、G++和GDB前置知识操作系统命令行（终端）的使用方法和基本命令第一部分：VimVim是我们使用的命令行代码编辑器。 首先，在命令行下输入以下命令启动Vim：vim code.cpp输入i进入编辑模式。 编辑模式下你可以输入字符代码。 按下esc进入命令模式。 命令模式下有几种操作： h：光标左移 j...
2018-04-29 17:17:30
1265
原创 【Tyvj 1432】楼兰图腾
前言看群里有人又提到这个问题，终于决定把自己以前写的这篇文章放上来……分析两遍树状数组求逆序对，针对每个点作为图腾尖端的情况，统计左右比它小（大）的个数，利用乘法原理求解，记得开64位整数。重要《算法竞赛进阶指南》和入门OJ中的题目描述的数据范围有误：原描述为N≤105N≤10^5，实际数据范围为N≤2×105N≤2\times 10^5。测试数据有误，估计是出题人标程中忘记类型转换，下面给出的代码
2018-04-26 09:29:57
571
1
原创 HAOI2018 之后
HAOI2018已经结束，没能进队…… 题目质量还是不错的，没有出太大的问题，成功地把我这种暴力选手区分下去了…… 有太多的遗憾还有太多的话想说，只能等明年了……这个博客要开始维护了，主要是平时练习题目的总结和题解，大都是OI相关的东西，以后复习会方便一些，希望能给也在奋斗的OIer一些参考和帮助吧……欢迎大家和我相互交流学习，我的联系方式： QQ：壹陆陆玖壹叁伍伍肆柒 Email...
2018-04-23 11:28:16
548
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人