昨天做了这场比赛,算是开学后第一场正规比赛,比的不是很理想,被那纯正的英语迷惑了一个多小时…再次提醒要学好英语..
买了两本英语书,发现好便宜,加起来才20多块,还没火凤燎原一本贵.
言归正传,开始写解题报告:(可以去这里提交)

Arithmetically Challenged

24点类似的题目,给你四张牌,要你求出能由+-*/所计算出的最长连续数列

3个dfs,第一个先枚举数的位置4!,再枚举符号4^3,再枚举运算顺序3!,把所有结果排序然后遍历

Cover Up

一个猜数字游戏,叫你猜5个数字,全部猜中才算赢,不必一次猜中,但是每次你至少要多猜对一个,每猜一次你都会知道结果(true or false),所以你有一个最佳的决策,现在告诉你每个位上的每个数字的概率,问你要最佳策略下赢的概率是多少

本场比赛最有质量的一道题目,想清除思路就要花好点时间:首先你要枚举猜测的方案(猜已经确定known的还是unknown的),在这些方案里取其中结果最优的一个,对于每个方案你还要枚举你猜测的对错情况,由于每次揭晓不同的答案后剩下的数字的概率就会改变,所以还要重新计算剩下数字的概率,然后递归到下一层,知道全不猜对..
状态好多好多..由于一开始我没有记忆化,直接TLE了..加了记忆化后才AC.去网上找了下标程,没用记忆化,109MS,时间比我快三倍,大概是省略了很多可以直接判断出来的状态没有递归下去

Decompressing in a GIF

告诉你怎么把字符串压缩:给你几个基本mapping,对应的数字用0开始计数,然后去匹配给你的一个长串,每次用匹配后如果没有结束,那么新加一个mapping = 原来的mapping + 下一个要匹配的字母,并且其对应的数字是计数++,有了这个法则之后,我们就可以将字符串压成一些交短的数字了,其对应的数位和当前mapping个数的数位相同.再根据他所给的条件进行解码

看懂之后一步一步来反着模拟就OK的,要特别注意个数从9到10,99到100这样的地方,很容易造成错误

Flipper

开始有很多牌放在桌子上,有的朝上有的朝下,然后给你加下去的操作,将一列牌倒过来扣到另外一列牌上,问你最后剩下的一列牌的情况

直接模拟就好了,用n个数组,每次翻转的时候把要翻转的数组倒过来赋值给目标数组,由于都是从两边开始的,所以定义s和e两个游标标记剩下的牌的头和尾就好了,我开始还以为可以从中间翻转,还用了vector…XD

The Flood

在一个高低不平的小岛上,问你多高的水位才能使小岛分成好几个部分

很暴力的一道题目,从小到大枚举水位,然后从四周向中间扩充(用dfs或者floodfill都可以,我喜欢用dfs,写起来方便点,4句话就解决)再判断剩下的部分有没有分成好几块

Here’s a Product Which Will Make You Tensor

给你矩阵叉积,问你有多少个方案使两个整数矩阵叉积得到所给的矩阵

我开始一直以为只要算出两个矩阵的大小就OK了,但是WA了好几遍之后才知道原来相同大小里边不同数字也可以得到这个矩阵,于是要再加一层枚举才能得到答案.
第一,二层枚举:n和m的因子
第三层枚举:所给矩阵中因子数最少的数的因子(找因子数最少的数有利于提高程序效率)
然后就可以算出两个矩阵,看看是否符合题意
这题的系数有点大,三层枚举如果都是枚举500和65536内因子数最多的360和55440的话就有69120 = 24*24*120了,然后乘上判断合法性的4层for循环的话(当然,非法的情况很可能一下就判断出来了),复杂度是非常恐怖的..

Trip the Lights Fantastic

给你一个城市的地图,每个结点处有红绿灯,红灯停绿灯行,问你从起点到终点的最小距离

比赛的时候没什么人去看这题..其实是很水的题目,只要最短路的时候稍微改变一下,存的是从起点到当前点出发时刻的最小时间就OK了(注意红色字样的地方)

Windows

告诉你很多个窗口的位子(窗口数<=100),问你点击鼠标的时候点到的是哪个窗口

全场最水的题目,我却做了一个小时..晕,没理解pixel像素的意思,sample用尽办法怎么调都出不来..最后还好有人在Clarification理提问并有人回答才明白..不然这道题一定做不出…

总体来说,这场比赛的题目都灰常的暴力..

Popularity: 13% [?]