2019-team666-0019

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

solved:6/11 1156
dirt:64%

[[Image(Submissions.jpg,1000px)]]


== 流水账 ==

开场hyw读了构造题G丢给tjc，yyc看了A的假题wa了一发，不过很快发现了问题。tjc写G，不久做法假了，后来yyc给出了J的解法，hyw上机写LIS竟然写挂了一发，然后又因为数组开小挂了一发，'''J3y44'''。tjc立刻上机把G改了，'''G1Y59'''。这时tjc跟hyw说了一下K可能是个非常trick的找规律题，把K丢给了hyw，自己和yyc去分别看H、I，后来又一起讨论B。hyw推K的式子推了20多分钟结果推错了，喊tjc过来一起推，这时yyc上机写H，tjc通过找规律搞出了公式，hyw上机把K秒了，'''K1y115'''。这时tjc和yyc表示都不会做B，把B丢给hyw，yyc继续写H，tjc做I。后来H不断Wa，中途tjc写了I，喜提Tle。hyw想出了B的大体做法，但一直有一个瓶颈过不去。两人各自继续查错，到3小时20分钟左右hyw想出了B的解决方法，跟tjc说了一下，两人都觉得复杂度很对。这时的tjc趁yyc下机静态查错的时候改了一下I提交，等评测的时候hyw开始上机写B，没想到10分钟就写完并且过了，'''B1y214'''。2分钟后yyc查出错把H改了，'''H7y217'''。tjc的I题仍然超时，于是tjc在机上调I，hyw和yyc考虑到别的题都不会做就一起去读至今未读的D，讨论了一小时无果。比赛快结束的时候tjc利用分块+手写bitset卡过了I，'''I4y273'''。

== 总结 == 


=== yyc ===

=== tjc  ===

G开场发现是构造，脑补了一个欧拉回路做法，上机写完发现是哈密顿回路，想了一会还是构造回了欧拉回路，最后又搞了一会板子才过（貌似抄错了一点？）

中间看I时限20秒打算直接指令集干上去，然后听了hyw对K的问题转化直接手算找到了一个规律（其实转化完的那个东西和1/(1-x)的多次卷积很像，于是直接朝着组合数方向找规律）

上机写I后TLE31，等大家都没题写了以后又去写了线段树+bitset的n^2^logn/w的算法（由于不会用STL自己手写了个bitset），本机MLE，最后冷静下来直接分块+bitset就过了

（upd@19.09.27）这个I有nlog^2^n的随机化做法

=== hyw  ===

这场题数nb但是dirt好高，其实感觉状态也不是很好，尤其是我单调队列LIS竟然挂了两发真是太丢人了……

K题一开始思路不清晰推了好久也要背锅。

B题这个题做得真的一波三折，拿到题当时心里就想“这一看基本就是我的题了”，然后想到暴力应该是n^2^log，感觉可以优化到nlog^2^，从高位到低位贪心做，如果当前位1的个数是奇数就不考虑，最后答案应该就是若干个集合的交，但是这样会T。

然后就开始卡题，后来其实换思路也挺快的，想到可以看成询问集合的包含关系，发现需要O(log)修改O(1)查询，一看n个点大概可以均摊，其实这时候已经想到正解了但是算错了复杂度，以为是n^2^的，后来在纸上手算了一下发现是nlog的边数，但是这个复杂度还是不对。这时候都想换题了，发现能做的题就BHI，HI都在队友手里，最后硬着头皮去想B，因为直觉思路应该没错于是重新从头一步步想了一遍才发现复杂度是对的。上机前我对写这样的题不是很有信心，和队友说“大概要写40min调40min”，没想到10min就写完而且过了，而且代码特别优美，缺乏信心可能主要还是这样的题写的少吧。不过以后这种复杂度不确定的题最好请队友也算一下。

比赛的时候听dhr说这场的主题是Linkin Park，这才发现题目名字的玄机，突然有一种奇怪的说不出的感觉。卡B题的时候看到B题就是那首经典的New Divide，真是百感交集。

Finally, R.i.p Linkin Park


=== 题解 ===

BUAA http://clatisus.com/Petrozavodsk%20Summer-2017.%20Moscow%20IPT%20Contest#a.-a-place-for-my-head


