- 博客(438)
- 收藏
- 关注
RSS订阅
原创 博弈类题目小结（HDU,POJ,ZOJ）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove首先当然要献上一些非常好的学习资料：基础博弈的小结：http://blog.csdn.net/acm_cxlove/article/details/7854530经典翻硬币游戏小结：http://blog.csdn.net/ac
2012-08-11 13:54:46
43752
34
原创 Coder-Strike 2014
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxloveQualification Round略Round 1D：想像一下DFS序，但是输出是反向的E：直接按@把串分成一段段的，然后以@为中心往两边找。Round 2C：贪心，肯定先把常规题目先做完，因
2014-04-25 19:24:32
4872
原创 North America - East Central NA 2012
North America - East Central NA 2012
2014-03-25 19:56:52
4033
原创 North America - East Central NA 2013
North America - East Central NA 2013 简易题解
2014-03-18 22:04:58
4666
原创 小记
2013年11月17日，长沙区域赛结束之后，吃翔爱就成了退役狗了。。。。。 作为比较弱的混了几年，所以也不需要什么退役贴了。。。 回想最后半年多，只能说自作孽不可活，不好好训练，只能混成这样了。。。这时候来遗憾也没什么用了。。。 退役之后做点水题啊，在CF,TC上水一水啊。。。。然后混混各个地方的比赛之类的。。。 其实这贴主要
2014-02-27 13:27:19
7762
6
原创 URAL 1996 Cipher Message 3 (FFT + KMP)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意 ：给出两个串A ， B，每个串是若干个byte，A串的每个byte的最后一个bit是可以修改的。问最少修改多少，使得B串是A的一个子串。2013年NEERC的题。。。。。。。感觉[buaa]sd0061教我做这题。NEERC是
2013-10-30 20:48:41
5435
原创 HDU 4498 Function Curve (分段， simpson)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove最近太逗了。。。感觉成都要打铁了。。。只能给队友端茶送水了。。。。积分都不会了。。。曲线长度不会求。。。。写个代码，一堆SB错误。。。。。纯属吐槽博文 。。。。。。解法 ：首先把n个函数以及y = 100求出交点。。。。把交点排序。
2013-10-10 00:40:08
6410
3
原创 UVALive 6135 Environment Protection (Simpson)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove非常裸的题。。。二分之后，求曲线交部分的面积。我只是保存自适应Simpson模板的。。#include #include #include using namespace std;const double eps = 1e-10
2013-10-09 14:46:29
3530
原创 SPOJ PGCD （mobius反演 + 分块）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意 ：求满足gcd(i , j)是素数(1 很值得总结的题。。。首先得会一点前提东西 。。。先简单说下Mobius反演，就是偏序集上的容斥原理。 定义F(n) = sigma (G(d)) d | n那么G(n)
2013-09-30 01:18:00
12831
7
原创 HDU 4760 Good Firewall （Trie）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：问两个IP是否在同一组中。。。每一组有若干个IP段。http://acm.hdu.edu.cn/showproblem.php?pid=4760又一次被题意玩坏了，被带成了线段树区间覆盖的节奏。。。因为给出的一IP段，子网掩码
2013-09-28 19:25:36
5155
11
原创 UVAlive 5792 Diccionário Portuñol (Trie)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题目：有两个字符串集合，从第一个集合中取某个串的非空前缀，从第二个集合中取某个串的非空后缀，拼接成一个串，问有多少个不同的新串。https://icpcarchive.ecs.baylor.edu/index.php?option=com_on
2013-09-24 00:09:56
4185
原创 2013长沙网络赛 G Goldbach （FFT）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove太逗了。。。比赛的时候，误以为素数会很多。。。。然后 就想歪 了，开始搞FFT。其实发现主要 是a + b + c的情况不好处理。先将a + b的情况FFT一下，然后 再 + c FFT一次。num[i]表示a + b = i的个数
2013-09-22 23:14:08
7152
5
原创 HDU 4721 Food and Productivity (二分+树状数组)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意 ：给出n * m的格子，每个格子有两个属性food , prod。对于每一个查询A，B，可以选择某个格子将food属性+A，prod+B，然后以这个格子为中心的正方形两个属性和的最小值最大。http://acm.hdu.edu.cn/sh
2013-09-20 19:38:10
4350
8
原创 HDU 4742 Pinball Game 3D （分治）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove毫无分治的灵感。。。一维的答案就是n，二维的就是按x排序然后 对y求LIS。三维的肯定要按X排序，就少掉一维。然后将Z离散化，用BIT维护。。。想法大概都知道，就是不会做分治做法，将区间的点按y排序，将左区间的点加入到BIT中
2013-09-20 16:53:52
5126
1
原创 SPOJ GCDEX (数论)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：求sigma (gcd (i , j)) 1 和POJ 2480类似，如果枚举j，求的话，还是会TLE的。。。考虑sigma(gcd (i , n)) = sigma (d * phi[n / d]) d | n。做法同样是先预
2013-09-19 21:53:20
4537
原创 SPOJ LCMSUM (数论)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove对于 n，求出sigma (LCM (i , n)) n >= i >=1重要的是复习一下推导过程。。。LCM(i , n) = i * n / gcd (i , n)所以我们按分母分类合并，gcd (i , n)显然是n的约数
2013-09-19 10:52:43
4965
1
原创 HDU 4747 Mex （线段树）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题目：给出一个序列，mex{}表示集合中没有出现的最小的自然数。然后 求sigma(mex (i , j)).比赛的时候，被老大秒了。。。太可怕了。。。做法：考虑左端点固定时的所有区间的mex值，这个序列是一个非递减了。。。首先要明白。
2013-09-16 22:52:24
8822
5
原创 HDU 4729 An Easy Problem for Elfness （主席树，树上第K大）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：给出一个带边权的图。对于每一个询问(S , T , K , A , B)，有两种操作，加一条单位边花费为A，将某条边流量扩展一个单位花费为B，在预算为K的情况下求S到T最大流的最大值。http://acm.hdu.edu.cn/showp
2013-09-16 22:38:04
5068
6
原创 SRM 590 DIV1
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove水水更健康，终于回到1800+了。。。DIV2 1000pt显然每一列是独立的，分开考虑。对于某一列，如果按单个字符U ， D从下往上考虑的话，发现连续两个U的话，下面的U可以移动的位置受上面一个影响。不过因此可以想到相邻的U ，
2013-09-08 19:54:14
2377
原创 CF 121D Lucky Segments （two points）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：给出若干个区间，区间可以左右移动，所有区间移动幅度总和最多为K。问最多有多少个lucky number同时在n个区间中。http://codeforces.com/contest/121/problem/D感觉还不错的题，
2013-09-06 21:46:19
1688
原创 HDU 4669 Mutiples on a circle （DP , 统计）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：给出一个环，每个点是一个数字，取一个子串，使得拼接起来的数字是K的倍数。由于K不大，暂且不考虑环的话，那么dp[i][j]表示以i结尾的，模K为j的有多少个子串。那么sigma (dp[i][0])便是不考虑环的答案。考虑
2013-08-29 22:02:20
1642
原创 HDU 4668 Finding string (解析字符串 + KMP)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：给出一个压缩后的串，以及一个模式串，问模式串出现了多少次。http://acm.hdu.edu.cn/showproblem.php?pid=4668这种压缩形式的话，在去年金华邀请赛中出现过，但是那题的范围不大。直接展开作多
2013-08-29 20:28:25
2087
原创 HDU 4693 Huge String
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意 ：给一个置换关系，然后原有字符串转换n次之后，查询第k个字符开始的m个字符。首先DP预处理每一个字符展开0-n次之后可以形成的字符串长度。然后就能按位确定，要查询的字符是由哪一个字符展开的。同理一层一层往下找。搜到底或者找
2013-08-28 16:41:02
1756
原创 CF 39E What Has Dirichlet Got to Do with That? （博弈）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：给出a ^ b，两个人轮流操作，可以 a + 1 也可以 b + 1，谁先使得a ^ b >= n则输。由于题目给的n并不大，1e9的范围，如果不考虑a == 1 or b == 1的情况下a最大为sqrt (n) ,b最大
2013-08-26 13:28:51
2206
原创 CF 338 D GCD Table(CRT)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove给定一个序列，a[1 。。k]，问是否存在(i , j)使得 GCD(i , j + r - 1) = a[r] (k>=r >=1)，其中 i http://codeforces.com/contest/338/problem/D
2013-08-18 22:26:56
2552
1
原创 CF 338E Optimize! （线段树）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove出题人题解没看懂。。。囧。然后看了下tourist代码，很短，也很好理解。。。我们将b排序之后，很显然如果组合的话肯定是贪心。那么对于a的某个子串a'要满足条件的话，那么显然是所有的数和b中最大元素相加不小于h。至少有len
2013-08-18 20:06:18
2017
转载 计算几何
这两天在学习计算几何，随便说说自己的学习过程吧。 基本的叉积、点积和凸包等东西就不多说什么了，网上一搜一大堆，切一些题目基本熟悉了就差不多了。 一些基本的题目可以自己搜索，比如这个blog：http://blog.sina.com.cn/s/blog_49c5866c0100f3om.html 接下来，研究了半平面交，思想方法看07年朱泽园的国家队论文，模板代码参考自我校大牛韬哥
2013-08-18 17:43:30
9506
3
原创 Codeforces Beta Round #32
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove时运不济，继续水CF。。。A：Reconnaissance 枚举B：Borze模拟C：Flea先算出最多可以多少个，然后 统计一下有多少个位置LL n , m , s;int main () {
2013-08-18 11:27:33
1310
2
原创 HDU 4601 Letter Tree (线段树+字典树+树型转线性)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题目：给出一棵树，1为根，边为字母，问从某个结点，向下走m步，路径形成一个字符串，要求字典序最大。http://acm.hdu.edu.cn/showproblem.php?pid=4601做法：直接做根本没法。。。每个结点孩子
2013-08-14 21:34:43
2262
原创 Codeforces Beta Round #23
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlovehttp://codeforces.com/contest/23水了一天，做场CF。。。。发现是如此地弱A：You are given a string暴力枚举，要是闲着蛋疼就写个SA什么的吧。。。或者HASH一下。
2013-08-14 21:06:07
1343
2
原创 CC Sereja and Ballons (主席树)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意：有n个盒子，每个盒子有若干个气球，每次操作可以拿走某个盒子的一个气球，然后 给出一些区间，问每次操作后有多少个区间的盒子全为空。http://www.codechef.com/AUG13/problems/SEABAL做法：用链表
2013-08-14 09:06:28
2592
2
原创 CC Prime Distance On Tree (树的点分治 + FFT)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题目：给出一棵树，问有选出一个二元组（u , v），满足u 到 v的路径长度为素数的概率为多少。所有边长度为1。http://www.codechef.com/AUG13/problems/PRIMEDST自从做了男人八题之后，觉得这种
2013-08-12 21:57:15
3110
8
原创 HDU 4574 Bombs (枚举+搜索)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove基本上想到了解法 ，但是一直在想[a,b]中乘积在[l,r]的组合有多少种怎么预处理。。。。觉得当b - a + 1很大的时候，个数很少，大概可以承受n * m 的DP预处理。。。结果结果就是个爆搜嘛。。。。不过加了些优化 。。。取的数
2013-08-12 21:47:56
2474
3
原创 HDU 4579 Random Walk （解方程）
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题意 ：n个位置，每次可以向前走1-m步或者向后者1-m步，或者不动，概率都可以计算出来。问从1走到n的期望步数。http://acm.hdu.edu.cn/showproblem.php?pid=4579由于m非常小，只有5。所以用d
2013-08-11 16:56:11
3000
1
原创 CF 293 E Close Vertices (树的分治+树状数组)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题目：给出一棵树，问有多少条路径权值和不大于w，长度不大于l。http://codeforces.com/contest/293/problem/E有男人八题很相似，但是多了一个限制。同样 还是点分治，考虑二元组(到根的路径权值和，
2013-08-09 20:35:18
2786
6
原创 随手小记
Firework组队一年多了，看来这次是至今为止最严重的矛盾，我这个退役狗也没啥了，随时做好单挑的准备吧。但是觉得即使做不了队友，要是如果连朋友都没法做，是不是大家应该反思下。这几天确实大家都只是在指出别人的问题，不过我确实觉得老大的行为一再挑战底线。大家认识一两年了，有些矛盾完全可以避免。这些天我基本上保持着沉默以及放任不管。不希望事情进一步激化。已经尽量简化到三个人的交集只有做
2013-08-07 23:25:20
4391
15
原创 HDU 4618 Palindrome Sub-Array (HASH + 枚举)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove题目：给出一个矩阵，选出一个子方阵，使得每一行每一列都是一个回文串http://acm.hdu.edu.cn/showproblem.php?pid=4618做法：预处理之后，O(n ^ 3)枚举，然后 O(1)判断选中的矩形是否是回文
2013-07-28 19:43:58
1761
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人