13级个人赛第一场

比赛地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=61737#overview 比赛总结 这次比赛打得还行- -,最近生活比较规律,连带着人也变得机智很多,暴力乱搞加开脑洞,过了很多题。但是,也从侧面暴露出编码能力不强,算法功底不扎实的缺点。接下来还是要好好训练,多多刷题。跟队友多交流,相互促进,不停地PUSH自己。 分题讲解 A题(STL,模拟) 比赛的时候真的看不懂题意= =,太弱了。赛后看的题解大涨姿势,学会了好多神奇的技巧。 只要理解了翻转的过程,题目并不是很难。 http://xuanwo.org/2014/11/04/UVa-120-Stacks-of-Flapjacks/ B题(构造) 超想像CLJ一样来一句傻逼题。 开脑洞过了题之后还没反应过来= =,当时的唯一想法是卧槽,这么逗的题怎么没人过? 然后吐槽了范神带歪了榜= =,导致前面很多水题大家都没做出来。 http://xuanwo.org/2014/11/05/UVa-1605-Building-for-UN/ C题(暴力) 乱搞,开了一个一千六百万的数组二分过了。 不知道是谁告诉我只要学会暴力就能区域赛拿银来着= =。 http://xuanwo.org/2014/11/05/UVa-1152-4-Values-whose-Sum-is-0/ D题(贪心) 把问题想得太复杂,其实X和Y方向根本就没有关系,完全可以分开考虑。 http://xuanwo.org/2014/11/04/UVa-11134-Fabled-Rooks/ E题(贪心) 大胆地喊一句:傻逼题。 想了半天的还差点开始敲网络流模板的我更加傻逼= =。 http://xuanwo.org/2014/11/05/UVa-11054-Wine-trading-in-Gergovia/ F题(几何) 扫描线算法,当年土豪学长跟我们说过,但是打比赛的时候完全没有印象。 也跟读题能力有关系,看到题目长,题意复杂就不敢下手,太弱了,要加强。 http://xuanwo.org/2014/11/04/UVa-1606-Amphiphilic-Carbon-Molecules/ G题(模拟) 一开始以为是神奇的数据结构,实际上不用那么复杂。 http://xuanwo.org/2014/11/05/UVa-11572-Unique-Snowflakes/ H题(二分,乱搞) 感觉是最长上升子序列演变过来的题目。 http://xuanwo.org/2014/11/05/UVa-1471-Defense-Lines/ I题(几何) 赛后看了大神的论文,数形结合是厉害啊= =。 http://xuanwo.org/2014/11/04/UVa-1451-Average/ J题(贪心) 小白书上的最大值最小化问题。 http://xuanwo.org/2014/11/04/UVa-714-Copying-Books/ K题(水题) 傻逼题——我还WA了一发。。。 http://xuanwo.org/2014/11/05/UVa-10954-Add-All/ L题(分治) 貌似是第一次接触分治,这种把大问题分解为多个小问题的思想需要掌握。 http://xuanwo.org/2014/11/05/UVa-12627-Erratic-Expansion/ M题(模拟,剪枝) 很多人过的题,但是我没想出来怎么敲。 http://xuanwo.org/2014/11/06/UVa-11093-Just-Finish-it-up/ N题 O题(模拟) 跟G题有点像,同样是另外开一个数组用来保存第一次出现的位置,这个技巧感觉很有用。 http://xuanwo.org/2014/11/04/UVa-12174-Shuffle/ 更新日志 2014年11月5日 完成部分题解。

Read More

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