CF拉练第一场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=61581#overview 比赛总结 这场比赛打得很挫,一上来看到D题之前做过,就直接贴了代码,被学长们狠狠地批评了一顿。确实,之前做过并不意味着我就能直接贴我的代码,我再写一次不一定写得出来,而且也丧失了一次检验自己是否真的确实掌握了的机会。以后一定要多注意,比赛态度要端正,不能看到自己做过的题就像占到了便宜一样,直接贴出自己的AC代码。 事实上可以看到,自己跟即将退役的12级差距还是很大的,这些水题都A不掉,或者姿势不优越,考虑不全面,思路受限这些问题暴露的很明显。还是题目做的太少,多做题,多总结。 分题讲解 A题(纯水题) 通过简单的分析就能搞定,一道比较简单的贪心。 http://xuanwo.org/2014/11/03/CF-4B/ B题(DP) 没做出来,一开始想的是DFS,但是没有处理好2跟5,以及出现0的一些情况。赛后看题解,才写出来使用DP的解法。 http://xuanwo.org/2014/11/03/CF-2B/ C题(模拟) WA了很多发,比赛的时候考虑的还是太不全面,没能从正面解决. http://xuanwo.org/2014/11/02/CF-3C/ D题(计算几何) 之前做过的题目,用到了海伦公式和计算圆心角知识。 http://xuanwo.org/2014/10/21/CF-1C/ E题(贪心) 用的贪心的思想,先使得所有的’?‘都变为’)‘,再来处理合法性和最优化的问题。 http://xuanwo.org/2014/11/03/CF-3D/ 更新日志 2014年11月3日 初稿。

Read More

Codeforces Beta Round 3 D Least Cost Bracket Sequence

题目

源地址:

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

理解

比赛的时候没有做出来,赛后看了琦神的解题报告才明白应该怎么敲。 实际上这个题目需要解决两个问题:第一是合法性,也就是是否满足左右括号匹配;第二是最优化,也就是要求Cost消耗最小。 使用一个变量cnt遍历输入的字符串,遇到’(‘则自增,遇到’)‘则自减。这样,只要判断cnt是否为零,就能判断是不是合法。一开始的时候将每一个’?‘都重置为’)‘,然后维护一个保存左右括号消耗差和当前节点的优先队列。然后开始不断地从优先队列中取出键对,使用保存了所有右括号消耗和的ss变量去减。 经过这样的处理之后,cnt只有两种情况。cnt不为零时,说明不可能合法,输出”-1”,cnt为零时,说明有解,输出ss以及最后符合要求的字符串。

Read More

Codeforces Beta Round 2 B The least round way

题目

源地址:

http://codeforces.com/contest/2/problem/B

理解

比赛的时候没有做出来,一看就知道应该是一个DP,选取一个2或者5最少的路径。 首先处理一下,设TWO为0,FIVE为1。在输入的时候就进行判断,当前输入的数和’0’,’2’,’5’之间的关系。得到的结果存在一个数组中,这样就得到整个数组中最多的0的个数。然后对2和5的数量进行比较,只需要考虑比较少的那个。 然后对第一个数为0的情况进行特判,此时只要随手输出就可以了。如果第一个数不为0,则开始取2比较少的路径开始行走。

大概是我写得不是很优美= =,在提交的时候遇到了各种问题,debug了半天,还是没有找出究竟错在哪里。直到我脑洞一开,把所有变量的定义放在了main函数的里面,居然过了!过了!!了!!! 蛋疼,不知道问题到底在哪里= =,唉,存疑。

Read More

Codeforces Beta Round 3 A Shortest path of the king

题目

源地址:

http://codeforces.com/contest/3/problem/A

理解

第一开始的想法是可以用DFS或者BFS搞定。后来仔细想了想,发现其实不需要这么复杂,通过建立一个坐标系,可以轻松搞定这个问题。 首先坐标化,将A~H转化为1~8,方便后续的处理,同时计算出终点与起点位移在x,y轴上的投影,分别设为mx,my。 然后下面是模拟的步骤: - 处理斜角:循环对mx和my进行递增或者递减的操作,直到有一个值变为零。 - 处理直线:对mx或者my进行递增或者递减的操作,直到这个值也为零,此时已经模拟完毕。

有两个值得注意的地方: - 首先需要输出步数,很显然,步数就是max(abs(mx),abs(my))。 - 不需要记忆路径,每次处理mx和my的时候,顺便把路径输出即可。

Read More

Codeforces Beta Round 3 C Tic-tac-toe

