2019-team666-0030

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:6/13 827 dirt:45%
rank:74/253
[http://10.71.10.90/pia/trac/wiki/2017-Sp82-team2 Legilimens]
[[Image(Submissions.jpg,800px)]]
== 流水账 ==
上来1分钟就看到有人过了L，tjc去看。一开始hyw看到了E觉得大概是个什么dp，还没想的时候被tjc丢了个L，5分钟的时候一看E过了一片，一看只要贪心就好，于是'''E1y6'''。这个时候tjc和yyc各自看题并交换题意，hyw想L，给了几个不对的贪心以后想到dp，觉得很稳就交了结果wa。tjc看了一下后删去一行再交，又wa。于是怀疑做法有问题，过了一会hyw给出了反例，fix了一下就过了，'''L3y46'''。这时榜上过了B和J，B之前没讨论出结果，又因为J看上去很可做而且过的人多到令人发指于是三个人就一起看J，结果三人一起卡了15分钟，tjc想到可以用prufer序列搞一搞，中间出了个小锅以后过了'''J2y85'''。这时三人各自开题，yyc给出了一个B的做法，和tjc讨论了一会儿，然后yyc上机写B，hyw把F的做法跟tjc讲了一下，tjc觉得可，这时yyc的B卡住了，于是hyw写F。后来B的做法假了，F题样例调了一会儿，'''F1y137'''。这时tjc说自己会I了就一个人去写I，hyw去救B题，yyc看C。后来I题wa了，yyc写C，tjc跟hyw讨论出I的正解，发现需要大改。这时'''C2y201'''，tjc接着写I。hyw卡了半小时B无果决定放弃B题，听yyc讲了一下剩下题的题意，讲到D题的时候yyc说是个经典不可做题，但hyw觉得应该可以做于是就去开了。yyc试图去开H题。封榜时hyw有事先走了，跟yyc交代了一下封榜后的安排，觉得B和H如果开不出还剩40分钟的时候就去帮忙I，结果I很快过了，'''I2y252'''。最后yyc和tjc搞B题，没有搞出来。
== 总结 == 
=== yyc ===
=== tjc  ===
这个B题后期想出了接近正解的东西，但只尝试了对两种连边方式取max，没有都建出来跑一遍，最后wa了有点gg
=== hyw  ===
这场因为一些事情早走了肥肠抱歉……orz
这场整体上基本上就是计数+套路场，D、G、H全是计数，B和J是套路题，这里大概就是和强队的差距吧……
中期C和I出的比较慢，特别是I题一开始做法假了非常伤，如果有自信单挑一个题的话求求你们稳一点啊qwq
决策上，B救不出来弃掉还算明智，在D、G、H三个计数题上纠结了很久，D其实已经很接近了但是没有深入向下想比较可惜，最后跑去看G了这里还是有一些问题，当时G出不来的时候应该坚定下来搞更有希望的D（@yyc不要随便扔题啊）。
以及A没有想到去打个表示个大失误，A和H我都没去管，这也算是个经典失误了吧，下次注意。
顺便吹一下这场的D和H两个计数出的相当妙。
=== 题解 ===
A: 见BUAA题解 [http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Makoto%20rng_58%20Soejima%20Contest%204 Nonsense Time]
B：曼哈顿距离转切比雪夫距离，然后按x+y和x-y排序，把所有点和x+y最大最小x-y最大最小共4个点连边，对建出来的边跑最小生成树
C：@yyc
D：见BUAA题解 [http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Makoto%20rng_58%20Soejima%20Contest%204 Nonsense Time]
E：sort后贪心
F：对于M<=sqrt(1e9)直接暴力，M>sqrt(1e9)时，我们可以将M~1e9这部分分成若干个区间[Li,Ri]，对于M=Li，相当于把数轴分成了若干段，算出每一张卡在第几段并判断是否满足题中限制条件，如果合法，通过解不等式得到上界Ri，使得对于任意M \in [Li,Ri]，每一张牌所在的段的名次都不变。可以证明这样做不会超过N次。
G：
H：见BUAA题解 [http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Makoto%20rng_58%20Soejima%20Contest%204 Nonsense Time]
I：每个机器人只会被四个方向上最近的机器人更新（而不是最早开始动的），对每个机器人的位置上的四个方向维护开始动的时间，再跑dijkstra即可
J：一个度数为d的点在prufer序列里出现的次数是d-1，推式子
K：
L：dp，设dp[i][j]为s前i个能否构造出t前j个，注意到如果t[l,r](l>1)中的字母均相同的话那么可以将t[l,r]全部视为是t[l-1]后加入的字母，于是有dp[i][j]|=dp[i][j-t]，t为连续相同后缀长度。当s[i]=t[j]时还需要dp[i][j]|=dp[i-1][j-1]。
M：如果n为奇数，直接枚举d从1到n/2，每次将i,i+d,i+2d连边（n个一循环）。如果n为偶数，对1到n−1枚举d从1到n/2−1做一遍上述操作，再枚举d从2到n/2−1做一遍，然后以n−1个一循环，将每个(i,i+1,n)连两条边，将(i,i+2,n)连一条边就行了。（BUAA给的三角形思想非常巧妙）
=== 补题 ===
进度条5/7
A,D,H,M by hyw
B by tjc

[/wiki/2019-team666 返回]

概述

solved:6/13 827 dirt:45%

rank:74/253

Legilimens

流水账

上来1分钟就看到有人过了L，tjc去看。一开始hyw看到了E觉得大概是个什么dp，还没想的时候被tjc丢了个L，5分钟的时候一看E过了一片，一看只要贪心就好，于是E1y6。这个时候tjc和yyc各自看题并交换题意，hyw想L，给了几个不对的贪心以后想到dp，觉得很稳就交了结果wa。tjc看了一下后删去一行再交，又wa。于是怀疑做法有问题，过了一会hyw给出了反例，fix了一下就过了，L3y46。这时榜上过了B和J，B之前没讨论出结果，又因为J看上去很可做而且过的人多到令人发指于是三个人就一起看J，结果三人一起卡了15分钟，tjc想到可以用prufer序列搞一搞，中间出了个小锅以后过了J2y85。这时三人各自开题，yyc给出了一个B的做法，和tjc讨论了一会儿，然后yyc上机写B，hyw把F的做法跟tjc讲了一下，tjc觉得可，这时yyc的B卡住了，于是hyw写F。后来B的做法假了，F题样例调了一会儿，F1y137。这时tjc说自己会I了就一个人去写I，hyw去救B题，yyc看C。后来I题wa了，yyc写C，tjc跟hyw讨论出I的正解，发现需要大改。这时C2y201，tjc接着写I。hyw卡了半小时B无果决定放弃B题，听yyc讲了一下剩下题的题意，讲到D题的时候yyc说是个经典不可做题，但hyw觉得应该可以做于是就去开了。yyc试图去开H题。封榜时hyw有事先走了，跟yyc交代了一下封榜后的安排，觉得B和H如果开不出还剩40分钟的时候就去帮忙I，结果I很快过了，I2y252。最后yyc和tjc搞B题，没有搞出来。

总结

yyc

tjc

这个B题后期想出了接近正解的东西，但只尝试了对两种连边方式取max，没有都建出来跑一遍，最后wa了有点gg

hyw

这场因为一些事情早走了肥肠抱歉……orz

这场整体上基本上就是计数+套路场，D、G、H全是计数，B和J是套路题，这里大概就是和强队的差距吧……

中期C和I出的比较慢，特别是I题一开始做法假了非常伤，如果有自信单挑一个题的话求求你们稳一点啊qwq

决策上，B救不出来弃掉还算明智，在D、G、H三个计数题上纠结了很久，D其实已经很接近了但是没有深入向下想比较可惜，最后跑去看G了这里还是有一些问题，当时G出不来的时候应该坚定下来搞更有希望的D（@yyc不要随便扔题啊）。

以及A没有想到去打个表示个大失误，A和H我都没去管，这也算是个经典失误了吧，下次注意。

顺便吹一下这场的D和H两个计数出的相当妙。

题解

A: 见BUAA题解 Nonsense Time

B：曼哈顿距离转切比雪夫距离，然后按x+y和x-y排序，把所有点和x+y最大最小x-y最大最小共4个点连边，对建出来的边跑最小生成树

C：@yyc

D：见BUAA题解 Nonsense Time

E：sort后贪心

F：对于M<=sqrt(1e9)直接暴力，M>sqrt(1e9)时，我们可以将M~1e9这部分分成若干个区间[Li,Ri]，对于M=Li，相当于把数轴分成了若干段，算出每一张卡在第几段并判断是否满足题中限制条件，如果合法，通过解不等式得到上界Ri，使得对于任意M \in [Li,Ri]，每一张牌所在的段的名次都不变。可以证明这样做不会超过N次。

G：

H：见BUAA题解 Nonsense Time

I：每个机器人只会被四个方向上最近的机器人更新（而不是最早开始动的），对每个机器人的位置上的四个方向维护开始动的时间，再跑dijkstra即可

J：一个度数为d的点在prufer序列里出现的次数是d-1，推式子

K：

L：dp，设dp[i][j]为s前i个能否构造出t前j个，注意到如果t[l,r](l>1)中的字母均相同的话那么可以将t[l,r]全部视为是t[l-1]后加入的字母，于是有dp[i][j]|=dp[i][j-t]，t为连续相同后缀长度。当s[i]=t[j]时还需要dp[i][j]|=dp[i-1][j-1]。

M：如果n为奇数，直接枚举d从1到n/2，每次将i,i+d,i+2d连边（n个一循环）。如果n为偶数，对1到n−1枚举d从1到n/2−1做一遍上述操作，再枚举d从2到n/2−1做一遍，然后以n−1个一循环，将每个(i,i+1,n)连两条边，将(i,i+2,n)连一条边就行了。（BUAA给的三角形思想非常巧妙）

补题

进度条5/7

A,D,H,M by hyw

B by tjc

附加文件

• Submissions.jpg by aison