2019-team666-0040

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:8/12 1008  dirt:47% 
rank:43/837
[[Image(Submissions.jpg,500px)]]

== 流水账 ==
开场tjc写了几分钟L做法假了，yyc'''B1y18''',hyw告诉tjc L的做法以后'''L2y27'''，然后hyw'''E1y41'''. 跟榜，tjc读了K丢给hyw推式子，hyw把大构造F和H丢给了tjc，yyc和tjc稍加讨论J后yyc上机，于是'''J2y72'''，很快hyw写完了K，'''K1y90'''。tjc弄出了一个F题看上去很对的做法，跟yyc说了以后上机，'''F2y111'''。这时看了一眼榜，A题有奇怪的人过，hyw和yyc讨论A，tjc想H的构造，一段时间后想不出去想I题。hyw和yyc讨论了A，hyw确认了一遍做法后上机，写得比较痛苦，花了半小时写完，交上去T了。在机上调了一会儿交了两次都获得了wa。这时换tjc上机写I。yyc开始思考G题。很快A修正了几个错误还是Wa，这时I也wa了，hyw请yyc查代码但并没有查出错，过了tjc一会儿改完了I，'''I2y215'''，hyw上机试着试着造出了一组反例，改完后依然wa。这时hyw和yyc讨论了一下觉得是一个break的问题，但是删去可能会T，tjc建议先删去交一次看看会不会T，结果真的T了，yyc试图改进了做法但是hyw觉得可能要重构，权衡之下不如写一个线段树来得快，于是喊线段树手速带师yyc用了三分钟敲完了线段树，改完后'''A6y274'''。最后yyc和tjc写了一会儿D做法假了，hyw修正了yyc的G题做法但是来不及写了。
== 总结 ==
=== yyc ===
=== tjc  ===
=== hyw  ===
以后在机上调试的人看到题目wa了以后要主动向队友问有没有题可以写，手上有题可以写的人也要及时主动跟上机的人说，避免耽误机时。
有多种修改方法的时候第一考虑是最好理解/最好写的（可以代码不一定很短），尽可能避免需要重构的“正解”，比如复杂度够的题敲一棵线段树就能解决的问题不去魔改模拟过程。
另外这场和yyc讨论A的时候只讨论了做法还是没讨论清楚写法导致最后出了很多锅，讨论的时候不能抱着“我不想写，让队友去写”的心态就不去好好讨论写法。
2020/1/22UPD：补了D，细节相当多+相当考验思维的一道好题，当时好像没看？？？
=== 题解 ===
A：dp，离散化之后转移，先预处理出每一段时间里面能开工的人里面耗时最短的人，设这个人做的时间为t[j]，设dp[i]为到i时刻最多能做几个任务，于是有dp[i]=min(dp[i-1],dp[i-t[j]]+1)，显然这样复杂度不对，注意到这个方程的第二项是+1，于是我们可以这样考虑：在每一段的段内尽可能做，直到某个时间点i满足如果在i时间开工，那么这个任务做完的时间(i+tj)就会在后面的段里面，这时有两种选择：一是做这个任务并且转移到后面的段，二是不做这个任务转移到下一段。显然对于在i ~ i+tj 当中的段，如果存在一个段满足做一个任务的结束时间早于i+tj，那么在i时刻选择不做下一个任务，直到这个段的段首再做下一个任务一定更优。于是我们选择做下一个任务最早结束的时间即可，可以用线段树维护这个最短时间。复杂度O(nlogn)（注：转移其实可以优化到O(n)的，但是预处理带log，所以总复杂度也带log）
B：签到
C：
D：每台机器只可能有两种输出值：一种是它的设定值，一种是它的设定值&它的检测值，分别记作CD值和CT值。因为只有3个feature，所以实际上只有2^3^=8种类型的点，构造方法显然是对000-111的每个组合找一个源点，且这些源点直接可以从111开始依次可达，然后所有CD值为i的点就从i的源点连一条边到这个点就行了。这个点要满足（1）它可以从1号点经过若干条边到达（2）它的CD值和CT值应该不同（否则这个点一定不是关键点，因为它的输入和输出相同，这个点是没有意义的）。其中111的源点显然是1号点，000不需要源点，对于某个值如果不存在以这个值为CD值的点，这个值同样不需要源点。难点在于如何对001-110的这些组合找源点。源点可以有两种可能：（1）这个点的CD值已经可达，CD不等于CT，且CT值还未找到源点，那么可以直接将CT值的源点设为这个点，并将这个点CT设为enabled。（2）如果对于某个值i，用（1）的方法找不到源点，此时如果这个值是001、010或者100，那么无解，否则，由于二进制中有两个1，我们可以对源点的输入方式进行拆分。以i=011为例，我们可以寻找某个点j，它的CD值等于i，并且满足(a)已经找到001和010的源点(b)001和010的源点均不等于j点的CT值。如果满足这两个条件，我们可以将001和010的源点分别连一条边到j，将i的源点设为j，将j的CT设为unenabled。经过6次循环查找之后，如果仍然存在某个需要有源点的值没有源点那么无解。
E：枚举哪个人最后会胜出，按照这个人的得票和第n个人的得票的差排序。
F：随意拼出一个prufer序列，然后构造@tjc
G：
H：
I：@tjc
J：@yyc
K：hash本质上是\sigma i=1 to length i*ki，其中ki<=i。然后组合数算一下就好了，注意kn不能为0，最后答案里要减掉。
L：每次先找到第k大的字符串最小能填什么字符填进去，然后剩下的依次填，每次维护一下已经填的部分相同的段，这些段需要符合大小关系，其他字符串由于大小关系已经确定了随便填就行。