B：做一个前缀异或，从高位到低位枚举每一位，如果前缀异或的这一位是1也就是说前面这么多数里有奇数个1，那么这个divide不管在哪这一位异或和都是1，所以不用考虑，否则我们要尽可能使高位两边异或在这一位都是1，这样相加是最优的。我们依次考虑最高位、前2高的数位、前3高的数位……然后构造一个二进制数，这一位如果不用考虑就设0，否则设1，没考虑到的数位全设0，然后只要知道前面所有的前缀异或组成的集合中是否存在一个数的二进制是包含我们构造出的这个数的，如果存在就说明存在一个分割位可以使得我们考虑的这前i高位都有最优分割。如果不存在说明这一位无法最优分割，把我们构造的二进制数这一位改为0，表示以后不考虑这一位了。根据最后得到的二进制数就可以统计答案了（如果当前位为1就说明当前位前缀有奇数个1并且可以最优分割，说明答案这一位为两个1相加；否则如果前缀异或这一位为1，答案这一位就是一个1）。

现在的问题是怎么判断对于一个给定的二进制数怎么判断是否存在一个前缀异或的二进制表示是包含这个数的。设dp[mask]表示是否有数的二进制表示包含mask，显然如果dp[mask]=1那么mask的任何子集的dp值也为1。并且显然一个mask的dp被改为1以后就不会再被更新了，而且它的子集dp值也一定全为1且不用再更新，所以每个mask只需要更新一次，于是每次记忆化搜索更新dp数组即可。修改复杂度均摊O(1)，查询显然是O(1)。

总复杂度O(nlogn)。

G：每次要么变成*2要么变成*2+1，把相邻两个点合并（出边也合并）后发现可以根据出边来判断当前上一步是从哪里走过来的，跑欧拉回路即可

H：

I：分块，每块维护一个bitset代表出现次数，全 部 暴 力，复杂度O(n^1.5^+n^2^/w)

(upd@19.09.27) 复杂度更优的做法：每个数随机ull权值，树套树维护，复杂度O(nlog^2^n)

考场大概还是写分块比较好，这个题满足差分性质，分块不需要分类讨论，贼好写

J：两个数列LIS长度相加

K：首先第m位以后是不用考虑的，所以可以认为问的是n-k+m个数所有大小为m的子集的最后一个数的排列。容易找出规律，设这一位的取值区间为[l,r]，m=1是为l,...,r，m=2时为l~r,l+1~r,...,r-1~r,r. 以后m每增加1就相当于把前一个的后缀复读一遍。推个公式即可，最后公式是2*c(r-l+m-1,m)-(r-l)，其中l=m,r=n-k+m，即2*c(n-k+m-1,m)-n+k。

[/wiki/2019-team666 返回]

概述

solved:6/11 1156

dirt:64%

流水账

开场hyw读了构造题G丢给tjc，yyc看了A的假题wa了一发，不过很快发现了问题。tjc写G，不久做法假了，后来yyc给出了J的解法，hyw上机写LIS竟然写挂了一发，然后又因为数组开小挂了一发，J3y44。tjc立刻上机把G改了，G1Y59。这时tjc跟hyw说了一下K可能是个非常trick的找规律题，把K丢给了hyw，自己和yyc去分别看H、I，后来又一起讨论B。hyw推K的式子推了20多分钟结果推错了，喊tjc过来一起推，这时yyc上机写H，tjc通过找规律搞出了公式，hyw上机把K秒了，K1y115。这时tjc和yyc表示都不会做B，把B丢给hyw，yyc继续写H，tjc做I。后来H不断Wa，中途tjc写了I，喜提Tle。hyw想出了B的大体做法，但一直有一个瓶颈过不去。两人各自继续查错，到3小时20分钟左右hyw想出了B的解决方法，跟tjc说了一下，两人都觉得复杂度很对。这时的tjc趁yyc下机静态查错的时候改了一下I提交，等评测的时候hyw开始上机写B，没想到10分钟就写完并且过了，B1y214。2分钟后yyc查出错把H改了，H7y217。tjc的I题仍然超时，于是tjc在机上调I，hyw和yyc考虑到别的题都不会做就一起去读至今未读的D，讨论了一小时无果。比赛快结束的时候tjc利用分块+手写bitset卡过了I，I4y273。

总结

yyc

tjc

G开场发现是构造，脑补了一个欧拉回路做法，上机写完发现是哈密顿回路，想了一会还是构造回了欧拉回路，最后又搞了一会板子才过（貌似抄错了一点？）

中间看I时限20秒打算直接指令集干上去，然后听了hyw对K的问题转化直接手算找到了一个规律（其实转化完的那个东西和1/(1-x)的多次卷积很像，于是直接朝着组合数方向找规律）

上机写I后TLE31，等大家都没题写了以后又去写了线段树+bitset的n2logn/w的算法（由于不会用STL自己手写了个bitset），本机MLE，最后冷静下来直接分块+bitset就过了

