2014acm亚洲区域赛陕西赛总结

Love The Way You Lie 2022-08-27 09:56 164阅读 0赞

这次是第一次出来到外面比赛，一切都是很新奇的，带着新奇来到了古城西安，首先感觉就是志愿者一点都不热情，一副爱理不理的，这不是有违我大西北人的热情好客么。直接说比赛吧。

第一天热身赛，出了两道很水很水的的题目外加一道防AK题目，第一道ZY读了题目之后给我讲了意思，我听的不是很清楚，但是听出来了是一道水题，说是给出一些点的坐标，然后最后一个点和第一个点是初始点和结束点，然后让你从第一个点出发到达最后一个点，每次走的距离不超过1000，我想的是先对所有的点排好序，然后找到起点或者终点，开始往最后一个点走，但是中间有可能有些点是不经过的，得暴力处理一下，边写便考虑，等写到处理一下的时候发现有人前两道都AC了，然后ZKC说B题水题，以前做过，然后让他写B题，果然几分钟就A了，然后回到A题，ZY说肯定是有序的，直接走，然后我就把写的一大片注释掉，按他说的写，写两点间距离的时候他说题目告诉两点距离的算法是fabs（a.x-a.y）+ fabs(b.x+b.y),写好之后已测试测试数据都过不了，然后就说这种方法不行，得按我说的写，写好之后回去测试，发现也过不了，看了一下第二组测试数据，发现就算按我的也过不了，然后开始怀疑是距离公式的问题，让他两读了几遍题目，他两说是说是那样算的，我改成fabs（a.x-b.x）+fabs（a.y-b.y），测试了一下过了，ZY说提交吧，我提交了一下AC。读了一些第三道题目，发现时个计算几何难题，搞不定。看了一下现场也没有人搞定，就放弃了。后面他说按ZY说A不排序直接找也可以，我说试试吧，顺便测试一下对long long 的支持一次wa的返回，果然写完已提交就AC，后来想了一下，其实他就是两道签到题目，测试数据特别的水，基本可以说的怎么水怎么过。

然后第二天正式赛，提前半小时进场，开了电脑没事干，练练代码吧，写个网络流练练打代码速度，写了一大半的时候开始发题目了，然后题目到手后他两各自选择了一道题目开始读了，我把所有题目到翻了一遍，看了一下所有的测试样例，A题看测试样例的意思是找doge的出现次数，然后我说A题应该是水题，谁读一下，KC看了一下说的和我想的一样，我说你读读题目我开始写，应该没想象的那么水，（第一次外出比赛有点小紧张，还有点小激动，然后想的是按行读进去处理，ZY说直接按单词度吧，好处理，然后就改成按单词，写出来之后发现没办法测试，是读到文件结束，我说直接交吧，这么简单应该没有问题，事实证明高估自己的，WA了。然后写了一个读入文件的，把测试样例写进去，发现出现的是0，输出中间处理的结果，发现没有输出，然后ZY就开始Debug调试了，可是他也没搞定，我说不了，咱加一句代码不就行了，加了一句度到0结束，测试了一下发现果然输出结果不对，for循环判断出错了，然后改了，测试过了。提交了，有wa。然后我说应该有坑，让想想什么坑，KC说测试一个d oge的样例，一测试发现直接退出了，原来错在这儿，改了交了就AC了。（下来之后想了一下刚上去确实太紧张了，也是签到题目，但是wa了两次不应该，平时比赛的话肯定很速度的1A了）。

然后ZY把D题意思给我说了一下，让是用26个小写字母构造一个长度为n的字符串，使得长度大于等于4的字串不能重复出现，然后他继续读题我想这个题目，我想到了一个思路ZY找到漏洞了，然后我看了一下榜，有人出J题了，然后ZY给我说了J题的题意，大概意思就是在一个n\*m的图中，有的点是可以走的用"."表示，有的点是不可以走的的用“X”表示，然后给出k对坐标，每一对可以从第一个坐标进去从第二个坐标点出来，是瞬间的，求把所有走一遍的最短时间，图中移动一格的时间是1，我想到思路是怎么处理出来任意给出的坐标之间的最短路径，然后运用克鲁斯卡尔最小生成树的思想，找距离最短的点，然后依次并查集到一起，最后所有的并到一起就行了。ZY没有想到什么漏洞，然后我说你先BFS求任意的最短路，我在考虑考虑，然后我在纠结用PRIM还是克鲁斯卡尔，然后我最后决定用PRIM又发现时两个点，处理的不一定对，但是克鲁斯卡尔一定能保证对，然后我觉得差不多之后就放下然后听KC说了一道B题，给出一个图中的所有点的路径，然后从1点出发，把所有点都走一遍，而且到所有点都有时间限制，如果能到达的话输出满足条件的最短路，然后我就感觉可以做，思路是先flayd处理所有点的最短路，然后从1点出发找所有中最短的，然后看看满足不满足到这个点的最短路条件，满足继续找一下个最短的，如果不满足看看直接从上上一个点过来满足不满足，知道找到这样一个满足的，感觉自己的思路是对的，给KC讲了他也没找到漏洞，然后等ZY写完我写这个。结果ZY写完之后一直调试不对，我搜索写的不好也帮不上什么忙，然后我就说在跟一下榜吧，看了一下好多人出了C题，然后就读了C题，发现时个接近裸地最短路，然后感觉题目不难，坐等AC的感觉，然后就继续看着他调试，终于调试出来了然后写克鲁斯卡尔的时候发现不对，那样走出来的会是一个树，不是直线，然后我说你在考虑一下吧（赛后考虑了一下发现就是一个prim），我写C题，很快写完然后测试过了就说提交吧，wa了，然后就说可能中间结果超int，但是发现超int的地方都改了，就说把所有的都改成long long吧，改了之后提交又wa，然后三个人一起找错也找不到，花了一个小时过点改了几个小问题一直wa，然后就说打印代码写J题，然后ZY写J题，我在那边考虑什么地方wa了，但是还是想不出来，ZY那边也是最短路出来了缩点不行，还有半个小时，我说一定要至少过一道，我调试C题吧，然后各种测试数据各种对，我说不然换个bello\_man算法吧，当我准备注释掉spfa的时候发现vector没初始化，然后加了一个初始化就ac了。忽然感觉好悲催好失误，回去调试J题，还是调试不对，最后10分钟说按旅行商问题处理一下，提交一次试试人品。写了之后样例没过，没时间了。就这样了。

确实是一次很失败的比赛，至少出三道的，出了两道题目，但是我觉得失败总是好的。他可以让我们在接下来的路上走得更远！

以前在高中的时候就听说过西工大，这次终于见识了一下西工大，刚去的感觉就是学校很安静，白天也是感觉人很少，不知道人都在哪儿。还有就是学校航空航天专业很牛啊，晚上逛学校发现有人拿着几个飞机在走路，过去问了一下说是拿过来试飞一下，然后说每天5:30在足球场有人飞飞机，跑过去之后说是下雨飞飞机的没来，有点遗憾了，这就能解释人家航空航天专业牛的原因了！虽然比赛成绩不理想，但是出去走走感觉还是收获很大，队友说忽然有考研的冲动了。

经验：

1：其实想想我们做题的策略很简单，就是上去先自己大概判断做，然后跟榜就行了。最主要的是要有安排调度，一道题目花费超过一个果断先放弃！

2：不要紧张，淡定的一道一道来。起码有思路的都要试着做一做！