2015-2016 ACM-ICPC Northeastern European Regional Contest

再开一个新坑吧

目前姿势有限,C、H、I仍然处于弃坑状态

代码戳这里

Problem A. Adjustment Office

显然假设每一行都没有进行过删除的话,那么答案就\(-n*x\)的和\(+n*x\)(\(x\)为行号或者列号)

考虑进行过清零以后的问题,由于是整行整列的删除的

那么我们只需要分别记录删除的行号和列号的总和,以及删掉的数量,然后就可以\(O(1)\)得到了结果了

当然,别忘了开两个数组分别记录行和列有没有删除过


Problem B. Binary vs Decimal

一个性质:\(10k\)的二进制表示的末尾一定恰有\(k\)个\(0\)

这样就可以枚举答案的位数,从低到高一位一位添加\(0 / 1\),维护当前二进制末尾k位都合法的数字集合,因为有上面那个性质,所以从低到高枚举的时候,当把一个数十进制第\(k\)位赋为\(1\)的时候,只会影响到这个数二进制中第\(k\)位之前的值

因此,这个数的二进制后k位就逐一确定了,就可以把所有答案从小到大枚举出来。要用高精度。
复杂度\(O(d^2* n)\),\(d\)为答案的位数


Problem C. Cactus Jubilee

仙人掌,日常弃坑系列


Problem D. Distance on Triangulation

由于给出的图是一个多边形的三角剖分,因此每条对角线都能将这个多边形分成两个部分,就可以采用分治的方法。

类似树分治,先构出一个分治结构:每次在当前多边形中选出一条对角线,使得两部分点数尽可能均匀(可以证明最坏情况下存在任意一侧不少于n/3的分法)。

这条对角线两侧就形成了两个子多边形,递归下去,直到当前多边形为三角形为止,并且通过bfs计算出每个子多边形上每个点到选定的对角线两点的距离。

询问的时候只要判断一下两个点是否在选定的对角线同侧,如果是则递归求解,否则可以通过之前预处理出的距离简单计算。

复杂度\(O(nlogn)\)

口胡起来真是简单…..写的时候,常数卡到心灰意冷啊…………………..

不过最后还是卡进去了………………….


Problem E. Easy Problemset

感觉这道题目才是货真价实的签到题啊?

怎么cf上A比E过的人多呢……一定是E的题目太长…不太有人愿意读啊

直接按照题目意思模拟即可,不多说


Problem F. Froggy Ford

显然,最有的情况下,添加的一个点一定是某两个点的终点那么两两之间连两条边,一条为原来的边,另一条为中间有点的边,第一条的权值为两点距离,第二条的权值为两点距离的一半然后限定,从起点到终点的最短路只能跑一次第二条边这类边

然后就是最短路了

写了个SPFA,喜闻乐见的卡掉了两个点,由于我比较懒,不想改dij了,那就直接………….


Problem G. Generators

发现c比较小,最坏情况下,循环节为c个

那么我们求出所有的循环节,那么最多一共有1e7个数,排个序

如果最大的和%m不为0,直接输出

否则,我们对于每一个数列,寻找最大的一个,满足\(%m\)不为0的解,取最优的一个

如果仍然不存在,那么就无解了


Problem H. Hypercube

四维计算几何?!日常弃坑系列


Problem I. Iceberg Orders

很繁琐啊……日常弃坑系列


Problem J. Jump

好像可以先随便猜一个n / 2位相同的串出来..期望次数大约是40..

现在我们想知道每一位具体的值。 似乎将每一位单独取反之后.. 答案要么+1要么-1.. 返回值都是0

这样就没有办法判断了

把每位与第一位同时取反,然后做一次询问,这样就能得到每一位和第一位之间的关系了,这一步要进行n – 1次询问

然后枚举第一位是0还是1.. 根据之前得到的每位与第一位之间的关系,就能得出每一位的值。

对这两种情况分别做一次询问就好了。


Problem K. King’s Inspection

众所周知,哈密顿回路是一个NPC问题

那这道题目的突破口就在于边数小于等于点数+10

那么,也就是说,图中有大量的点是呈链状分布的,也就是说,我们可以把链所在一起

首先把入度和出度均为1的点,相连通的全部所谓一个点,那么剩下的点,在图中直接跑dfs即可


Problem L. Landscape Improved

二分答案

暴力枚举答案所在的列,剩下的问题就是验证答案了

首先我们发现,最后的形状一定是金字塔形的

那么,我们可以直接用优先队列大力预处理一发

然后根据预处理出的左边界和右边界,直接O(1)计算得到所需要的砖块,和n比较,得到可不可行即可


 


发表评论

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