Codeforces Round #610(Div.2) 解题报告

还是终于能有这么一场最后一题会做了……

比赛页面(1282)

A-Temporarily unavailable

这题麻烦地方就在于情况有点多,包括圆含不含左右端点这些。其实稍微整理一下就行。

B1-K for the Price of One (Easy Version)

B2-K for the Price of One (Hard Version)

直接说Hard Version吧…

其实我也没怎么看这题,xydg出的

C-Petya and Exam

嘛这题其实就按照$t_i$从小到大贪心就行了……

总的来说,一个思路是先做简单题再做大题,这样必须做的题就变少了,当然具体怎么做还是要贪贪的……

我们在$t_i-1$处离开考场是可以更优的,因为你少做一道必须的题,而之前的题你都能做,所以花费的总时间也算得出来,所以就这么贪就行……

D-Enchanted Artifact

交互题都是人类智慧,还好这题不难。

一种构造方案是,先构造一个长度为$300$的全是a的串,这样可以问出串中b的个数。同样的道理,可以问出串中a的个数,这样串长就确定了。

然后就让答案串和询问串先全设为a,然后第i次询问将第i个a变为b,看编辑距离是增加还是减少,这样可以确定这个位置的答案。

另外,最后那个位置其实是不需要询问的,因为可以通过前面a的个数和b的个数直接得出来,这样就做完了。

E-The Cake Is a Lie

(蛋糕是个谎言!)

这题其实思路很简单……就是实现有点麻烦。

如果我们把三角形抽象为点,这题要好写一些。

观察到最后的图形,有若干个三角形,其中最外层的三角形(即删除后剩下的图形还是一个凸多边形)一定与剩下的多边形只有一个公共边,将三角形抽象为点后,发现这个点的度数为1,于是剩下的工作就是建图,然后做一遍拓扑排序,就可以解决第二问。

第一问的话我的解法是:不把三角形抽象为点,而是顶点为点,像这样动态加边,因为最外层的三角形的一个顶点出现次数一定为1(因为只有一个三角形以其为顶点),所以我们就可以把这个点删除后,与这个顶点相连的两个点各加一条边。但加边是有限制的,如果这两个点已经在同一连通分量里面,那就不加这条边。像这样,用一个队列进行bfs的话,最后加出来的图一定是一条链,这样就解决了第一问。

代码先留着,后面再补。

发表评论