[/wiki/2019-team666 返回]

概述

solved:8/12 1008 dirt:47%

rank:43/837

流水账

开场tjc写了几分钟L做法假了，yycB1y18,hyw告诉tjc L的做法以后L2y27，然后hywE1y41. 跟榜，tjc读了K丢给hyw推式子，hyw把大构造F和H丢给了tjc，yyc和tjc稍加讨论J后yyc上机，于是J2y72，很快hyw写完了K，K1y90。tjc弄出了一个F题看上去很对的做法，跟yyc说了以后上机，F2y111。这时看了一眼榜，A题有奇怪的人过，hyw和yyc讨论A，tjc想H的构造，一段时间后想不出去想I题。hyw和yyc讨论了A，hyw确认了一遍做法后上机，写得比较痛苦，花了半小时写完，交上去T了。在机上调了一会儿交了两次都获得了wa。这时换tjc上机写I。yyc开始思考G题。很快A修正了几个错误还是Wa，这时I也wa了，hyw请yyc查代码但并没有查出错，过了tjc一会儿改完了I，I2y215，hyw上机试着试着造出了一组反例，改完后依然wa。这时hyw和yyc讨论了一下觉得是一个break的问题，但是删去可能会T，tjc建议先删去交一次看看会不会T，结果真的T了，yyc试图改进了做法但是hyw觉得可能要重构，权衡之下不如写一个线段树来得快，于是喊线段树手速带师yyc用了三分钟敲完了线段树，改完后A6y274。最后yyc和tjc写了一会儿D做法假了，hyw修正了yyc的G题做法但是来不及写了。

总结

yyc

tjc

hyw

以后在机上调试的人看到题目wa了以后要主动向队友问有没有题可以写，手上有题可以写的人也要及时主动跟上机的人说，避免耽误机时。

有多种修改方法的时候第一考虑是最好理解/最好写的（可以代码不一定很短），尽可能避免需要重构的“正解”，比如复杂度够的题敲一棵线段树就能解决的问题不去魔改模拟过程。

另外这场和yyc讨论A的时候只讨论了做法还是没讨论清楚写法导致最后出了很多锅，讨论的时候不能抱着“我不想写，让队友去写”的心态就不去好好讨论写法。

2020/1/22UPD：补了D，细节相当多+相当考验思维的一道好题，当时好像没看？？？

题解

A：dp，离散化之后转移，先预处理出每一段时间里面能开工的人里面耗时最短的人，设这个人做的时间为t[j]，设dp[i]为到i时刻最多能做几个任务，于是有dp[i]=min(dp[i-1],dp[i-t[j]]+1)，显然这样复杂度不对，注意到这个方程的第二项是+1，于是我们可以这样考虑：在每一段的段内尽可能做，直到某个时间点i满足如果在i时间开工，那么这个任务做完的时间(i+tj)就会在后面的段里面，这时有两种选择：一是做这个任务并且转移到后面的段，二是不做这个任务转移到下一段。显然对于在i ~ i+tj 当中的段，如果存在一个段满足做一个任务的结束时间早于i+tj，那么在i时刻选择不做下一个任务，直到这个段的段首再做下一个任务一定更优。于是我们选择做下一个任务最早结束的时间即可，可以用线段树维护这个最短时间。复杂度O(nlogn)（注：转移其实可以优化到O(n)的，但是预处理带log，所以总复杂度也带log）

B：签到

C：

D：每台机器只可能有两种输出值：一种是它的设定值，一种是它的设定值&它的检测值，分别记作CD值和CT值。因为只有3个feature，所以实际上只有23=8种类型的点，构造方法显然是对000-111的每个组合找一个源点，且这些源点直接可以从111开始依次可达，然后所有CD值为i的点就从i的源点连一条边到这个点就行了。这个点要满足（1）它可以从1号点经过若干条边到达（2）它的CD值和CT值应该不同（否则这个点一定不是关键点，因为它的输入和输出相同，这个点是没有意义的）。其中111的源点显然是1号点，000不需要源点，对于某个值如果不存在以这个值为CD值的点，这个值同样不需要源点。难点在于如何对001-110的这些组合找源点。源点可以有两种可能：（1）这个点的CD值已经可达，CD不等于CT，且CT值还未找到源点，那么可以直接将CT值的源点设为这个点，并将这个点CT设为enabled。（2）如果对于某个值i，用（1）的方法找不到源点，此时如果这个值是001、010或者100，那么无解，否则，由于二进制中有两个1，我们可以对源点的输入方式进行拆分。以i=011为例，我们可以寻找某个点j，它的CD值等于i，并且满足(a)已经找到001和010的源点(b)001和010的源点均不等于j点的CT值。如果满足这两个条件，我们可以将001和010的源点分别连一条边到j，将i的源点设为j，将j的CT设为unenabled。经过6次循环查找之后，如果仍然存在某个需要有源点的值没有源点那么无解。

E：枚举哪个人最后会胜出，按照这个人的得票和第n个人的得票的差排序。

F：随意拼出一个prufer序列，然后构造@tjc

G：

H：

I：@tjc

J：@yyc

K：hash本质上是\sigma i=1 to length i*ki，其中ki<=i。然后组合数算一下就好了，注意kn不能为0，最后答案里要减掉。

L：每次先找到第k大的字符串最小能填什么字符填进去，然后剩下的依次填，每次维护一下已经填的部分相同的段，这些段需要符合大小关系，其他字符串由于大小关系已经确定了随便填就行。

附加文件