【灰色头像模拟赛】总结+简略题解

首先要道歉。。真是太对不起大家了。。第一题gray的描述有点问题。。尽管后来在空间上更新了最终版。。
可能还是导致一些童鞋0分。。太囧了。。。
而且题目的难度有点。。。囧。。。。
因为是第一次举办比赛。。不是很会控制难度。。真是太对不住了。。。
解题报告:
1.gray
此题本来是要送分的。。因为描述上SB了囧。。导致很多人丢分。。太囧了。。
题解的话直接排序。。然后统计次数。然后输出。。。
而且标程还写错导致各种SB。。。
2.face
各位童鞋那个笔随便点几个点画一下。。
可以发现结果是有很多个矩阵组成的。。
具体的说,如果两个顶点有相同的坐标,那么他们之间连一条边。。
那么对于一个连通分量。。。最后会变成一个其中不同X坐标的个数*不同Y坐标的个数的矩阵。。
然后BFS一下求连通分量就可以了。。
3.snow
这个题目有点囧的。。设Dp[i]表示WJMZBMR在i点,NZK神犇还有一次机会的答案。
那么考虑一条边i->j
NZK神犇可以有两个决策。。删 or不删
删的话:
WJMZBMR就可以走最短路了,需要 Dist[i][1](i->j被删)。。
不删的话:
WJMZBMR就可以往j走。。就是Cost(i->j)+Dp[j]。。
NZK神犇显然要选最大值。。
用这个更新Dp[i]..然后用SPFA不断的更新。。。
Dp[0]就是答案了T_T。。
4.why
此题有点复杂和XX。。先看标程吧。。
可以证明按标程的方法,状态数是N^3的。。所以不会T

总而言之这次模拟赛办的也不是很成功。。难度过大了囧。。。
如果11月份我还有空的话我可能会再办一场。。按照我原来的想法。。
就是无限制XXX比赛了。。。

9 thoughts on “【灰色头像模拟赛】总结+简略题解

Leave a Reply to vikingsh Cancel reply

Your email address will not be published. Required fields are marked *