2019-team666-0025

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:8/13 dirt:38%
rank:48/697
[[Image(Submissions.jpg,800px)]]
== 流水账 ==
开场yyc读了A的假题，导致A先挂一发，hyw读了E的假题，好在很快发现。看榜发现榜上过的题很奇怪，tjc先和hyw讨论了一下J觉得复杂度不对，后来hyw发现I是个裸的网络流，tjc给出了建图方法后喊yyc上去写，'''I1y43'''。tjc发现J的复杂度推错了，上机秒了J，'''J1y52'''，期间yyc推出了A，'''A2y56'''。yyc接着写L，挂了一发一段时间后发现做法假了。这时hyw在推G的式子，yyc想M。L假了以后tjc就开始写K，写到一半hyw推出了G，喊yyc帮个忙上去1分钟写完G，没想到竟然写挂了一发，'''G2y96'''。后来'''K1y107'''。看榜，yyc把不会做的D拿出来讨论，hyw说可以三分套三分套三分但不确定，tjc觉得很对，于是hyw写D，'''D1y122'''。后期yyc想M，hyw提了一下E可能是建图以后tjc觉得E可能可以做，就去想E，hyw推B。后来'''E1y196'''。B题很早就写了但是中途出了很多锅，后来改了很长时间才改对，期间yyc本来想写M的后缀自动机但是没有把握，最后yyc和tjc搞H题，中间hyw把B题一个小于号改成小于等于号就过了，'''B3y282'''，最后H题rush了好几发没过。
== 总结 == 
这场开场有点慢，除了读了两个假题的锅以外，感觉开场被榜带偏了，以后开场可以按照自己节奏开，直到有4-5支队过了某个题再考虑跟榜。
=== yyc ===
=== tjc  ===
=== hyw  ===
B是暑假的原题，决策单调性可以有很多种，wqs二分最后减的是k倍cost不是ansk倍cost，这两个都需要补一补。
C想到正解了没写。E的规约非常巧妙。
M题是好题，我当时想到可以把两个串拼起来跑个后缀自动机，其实离KMP就差一步竟然没想到……后来tjc提到的hash+二分其实是另一种解，网上好像也有人这么写过了（？）
正解是扩展kmp，留坑，回头补。（upd10.15已补）
=== 题解 ===
A：签到
B：暑假dhr队讲过的原题，wqs二分+决策单调性优化，维护一个队列，每次从队首转移，每算完一个dp[i]就和队尾比较一下，看一下队尾最远可以转移的位置（设为pos，因为决策单调性所以pos以前的点从队尾转移，pos以后的点从i转移，这个pos可以二分得到，用数组记录一下pos），如果这个pos存在（不超过n）就把它加进队。注意wqs二分最后答案减的是k倍cost而不是ansk倍cost。
C：第一个人选一个点以后第二个人一定选最大子树重心，然后第一个人删去最大子树
D：三分套三分套三分（不知道别的队为啥做得很复杂）
E：扫一遍，扫的过程中把任意连续的k个相同的消掉然后判是否相等（细节有点多）
F：
G：推公式，向上的正三角形n*(n+1)/2个，每条边n等分后对应的等分点连起来可以得到n-1个不规则正三角形，注意到这一点就可以直接推出公式，最后听说化简以后是C(n+3,4)
H：
I：网络流
J：枚举质因数按每个数存一个vector就行，复杂度是对的
K：选一个左上角的点作为终点，每次把距离终点最远的点移过来，同时维护其它的位置即可
L：
M：题意，在s中找s1+s2，在t中找s3，其中s1和s3回文，s2回文，求能找到多少组。KMP+Manacher，先求len[i]表示s字符串中以s[i]为左端点的回文串的个数，这部分可以先用manacher求出以s[i]为中心的回文半径，然后在差分数组上累加，最后求一遍前缀和即可。之后将s翻转，用exkmp求s每个后缀和t的lcp，最后答案就是lcp的长度乘上s1结束位置之后回文串的个数（即以s2左端点为左端点的回文串个数）求和。

