2019-team666-0035

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

solved:6/12  dirt:40% 赛后1min过了J

rank:69/116

[[Image(Submissions.2.jpg,800px)]]

[[Image(Standings.jpg,800px)]]



== 流水账 ==

开场hyw拿到几何体E感觉可以三分就上去写，发现样例过不去（精度不够），于是大家以为三分精度不行决定手推。这时榜上过了C、D，tjc分情况讨论后让yyc上去写了C，WA以后很快发现漏了一种情况，'''C2y37'''，yyc听到题意后秒了K，'''K2y56'''。这时榜上过了H，hyw和tjc说了一下题意，tjc觉得H随便构造就完事了，于是'''H1y64'''。hyw推了一年式子推不出决定用tjc的几何做法，上机写了大约10分钟以后yyc说了句“你要不检查一下三分”，一看发现把double写成了int，于是'''E1y80'''。然后tjc把D丢给hyw，hyw接着写D的矩乘，写了一会儿发现样例过不了，反复修改了好几次矩阵还是有问题，大约卡了有1个小时，这时tjc和yyc搞出了I和J，yyc上机写J，上机前跟hyw说了几句“你把数都放在第一列就行了”，hyw瞬间被点醒，很快推出了正确的矩阵，这时yyc表示自己的J快写完了一直占着机位，又过了大约10-15分钟后J还没有好，于是打印J，hyw改D，交上去T了。众人多次卡常无果，hyw想到矩阵大小其实可以优化，于是'''D4y226'''。yyc发现J假了，写I，hyw从tjc那里听说了J的题意后光速想出了解法，于是光速上机rush，和I题交题上机，最后'''I1y290'''，J题由于和yyc的代码衔接有一些问题导致比赛结束后一分钟才过。

== 总结 == 

=== yyc ===

=== tjc  ===

E比较有趣啊 记得有个结论是最大角<120度的时候以一边为底边向外作一个正三角形，再连那条没连上的对角线，那么答案一定在这条对角线上。
一开始听说三分过不去就给出了这个做法，不过好像要写好久。。结果最后还是靠三分过的

剩下题有点忘了。。待会再补

=== hyw  ===

这场我是假人，E上来的时候想的是“三分怎么可能写错”，当时应该更冷静下来检查一下的，这算一个重大失误。

D题卡了好久也是我的问题，这类推矩阵的题以前遇到的时候思考还是不够，导致这次推了好久，这类套路题以后一定要掌握。（其实D还有组合数的做法）

J题丢给我丢的晚了，不然也应该是能出的。

这场我们队的节奏感觉非常缓慢，D和J两个题严重拖慢了进度，这启示我们队还是要加强队员之间的交流，最好不要一个人在队友不知情的情况下对一个题死磕，很多时候会出现过于自信最后卡了一年卡不出的状况。

upd: 补了B和G，难度其实都不大……感觉还是菜啊

=== 题解 ===

A:

