2019-team666-0042

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:5/11 818  dirt:67% 
rank:16/64
[[Image(Submissions.jpg,500px)]]
[[Image(Standings.jpg,800px)]]

== 流水账 ==
上来yyc写D，写了15分钟卡了。这时看榜上很多人过了B，hyw读B，跟tjc说了一下，两人想了10分钟之后tjc突然发现是个傻逼题，于是'''B1y28'''。yyc修正了D，得到了WA。hyw跟tjc交换了一下题意，tjc把J题数位dp丢给了hyw，又很快得出了G的做法，然后写了一发也wa了。tjc和yyc轮流上机调试，hyw在机下做写J题的准备，后来'''D2y66''','''G2y67'''（G题死于n=1的corner case）。然后hyw开始写数位dp，tjc和yyc思考C、H和I，陆续开出了H题和C题。hyw1小时40分钟左右写完了J，2个小时左右调试完交了一发T了，于是tjc和yyc都凑过来看，看了一下别的队也在T估计这题卡常，一开始三人一起卡了10多分钟，然后hyw下机去想E题，yyc和tjc继续卡常，终于在2小时42分钟通过了J，'''J4y162'''。然后tjc光速写了一发H，也T了，看别的队在后面的点T或者Wa，并且想不出卡常方法，于是想了一会儿就弃题了。写H的时候hyw发现了E的三个性质，跟yyc讨论了一下。H题T了以后机位空了出来，hyw上机打了一个E的表，在tjc帮助下找了一个规律写了一发wa了。打印，换yyc写C。之后tjc发现了E做法的问题并想出了一个fix的方法，多次修正后仍然wa。最后关头hyw发现了tjc做法中的问题，冷静分析后给出了一个fix，最后'''E6y295'''。yyc的C题没有调完。
== 总结 ==
=== yyc ===
=== tjc  ===
=== hyw  ===
前期D慢了一点以外还好。
中期：主要慢在J题卡常，一方面我长时间没写数位dp有一些遗忘写的慢了一些，另一方面花了较长的时间卡常，这次卡常主要是在卡mod的常数，以后可以直接借鉴这次的经验减少这方面花的时间。
后期先开了H题，Tle了，这个题复杂度和标答是一样的（事实上最后tjc想出了一个log的做法），留坑@tjc快去把1个log的做法写了然后来喷出题人。
C题也算套路题吧，像C和J这样的套路题还可以更快一点。
E题这个题出的好棒啊，也确实有一定难度，（因为菜）花了较长的时间，不过过了贼爽。
=== 题解 ===
A：对称轴一定是水平线/竖直线/对角线，如果两个矩形没有公共边那么直接判断边是否匹配，否则将边界合并。
B：每次取的点数一定是奇数个，所以判边条数的奇偶性就行了。
C：点分治模板题，题意是统计u到v的路径上的点权能构成多边形的路径总数。做法是求一个到树根的前缀和、前缀最大值，能形成多边形等价于（路径上所有点权和）>2（路径上最大点权）。u到v的路径满足题意当且仅当sum[u]+sum[v]-a[root]>2max(M[u],M[v]),按M排序以后可以得到M[u]>M[v]，对于固定的u统计有多少个v符合题意即可，用树状数组维护，复杂度O(nlognlogn)。本题略卡常，改进方式是solve函数可以对树根和孩子一起写，不用分开来，这样可以避免多次离散化。
D：@yyc
E：贪心。
对于当前考虑的数Ai，我们把比他小的看做0，大的看做1。那么选择连续三个数可以分为几类：（1）三个数都在Ai左边/右边。（2）Ai是三个数中最左/最右的一个数。（3）Ai是三个数中中间的一个数。
性质1：第（2）类区间是不用考虑的。因为如果选择的区间包含了Ai，那么要使Ai留下，剩下两个数只能是0和1，于是（2）类区间可以视为消去了一个0和一个1。对于任何一个含有至少1个0和至少1个1的区间来说，消去最大和最小就是消去1和0。所以第（2）类区间可以等价为选择了0、1和另一侧的一个数（如果存在）这个区间。
性质2：对于第（3）类区间，除了Ai剩下两个数一定是0和1，理由同上。由于第（3）类区间是在Ai左右两边各消去一个数，我们可以假设消去的数仍然保留在原位置，并且后面选择的区间都不包含该数，直到最后再依次从Ai两侧消去数字。要使Ai保留就说明对左右两边分别进行若干次操作后留下来的数字是相对应的（在Ai两侧分别为一对对0和1），这说明Ai左右的两个区间是可以分开考虑的。
于是我们只需要考虑Ai的两边区间，对于区间长度是偶数，判断它能否经过若干次操作变为00/01（或10）/11. 对于区间长度是奇数，判断它能否经过若干次操作变为0/1. 对于A1和An只需要判断另一侧区间能否变为01（或10）就行了。
（1）判断能否变为00：要使0比1尽可能多，就要尽可能消去1，对于连续的3个1可以直接消成1个1。这个做法是不够的，因为可能出现0110110这样的情况，消去中间的0和相邻的1以后可以凑出新的3个1的区间。所以我们维护1个计数器s，遇到1则s++,if(s==3)s-=2,tot++，遇到0则s=max(0,s-1). tot就是消去2个1的次数。判断能否变为11同理。
（2）判断能否变为01（或10）：要使0和1的个数尽可能相等，于是先计算0、1个数差，如果为0那一定可以。如果0比1多，仿照上一步算出最多能消去多少个0，和当前0、1的个数差比较，如果最多消去0的个数>=当前0的个数-当前1的个数则可以。1比0多类似。
（3）判断能否变为0/1（奇数）：和第（1）步中区间长为偶数时判断能否变为00/11是等价的。
枚举原数列每个数对两边的区间分开讨论即可，如果两边可以对应这个数最后就可以保留。（00和11对应，01（或10）和01（或10）对应，这里01和10、10和01是等价的，因为对于"0,1,(Ai),1,0"的情况，可以认为是先选了左边3个再选右边3个），总复杂度O(n^2^).
F：
G：构造，就是构造a，b，c使得k=a*b+c，注意细节。
H：@tjc
I：
J：数位dp，注意取模卡常
K：

