2019-team666-0011

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
八月集训第4场
rank:校内选拔1/14 总9/26
== 流水账 ==
出门hyw看E是个和之前有一场类似的题，就直接喊tjc上去写，'''E1y19'''，接着yyc开出B，hyw上机写，挂了一发，tjc开出H，也挂了一发，hyw发现B输出没有换行，改完'''B2y42'''，tjc发现H的vector把第size位也遍历了，改完'''H3y47'''。然后yyc写了一波F，tjc开出D以后找了一下CRT的板子，就去写D的python了，两题都比较顺利，'''F1y89'''，'''D1y108'''。期间hyw想J，后来发现读了假题，重新推式子，觉得可以斜率优化，上机写，改了好几次，期间其余两人开题，3小时的时候发现J的式子推错了，yyc和tjc讨论A无果，tjc有一个C的想法但不确定，就上去写了，没有想到竟然过了，'''C1y204'''，hyw也顺利推出了J的式子，3个半小时交了第一发，Wa了，在机上又调了半小时，交了两次接着wa，这时yyc和tjc讨论出G，也很顺利的过了，'''G1y261'''。J题静态动态查错都没查出来，最后半小时众人对拍了一下，终于改过了，'''J8y293'''。
== 总结 == 
=== yyc ===

=== tjc  ===
听说字符串题容易被乱搞过/呲牙 以后遇到不会做的字符串题可以参考这次
如果榜上很多人过了某个题可以想想自己的复杂做法能不能简化
=== hyw  ===
'''斜率优化dp要特别注意横坐标相等的情况'''，本来以为横坐标相等算斜率应该会RE，没想到因为用了double横坐标之差会被当成eps，所以斜率炸了，以后要特别注意。
静态+动态调不出题要勇于对拍。
=== 题解 ===
A：枚举最后一个选的数，设dp[i][j]为在除了这个数以外的n-1个数里选i个和恰好为j的方案数，可以O(n^4^)转移，用可逆背包可以优化到O(n^3^)。（可逆背包套路题）
B：递归做，注意长度>1e12了以后，设第一个超过1e12的位置为x，第二个y，n奇偶性和x相同时第k位在第x个字符串里，否则在第y个字符串里。
C：周期是logn段等差数列，维护即可（原数据甚至认为首项=公差也能过，卡法aaa...aaabaaa...aaa）
D：CRT板子，用python判是否答案>m
E：递归
F：枚举竖着的三列，删掉上面的点，然后在横着的里面取三个最大的。
G：结论题，最后的直线要么平行于两点连线，要么是两点中垂线，证明是取最大值是必然有两点到直线距离相等，如果不平行/垂直于两点连线必然可以通过调整使结果更优，并且可以证明两点位于直线异侧的时候过两点中点的直线通过旋转取最值时一定是中垂线（但我不会证）。
H：暴力
I：随机化给图01染色，然后暴力，见Runespoor
J：先按高度排序，合并所有高度相同的点（※注意），设dp[i][j]表示前i根木板合并成j块的最小浪费，注意到一定合并高度排名连续的一段最优，有dp[i][j]=min(k=0 to i-1) dp[k][j-1] + /sum (p=k+1 to i)(h[p]-h[k+1])*w[p]， 然后斜率优化dp。

[/wiki/2019-team666 返回]

概述

八月集训第4场

rank:校内选拔1/14 总9/26

流水账

出门hyw看E是个和之前有一场类似的题，就直接喊tjc上去写，E1y19，接着yyc开出B，hyw上机写，挂了一发，tjc开出H，也挂了一发，hyw发现B输出没有换行，改完B2y42，tjc发现H的vector把第size位也遍历了，改完H3y47。然后yyc写了一波F，tjc开出D以后找了一下CRT的板子，就去写D的python了，两题都比较顺利，F1y89，D1y108。期间hyw想J，后来发现读了假题，重新推式子，觉得可以斜率优化，上机写，改了好几次，期间其余两人开题，3小时的时候发现J的式子推错了，yyc和tjc讨论A无果，tjc有一个C的想法但不确定，就上去写了，没有想到竟然过了，C1y204，hyw也顺利推出了J的式子，3个半小时交了第一发，Wa了，在机上又调了半小时，交了两次接着wa，这时yyc和tjc讨论出G，也很顺利的过了，G1y261。J题静态动态查错都没查出来，最后半小时众人对拍了一下，终于改过了，J8y293。

总结

yyc

tjc

听说字符串题容易被乱搞过/呲牙 以后遇到不会做的字符串题可以参考这次

如果榜上很多人过了某个题可以想想自己的复杂做法能不能简化

hyw

斜率优化dp要特别注意横坐标相等的情况，本来以为横坐标相等算斜率应该会RE，没想到因为用了double横坐标之差会被当成eps，所以斜率炸了，以后要特别注意。

静态+动态调不出题要勇于对拍。

题解

A：枚举最后一个选的数，设dp[i][j]为在除了这个数以外的n-1个数里选i个和恰好为j的方案数，可以O(n⁴)转移，用可逆背包可以优化到O(n³)。（可逆背包套路题）

B：递归做，注意长度>1e12了以后，设第一个超过1e12的位置为x，第二个y，n奇偶性和x相同时第k位在第x个字符串里，否则在第y个字符串里。

C：周期是logn段等差数列，维护即可（原数据甚至认为首项=公差也能过，卡法aaa...aaabaaa...aaa）

D：CRT板子，用python判是否答案>m

E：递归

F：枚举竖着的三列，删掉上面的点，然后在横着的里面取三个最大的。

G：结论题，最后的直线要么平行于两点连线，要么是两点中垂线，证明是取最大值是必然有两点到直线距离相等，如果不平行/垂直于两点连线必然可以通过调整使结果更优，并且可以证明两点位于直线异侧的时候过两点中点的直线通过旋转取最值时一定是中垂线（但我不会证）。

H：暴力

I：随机化给图01染色，然后暴力，见Runespoor

J：先按高度排序，合并所有高度相同的点（※注意），设dp[i][j]表示前i根木板合并成j块的最小浪费，注意到一定合并高度排名连续的一段最优，有dp[i][j]=min(k=0 to i-1) dp[k][j-1] + /sum (p=k+1 to i)(h[p]-h[k+1])*w[p]， 然后斜率优化dp。