B: 构造，k=2时特判。k为奇数时，首先如果只考虑1*n的矩阵，相邻两个数的组合都要出现，那找个欧拉回路就好了，然后把这个序列向右循环shift 1格得到第2行，把第2行向右循环shift 2格得到第3行，...，最后一行和第一行相同。证明无，大概需要感性理解。（[https://pan.zju.edu.cn/share/9beaec8ed14d18eaf32383b82e 题解视频下载]）

C: 分类讨论，翻转次数不超过3，corner case在k=2或n-2时可以翻转重叠的两段

D: 矩乘，把所有数放在第一列，注意到dp[i]+=dp[i-1]这里的更新结束后所有数都是1，所以可以把100*100的矩阵优化到75*75。

E: 三分套三分套三分

F: （其实搞个dp就好了，但是我硬构造的）

对于一个子树大小mod3!=0的点，随便去掉一条边把子树分为两个部分，使得其中一个部分大小<3，另一个部分mod3=0，转换成mod3=0的情况

claim：任意一棵子树在上述操作以后可以使得三种颜色数一样

mod3=0（去掉根后）可以分为0+0+2/0+1+1/1+2+2（mod3）三种情况

由于颜色具有对称性，子树外对子树内的影响不超过2个点时可以通过某种对子树内颜色的置换调整至可行方案

0+1+1的情况显然，0+2+2的情况去掉的“叶子”要么可以选两个连到同一个节点上的叶子（称作A情况），要么可以选一条长度为2的无分叉链（称作B情况）

1+2+2的情况（不妨设根的颜色为1）的两个2可能是AA，BB，或AB（称剩下那棵子树为C）；AA的情况可以把C的颜色设为1，2个A分别设为22和33；AB情况把A设为22，B设为13，C设为3；BB情况把2个B设为23和32，C设为1

讨论完了，至此我们递归证明了上面的claim，题也就做完了。~~（md谁爱写谁写去吧）~~ 口胡选手的感性理解是先dfs一遍统计子树大小并推一推可以去掉的点，然后从上往下构造



G: dp[i][j]表示前i个选j个，最后两个高度差的最小值。用线段树转移，记录前驱输出方案。

H: 跑个dfs，记录每个点进入时间和离开时间，奇数深度的点取进入时间，偶数深度的店取离开时间即可

I: 维护凸包后转换成一个关于区间的经典贪心问题，随便做

J: 找到所有的区间以后按左端点排序，设dp[i]为当前考虑到字符串第i个字符，第i个字符要选，且左端点小于等于i的所有区间中都已经至少一个选中的数的最小花费，那么dp[i]=dp[j]+cost(i),j需要满足所有左端点在j+1~i中的区间的右端点的最小值>=i，否则说明存在一个左端点大于j且右端点小于i的区间内部没有选中的点，需要将j右移。这个j可以二分得到，查右端点最小值用线段树，复杂度O（nlognlogn）

K: 贪心 @yyc

L:

[/wiki/2019-team666 返回]

概述

solved:6/12 dirt:40% 赛后1min过了J

rank:69/116

流水账

开场hyw拿到几何体E感觉可以三分就上去写，发现样例过不去（精度不够），于是大家以为三分精度不行决定手推。这时榜上过了C、D，tjc分情况讨论后让yyc上去写了C，WA以后很快发现漏了一种情况，C2y37，yyc听到题意后秒了K，K2y56。这时榜上过了H，hyw和tjc说了一下题意，tjc觉得H随便构造就完事了，于是H1y64。hyw推了一年式子推不出决定用tjc的几何做法，上机写了大约10分钟以后yyc说了句“你要不检查一下三分”，一看发现把double写成了int，于是E1y80。然后tjc把D丢给hyw，hyw接着写D的矩乘，写了一会儿发现样例过不了，反复修改了好几次矩阵还是有问题，大约卡了有1个小时，这时tjc和yyc搞出了I和J，yyc上机写J，上机前跟hyw说了几句“你把数都放在第一列就行了”，hyw瞬间被点醒，很快推出了正确的矩阵，这时yyc表示自己的J快写完了一直占着机位，又过了大约10-15分钟后J还没有好，于是打印J，hyw改D，交上去T了。众人多次卡常无果，hyw想到矩阵大小其实可以优化，于是D4y226。yyc发现J假了，写I，hyw从tjc那里听说了J的题意后光速想出了解法，于是光速上机rush，和I题交题上机，最后I1y290，J题由于和yyc的代码衔接有一些问题导致比赛结束后一分钟才过。

总结

yyc

tjc

E比较有趣啊 记得有个结论是最大角<120度的时候以一边为底边向外作一个正三角形，再连那条没连上的对角线，那么答案一定在这条对角线上。

一开始听说三分过不去就给出了这个做法，不过好像要写好久。。结果最后还是靠三分过的

剩下题有点忘了。。待会再补

hyw

这场我是假人，E上来的时候想的是“三分怎么可能写错”，当时应该更冷静下来检查一下的，这算一个重大失误。

D题卡了好久也是我的问题，这类推矩阵的题以前遇到的时候思考还是不够，导致这次推了好久，这类套路题以后一定要掌握。（其实D还有组合数的做法）

J题丢给我丢的晚了，不然也应该是能出的。

这场我们队的节奏感觉非常缓慢，D和J两个题严重拖慢了进度，这启示我们队还是要加强队员之间的交流，最好不要一个人在队友不知情的情况下对一个题死磕，很多时候会出现过于自信最后卡了一年卡不出的状况。

upd: 补了B和G，难度其实都不大……感觉还是菜啊

题解

A:

B: 构造，k=2时特判。k为奇数时，首先如果只考虑1*n的矩阵，相邻两个数的组合都要出现，那找个欧拉回路就好了，然后把这个序列向右循环shift 1格得到第2行，把第2行向右循环shift 2格得到第3行，...，最后一行和第一行相同。证明无，大概需要感性理解。（题解视频下载）

C: 分类讨论，翻转次数不超过3，corner case在k=2或n-2时可以翻转重叠的两段

D: 矩乘，把所有数放在第一列，注意到dp[i]+=dp[i-1]这里的更新结束后所有数都是1，所以可以把100*100的矩阵优化到75*75。

E: 三分套三分套三分

F: （其实搞个dp就好了，但是我硬构造的）

对于一个子树大小mod3!=0的点，随便去掉一条边把子树分为两个部分，使得其中一个部分大小<3，另一个部分mod3=0，转换成mod3=0的情况

claim：任意一棵子树在上述操作以后可以使得三种颜色数一样

mod3=0（去掉根后）可以分为0+0+2/0+1+1/1+2+2（mod3）三种情况

由于颜色具有对称性，子树外对子树内的影响不超过2个点时可以通过某种对子树内颜色的置换调整至可行方案

0+1+1的情况显然，0+2+2的情况去掉的“叶子”要么可以选两个连到同一个节点上的叶子（称作A情况），要么可以选一条长度为2的无分叉链（称作B情况）

1+2+2的情况（不妨设根的颜色为1）的两个2可能是AA，BB，或AB（称剩下那棵子树为C）；AA的情况可以把C的颜色设为1，2个A分别设为22和33；AB情况把A设为22，B设为13，C设为3；BB情况把2个B设为23和32，C设为1

讨论完了，至此我们递归证明了上面的claim，题也就做完了。（md谁爱写谁写去吧） 口胡选手的感性理解是先dfs一遍统计子树大小并推一推可以去掉的点，然后从上往下构造

G: dp[i][j]表示前i个选j个，最后两个高度差的最小值。用线段树转移，记录前驱输出方案。

H: 跑个dfs，记录每个点进入时间和离开时间，奇数深度的点取进入时间，偶数深度的店取离开时间即可

I: 维护凸包后转换成一个关于区间的经典贪心问题，随便做

J: 找到所有的区间以后按左端点排序，设dp[i]为当前考虑到字符串第i个字符，第i个字符要选，且左端点小于等于i的所有区间中都已经至少一个选中的数的最小花费，那么dp[i]=dp[j]+cost(i),j需要满足所有左端点在j+1~i中的区间的右端点的最小值>=i，否则说明存在一个左端点大于j且右端点小于i的区间内部没有选中的点，需要将j右移。这个j可以二分得到，查右端点最小值用线段树，复杂度O（nlognlogn）

K: 贪心 @yyc

L:

附加文件