[/wiki/2019-team666 返回]

概述

solved:5/11 818 dirt:67%

rank:16/64

流水账

上来yyc写D，写了15分钟卡了。这时看榜上很多人过了B，hyw读B，跟tjc说了一下，两人想了10分钟之后tjc突然发现是个傻逼题，于是B1y28。yyc修正了D，得到了WA。hyw跟tjc交换了一下题意，tjc把J题数位dp丢给了hyw，又很快得出了G的做法，然后写了一发也wa了。tjc和yyc轮流上机调试，hyw在机下做写J题的准备，后来D2y66,G2y67（G题死于n=1的corner case）。然后hyw开始写数位dp，tjc和yyc思考C、H和I，陆续开出了H题和C题。hyw1小时40分钟左右写完了J，2个小时左右调试完交了一发T了，于是tjc和yyc都凑过来看，看了一下别的队也在T估计这题卡常，一开始三人一起卡了10多分钟，然后hyw下机去想E题，yyc和tjc继续卡常，终于在2小时42分钟通过了J，J4y162。然后tjc光速写了一发H，也T了，看别的队在后面的点T或者Wa，并且想不出卡常方法，于是想了一会儿就弃题了。写H的时候hyw发现了E的三个性质，跟yyc讨论了一下。H题T了以后机位空了出来，hyw上机打了一个E的表，在tjc帮助下找了一个规律写了一发wa了。打印，换yyc写C。之后tjc发现了E做法的问题并想出了一个fix的方法，多次修正后仍然wa。最后关头hyw发现了tjc做法中的问题，冷静分析后给出了一个fix，最后E6y295。yyc的C题没有调完。

总结

yyc

tjc

hyw

前期D慢了一点以外还好。

中期：主要慢在J题卡常，一方面我长时间没写数位dp有一些遗忘写的慢了一些，另一方面花了较长的时间卡常，这次卡常主要是在卡mod的常数，以后可以直接借鉴这次的经验减少这方面花的时间。

