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

Codeforces Beta Round 12 D Ball (Div.2 Only)

题目

源地址:

http://codeforces.com/contest/12/problem/D

理解

一个很神奇的题目= =。 给你N个女人的Beauty,Intelect,Richness值。在i女人和j女人之间如果有Bi<Bj&&Ii<Ij&&Ri<Rj,那么i女人就会去自杀!。!问总共有多少个女人会自杀= =。(这心理是有多阴暗。。。。) 实际上感觉就是一个三维的排序,不过有些细节需要处理。 首先开一个结构体来保存b,i,r以及id号。然后对每一个女人的beauty值排序,然后将b值离散化,作为这个树状数组的下标。然后再对i值进行排序,这样,每次只要getmax(lady[j].id+1),就能得到当前最大的女的r值。

Read More

Codeforces Beta Round 13 C Sequence

题目

源地址:

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

理解

给定一个序列,然后对于每一个数,你都可以进行自增或者自减操作。要求求出使得这个序列变为非减序列的最少操作次数。 我一开始的想法比较朴素,我想,只要找到一个比较的标准,比这个标准大我就–,比这个标准小我就++,这样就能得到这个非减序列的最少次操作。然后我就开始寻找这样的标准,后来发现,这是一个不可能的任务。因为给定的序列什么可能都有,我没有办法来衡量每一个数对于整体值的重要程度,然后也没有办法来计算操作的次数。 没有思路之后就开始开脑洞了。很显然,我可以得到这样一个结论,对于一个序列中的某一个数而言,步数最少的,肯定是变成左边或者右边的那个数。如果再考虑到对于整体数列的影响(因为这是一个循环的过程,整个数列都有整体上移或者下移的趋势),这个数可能的取值,肯定是这个数列中已经存在的数。不难猜想,如果这个数变成的最后结果不是这个数列中的数,说明这个解一定不是最优解。(因为要么就多操作了,要么就少操作了。 这么说好像有点难懂,我来举一个栗子吧,就是数列4 1 9。很显然,我们一眼就能看出,最优解的状态应该是4 4 9,也就是这个1恰好变成了4。试想,如果1变成了3,状态变为4 3 9,不合题意;如果1变成了5,状态变为4 5 9,符合题意,但是操作数多了1。那么问题来了,我变成3 3 9,难道不好吗?确实是这样,符合题意,而且结果最优。但是我们可以继续想,3 3 9可以,2 2 9可以吗?再继续,1 1 9可以吗?0 0 9可以吗?然后我们就能看出,位于4 4 91 1 9之间的数列都是可以的,超过了就不行了。这里的4和1,都是原来数列里面的数。我想,这或许并不是能不能问题,而是算法设计方便的问题。如果取原来数列的数,我们直接进行判断即可;如果不是,我们依然是要取原来数列里的数,判断是否在区间内。 根据上面的讨论,我们不妨得出这样的结论:对任何数进行的操作,最后的结果都是把它们变成原数列中的某个数。 解决了理论上的问题之后,下面进入实际的编码过程。直接开二维数组暴力搞的话,这个问题的时间复杂度过高,不可行。所以我们需要对原数组来一次sort,保证b数组是递增的。然后我们可以看到,dp的过程中,只会用到前后两个数,因此我们可以使用滚动数组来降低空间复杂度。这样,这个问题就得到解了。

Read More

Codeforces Beta Round 14 B Young Photographer (Div. 2)

题目

源地址:

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

理解

一个摄影师要拍摄运动员比赛的照片,然后给定摄影师的坐标,以及每一位运动员的活动范围。要求计算出摄影是需要活动的最小步数。 首先我们需要对输入的数据进行一次处理,也就是必须保证左端比右段小。处理完毕之后,两端分别进行sort,这样就得到了运动员活动范围的起点和终点的有序列。显然,只有当最大的起点比最小的终点还小的时候,摄影师才有可能同时看到。然后,如果当前摄影师的坐标比最大的起点小,他只要移动到最大起点即可;如果当前摄影师的坐标比最小的终点大,他就需要移动到最小终点。 这样,我们就得到了摄影师需要移动的距离。

Read More