6 Lerence1201

尚未进行身份认证

暂无相关简介

等级
TA的排名 10w+

HDU 4778 2013 ACM/ICPC 杭州赛区现场赛 I. Gems Fight!

这题想了非常之久,AC之后必须写结题报告啊!!!!!!!其实最终还是不能算自己想出来的,还是靠问了网上写解题报告的大牛,才算明白了。确实觉得自己思维有缺陷,只会往一个方向去想,没想出来不知道稍微变化一下。这题显然是状态压缩DP,因为包21个,所以可以用一个二进制表示包有没有被取,其中 1 表示还没被取,dp[i] 表示 初始可取包状态为 i 的时候 先手利用剩下的包还能取到的最大值。那么我们要

2013-11-18 21:48:21

HDU 4790 2013 ACM/ICPC 成都赛区现场赛 J. Just Random

hdu上模拟现场赛,做这题的时候很快出了想法,但是就是写错,一直wa, 不过再调试过程中应该算把这题理解地非常透彻了,感觉如果标解是和我思路一样的话,这题的难点就是细节处理,详细的分类讨论。其实后来想明白了以后分类也很清晰自然了,感觉现场老是紧张有点想不清楚,但是还是硬着头皮写,ym那些现场怒A这题的大神。下面说下我的思路: 对于题目给的区间,[a, b], [c, d],区间的端点模p的值不

2013-11-16 20:58:31

Codeforces Round #209 (Div. 2) D. Pair of Numbers

这题的技巧貌似非常经典,但是但是比赛的时候不会,所以没做出来,后来前天下午做了一下福州大学的有奖月赛,其中卡在一题上2.5小时,终于想出来了这个技巧,(完全自己YY),后来和同学交流发现这种技巧很经典,很常用,然后有点小开心,(哎高中没搞过OI,就是这么蛋疼,这个技巧都得自己YY。。。有个人点你一下也许会少花点时间,不过自己想出来的总是会更有成就感,理解也更透彻啦。。。)顺便联想到这题可以用这个技

2013-11-12 17:28:24

树形DP小结

最近做的题里面出现了好几道树形DP比较,经典,有个类型的题目我写错了好多遍,最后终于查出来了,顺便就写个小结纪念一下。大概树上的DP主要围绕树的直径,树上节点到其他点的最远距离这样两点展开,树的直径的就是两遍DFS,(或者BFS),然后后一个类型,需要两边DFS来把想要的信息转移,得到最后的结果,(这就是数这种数据结构的好处),转移过程自己总结一下,细心一点即可,我觉得我写错的那个类型的题目完

2013-11-07 18:57:11

HDU 4055 Number String

区域赛的题,虽然水,但是还是见思维,有个细节败了,写篇结题报告,哎不wa不幸福斯基。。。题目就是给一个排列的增减性描述的字符串,让你求满足这个字符串模式的排列的个数。一开始我是这么想的:dp过程中需要描述增减性,又要保证整个数列是一个1--n的排列,可以这样:对于任意一个从1--n中选出的k的一个排列,可以通过比大小标号,转化成1--k的一个排列,比如:1 6 3 4 9 可以变成 1 4

2013-11-04 21:21:24

SGU 139 Help Needed!

最近在刷SGU,感觉虽然已经很久没更新题库了,但是题目还是很不错的能激发思考,学到东西,不知道多久才能把第一版刷完啊。这题是个小时候就玩过的游戏,拼图,相信大部分人都玩过,小时候玩这个游戏的时候就发现小霸王机子上给的拼图总是能拼回去,但是如果把一幅能拼回去的拼图的两个相邻的方块(不是空格)换个位置,就变成了一个不可能复原的局面,当时就坚信这个结论是对的,然后在这题上实验了一下,AC了,很是开心

2013-10-31 19:52:03

Codeforces Round #207 (Div. 2) C. Knight Tournament

比赛的时候线段树写挫了,STL又不会,不敢用,加上B题看错,想不出来,C调了一下比赛就结束了,我就爆零了!D,E都没来得及看!实在是弱到不行了!写篇报告来纪念一下,主要是回顾一下线段树。线段树的区间修改查询还是很经典的,对于这题,我们可以用线段树做,倒着想,就相当于一个区间修改问题,每次把在区间里的数改成固定值,对于胜利者要特殊处理,不修改,所以这里有个小技巧,就是把这个区间分成两个区间,

2013-10-21 16:33:26

HDU 4679 Terrorist’s destroy

可以树DP(可能不是很容易写),也可以利用树的直径的性质,这里用的是第二种方法,等会再去写第一种。做这道题以前也遇到过类似的,一直是用树DP做,感觉不是很好写,容易写错,这题这题和同学讨论之后有了新发现,树直径的性质,百度之后发现也是对的,所以比较推荐这种解法,题意是给定一颗二叉树,你可以断其中一条边,断边需要消耗一定能量值,之后树变成两棵二叉树,对于每个树求他们的直径,取两个中的较大值乘以你

2013-10-21 15:29:40

Codeforces Round #206 (Div. 2) E. Vasya and Beautiful Arrays

