2012-2013 ACM-ICPC Northeastern European Regional Contest (NEERC 12)

NEERC 12

• 某三题题解[solutions]

• 官方题解[solutions]

Problem A

Solved by oxx1108. 00:34

题意：签到题，消灭星星。给定每次消的个数，构造初始状态。

题解：由于没有限定颜色个数，蛇形放就行。

Problem B

Upsolved by oxx.(-16)

垃圾题目毁我青春

题意：求题意比较难懂。（题意巨坑）

给一些物品，每个可以取或者不取，想要不大于$c$的最大物品重量和。

一开始随机有一个A序列（01串），每一位表示物品取还是不取。

每次给一个随机B序列的重量和，随机方式是在A序列上随机修改一位01。

每次有三个选项，可以拿新的B串代替A串，不做任何操作，或者结束操作直接返回（答案就为现在的B串）。

要求操作次数少于1000。

题解：直接先将01串变为全0，然后变为全1，然后就可以计算出每个物品的质量，状压算出最大状态，最后随机到答案。

由于没看到一开始A序列随机死活过不了。

Problem C

Solved by Xiejiadong.02:53(+9)

题意：给每个人分配一个相同的长度，使得每个人可以在自己的区间里面找出互不重叠的区间。

题解：用long double来二分答案，然后暴力枚举分母，找出分数的表示。

需要注意精度问题，wa了好几发。

Problem D

Unsolved.

题意：

题解：

Problem E

Solved by oxx1108.02:29(+1)

题意：

题解：

Problem F

Unsolved.

题意：

题解：

Problem G

Solved by dreamcloud.02:01( +1(by oxx) )

题意：[0，n]中有多少个数满足k进制下，和-k进制下表达一样

题解：转换一下题意，就变成了一个数取k进制之后，$a_m,a_{m-1},……a_3,a_2,a_1,a_0$,要满足$a_m,,……,0,a_2,0,a_0$,即奇数位一定是0，数位dp一下。

Problem H

Solved by dreamcloud.01:34

题意：给你一个字符串s，求它有多少个子序列，满足重构之后是回文串。(重构指的是将子序列中的字符任意交换位置)

题解：子序列重构是回文，其实就是最多只有一个字母出现次数是奇数。利用hash异或和来维护前缀中每个字母出现的次数为奇还是为偶。从前往后扫，要么每个字母都是偶数，要么枚举一个字母出现奇数，只需要看前面该状态有多少个。类似于EOJ七月月赛。

Problem I

Unsolved.

题意：

题解：

Problem J

Solved by Xiejiadong. 03:59(+1)

题意：从0出发，用$a$次$\pm 1$,$b$次$\pm 2$,$c$次$\pm 3$遍历所有的$0$到$a+b+c$点。

题解：先把$c$次$\pm 3$的处理掉。我们通过向右、向左、再向右三部分，把前面的一部分填满，并且最后填的一个的左边已经全部填满，右边全部没有填过

再向右一步一步填，剩下一个$\pm 1$用来在最后改变方向，剩下的$\pm 2$我们用过向右、转弯、向左来填满右边剩下的部分

注意各类情况的处理与细节问题

Problem K

Unsolved.

题意：

题解：

Problem L

Unsolved.

题意：

题解：