2015-2016 ACM-ICPC Northeastern European Regional Contest (NEERC 15)

From EOJ Wiki
Jump to navigation Jump to search

三人三机。做了三个小时摸了。

Problem A

Solved by kblack. 00:34 (+1)

行列分别统计即可,没写文件贡献一发罚时。

Problem B

Solved by ultmaster. 01:32 (+1)

题意:有一种好数(满足性质 $B$)是 二进制表示 是 十进制 的后缀。求第 $n$ 个好数。

题解:如果 $n$ 满足性质 $B$,那么 $n$ 的十进制表示的所有后缀都满足性质 $B$。然后 BFS 就可以。Python 特别好用除了会超时。

优化暴力是不可能的。这辈子都不会优化的。只能打个表。然后交不上去?压缩一下,就结了。。。

Problem C

Problem D

Problem E

Solved by ultmaster. 00:26 (+)

签到。

Problem F

Solved by ultmaster. 02:27 (+2)

题意:青蛙过河。二维的河里有很多石头。现在可以加一块,使得青蛙跳跃距离的最大值最小。

题解:二分答案 $ans$,然后距离不超过 $ans$ 的直接合并(加入两个虚拟节点 $S$ 和 $T$),然后检查 $S$ 阵营和 $T$ 阵营是否存在两块石头距离不超过 $2 ans$(或者 $S$ 和 $T$ 已经合并成功了)。注意以下问题:

  • 没石头的时候怎么办(要不要放石头)。
  • 不需要石头的时候石头放在哪儿。
  • 岸和一块石头中间需要插入一块石头的情况。

Problem G

Solved by zerol. 02:09 (+1)

题意:给不超过 10000 个循环节小于 1000 随机数列,要求从每个数列中抽出一个数,使得和最大且不是 k 的倍数。

题解:记录每个数列的最大值和模 k 意义下不同的次大值。如果最大值之和是 k 的倍数,那么挑一个损失最小的次大值来替换最大值即可。

Problem H

Problem I

Problem J

Solved by zerol. 03:09 (+3)

题意:猜二进制串。每次它会告诉你是不是有恰好一半猜对了,或者完全猜对了,或者两者都不是。要求在 1500 次内猜出长度为 1000 的 01 串。

题解:如果没有得到恰好一半的回答的话,信息量太少了。所以一开始随机 01 串知道得到了一个恰好一半猜对的串(这个概率还行)。然后如果修改两位,如果还是恰好一半,说明这两位恰好一对一错,反之则都对或者都错。那么修改 (1,2),(1,3),...,(1,n) 那么得到了 位置1 与其他位的猜的正确性是一致或者相反。然后枚举 位置1 的正确性就能在 2 次内猜对了。

Problem K

Problem L

Solved by kblack. 02:23 (+3)

题意:二维堆积木,新堆的积木下方左中右三块都必须已经有积木,给出最多增加的积木数量,求堆最高。

题解:枚举最高点所在位置,二分最高点,通过 $h_i+i$ 与 $h_i-i$ 得到左右落脚点,即可判断。注意不能堆出去。