[/wiki/2019-team666 返回]

概述

solved:8/13 dirt:38%

rank:48/697

流水账

开场yyc读了A的假题，导致A先挂一发，hyw读了E的假题，好在很快发现。看榜发现榜上过的题很奇怪，tjc先和hyw讨论了一下J觉得复杂度不对，后来hyw发现I是个裸的网络流，tjc给出了建图方法后喊yyc上去写，I1y43。tjc发现J的复杂度推错了，上机秒了J，J1y52，期间yyc推出了A，A2y56。yyc接着写L，挂了一发一段时间后发现做法假了。这时hyw在推G的式子，yyc想M。L假了以后tjc就开始写K，写到一半hyw推出了G，喊yyc帮个忙上去1分钟写完G，没想到竟然写挂了一发，G2y96。后来K1y107。看榜，yyc把不会做的D拿出来讨论，hyw说可以三分套三分套三分但不确定，tjc觉得很对，于是hyw写D，D1y122。后期yyc想M，hyw提了一下E可能是建图以后tjc觉得E可能可以做，就去想E，hyw推B。后来E1y196。B题很早就写了但是中途出了很多锅，后来改了很长时间才改对，期间yyc本来想写M的后缀自动机但是没有把握，最后yyc和tjc搞H题，中间hyw把B题一个小于号改成小于等于号就过了，B3y282，最后H题rush了好几发没过。

总结

这场开场有点慢，除了读了两个假题的锅以外，感觉开场被榜带偏了，以后开场可以按照自己节奏开，直到有4-5支队过了某个题再考虑跟榜。

yyc

tjc

hyw

B是暑假的原题，决策单调性可以有很多种，wqs二分最后减的是k倍cost不是ansk倍cost，这两个都需要补一补。

C想到正解了没写。E的规约非常巧妙。

M题是好题，我当时想到可以把两个串拼起来跑个后缀自动机，其实离KMP就差一步竟然没想到……后来tjc提到的hash+二分其实是另一种解，网上好像也有人这么写过了（？）

正解是扩展kmp，留坑，回头补。（upd10.15已补）

题解

A：签到

B：暑假dhr队讲过的原题，wqs二分+决策单调性优化，维护一个队列，每次从队首转移，每算完一个dp[i]就和队尾比较一下，看一下队尾最远可以转移的位置（设为pos，因为决策单调性所以pos以前的点从队尾转移，pos以后的点从i转移，这个pos可以二分得到，用数组记录一下pos），如果这个pos存在（不超过n）就把它加进队。注意wqs二分最后答案减的是k倍cost而不是ansk倍cost。

C：第一个人选一个点以后第二个人一定选最大子树重心，然后第一个人删去最大子树

D：三分套三分套三分（不知道别的队为啥做得很复杂）

E：扫一遍，扫的过程中把任意连续的k个相同的消掉然后判是否相等（细节有点多）

F：

G：推公式，向上的正三角形n*(n+1)/2个，每条边n等分后对应的等分点连起来可以得到n-1个不规则正三角形，注意到这一点就可以直接推出公式，最后听说化简以后是C(n+3,4)

H：

I：网络流

J：枚举质因数按每个数存一个vector就行，复杂度是对的

K：选一个左上角的点作为终点，每次把距离终点最远的点移过来，同时维护其它的位置即可

L：

M：题意，在s中找s1+s2，在t中找s3，其中s1和s3回文，s2回文，求能找到多少组。KMP+Manacher，先求len[i]表示s字符串中以s[i]为左端点的回文串的个数，这部分可以先用manacher求出以s[i]为中心的回文半径，然后在差分数组上累加，最后求一遍前缀和即可。之后将s翻转，用exkmp求s每个后缀和t的lcp，最后答案就是lcp的长度乘上s1结束位置之后回文串的个数（即以s2左端点为左端点的回文串个数）求和。

附加文件