Difference between revisions of "2014-2015 ACM-ICPC Northeastern European Regional Contest (NEERC 14)"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
(11 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
Solved by oxx1108. 0:15:12 | Solved by oxx1108. 0:15:12 | ||
− | + | 题意:给一个黑白相间的矩形,每次可以选一个子矩阵改变颜色,问至少改变多少次。 | |
− | + | 题解:改变所有偶数行偶数列即可。 | |
== Problem B == | == Problem B == | ||
Line 33: | Line 33: | ||
== Problem E == | == Problem E == | ||
− | + | Upsolved by oxx1108. | |
− | + | 题意:石头剪刀布游戏,给定计算机的状态机,让你构造一个状态机使得胜率高于99%。 | |
− | + | 题解:显而易见只要在某时刻进入某循环,那么可以一直胜利。因此只需要构造k个必胜的循环,然后通过若干步进入这个循环即可。 | |
+ | 构造必胜的循环很容易,只需要每一步出的都是原来自动机出的+1,然后转移和其一样即可。那么只要保证一定会进入循环即可。 | ||
+ | 那么对每次非进入必胜循环,则随机跳入下一个循环的随机位置,那么一直未进入循环的概率是$(1 - 1 / n) ^ k$ (n最大100,k设为500,那么未进循环的最大概率为0.006) | ||
== Problem F == | == Problem F == | ||
Line 43: | Line 45: | ||
Solved by oxx1108. 1:34:38(-1) | Solved by oxx1108. 1:34:38(-1) | ||
− | + | 题意:题意比较难懂。给若干个哈希函数和若干个文件,每种函数得到一个哈希值,求哪些文件夹里包含所有文件。 | |
− | + | 题解:bitset模拟一下即可,注意直接乘可能会爆int。 | |
== Problem G == | == Problem G == | ||
Line 64: | Line 66: | ||
== Problem I == | == Problem I == | ||
+ | |||
+ | [[File:Wiki-8.23-1.png|200px|thumb|right|高端配图]] | ||
Solved by Xiejiadong. 1:56:32 | Solved by Xiejiadong. 1:56:32 | ||
Line 71: | Line 75: | ||
题解:如果我们按照飞船的坐标排序形成飞船的编号数列,我们可以发现只需要对编号数列求一个单峰的最长子序列即可。 | 题解:如果我们按照飞船的坐标排序形成飞船的编号数列,我们可以发现只需要对编号数列求一个单峰的最长子序列即可。 | ||
− | + | 我们发现,所有不交叉的绳子都是在不断缩小的区间里面来回跳,那么我们做了单峰的最长子序列以后我们可以发现区间中的跳,变成了右图这样的跳: | |
− | |||
− | |||
− | |||
− | + | 顺着做一遍最长上生子序列,再到这做一遍最长上生子序列,暴力枚举拼起来即可。 | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Problem J == | == Problem J == | ||
Line 95: | Line 83: | ||
Solved by oxx1108. 0:46:31 | Solved by oxx1108. 0:46:31 | ||
− | + | 题意:给一个全排列去掉空格的字符串,求原来的全排列 | |
− | + | 题解:暴力dfs一下即可 | |
== Problem K == | == Problem K == | ||
Line 103: | Line 91: | ||
Solved by dreamcloud. 0:23:11 | Solved by dreamcloud. 0:23:11 | ||
− | + | 题意:傻逼题 | |
− | + | 题解:暴力 |
Latest revision as of 01:06, 26 August 2018
Problem A
Solved by oxx1108. 0:15:12
题意:给一个黑白相间的矩形,每次可以选一个子矩阵改变颜色,问至少改变多少次。
题解:改变所有偶数行偶数列即可。
Problem B
Solved by Xiejiadong. 0:58:32
题意:可以获得的快乐值是$\sum _{i=1}^{n} s_i*a_i$,不快乐值是$\sum _{i=1}^{n} s_i*b_i$,在保证不快乐值小于等于$B$的情况下最大化快乐值。
题解:按照$a_i/b_i$排序,便可以保证在$\sum b_i*s_i$小的情况下$\sum a_i*s_i$最大,贪心地把不快乐值填满即可。
Problem C
Unsolved.
题意:
题解:
Problem D
Unsolved.
题意:
题解:
Problem E
Upsolved by oxx1108.
题意:石头剪刀布游戏,给定计算机的状态机,让你构造一个状态机使得胜率高于99%。
题解:显而易见只要在某时刻进入某循环,那么可以一直胜利。因此只需要构造k个必胜的循环,然后通过若干步进入这个循环即可。 构造必胜的循环很容易,只需要每一步出的都是原来自动机出的+1,然后转移和其一样即可。那么只要保证一定会进入循环即可。 那么对每次非进入必胜循环,则随机跳入下一个循环的随机位置,那么一直未进入循环的概率是$(1 - 1 / n) ^ k$ (n最大100,k设为500,那么未进循环的最大概率为0.006)
Problem F
Solved by oxx1108. 1:34:38(-1)
题意:题意比较难懂。给若干个哈希函数和若干个文件,每种函数得到一个哈希值,求哪些文件夹里包含所有文件。
题解:bitset模拟一下即可,注意直接乘可能会爆int。
Problem G
Unsolved.
题意:
题解:
Problem H
Unsolved.
题意:
题解:
Problem I
Solved by Xiejiadong. 1:56:32
题意:相邻的飞船之间有绳相连,第一个飞船与坐标为0的空间站相连,移动尽量少的飞船,使得绳子之间没有交叉。
题解:如果我们按照飞船的坐标排序形成飞船的编号数列,我们可以发现只需要对编号数列求一个单峰的最长子序列即可。
我们发现,所有不交叉的绳子都是在不断缩小的区间里面来回跳,那么我们做了单峰的最长子序列以后我们可以发现区间中的跳,变成了右图这样的跳:
顺着做一遍最长上生子序列,再到这做一遍最长上生子序列,暴力枚举拼起来即可。
Problem J
Solved by oxx1108. 0:46:31
题意:给一个全排列去掉空格的字符串,求原来的全排列
题解:暴力dfs一下即可
Problem K
Solved by dreamcloud. 0:23:11
题意:傻逼题
题解:暴力