- 博客(38)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 HDU 4778 2013 ACM/ICPC 杭州赛区现场赛 I. Gems Fight!
这题想了非常之久，AC之后必须写结题报告啊！！！！！！！其实最终还是不能算自己想出来的，还是靠问了网上写解题报告的大牛，才算明白了。确实觉得自己思维有缺陷，只会往一个方向去想，没想出来不知道稍微变化一下。这题显然是状态压缩DP，因为包21个，所以可以用一个二进制表示包有没有被取，其中 1 表示还没被取，dp[i] 表示 初始可取包状态为 i 的时候 先手利用剩下的包还能取到的最大值。那么我们要
2013-11-18 21:48:21
1336
原创 HDU 4790 2013 ACM/ICPC 成都赛区现场赛 J. Just Random
hdu上模拟现场赛，做这题的时候很快出了想法，但是就是写错，一直wa, 不过再调试过程中应该算把这题理解地非常透彻了，感觉如果标解是和我思路一样的话，这题的难点就是细节处理，详细的分类讨论。其实后来想明白了以后分类也很清晰自然了，感觉现场老是紧张有点想不清楚，但是还是硬着头皮写，ym那些现场怒A这题的大神。下面说下我的思路： 对于题目给的区间，[a, b], [c, d]，区间的端点模p的值不
2013-11-16 20:58:31
2594
原创 Codeforces Round #209 (Div. 2) D. Pair of Numbers
这题的技巧貌似非常经典，但是但是比赛的时候不会，所以没做出来，后来前天下午做了一下福州大学的有奖月赛，其中卡在一题上2.5小时，终于想出来了这个技巧，（完全自己YY），后来和同学交流发现这种技巧很经典，很常用，然后有点小开心，（哎高中没搞过OI，就是这么蛋疼，这个技巧都得自己YY。。。有个人点你一下也许会少花点时间，不过自己想出来的总是会更有成就感，理解也更透彻啦。。。）顺便联想到这题可以用这个技
2013-11-12 17:28:24
1010
原创 树形DP小结
最近做的题里面出现了好几道树形DP比较，经典，有个类型的题目我写错了好多遍，最后终于查出来了，顺便就写个小结纪念一下。大概树上的DP主要围绕树的直径，树上节点到其他点的最远距离这样两点展开，树的直径的就是两遍DFS，（或者BFS），然后后一个类型，需要两边DFS来把想要的信息转移，得到最后的结果，（这就是数这种数据结构的好处），转移过程自己总结一下，细心一点即可，我觉得我写错的那个类型的题目完
2013-11-07 18:57:11
922
原创 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
933
原创 SGU 139 Help Needed!
最近在刷SGU，感觉虽然已经很久没更新题库了，但是题目还是很不错的能激发思考，学到东西，不知道多久才能把第一版刷完啊。这题是个小时候就玩过的游戏，拼图，相信大部分人都玩过，小时候玩这个游戏的时候就发现小霸王机子上给的拼图总是能拼回去，但是如果把一幅能拼回去的拼图的两个相邻的方块（不是空格）换个位置，就变成了一个不可能复原的局面，当时就坚信这个结论是对的，然后在这题上实验了一下，AC了，很是开心
2013-10-31 19:52:03
1215
1
原创 Codeforces Round #207 (Div. 2) C. Knight Tournament
比赛的时候线段树写挫了，STL又不会，不敢用，加上B题看错，想不出来，C调了一下比赛就结束了，我就爆零了！D，E都没来得及看！实在是弱到不行了！写篇报告来纪念一下，主要是回顾一下线段树。线段树的区间修改查询还是很经典的，对于这题，我们可以用线段树做，倒着想，就相当于一个区间修改问题，每次把在区间里的数改成固定值，对于胜利者要特殊处理，不修改，所以这里有个小技巧，就是把这个区间分成两个区间，
2013-10-21 16:33:26
1119
原创 HDU 4679 Terrorist’s destroy
可以树DP（可能不是很容易写），也可以利用树的直径的性质，这里用的是第二种方法，等会再去写第一种。做这道题以前也遇到过类似的，一直是用树DP做，感觉不是很好写，容易写错，这题这题和同学讨论之后有了新发现，树直径的性质，百度之后发现也是对的，所以比较推荐这种解法，题意是给定一颗二叉树，你可以断其中一条边，断边需要消耗一定能量值，之后树变成两棵二叉树，对于每个树求他们的直径，取两个中的较大值乘以你
2013-10-21 15:29:40
1025
原创 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
1102
原创 HDU 4705 Y 多校训练第十场1010
题意就是在一棵树上找三个点，使得没有一条简单路径包含这三个点。我们换个角度来想，所有方案很好求，n个里选3个的组合数， 然后我们减去在一条简单路径上的三点对的个数。于是问题转化成求这样的三点对，我是这么想的，可以枚举2个点， 把不符合要求的第三个点找到，然后因为树上的两点有唯一的简单路径相连， 于是我们就可以知道有多少个点是不能作为第三个点的点了。个数恰好等于两端这两个点之间的距离减1。（每条
2013-10-12 14:30:39
829
原创 Codeforces Round #202 (Div. 1) D. Turtles
深受数学竞赛影响，一开始在想折线计数方法，想用容斥原理来搞定有不能取的点的情况，事实说明我是个傻吊。。。3000*3000，有可能全是不能取的点，这么多点用个毛线容斥。。。刷题少了！！！！肯定DP啊，而且方程是十分简单，但是题目中有个限制是两条路径不能相交，这就需要大神的指引了！题解给出的是rng_58给的高贵冷艳的Lindström–Gessel–Viennot 引理，见链接：http://en
2013-10-10 19:43:05
1331
原创 Eratosthenes筛法和欧拉筛法对比
Eratosthenes筛法名字虽然高贵冷艳，但是并不难理解，原理就不多说了，但是它做了许多无用功，一个数会被筛到好几次，最后的时间复杂度是O（nloglogn），不要以为这个复杂度已经很好了，因为有直接O（n）的欧拉筛法存在，下面简单叙述一下其原理，最后由程序的运行结果来说明两者的差距。欧拉筛法的思想就是不做无用功，原本Eratosthenes筛法的第一重循环是用来找素数，然后把素数的倍数标
2013-10-08 10:56:02
7100
2
原创 Codeforces Round #204 (Div. 1) E. Jeff and Permutation
需要分析： 关键在于对要抓住极值。。。这道题需要我们抓住最大值。。。。显然我们把所有数按绝对值保存下来都没关系。。（因为可以任意添加负号）。然后我们考虑这个数列中的最大值，最大值有什么好处？他的符号改变不会影响到其他数，例如绝对值最大为10，在他左边有数字，比如数字是5，那么如果10取10，当5改变符号时，-5说明一个数列中的绝对值最大的数符号确定以后不会影响其他数无论符号怎么变化，和
2013-10-07 17:22:14
1712
2
原创 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
1554
2
转载 哈密尔顿回路
转载自：http://www.cnblogs.com/zhj5chengfeng/p/3233992.html哈密尔顿回路总结 一、引子 1959 年 William Rowan Hamilton 发明了一个小玩具，这个玩具是一个木刻的正十二面体，每面系正五角形，三面交于一角，共 20 个角，没每个角上标有世界上一个重要城市。他提出一个问题：要求沿着正十
2013-10-02 13:49:11
3491
原创 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
2418
原创 HDUOJ 4751 Divide Groups 2013南京网络赛1004
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4751不得不吐槽一下坑爹的出题人，题目不知道改了多少个。。。不过也就早过一题，晚过一题的问题（因为只A了一题），弱到不能再弱。吃翔去。。。题目意思就是把一幅有向图的点分成两个集合，使得每个集合内的点构成完全图。可以转化成二分图，然后染色解决。我们用邻接矩阵保存边，（有正反），然后重新定义连通
2013-09-21 20:25:09
1228
原创 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
933
原创 USTCOJ 1215 未知星球
题目链接：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1215个人觉得是一道好题，大意是给一串数字，循环的（首位实际上是相接的），求最长的一段使得这段里最大的值减最小值不超过k。下面给出我想的一个nlogn的算法，主要是用ST求RMQ问题，加上二分猜答案思想，我们的序列长度最大值已知，且一旦一个较小的k不可能是解，则更大的更不可能（因为判断一个k是
2013-09-03 21:27:04
866
原创 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
872
原创 Codeforces Round #198（Div.2）ABCDE
这本来应该是一场AK的比赛，结果自己没把握住机会，有点遗憾。其实除了D是看了题解之后顿悟的，其他题目都不难，比赛时候写不出来，也只能说自己水平不够，因此写篇博客纪念。题目链接：http://codeforces.ru/contest/340A：一直是水题的一道题，每次要抓紧时间，我现在最快也就4分钟A这题。。。英语实在捉急。。。题目就是求一个最小公倍数。然后区间减法。代码：#i
2013-08-31 18:31:41
1122
1
原创 UVaOJ 11038 How Many O's?
最近深感数学不给力，决定刷题，复习，从细节做起，复习知识技巧，于是做起白书的数学篇习题，UVaOJ的数据真的很强。。。。Orz。很是锻炼思维。这道区间减法想到不难，关键在细节，于是我还是决定写下来。（虽然1A，但是仍有可以总结的地方）题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=
2013-08-30 00:30:10
806
原创 USTCOJ 1266 Sequence Again
题目链接：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1266题意理解起来比较简单给一串数字，在其中找最长的一段连续串使得它是1--x的一个排列，比如5 1 2 3 4，这个串本身就是1--5的一个排列，所以输出5，3 1 2 3 3 4则最长为3 1 2，输出3。至今没有想到比N^2快的算法，所以贴出来给大家探讨一下，如果有好方法，请赐教。
2013-08-21 20:04:19
889
原创 Codechef Bytecode 1-10
这个比赛好像不是很有名气，参加的人不多，前五题感觉比较平，题目有简单的也有中等的，但应该说不难，反正我是AK了。第3，4题还是很好的。链接：http://www.codechef.com/BTCD2013/1：#include#include#include#include#include#include#include#include#include#inclu
2013-08-19 21:00:19
801
原创 USTCOJ 1274 K_Star风波
题目链接：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1274很典型的题目：n个数分成m段使所有分成的段的最大值最小（每段非空），最后输出方案，要求前面的划分越小越好。把所有数加起来的sum作为最值大了，但是我们有了上界，之后二分猜答案。关键是输出方案，是个贪心算法，后面能放的尽量放，但要保证至少前面每段一个。。。调了一个下午。。。。。代码
2013-08-15 01:13:27
1117
原创 MemSQL start[c]up Round 2 - online version C. More Reclamation
学习tourist的代码，自己编写了一个，基本一样，思路显然是SG函数，类似刘汝佳书本上的例题UVaoj 10561。就直接贴代码了：#include#includeusing namespace std;#define LL long longint g[111][111];int SG(int a, int b, int c, int d, int l){ int
2013-08-09 00:17:16
1071
原创 Codeforces Round #193 (Div. 2) ABCD
悲剧的一场比赛，感觉败在英语上了，题意理解错误题目肯定做不出来。第一题看懂就可以直接写：A：#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#inc
2013-07-25 23:05:10
1011
原创 N皇后位运算版
#includeusing namespace std;int lim, ans;void test(int t, int l, int r){ int p, pos; if (t == lim) ans++; else { pos = lim & (~(t | l | r)); while (pos) { p = pos &
2013-07-19 21:39:11
1025
原创 Codeforces Round #189 (Div. 1) Kalila and Dimna in the Logging Industry 斜率DP
题目链接：http://codeforces.com/problemset/problem/319/C
2013-07-18 15:30:18
1457
原创 Codeforces Round #188 (Div. 1) Game with Powers 引发的联想 NIM游戏 Sprague Grundy Theory
考完试，有空总结一下一个很大的收获：Sprague Grundy Theory这是由Codeforces Round #188 (Div. 1) Game with Powers这道题引发的思考，一开始疏忽，考虑错了问题，把问题引向了NIM游戏，歪打正着想到了NIM游戏的必胜策略证明，后来意识到虽然问题考虑错了，（也没能解决这个问题）但确实这两者还是有很大联系，我觉能能觉察到两者联系已经算
2013-07-08 16:52:45
1933
4
原创 Codeforces Round #191 (Div. 2) ABCD
今天是算我第一次正式参加CF的比赛吧，其实在那之前有一次打算认真做来着，结果时间问题，过了午夜，断网了，也没法开热点，就不了了之了，所以并不算参加了吧，今天因为官方把比赛时间提前了，所以很幸运的我不用半夜做比赛了，我对这场比赛期待还是蛮高的。（实现定了目标3题以上吧，因为是Div.2 所以前三题应当是一定要写出来的，然后我对有关图论的算法什么的还没学习，所以只能寄希望少点这种体型，就能争取4题了）
2013-07-04 23:56:38
1391
3
原创 USTCOJ 1213 取石子游戏 （经典NIM问题）及一些扩展 与（&） 或 （|）异或 （^）运算性质
题目链接：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1213在做本题之前，虽然听说过NIM游戏，但并不知道其必胜策略，之前遇到的另一个NIM问题是两堆石子的版本，取石子规则又略有不同，在思考两天之后终于解决了，结论非常优美，用到了数学竞赛知识里的Betty定理，结论和黄金分割有关，这里给个POJ百练上的题目链接：http://poj.grids.
2013-07-03 14:08:53
1510
原创 USTCOJ 1382 毛毛虫
题目链接：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1382想清楚其中变化规律很重要，一开始只想到位置的变化技巧，没注意到方向也有这种规律：虫子可以视为对穿而过，那么所有虫子假设不转头，t时间后，有t个位置，这与虫子转头情况下的的位置一样，（虫子的位置换了，但还是那几个坐标）其实到这里可以在想想方向的变化是一样的，因为每次掉头，相当于虫子
2013-06-26 14:38:13
982
原创 NOIP1999 拦截导弹
这是一道很经典的动态规划问题，对于我这种还没系统学算法的人，还是需要多加练习，有很多人写过这题的解题报告，我还是决定自己在写一篇，帮助自己加深理解，感觉对DP没有什么感觉，拿到题目思路有点难拓开，怎么找到动态转移方程，这对我来说是个问题。题目链接:http://www.rqnoj.cn/Problem_217.htmlRQNOJ据说是个高中NOIP选手创的OJ,被广大高中NOIP竞赛选手使
2013-06-09 13:46:44
1533
原创 USTCOJ 1106 The Luckiest number，2008 Asia Regional, Hefei, Preliminary
这是很明显的数论题,求10模某数的阶.(要构造的数是8*(10 ^ n - 1) / 9, 所以是求10)题目链接:http://acm.ustc.edu.cn/ustcoj/problem.php?id=1106注意到一些特殊小情况,其余直接求阶,一是10有因子5,所以,设幸运数是l, l能被5整除则不能被构造,另外,要构造的数中2的次数最多3次,所以模16等于0一概不能被构造,最后
2013-06-03 12:29:32
851
原创 USTCOJ 1388 钻石
这道题是一道原创的数学题，我的思路是直接算出询问点处的概率概率，仅供大家参考。题目链接：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1388经过分析：不难得出，钻石下落后的行为是堆成一个小三角形，然后往两边继续堆，堆至最高点又形成一个稍大的三角形,然后继续往两边堆,如此往复.因此,我们得出结论,对于n颗钻石堆成的一个小三角形加他的两个边,这
2013-06-02 18:24:25
1293
原创 c语言中指针与数组名
作为初学者，开始时听到最多的就是c语言的指针很难,我倒是觉得指针很形象，容易理解,只是c语言对指针的声明很容易混淆,尤其是和数组名搭配在一起时，让人难以理解.经过一学期学习,我还算理清楚了,因此作为这学期的的总结,我就只谈谈这一个话题吧,一个话题虽然少,但也能代表这门课中我的收获是很重要的,因为这些知识一直是难点,和关键点---c语言中的指针以及数组名.我们看以下3个语句:1. int *p[
2013-05-28 10:15:21
1556
原创 USTCOJ 1239 God Created The Integers
这是我的第一篇博客，现在正在努力学习编程语言中，以此记录学习心得。题目链接：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1239;题目大意是要求计算一个与p有关Sp，然后模p后取逆即结果。 其中p是4k+1型质数p > 10。这题我们需要以下知识，原理。（主要是二次剩余）
2013-05-13 19:04:12
1245
2
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人