Difference between revisions of "2014-2015 ACM-ICPC Northeastern European Regional Contest (NEERC 14)"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 74: | Line 74: | ||
[[File:Wiki-8.23-1.png|200px|thumb|left|alt text]] | [[File:Wiki-8.23-1.png|200px|thumb|left|alt text]] | ||
+ | |||
+ | |||
+ | |||
+ | |||
顺着做一遍最长上生子序列,再到这做一遍最长上生子序列,暴力美女拼起来即可。 | 顺着做一遍最长上生子序列,再到这做一遍最长上生子序列,暴力美女拼起来即可。 |
Revision as of 05:58, 23 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
Unsolved.
题意:
题解:
Problem F
Solved by oxx1108. 1:34:38(-1)
题意:
题解:
Problem G
Unsolved.
题意:
题解:
Problem H
Unsolved.
题意:
题解:
Problem I
Solved by Xiejiadong. 1:56:32
题意:相邻的飞船之间有绳相连,第一个飞船与坐标为0的空间站相连,移动尽量少的飞船,使得绳子之间没有交叉。
题解:如果我们按照飞船的坐标排序形成飞船的编号数列,我们可以发现只需要对编号数列求一个单峰的最长子序列即可。
我们发现,所有不交叉的绳子都是在不断缩小的区间里面来回跳,那么我们做了单峰的最长子序列以后我们可以发现区间中的跳,变成了下午这样的跳:
顺着做一遍最长上生子序列,再到这做一遍最长上生子序列,暴力美女拼起来即可。
Problem J
Solved by oxx1108. 0:46:31
题意:
题解:
Problem K
Solved by dreamcloud. 0:23:11
题意:
题解: