2017-C13-team3

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(0902.png)]]
= 流水账 =
   今天Johann学长继续军训，reku和lzw两个人打。

   香港题好jb恶心，连个显然一点的签到题都没有。读了B，两人讨论一下，好像是傻吊几何题。但是两个人都没写过，勇敢的lzw从裤裆里掏出了白书，抄起了点到线段距离的板子。

   reku看了看C，感觉gcd和lcm大于等于2的情况似乎很傻吊，但是这个只有1次的情况好像有点复杂。于是猜一下，觉得是只摘一个数字出来，其他的数字都做一种操作就好了。但是写着写着，自己发现了一个反例，然后陷入僵局。lzw提出了一个1000*50000的枚举，但是lzw感觉好像过不了，reku表示莽一波，终于缓慢的过了C。（赛后用反例数据叉掉了浙大除了五队包括去年3队在内的所有AC代码，垃圾数据）

  然后lzw看了一眼J，就说是AC自动机瞎搞搞就行，然后闪电一样A了。讨论了半天K，两个人都没啥思路。然后两个人讨论了一下A，lzw感觉如果颜色数量相同的话生成树搞一下，挺好的。然后讨论了一下，发现颜色不同也可以生成树乱搞。然后开始写A，写了一个半小时终于过了，于是开始点外卖，打出GG。
= 总结 =

== reku ==
  感觉今天就是在躺着，主要的锅就是我没想出K。其实赛后觉得非常显然，这个讨论感觉也似曾相识。然而比赛时候就是不会，菜啊。
== lzw4896s ==
  今天签到非常慢，K题感觉应该能想出来的，看到子集就感觉是bitset搞搞，一开始方向就歪掉了。 写A题的时候犯了一些小错误，原本半个小时能写好的题花了一个半小时才过掉，代码能力还需加强。
== Johann ==

= 教训 =

= 题解 =
   * K： 来自七队的超简单做法： cnt[i]表示有多少个人拥有第i种技能，显然答案上界就是min{cnt[i]}.  对所有人按照他们的职业拥有的技能数从大到小排序，技能数相同的让职业一样的排在一起。 按顺序更新cnt数组， 如果一个人使得cnt[i]变成了cnt[i] + 1, 就把这个人加入第cnt[i] + 1支队伍里。 题目的性质保证这样可以拼出min{cnt[i]}支队伍。
   * D： 首先对高度离散化，最优情况下最后所有塔的高度都是原来某个塔高度[h - 70, h + 70],  f[i][j][h] 表示前i个塔，能看到j个，最高的塔高度是h的最优解。 转移的时候考虑第i个塔是不是最高的，利用前缀最小值优化到O(N^4^).

流水账

今天Johann学长继续军训，reku和lzw两个人打。

香港题好jb恶心，连个显然一点的签到题都没有。读了B，两人讨论一下，好像是傻吊几何题。但是两个人都没写过，勇敢的lzw从裤裆里掏出了白书，抄起了点到线段距离的板子。

reku看了看C，感觉gcd和lcm大于等于2的情况似乎很傻吊，但是这个只有1次的情况好像有点复杂。于是猜一下，觉得是只摘一个数字出来，其他的数字都做一种操作就好了。但是写着写着，自己发现了一个反例，然后陷入僵局。lzw提出了一个1000*50000的枚举，但是lzw感觉好像过不了，reku表示莽一波，终于缓慢的过了C。（赛后用反例数据叉掉了浙大除了五队包括去年3队在内的所有AC代码，垃圾数据）

然后lzw看了一眼J，就说是AC自动机瞎搞搞就行，然后闪电一样A了。讨论了半天K，两个人都没啥思路。然后两个人讨论了一下A，lzw感觉如果颜色数量相同的话生成树搞一下，挺好的。然后讨论了一下，发现颜色不同也可以生成树乱搞。然后开始写A，写了一个半小时终于过了，于是开始点外卖，打出GG。

总结

reku

感觉今天就是在躺着，主要的锅就是我没想出K。其实赛后觉得非常显然，这个讨论感觉也似曾相识。然而比赛时候就是不会，菜啊。

lzw4896s

今天签到非常慢，K题感觉应该能想出来的，看到子集就感觉是bitset搞搞，一开始方向就歪掉了。 写A题的时候犯了一些小错误，原本半个小时能写好的题花了一个半小时才过掉，代码能力还需加强。

Johann

教训

题解

  • K： 来自七队的超简单做法： cnt[i]表示有多少个人拥有第i种技能，显然答案上界就是min{cnt[i]}. 对所有人按照他们的职业拥有的技能数从大到小排序，技能数相同的让职业一样的排在一起。 按顺序更新cnt数组， 如果一个人使得cnt[i]变成了cnt[i] + 1, 就把这个人加入第cnt[i] + 1支队伍里。 题目的性质保证这样可以拼出min{cnt[i]}支队伍。
  • D： 首先对高度离散化，最优情况下最后所有塔的高度都是原来某个塔高度[h - 70, h + 70], f[i][j][h] 表示前i个塔，能看到j个，最高的塔高度是h的最优解。 转移的时候考虑第i个塔是不是最高的，利用前缀最小值优化到O(N4).
附加文件