2017-Sp268-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
出门搞A，cjb乱搞了一下'''A2y25'''。之后yzc上机'''D1y44'''。中间sub尝试了K wa了，cjb痛苦写B，写了很久'''B1y122'''。cjb下机发现队友对着E和K一筹莫展，就让他们放弃了E，cjb搞K，然后sub和yzc推C那个dp，之后cjb '''K4y185'''，yzc '''C3y202'''。cjb读了I，丢给sub准备，然后读了J丢给yzc准备，之后'''I2y236'''，J tle后sub上机'''E2y252'''，J 继续tle，cjb开出F，'''F2y289'''，最后努力爆J失败。
=== chenjb ===
今天写B写的心态爆炸，下机发现队友也爆炸了。感觉之后的操作还是不错的，放一题，换人想K，然后读题分配给适合做这个题的对手，如果这个J不卡常，封榜真的是4题反杀，而且如果更顺利一点这个H其实对于yzc来说是沙雕题。我觉得，首先是cjb不能轻易上机，特别是前期，哪怕是丢做法时间比较久。然后sub和yzc最近总容易掉进题目，都是老逼了麻烦注意一点。然后这个H有点可惜，反过来说如果前面yzc他们读了就不会这样了，前期没管理好造成的缺失。最后是这个J，点分治太想当然了，以后要多考虑dsu on tree或者长链剖分的可能性。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：每次进来的如果在now+450内就接受。

 * B：线段树暴力维护，flag[0/1]表示必定为0/1的位置，同时维护最小值，查询的时候直接两边取答案后|=flag[1]，修改的时候，每次考虑区间flag标记和修改mask的关系，更新后把mask里可以整体在本节点打标记的部分去掉，继续下放，复杂度是O(30*nlogn)。

 * C：f[i][j][k]表示前i个人，目前连续一段已经放了j个人，想要从连续段出去的人和想要从外界进来的人的差为k，暴力转移即可。

 * D：二分。

 * E：列出f[n][x]代表n个人走了x步完全分开的概率，无穷求和，展开，得到分子是斯特林数，分母是等比数列求和。

 * F：奇数边权的边可贡献ai，偶数边权的边贡献ai/2，对于每个联通块分开计算后加起来，对于一个联通块，考虑把奇数边缩起来后的点的数量p，要么不取要么取两个点则C(p,2)+1，然后乘以边权贡献后，考虑环的数量t，可取可不取是2^t^。对于多个联通块，需要同时-1后最后+1去掉重复计算不取。

 * G：[https://icpc.camp/new-meta/2017/3/2%20Moscow%20IPT%20Contest NewMeta]

 * H：显然移动总距离和插入顺序无关。然后就是线段树分治经典模型。

 * I：只会在速度改变的点或某段线段最近点取得答案。

 * J：长链剖分

 * K：猜了个结论：a[i]只需要考虑和a[1]连边，然后求出p[i]表示a[i]+a[p[i]]>=M且p[i]尽可能小，猜测只需要考虑p[i-1]到p[i]的点连边。实际上可以直接套用第三种MST求法：一开始所有人都是独立的点，将每个点连出去最小的边抠出来kruskal合并，然后不断重复该过程。

流水账

出门搞A，cjb乱搞了一下A2y25。之后yzc上机D1y44。中间sub尝试了K wa了，cjb痛苦写B，写了很久B1y122。cjb下机发现队友对着E和K一筹莫展，就让他们放弃了E，cjb搞K，然后sub和yzc推C那个dp，之后cjb K4y185，yzc C3y202。cjb读了I，丢给sub准备，然后读了J丢给yzc准备，之后I2y236，J tle后sub上机E2y252，J 继续tle，cjb开出F，F2y289，最后努力爆J失败。

chenjb

今天写B写的心态爆炸，下机发现队友也爆炸了。感觉之后的操作还是不错的，放一题，换人想K，然后读题分配给适合做这个题的对手，如果这个J不卡常，封榜真的是4题反杀，而且如果更顺利一点这个H其实对于yzc来说是沙雕题。我觉得，首先是cjb不能轻易上机，特别是前期，哪怕是丢做法时间比较久。然后sub和yzc最近总容易掉进题目，都是老逼了麻烦注意一点。然后这个H有点可惜，反过来说如果前面yzc他们读了就不会这样了，前期没管理好造成的缺失。最后是这个J，点分治太想当然了，以后要多考虑dsu on tree或者长链剖分的可能性。

oipotato

subconscious

题解

A：每次进来的如果在now+450内就接受。
B：线段树暴力维护，flag[0/1]表示必定为0/1的位置，同时维护最小值，查询的时候直接两边取答案后|=flag[1]，修改的时候，每次考虑区间flag标记和修改mask的关系，更新后把mask里可以整体在本节点打标记的部分去掉，继续下放，复杂度是O(30*nlogn)。
C：f[i][j][k]表示前i个人，目前连续一段已经放了j个人，想要从连续段出去的人和想要从外界进来的人的差为k，暴力转移即可。
D：二分。
E：列出f[n][x]代表n个人走了x步完全分开的概率，无穷求和，展开，得到分子是斯特林数，分母是等比数列求和。
F：奇数边权的边可贡献ai，偶数边权的边贡献ai/2，对于每个联通块分开计算后加起来，对于一个联通块，考虑把奇数边缩起来后的点的数量p，要么不取要么取两个点则C(p,2)+1，然后乘以边权贡献后，考虑环的数量t，可取可不取是2^t。对于多个联通块，需要同时-1后最后+1去掉重复计算不取。
G：NewMeta
H：显然移动总距离和插入顺序无关。然后就是线段树分治经典模型。
I：只会在速度改变的点或某段线段最近点取得答案。
J：长链剖分
K：猜了个结论：a[i]只需要考虑和a[1]连边，然后求出p[i]表示a[i]+a[p[i]]>=M且p[i]尽可能小，猜测只需要考虑p[i-1]到p[i]的点连边。实际上可以直接套用第三种MST求法：一开始所有人都是独立的点，将每个点连出去最小的边抠出来kruskal合并，然后不断重复该过程。

附加文件

1.png by chenjb