（upd@19.09.27）这个I有nlog2n的随机化做法

hyw

这场题数nb但是dirt好高，其实感觉状态也不是很好，尤其是我单调队列LIS竟然挂了两发真是太丢人了……

K题一开始思路不清晰推了好久也要背锅。

B题这个题做得真的一波三折，拿到题当时心里就想“这一看基本就是我的题了”，然后想到暴力应该是n2log，感觉可以优化到nlog2，从高位到低位贪心做，如果当前位1的个数是奇数就不考虑，最后答案应该就是若干个集合的交，但是这样会T。

然后就开始卡题，后来其实换思路也挺快的，想到可以看成询问集合的包含关系，发现需要O(log)修改O(1)查询，一看n个点大概可以均摊，其实这时候已经想到正解了但是算错了复杂度，以为是n2的，后来在纸上手算了一下发现是nlog的边数，但是这个复杂度还是不对。这时候都想换题了，发现能做的题就BHI，HI都在队友手里，最后硬着头皮去想B，因为直觉思路应该没错于是重新从头一步步想了一遍才发现复杂度是对的。上机前我对写这样的题不是很有信心，和队友说“大概要写40min调40min”，没想到10min就写完而且过了，而且代码特别优美，缺乏信心可能主要还是这样的题写的少吧。不过以后这种复杂度不确定的题最好请队友也算一下。

比赛的时候听dhr说这场的主题是Linkin Park，这才发现题目名字的玄机，突然有一种奇怪的说不出的感觉。卡B题的时候看到B题就是那首经典的New Divide，真是百感交集。

Finally, R.i.p Linkin Park

题解

BUAA http://clatisus.com/Petrozavodsk%20Summer-2017.%20Moscow%20IPT%20Contest#a.-a-place-for-my-head

B：做一个前缀异或，从高位到低位枚举每一位，如果前缀异或的这一位是1也就是说前面这么多数里有奇数个1，那么这个divide不管在哪这一位异或和都是1，所以不用考虑，否则我们要尽可能使高位两边异或在这一位都是1，这样相加是最优的。我们依次考虑最高位、前2高的数位、前3高的数位……然后构造一个二进制数，这一位如果不用考虑就设0，否则设1，没考虑到的数位全设0，然后只要知道前面所有的前缀异或组成的集合中是否存在一个数的二进制是包含我们构造出的这个数的，如果存在就说明存在一个分割位可以使得我们考虑的这前i高位都有最优分割。如果不存在说明这一位无法最优分割，把我们构造的二进制数这一位改为0，表示以后不考虑这一位了。根据最后得到的二进制数就可以统计答案了（如果当前位为1就说明当前位前缀有奇数个1并且可以最优分割，说明答案这一位为两个1相加；否则如果前缀异或这一位为1，答案这一位就是一个1）。

现在的问题是怎么判断对于一个给定的二进制数怎么判断是否存在一个前缀异或的二进制表示是包含这个数的。设dp[mask]表示是否有数的二进制表示包含mask，显然如果dp[mask]=1那么mask的任何子集的dp值也为1。并且显然一个mask的dp被改为1以后就不会再被更新了，而且它的子集dp值也一定全为1且不用再更新，所以每个mask只需要更新一次，于是每次记忆化搜索更新dp数组即可。修改复杂度均摊O(1)，查询显然是O(1)。

总复杂度O(nlogn)。

G：每次要么变成*2要么变成*2+1，把相邻两个点合并（出边也合并）后发现可以根据出边来判断当前上一步是从哪里走过来的，跑欧拉回路即可

H：

I：分块，每块维护一个bitset代表出现次数，全 部 暴 力，复杂度O(n1.5+n2/w)

(upd@19.09.27) 复杂度更优的做法：每个数随机ull权值，树套树维护，复杂度O(nlog2n)

考场大概还是写分块比较好，这个题满足差分性质，分块不需要分类讨论，贼好写

J：两个数列LIS长度相加

K：首先第m位以后是不用考虑的，所以可以认为问的是n-k+m个数所有大小为m的子集的最后一个数的排列。容易找出规律，设这一位的取值区间为[l,r]，m=1是为l,...,r，m=2时为l~r,l+1~r,...,r-1~r,r. 以后m每增加1就相当于把前一个的后缀复读一遍。推个公式即可，最后公式是2*c(r-l+m-1,m)-(r-l)，其中l=m,r=n-k+m，即2*c(n-k+m-1,m)-n+k。

附加文件