比赛时貌似出了挺多的,我根本不会,最怕这种需要智商的题目了,得好好分析才能做,看了一个AC代码觉得很神学习一下。显然我们要从所有已知的最小值开始测试,但是每次检查最坏是n的时间,显然要超时,怎么加速?有一行关键代码是这样的,x = c[i] / (c[i] / x + 1); 设X是当前测试其是否可行的值,如果c[i] % x > k 则x将不可行,但是下一个有可能的可行的数是什么呢?x-

2013-10-14 21:56:23

HDU 4705 Y 多校训练第十场1010

题意就是在一棵树上找三个点,使得没有一条简单路径包含这三个点。我们换个角度来想,所有方案很好求,n个里选3个的组合数, 然后我们减去在一条简单路径上的三点对的个数。于是问题转化成求这样的三点对,我是这么想的,可以枚举2个点, 把不符合要求的第三个点找到,然后因为树上的两点有唯一的简单路径相连, 于是我们就可以知道有多少个点是不能作为第三个点的点了。个数恰好等于两端这两个点之间的距离减1。(每条

2013-10-12 14:30:39

Codeforces Round #202 (Div. 1) D. Turtles

深受数学竞赛影响,一开始在想折线计数方法,想用容斥原理来搞定有不能取的点的情况,事实说明我是个傻吊。。。3000*3000,有可能全是不能取的点,这么多点用个毛线容斥。。。刷题少了!!!!肯定DP啊,而且方程是十分简单,但是题目中有个限制是两条路径不能相交,这就需要大神的指引了!题解给出的是rng_58给的高贵冷艳的Lindström–Gessel–Viennot 引理,见链接:http://en

2013-10-10 19:43:05

Eratosthenes筛法和欧拉筛法对比

Eratosthenes筛法名字虽然高贵冷艳,但是并不难理解,原理就不多说了,但是它做了许多无用功,一个数会被筛到好几次,最后的时间复杂度是O(nloglogn),不要以为这个复杂度已经很好了,因为有直接O(n)的欧拉筛法存在,下面简单叙述一下其原理,最后由程序的运行结果来说明两者的差距。欧拉筛法的思想就是不做无用功,原本Eratosthenes筛法的第一重循环是用来找素数,然后把素数的倍数标

2013-10-08 10:56:02

Codeforces Round #204 (Div. 1) E. Jeff and Permutation

需要分析: 关键在于对要抓住极值。。。这道题需要我们抓住最大值。。。。显然我们把所有数按绝对值保存下来都没关系。。(因为可以任意添加负号)。然后我们考虑这个数列中的最大值,最大值有什么好处?他的符号改变不会影响到其他数,例如绝对值最大为10,在他左边有数字,比如数字是5,那么如果10取10,当5改变符号时,-5说明一个数列中的绝对值最大的数符号确定以后不会影响其他数无论符号怎么变化,和

2013-10-07 17:22:14

Topcoder SRM593 MayTheBestPetWin

Problem Statement  The pony Rainbow Dash wants to choose her pet. There are N animals who want to be her pet. Rainbow Dash numbered them 0 through N-1.To help her make the decision, Rain

2013-10-07 15:02:22

哈密尔顿回路

转载自:http://www.cnblogs.com/zhj5chengfeng/p/3233992.html哈密尔顿回路总结 一、引子 1959 年 William Rowan Hamilton 发明了一个小玩具,这个玩具是一个木刻的正十二面体,每面系正五角形,三面交于一角,共 20 个角,没每个角上标有世界上一个重要城市。他提出一个问题:要求沿着正十

2013-10-02 13:49:11

HDUOJ 4767 Bell 长春网络赛1009

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4767Bell 数背景知识:http://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%95%B0当时比赛临时google的,发现有一个递推式可以用:B[n+p] = B[n] +B[n+1] (mod p),然后又因为一幕中给的大数可以分解为:31*3

2013-09-28 22:51:45

HDUOJ 4751 Divide Groups 2013南京网络赛1004

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4751不得不吐槽一下坑爹的出题人,题目不知道改了多少个。。。不过也就早过一题,晚过一题的问题(因为只A了一题),弱到不能再弱。吃翔去。。。题目意思就是把一幅有向图的点分成两个集合,使得每个集合内的点构成完全图。可以转化成二分图,然后染色解决。我们用邻接矩阵保存边,(有正反),然后重新定义连通

2013-09-21 20:25:09

UVaOJ 11136 Hoax or what

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2077题目要求不要用STL。所以需要自己实现priority_queue, STL的是用堆实现的,仿造之。。。第一次实现,刚学的类。。比较挫,不知道会不会过系统测试,现在

2013-09-20 21:38:52

USTCOJ 1215 未知星球

题目链接:http://acm.ustc.edu.cn/ustcoj/problem.php?id=1215个人觉得是一道好题,大意是给一串数字,循环的(首位实际上是相接的),求最长的一段使得这段里最大的值减最小值不超过k。下面给出我想的一个nlogn的算法,主要是用ST求RMQ问题,加上二分猜答案思想,我们的序列长度最大值已知,且一旦一个较小的k不可能是解,则更大的更不可能(因为判断一个k是

2013-09-03 21:27:04

UVaOJ 11375 Matches

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2370这题是递推,一开始没考虑会超精度WA了,后来打印了一下才知道得用高精度,于是手写高精度加法,减法。第一次重载运算符,第一次用10^8进制,结果都很顺利地实现了,实在欣慰。递推方程比较简

2013-09-01 20:39:19

查看更多

勋章 我的勋章
    暂无奖章