2017-C15-team4

从 Trac 迁移的文章

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

原文章内容如下：

||10621584 ||ZJUTeam4||G||Accepted||C++|| 04:46:16||
||10621423 ||ZJUTeam4||L||Accepted||C++|| 04:15:40||
||10621390 ||ZJUTeam4||L||Wrong Answer||C++|| 04:08:08||
||10621271 ||ZJUTeam4||L||Wrong Answer||C++|| 03:45:06||
||10621153 ||ZJUTeam4||D||Accepted ||C++|| 03:15:23||
||10620965 ||ZJUTeam4||D||Wrong Answer||C++|| 02:33:23||
||10620564 ||ZJUTeam4||B||Accepted||C++|| 01:41:16||
||10620466 ||ZJUTeam4||B||Wrong Answer||C++|| 01:25:23||
||10620256 ||ZJUTeam4||K||Accepted||C++|| 00:41:46||
||10620201 ||ZJUTeam4||C||Accepted||C++|| 00:28:27||
||10620184 ||ZJUTeam4||C||Wrong Answer||C++|| 00:23:15||
||10620170 ||ZJUTeam4||C||Wrong Answer||C++|| 00:20:28||
||10620136 ||ZJUTeam4||I||Accepted||C++|| 00:13:01||
== zya ==
开场先看M题感觉是个巨大的数据结构题，思考一会儿没有想法，跳过。L题想到一半发现是错的，这时候JYW学长让我想C题，我想到了上去写，JYW发现I题签到，签完后我交C，因为小错误wa了两发，之后JYW学长过了K和B，我想到了D的做法，让他给我写一个维护分数最小值的线段树，写到一半发现这个线段树不是很好写，好像是错的。后来我发现根据题目的特殊性，这种写法又是对的，唯一的问题就是分数相等的时候保留分母大的还是小的，一开始保留大的WA了一发，我猜想应该保留小的就过了。之后JYW学长想到了L，我看别的题，发现G可做，于是最后我们就写这两题。最后都过了。
== 题解 ==
D()从左到右扫描，考虑以当前颜色A为右端点的所有区间，只有在上次A位置之后的区间分子会加一，而整个区间的分母则都加一，这样就转化为一个区间分母加1，分子分母同时加1然后询问区间最小值的问题，题目特殊性使得区间内部的大小关系不会改变，所以可以用线段树写。问题在于，节点中如果两个儿子分数相等，应该保留哪个，保留小的可以通过题目数据，但是其正确性不得而知。
== 补题 ==
A()
E()
F()
H()
J()
M()

10621584	ZJUTeam4	G	Accepted	C++	04:46:16
10621423	ZJUTeam4	L	Accepted	C++	04:15:40
10621390	ZJUTeam4	L	Wrong Answer	C++	04:08:08
10621271	ZJUTeam4	L	Wrong Answer	C++	03:45:06
10621153	ZJUTeam4	D	Accepted	C++	03:15:23
10620965	ZJUTeam4	D	Wrong Answer	C++	02:33:23
10620564	ZJUTeam4	B	Accepted	C++	01:41:16
10620466	ZJUTeam4	B	Wrong Answer	C++	01:25:23
10620256	ZJUTeam4	K	Accepted	C++	00:41:46
10620201	ZJUTeam4	C	Accepted	C++	00:28:27
10620184	ZJUTeam4	C	Wrong Answer	C++	00:23:15
10620170	ZJUTeam4	C	Wrong Answer	C++	00:20:28
10620136	ZJUTeam4	I	Accepted	C++	00:13:01

zya

开场先看M题感觉是个巨大的数据结构题，思考一会儿没有想法，跳过。L题想到一半发现是错的，这时候JYW学长让我想C题，我想到了上去写，JYW发现I题签到，签完后我交C，因为小错误wa了两发，之后JYW学长过了K和B，我想到了D的做法，让他给我写一个维护分数最小值的线段树，写到一半发现这个线段树不是很好写，好像是错的。后来我发现根据题目的特殊性，这种写法又是对的，唯一的问题就是分数相等的时候保留分母大的还是小的，一开始保留大的WA了一发，我猜想应该保留小的就过了。之后JYW学长想到了L，我看别的题，发现G可做，于是最后我们就写这两题。最后都过了。

题解

D()从左到右扫描，考虑以当前颜色A为右端点的所有区间，只有在上次A位置之后的区间分子会加一，而整个区间的分母则都加一，这样就转化为一个区间分母加1，分子分母同时加1然后询问区间最小值的问题，题目特殊性使得区间内部的大小关系不会改变，所以可以用线段树写。问题在于，节点中如果两个儿子分数相等，应该保留哪个，保留小的可以通过题目数据，但是其正确性不得而知。

补题

A()

E()

F()

H()

J()

M()