2019-team666-0033

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:8/12 1447 dirt:58%
rank:56/307
[[Image(Submissions.png,800px)]]
[[Image(Standings.jpg,800px)]]
== 流水账 ==
上来yyc签了D,'''D1y7''',这时tjc说K是个2Sat，找了个板子就上机，'''K1y27'''. hyw读了E后和yyc讨论了一会儿觉得是个复杂dp，这时榜上过了L，发现贪心就好了，hyw'''L1y58'''。过了一会儿yyc和tjc搞出了A，yyc写A，hyw向tjc转述E题题意的时候tjc发现题读错了，得到正确题意以后发现二分+贪心就好了，hyw写E，中途yyc修改了A，'''A2y113'''。E交上去wa2，发现没有满足L1<=L2，改完wa3，发现函数值不一定是中位数，改完wa7. 中间tjc跟hyw说了一下F的做法，得到认同后tjc推了一下F的细节上机写F，hyw和yyc反复查E没有查出问题。大约半小时后yyc去看B，hyw又看了10分钟E，这时F已经wa了两次，于是hyw和tjc互换题目互查，这时yyc的B有了做法，跟hyw说后得到认同上机，得到Tle，yyc冷静下来查了一会儿发现复杂度算错了，修正了做法后'''B3y222'''，刚过完B的yyc又读了一遍E瞬间发现了corner case，改完以后'''E4y234'''。这时临近封榜，三人一起讨论了一下J，一开始的做法复杂度不对，tjc修正了做法，和hyw商量了一下决定tjc自己上机，hyw帮忙查F，过了10分钟hyw想到了F的corner case，改完后'''F3y276'''。最后tjc在hyw帮助下改完了J，'''J2y290'''。
== 总结 == 
=== yyc ===
=== tjc  ===
F没有一遍写对，调到自闭，结果后面J也没有一遍写对。。 （主要还是自己菜？）
=== hyw  ===
这场总结起来就是E和F两个题Wa了一年，都有非常牛逼的Corner case.
我的话这场上来被队友丢了个L过了以后就开始卡E了，一开始读了假题（话说和乌鸦队一样把max读成了Σ），得到正确题意后改后Wa2，后来发现我们的贪心并不能满足L1<=L2，修改后Wa7，拉了yyc想不出就把这题扔了，和tjc交换了题，帮tjc查F，到比赛快结束才灵机一动想到Corner case. 本来想仔细去想C的，但是由于两个题卡了一年最后也没空去想了。
整体打得还算不错，要是E能早点想到再去仔细读一遍题就好了。
UPD2020/1/23：G题是个很基础的概统题
=== 题解 ===
A：@yyc
B：@yyc
C:
D: 签到
E：二分答案+贪心验证，corner case在于V=0时L必须等于0才可以分在第一段。
F：分类讨论+栈模拟，我们的做法corner case在于"a+"应当为error而不是improper.
G：积分，（ta,tb,tc）的大小关系共有6种，以ta<=tb<=tc为例，固定tb，分别求出此时AB相遇的概率和BC相遇的概率，两者是相互独立的，直接相乘后积分，积分时需要乘上概率密度函数1/S（因为t2恰好取需要的那个点的概率是1/S，这一点容易忽略）。对6个大小关系分别求解概率相加即可。最后的式子见-->[https://ferin-tech.hatenablog.com/entry/2019/11/30/2018-2019_ACM-ICPC%2C_Asia_Seoul_Regional_Contest_G_-_Secret_Code 式子]
H：
I：
J：枚举所有颜色相同的边对，将两条边起点的点对作为一个新点，两条边作为一条新边，反向建边（为了dp）建立新图，设dp[i][j]为能否从(i,j)出发转移到终点，然后将所有终点的点对的dp[i][j]设为1，遍历整张图转移，如果存在一个点对(i,j)其中i是好点j是坏点，且dp[i][j]=1则答案为Yes，否则为No。
K：!a->b，!a->c，剩下两种边同理，2SAT
L：贪心，每次选剩余工作天数最大的人

[/wiki/2019-team666 返回]

概述

solved:8/12 1447 dirt:58%

rank:56/307

流水账

上来yyc签了D,D1y7,这时tjc说K是个2Sat，找了个板子就上机，K1y27. hyw读了E后和yyc讨论了一会儿觉得是个复杂dp，这时榜上过了L，发现贪心就好了，hywL1y58。过了一会儿yyc和tjc搞出了A，yyc写A，hyw向tjc转述E题题意的时候tjc发现题读错了，得到正确题意以后发现二分+贪心就好了，hyw写E，中途yyc修改了A，A2y113。E交上去wa2，发现没有满足L1<=L2，改完wa3，发现函数值不一定是中位数，改完wa7. 中间tjc跟hyw说了一下F的做法，得到认同后tjc推了一下F的细节上机写F，hyw和yyc反复查E没有查出问题。大约半小时后yyc去看B，hyw又看了10分钟E，这时F已经wa了两次，于是hyw和tjc互换题目互查，这时yyc的B有了做法，跟hyw说后得到认同上机，得到Tle，yyc冷静下来查了一会儿发现复杂度算错了，修正了做法后B3y222，刚过完B的yyc又读了一遍E瞬间发现了corner case，改完以后E4y234。这时临近封榜，三人一起讨论了一下J，一开始的做法复杂度不对，tjc修正了做法，和hyw商量了一下决定tjc自己上机，hyw帮忙查F，过了10分钟hyw想到了F的corner case，改完后F3y276。最后tjc在hyw帮助下改完了J，J2y290。

总结

yyc

tjc

F没有一遍写对，调到自闭，结果后面J也没有一遍写对。。 （主要还是自己菜？）

hyw

这场总结起来就是E和F两个题Wa了一年，都有非常牛逼的Corner case.

我的话这场上来被队友丢了个L过了以后就开始卡E了，一开始读了假题（话说和乌鸦队一样把max读成了Σ），得到正确题意后改后Wa2，后来发现我们的贪心并不能满足L1<=L2，修改后Wa7，拉了yyc想不出就把这题扔了，和tjc交换了题，帮tjc查F，到比赛快结束才灵机一动想到Corner case. 本来想仔细去想C的，但是由于两个题卡了一年最后也没空去想了。

整体打得还算不错，要是E能早点想到再去仔细读一遍题就好了。

UPD2020/1/23：G题是个很基础的概统题

题解

A：@yyc

B：@yyc

C:

D: 签到

E：二分答案+贪心验证，corner case在于V=0时L必须等于0才可以分在第一段。

F：分类讨论+栈模拟，我们的做法corner case在于"a+"应当为error而不是improper.

G：积分，（ta,tb,tc）的大小关系共有6种，以ta<=tb<=tc为例，固定tb，分别求出此时AB相遇的概率和BC相遇的概率，两者是相互独立的，直接相乘后积分，积分时需要乘上概率密度函数1/S（因为t2恰好取需要的那个点的概率是1/S，这一点容易忽略）。对6个大小关系分别求解概率相加即可。最后的式子见-->式子

H：

I：

J：枚举所有颜色相同的边对，将两条边起点的点对作为一个新点，两条边作为一条新边，反向建边（为了dp）建立新图，设dp[i][j]为能否从(i,j)出发转移到终点，然后将所有终点的点对的dp[i][j]设为1，遍历整张图转移，如果存在一个点对(i,j)其中i是好点j是坏点，且dp[i][j]=1则答案为Yes，否则为No。

K：!a->b，!a->c，剩下两种边同理，2SAT

L：贪心，每次选剩余工作天数最大的人

附加文件