2019-team666-0024

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:6/11 dirt:14%
rank:39/188
[[Image(Submissions.jpg,800px)]]
== 流水账 ==
前期双打，hyw上来签了ABC，'''A1y12,B1y32,C2y54'''（C爆了一发longlong）。之后yyc来了，和tjc讨论出I和E，hyw看了一会儿G讲了大致做法就丢给yyc，yyc把H丢给hyw。tjc上机稳稳地写完了I和F，'''I1Y73,F1y124'''。yyc在hyw帮助下推完了G就上机rush一发，过了，'''G1y165'''。后来hyw卡H，tjc卡K，三个半小时的时候yyc走了，tjc重写E又Wa了，最后一小时发现E的做法假了，全员自闭卡E。
== 总结 == 
打得没啥毛病的一场，后期难题不会做，除了爆了发longlong以外没有dirt，最后6题罚时第一。加油继续练吧。
=== yyc ===
=== tjc  ===
=== hyw  ===
H看到数据范围纠结了好久是dp还是网络流，结果果然是建图……这个建图没想出来，还是太菜了啊。
E没做出来挺不应该的，主要最后一小时思路总是往奇怪的方向去了。
J其实不难没去仔细想，K的话tjc一开始也提过一个做法不过我没在意，其实离正解很近了。
=== 题解 ===
'''官方题解见附件'''（无敌良心）
A,B,C: 签到
E：dp,设dp[i]表示涂好前i个格子的最小操作次数，答案就是dp[i]=min{j+k>=i}dp[j]+cost(j+1,i)，其中cost(j,i)=(i到j连续的颜色块数)/2. 由于cost(j+1,i)=cost[i]-cost[j]，可以单调队列或线段树优化。
F：tjc
G：几何，考虑展开图，相当于在无穷平面上走，枚举三角形即可，或者找规律。
H：最大值贪心即可，对于最小值， 可以将A类作业和源点相连以及自身对应的时间起点相连， B类作业和汇点相连以及自身对应的时间的终点相连，跑最小割。
I: tjc
J: （官方题解）把每个子串的信息沿着提示储存到最左边即可。
K: （官方题解）去掉所有度不超过2的点，找环。

[/wiki/2019-team666 返回]

概述

solved:6/11 dirt:14%

rank:39/188

流水账

前期双打，hyw上来签了ABC，A1y12,B1y32,C2y54（C爆了一发longlong）。之后yyc来了，和tjc讨论出I和E，hyw看了一会儿G讲了大致做法就丢给yyc，yyc把H丢给hyw。tjc上机稳稳地写完了I和F，I1Y73,F1y124。yyc在hyw帮助下推完了G就上机rush一发，过了，G1y165。后来hyw卡H，tjc卡K，三个半小时的时候yyc走了，tjc重写E又Wa了，最后一小时发现E的做法假了，全员自闭卡E。

总结

打得没啥毛病的一场，后期难题不会做，除了爆了发longlong以外没有dirt，最后6题罚时第一。加油继续练吧。

yyc

tjc

hyw

H看到数据范围纠结了好久是dp还是网络流，结果果然是建图……这个建图没想出来，还是太菜了啊。

E没做出来挺不应该的，主要最后一小时思路总是往奇怪的方向去了。

J其实不难没去仔细想，K的话tjc一开始也提过一个做法不过我没在意，其实离正解很近了。

题解

官方题解见附件（无敌良心）

A,B,C: 签到

E：dp,设dp[i]表示涂好前i个格子的最小操作次数，答案就是dp[i]=min{j+k>=i}dp[j]+cost(j+1,i)，其中cost(j,i)=(i到j连续的颜色块数)/2. 由于cost(j+1,i)=cost[i]-cost[j]，可以单调队列或线段树优化。

F：tjc

G：几何，考虑展开图，相当于在无穷平面上走，枚举三角形即可，或者找规律。

H：最大值贪心即可，对于最小值， 可以将A类作业和源点相连以及自身对应的时间起点相连， B类作业和汇点相连以及自身对应的时间的终点相连，跑最小割。

I: tjc

J: （官方题解）把每个子串的信息沿着提示储存到最左边即可。

K: （官方题解）去掉所有度不超过2的点，找环。

附加文件