题目

源地址:

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

理解

一开始看到3*3,第一反应是想要枚举出所有可能的情况,也就是总共有9^3次种,但是发现自己很难处理这些情况,后来还是决定用暴力模拟的方法来做。

错误解法

为了简化情况的讨论,我取’.‘为0,’X’为1,’0’为2。这样,只要三个数的积为0,说明没有人胜利;三个数的积为1,说明先手胜;三个数的积为8,说明后手胜。这样,在判定胜负的时候,情况就简单了很多。 但是,我犯的错误就是对非法的状况考虑得不全面,或者说,懒得去自己判定是否非法,直接将非法的判断写在else语句里面,导致这段语句摆在前面挂test4,摆在后面挂test8这样尴尬局面的发生。

正确解法

赛后我重新写了这道题,正面强干,没有转换成int数组来处理。将胜负判定和非法判定全都写成了独立的函数,在最开始先判断是否非法,然后判定有没有出现胜者,最后判定是谁进行下一步。

Read More

UVa 1374 Power Calculus

题目

源地址:

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

理解

这次的题意比较清楚,就是给定n,求出从1变换到n的最小步数。 同样的迭代深搜,- -,我不行了= =,一口气补了三道,整个人都虚了。。

还是来小结一下吧。以前做的DFS都是裸题,很容易就能看出来。而迭代深搜这一类的题目,通常都是给定一些条件,要求求出指定条件的一些组合,可能是字符串也有可能是数。而且,通常都会有暴力的做法,不过姿势不优越的话,很容易超时。 然后在迭代深搜的过程中,一定要注意初始状态和边界条件,要不然很容易陷入死循环或者无法得到完整的结果。

Read More

UVa 129 Krypton Factor

题目

源地址:

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

理解

题意不是很好懂= =,我搬运一下翻译。

Problem “超级氪因素大赛”(译注:英国的一档电视心智竞答节目)的主办方雇你来对付那些足智多谋的参赛选手。在比赛的一个环节中,节目主持人将念出一长串的字母来考验选手的记忆能力。因为许多选手都是分析字串模式的高手,为了增加一些比赛的难度,主办方决定不再使用那些含有特定重复子串的字串。但是他们又不能将所有重复的子串都删掉,如果那样的话字串中就不存在两个相同的单字了,这反倒会让问题变的非常简单。为了解决这一问题,他们决定仅删除那些包含相邻重复子串的字串。我们将存在上述相邻重复情况的字串称为“easy”(简单),否则称为“hard”(难)。

Input and Output 为了能给节目主持人提供无限量的问题字串,要求你来写一个程序执行生成运算。程序从输入中读取多行数据,每行包括两个整数n和L(即按此顺序给出),其中n > 0,L的范围是1 ≤ L ≤ 26。根据这些输入,程序要按照字母表升序打印出第n个“hard”字串(由字母表中的前L个字母构成),并在接下来的一行打印这个串的长度。按照上述规则,第一个串应该是“A”。对于给定的n和L,你可以认为第n个“hard”串是一定存在的。 比方说,当L = 3时,头7个“hard”字串为: A AB ABA ABAC ABACA ABACAB ABACABA 字串可能很长,因此要将它们分成4个字为一组,中间用空格隔开。如果超过16组,则换一行,再接着输出第17组。 ABAC ABA 7 输入由一行两个零表示结束。你的程序可以限定最大的字串长度为80。

回溯搜索,还用到了string的一些比较方便的函数。

Read More

UVa 524 Prime Ring Problem

题目

源地址:

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

理解

一开始写了一个特别暴力的程序,吃饭之前让它一直跑,但是一直到我吃完饭回来还在跑14- -,默然泪。 然后推倒重来,开始用回朔法重写。实际上,我并不需要把所有的排列完全生成出来再进行判断,通过回朔法,我可以在生成排列的同时进行判断。这里也运用了深搜的思想,实际上是一个n*n的矩阵,我要找出满足表达式i+A[cur-1]为指数的那条路径。 搞定了主要的算法,下面就是一些细节的处理。首先,我不需要每一次都调用isPrime函数,因为n<=16,也就是可能出现的最大和是小于32的,我可以在预处理中先判断好是否为质数再拿来用。其次,事先必须指定A[0]=1,vis[1]=1,同时dfs()是从1开始的,注意数组的下标。最后,是输出的处理:每一行末尾的空格,每组数据之间的空行,不要多也不要少,虽然琐碎但是却会决定你能否AC。

Read More