CF拉练第七场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=63852#overview 比赛总结 这场比赛做的很渣,第一题卡了很久,还WA了两发。第二题一个裸的最短路模板题还折腾了半天。第三题是一个比较简单的数论题,用到了GCD。然后D和E都没有敲出来,其实D是一个要用到一点技巧的裸Nim。而E题。。。正面解法思绪繁杂,没有捋出来,而从结果入手开开脑洞倒是可以有点思路= =。 分题讲解 A题(暴力) 从前后分别入手求出和,然后对应进行判断即可。 http://xuanwo.org/2014/11/26/CF-18C/ B题(最短路) 模板题,注意路径的输出。 http://xuanwo.org/2014/11/26/CF-20C/ C题(数论) 用到了GCD,只要找出原来的最简比例就可以了。 http://xuanwo.org/2014/11/26/CF-16C/ D题(Nim博弈) 用到了很多异或的性质,位运算果然是一门大学问。 http://xuanwo.org/2014/11/26/CF-15C/ E题(DP,构造) 这个题= =,还没有办法证明。 http://xuanwo.org/2014/11/23/CF-15E/ 更新日志 2014年11月26日 完成题解。

Read More

Codeforces Beta Round 15 C Industrial Nim

题目

源地址:

http://codeforces.com/problemset/problem/15/C

理解

有n个矿场,第i个矿场有mi辆矿车,第一辆矿车有xi颗石头,第二辆xi+1颗,如此递推,直到第mi辆有mi+xi-1颗。然后有两个人轮流取石头(金矿?),他们可以选择任意一个矿场任意一辆矿车取走任意非0数量的石头,直到第一个不能再取的人认输。 实际上,这就是一个裸的Nim博弈问题,只要直接运用结论就能完成解答。但是问题在于,数据太多,导致每一个全都异或起来的话耗时太长。所以需要采用一些手段处理一下。我们需要用到两个结论:第一,从1异或到n的答案存在着这样一个特性:n%4==1时,答案为1;n%4==2时,答案为x+1;n%4==3时,答案为0;n%4==4时,答案为x。第二,从x异或到y的值等于nim(x-1)^nim(y)。 经过上述的处理,最后的结果就出来了~

Read More

Codeforces Beta Round 16 C Monitor (Div. 2 Only)

题目

源地址:

http://codeforces.com/problemset/problem/16/C

理解

一道关于分辨率转化的问题。要求将一个大分辨率按照指定的宽高比进行转化,如果宽高比不符,则进行切割。首先,我们来求一个x和y的最大公约数d,然后分别令x=x/d,y=y/d,这样就得到了x和y之间最简的比例形式。然后a和b分别去除以x和y,得到的两个背书中去掉小数部分较小的那个,就是切割之后的倍数比。最后得到的结果就是符合要求的结果。

Read More

Codeforces Alpha Round 20 C Dijkstra? (Codeforces format)

题目

源地址:

http://codeforces.com/problemset/problem/20/C

理解

实际上题目不难,但是我们都捣鼓了很久。原因是我们根本就没有掌握这种算法,导致连一个输出路径都搞得这么蛋疼。使用邻接表来存储每一个节点,每一个节点都自带一个指针指向下一个节点(可以自己使用数组模拟),最后的结果倒过来输出即可。

Read More

UVa 10082 WERTYU

题目

源地址:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=829&page=show_problem&problem=1023

理解

很简单的一道题,不过想了很久。我觉得需要注意的地方大概有三处: - 不用自己手写所有情况的判断,使用一个字符串数组可以高效地解决问题。 - 可以采用一边读入一边处理的方法,不需要开一个数组来保存所有的数,更何况那样做还要处理空格和回车的问题。 - 读题的时候忽略了两处地方,多行以及没有QAZ这些字符,导致最后处理的时候出现了问题。 注意到这些,这道题就可以轻松A了。

Read More

Codeforces Beta Round 15 E Triangles

题目

源地址:

http://codeforces.com/contest/15/problem/E

理解

数学渣,这道题无从下手= =。为了方便能自己看出一些东西来,我打了前两项的表去CF提交,幸运地得到了n=6的解,结果是1354。这个结果印证了昨晚比赛时候我的一些想法,因为10=(2^2+1)*274=(6^2+1)*21354=(26^2+1)*2。也就是说,最后的结果一定是某一个数的平方加上一再乘二的结果。这样,这个问题就转化成了,如何找到那个数。我们可以看到,这个数组成的数列是2 6 26。考虑到最后的取模,这个数一定是指数级别的,要不然增长速度太慢了,作为一个未来的码农,想到的第一个数列就是2 4 8。乍一看感觉跟2 6 26扯不上关系,不过再观察一下,2 6 26向前递减之后可以得到另外一个衍生数列,也就是2 4 20。第一个反应就是20=4*5,但是对不上啊,4怎么处理?小脑一动,对啊,4=4*1。1和5跟原数列有什么关系呢?可以看到,1=4-35=8-3。 写到这里,脑子里面已经是一团浆糊了,我来列成表格梳理一下。

a  c  b
2  4  2
4  4  6
8  20 26

这样可以看出,a=pow(2,i),c就等于c*(a-3),明显,b=b+c。于是我就得到了最后的公式。 以上,是通过偷鸡往后再推了一项得到的题解,在实际的比赛中,一方面题目不会再给你下一项(CF倒是可以用这种方法骗答案),另一方面,真的比赛中思路也不会这么清晰。所以还是要学习正规的组合数学+DP的做法,在我学会之前,还是先挖一个坑吧= =。

Read More

Codeforces Beta Round 6 B President's Office (Div.2 Only)

题目

源地址:

http://codeforces.com/problemset/problem/6/B

理解

总统的办公室里面坐着他的副手,然后每个人都会有一张办公桌(长短不一,但每个人都有自己的颜色)。然后告诉你每个人的办公桌都是长方形,给定一个描述办公室布局的图,要你求出这个办公室里面总统的副手有几个。 一开始我想得太多,觉得应该用DFS来暴力搜索,只要判断总统办公桌的四周即可。后来发现这种方法是不可行,决定采用STL里面的pair+set来做。思路很简单,既然已经告诉我办公桌都是长方形的,那么,我只要找到总统办公桌所占的区域,然后直接遍历这块区域外围的一圈即可。

Read More

CF拉练第六场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=63720#overview 比赛总结 做的好渣= =,跟SB一样卡B题的字符串卡半天。以后出问题了一定要仔细检查循环的初始值的问题。然后D题的脑洞大开也是神奇,后来学长提到了左偏树,有空一定要补一补。。 分题讲解 A题(暴力) 没啥好说的,暴力乱搞。 http://xuanwo.org/2014/11/21/CF-12A/ B题(暴力,排序) 写得很挫- -,暴力乱搞过了,应该是数据弱。。 http://xuanwo.org/2014/11/21/CF-12C/ C题(贪心) 想清楚区间与区间之间的关系,并不是很难。 http://xuanwo.org/2014/11/21/CF-14B/ D题(脑洞DP) 这个DP也是神了,其实并没有怎么用到DP的思想,关键在于结论是怎样得出的。 http://xuanwo.org/2014/11/21/CF-13C/ E题(树状数组) 一碰到数据结构就A不了,只会暴力乱搞和开脑洞,太弱了。 http://xuanwo.org/2014/11/21/CF-12D/ 更新日志 2014年11月21日 完成题解。

Read More