后期先开了H题，Tle了，这个题复杂度和标答是一样的（事实上最后tjc想出了一个log的做法），留坑@tjc快去把1个log的做法写了然后来喷出题人。

C题也算套路题吧，像C和J这样的套路题还可以更快一点。

E题这个题出的好棒啊，也确实有一定难度，（因为菜）花了较长的时间，不过过了贼爽。

题解

A：对称轴一定是水平线/竖直线/对角线，如果两个矩形没有公共边那么直接判断边是否匹配，否则将边界合并。

B：每次取的点数一定是奇数个，所以判边条数的奇偶性就行了。

C：点分治模板题，题意是统计u到v的路径上的点权能构成多边形的路径总数。做法是求一个到树根的前缀和、前缀最大值，能形成多边形等价于（路径上所有点权和）>2（路径上最大点权）。u到v的路径满足题意当且仅当sum[u]+sum[v]-a[root]>2max(M[u],M[v]),按M排序以后可以得到M[u]>M[v]，对于固定的u统计有多少个v符合题意即可，用树状数组维护，复杂度O(nlognlogn)。本题略卡常，改进方式是solve函数可以对树根和孩子一起写，不用分开来，这样可以避免多次离散化。

D：@yyc

E：贪心。

对于当前考虑的数Ai，我们把比他小的看做0，大的看做1。那么选择连续三个数可以分为几类：（1）三个数都在Ai左边/右边。（2）Ai是三个数中最左/最右的一个数。（3）Ai是三个数中中间的一个数。

性质1：第（2）类区间是不用考虑的。因为如果选择的区间包含了Ai，那么要使Ai留下，剩下两个数只能是0和1，于是（2）类区间可以视为消去了一个0和一个1。对于任何一个含有至少1个0和至少1个1的区间来说，消去最大和最小就是消去1和0。所以第（2）类区间可以等价为选择了0、1和另一侧的一个数（如果存在）这个区间。

性质2：对于第（3）类区间，除了Ai剩下两个数一定是0和1，理由同上。由于第（3）类区间是在Ai左右两边各消去一个数，我们可以假设消去的数仍然保留在原位置，并且后面选择的区间都不包含该数，直到最后再依次从Ai两侧消去数字。要使Ai保留就说明对左右两边分别进行若干次操作后留下来的数字是相对应的（在Ai两侧分别为一对对0和1），这说明Ai左右的两个区间是可以分开考虑的。

于是我们只需要考虑Ai的两边区间，对于区间长度是偶数，判断它能否经过若干次操作变为00/01（或10）/11. 对于区间长度是奇数，判断它能否经过若干次操作变为0/1. 对于A1和An只需要判断另一侧区间能否变为01（或10）就行了。

（1）判断能否变为00：要使0比1尽可能多，就要尽可能消去1，对于连续的3个1可以直接消成1个1。这个做法是不够的，因为可能出现0110110这样的情况，消去中间的0和相邻的1以后可以凑出新的3个1的区间。所以我们维护1个计数器s，遇到1则s++,if(s==3)s-=2,tot++，遇到0则s=max(0,s-1). tot就是消去2个1的次数。判断能否变为11同理。

（2）判断能否变为01（或10）：要使0和1的个数尽可能相等，于是先计算0、1个数差，如果为0那一定可以。如果0比1多，仿照上一步算出最多能消去多少个0，和当前0、1的个数差比较，如果最多消去0的个数>=当前0的个数-当前1的个数则可以。1比0多类似。

（3）判断能否变为0/1（奇数）：和第（1）步中区间长为偶数时判断能否变为00/11是等价的。

枚举原数列每个数对两边的区间分开讨论即可，如果两边可以对应这个数最后就可以保留。（00和11对应，01（或10）和01（或10）对应，这里01和10、10和01是等价的，因为对于"0,1,(Ai),1,0"的情况，可以认为是先选了左边3个再选右边3个），总复杂度O(n2).

F：

G：构造，就是构造a，b，c使得k=a*b+c，注意细节。

H：@tjc

I：

J：数位dp，注意取模卡常

K：

附加文件