2016编程之美初赛体验

关于题目

BOP 的难度和 Code Hunt 根本不是一个难法。相比之下,Pex4Fun 和 Code Hunt 区更多地是以考验洞察力为主。

今天参加的 BOP2016 PRELIM A 共有两个 Sector 。很不幸的是,我最终只能成功提交一道题(00.04)。另有两道题则一直被 path bound exceeded 的错误困扰。

另请参阅:BOP2016 PRELIM A Leaderboard

00.01

输入为 float[] a ,输出为 int[],包含了 a 中对应元素在整个 a 中的排名(从 0 开始),需要考虑并列排名的情况,有些类似于 Excel 的 RANK 函数。

思路:生成一个 [0, x.Length) 区间的整数序列 ind,然后使用 Array.Sort(a, ind) 进行排序。再开辟一个数组 rank,则此时 ind[i] 就意味着顺序排名第 i 的元素在排序前的原数组 a 中的位置。

本题较为麻烦的地方在于,如何处理并列排名的情况。我使用了双层循环。

以下是核心代码的残骸

结果:path bound exceeded

后来使用 Array.IndexOf 代替内层第一个循环,问题依旧。

00.02

说实话,这道题,我并没有看出来什么规律。IQ捉急。

后来群里有人说,这是几何平均数。

好吧。

a Result
{1, 1, 1, 1, 1} 1
{1, 1, 1, 1} 1
{1, 1, 1} 1
{1, 1} 1
{1, 2} 1
{1} 1
{2, 1, 1, 1} 1
{2, 1} 1
{2, 2, 1} 1
{3, 1} 1
{5, 5, 1, 1, 1} 1
{2} 2
{3, 4, 5, 6} 4
{4} 4
{10, 5} 7
{10, 6} 7
{13, 4} 7
{4, 14, 7} 7
{5, 10} 7
{8, 7} 7

00.03

这道题的输入比较复杂。此处列出其函数头

其中,strs指定了一个地图。地图中的 . 表示通路, # 表示障碍。需要求出从坐标 (r1, c1) 到达 (r2, c2) 的最短路径长度。如果没有可行通路,则返回 "No path found!"

以下给出三个测试用例

思路:当然是使用 BFS 啦~ 用队列解决一切问题。为了能把每一步的行、列和路程保存下来,最好做一个类或者结构体。

结果:path bound exceeded

由于代码过于惨不忍睹,此处就不贴上来了。

只知道最后为了试着解决这个问题,我甚至将 BFS 换成了 DFS + 距离启发 (<– 不知道是不是在瞎胡搞)。最后,比赛结束了……

00.04

输入一个 int n,按顺序输出所有可能的、包含 n 个左括号的、左右括号匹配的字符串列表。

思路:使用一棵树来表示每个字符的选择。由于每个字符只能选择'('')'之一,因此,最后会得到一棵二叉树。只要使用 DFS + 剪枝就可以了。分支截至字符串中的左括号数量等于 n,剪掉所有右括号数量大于左括号的节点。

代码如下

结果:系统评级为1(It worked!),7分。这也是本场唯一拿到分的题目。

01.xx

很不幸,我没能活着从 TAIHU 出来。不知道 POYANG 如何(会不会像 PEX4FUN 的 Sector 03 一样)。

Epilogue

今年,大赛分为编程赛与创意赛,编程赛分初赛,复赛和决赛三部分。初赛和复赛在网络比赛平台上举行。今年初赛的网络平台为 Code Hunt平台。比赛时间为4月23日至4月24日,每天进行一场,时间为14:00-16:00。每场晋级1500人,共决出3000人晋级复赛。 [1]

按照今天 Code Hunt 的排名情况,似乎只要做出一道题,就能晋级了。不知道。总之,革命尚未成功,同志仍需努力。

今年的项目只有codehunt,各位oi/acm选手准备好被都是bug的平台玩奶子吧  [2]

我还是继续去 Coursera 上刷网课吧。在此之前……

我的工程优化好像还有4天的时间复习。

我的随机过程好像还有14天的时间复习。

发布者

CXuesong

CXuesong

给我一点点考虑的时间。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*