2019-team666-0036

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
solved:8/12  dirt:60%
rank:13/723
[[Image(Submissions1.jpg,500px)]]
[[Image(Submission2.jpg,500px)]]
[[Image(Standings.jpg,800px)]]

== 流水账 ==
开场tjc签了J，'''J1y2'''，yyc签了K，'''K2y15'''。这时跟榜，tjc和yyc看F。hyw签了I，'''I1y23'''。这时tjc和yyc发现F是个傻题，'''F1y32'''。这时rnk4，榜上没题，于是三人各自开题。hyw和tjc说了一下E，想了一段时间后暂时搁置。后来hyw又和yyc讲了E这个题，tjc听的过程中发现忽略了一个细节，于是上机，中间因为奇怪的原因挂了好几次，'''E4y97'''. hyw去写之前开出来的A，后来A题T了，yyc说可以把spfa改成dfs版的，中间inf把0x3f开成了0x7f挂了几发，上然后'''A4y139'''。hyw读了B，表示需要上机打个表，然后yyc和tjc搞出了L，虽然wa了几次但很快找出错，'''L3y175'''。写L的时候hyw让tjc做写大模拟的准备，于是L写完后tjc写C，hyw试图找B的规律，yyc思考D题。tjc的C题wa了很长时间，中途hyw几次猜测规律上机但都没有过，后来tjc艰难地调出了C，'''C4y269'''。最后hyw和tjc还是找了很长时间B的规律但都没有过，yyc搞出了D但是过于难写于是弃疗。
== 总结 == 
=== yyc ===
=== tjc  ===
俺懂了，端茶倒水写模拟才是最养老的打法
=== hyw  ===
tjc大模拟nb
这个B题想了很长时间也没有想到转化成LCA，一直以为是找规律，虽然看数据范围第一反应也是dp但是不知道从何下手QAQ
E题和L题都可以更快出的，在转达题意时没有把一些容易忽略的点着重强调是我的锅，比如E题是“只询问第n个”而不是询问全部n个，有的时候会出现讲题人确实讲了但是没有强调导致听题人忽略的情况。
L题的话后来才知道自己听了假的题意，本来也可以出得更早。
这场打的时候发现榜上dirt率极高所以交的时候还是有点不谨慎的，这种时候关键是自己要稳住，不要受榜的影响。
=== 题解 ===
A：差分约束
B：f函数相当于二进制的lca，然后发现可以将任意的k属于某个区间转化成只考虑k等于区间两个端点，于是dp，注意模数1e8+7
C：大模拟，分数类分子和分母都在long long范围内时做加法需要先除gcd再通分
D：直线和端点处垂线把平面分成若干个区域，在每个区域里大力讨论，再积分
E：可能答案满足区间合并性质，暴力合并最后统计次数即可
F：暴力
G：
H：
I：若h[i]≠h[i-1]答案乘2，否则乘上(h[i]-i+2)。注意考虑清楚答案为0的情况
J：签到
K：期望之比不变
L：注意到相同时间随着缓存大小增大只会在链表后面添加东西，hash维护即可

[/wiki/2019-team666 返回]

概述

solved:8/12 dirt:60%

rank:13/723

流水账

开场tjc签了J，J1y2，yyc签了K，K2y15。这时跟榜，tjc和yyc看F。hyw签了I，I1y23。这时tjc和yyc发现F是个傻题，F1y32。这时rnk4，榜上没题，于是三人各自开题。hyw和tjc说了一下E，想了一段时间后暂时搁置。后来hyw又和yyc讲了E这个题，tjc听的过程中发现忽略了一个细节，于是上机，中间因为奇怪的原因挂了好几次，E4y97. hyw去写之前开出来的A，后来A题T了，yyc说可以把spfa改成dfs版的，中间inf把0x3f开成了0x7f挂了几发，上然后A4y139。hyw读了B，表示需要上机打个表，然后yyc和tjc搞出了L，虽然wa了几次但很快找出错，L3y175。写L的时候hyw让tjc做写大模拟的准备，于是L写完后tjc写C，hyw试图找B的规律，yyc思考D题。tjc的C题wa了很长时间，中途hyw几次猜测规律上机但都没有过，后来tjc艰难地调出了C，C4y269。最后hyw和tjc还是找了很长时间B的规律但都没有过，yyc搞出了D但是过于难写于是弃疗。

总结

yyc

tjc

俺懂了，端茶倒水写模拟才是最养老的打法

hyw

tjc大模拟nb

这个B题想了很长时间也没有想到转化成LCA，一直以为是找规律，虽然看数据范围第一反应也是dp但是不知道从何下手QAQ

E题和L题都可以更快出的，在转达题意时没有把一些容易忽略的点着重强调是我的锅，比如E题是“只询问第n个”而不是询问全部n个，有的时候会出现讲题人确实讲了但是没有强调导致听题人忽略的情况。

L题的话后来才知道自己听了假的题意，本来也可以出得更早。

这场打的时候发现榜上dirt率极高所以交的时候还是有点不谨慎的，这种时候关键是自己要稳住，不要受榜的影响。

题解

A：差分约束

B：f函数相当于二进制的lca，然后发现可以将任意的k属于某个区间转化成只考虑k等于区间两个端点，于是dp，注意模数1e8+7

C：大模拟，分数类分子和分母都在long long范围内时做加法需要先除gcd再通分

D：直线和端点处垂线把平面分成若干个区域，在每个区域里大力讨论，再积分

E：可能答案满足区间合并性质，暴力合并最后统计次数即可

F：暴力

G：

H：

I：若h[i]≠h[i-1]答案乘2，否则乘上(h[i]-i+2)。注意考虑清楚答案为0的情况

J：签到

K：期望之比不变

L：注意到相同时间随着缓存大小增大只会在链表后面添加东西，hash维护即可

附加文件