2017-Sp90-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，感觉C能秒，讨论了一下，sub上机'''C1y19'''。yzc读了A，很sb，之后上机'''A1y24'''。发现有人过B，读了之后简单讨论了一下，yzc上机'''B1y47'''。之后感觉E是个点分治模板，cjb上机写了绝大部分，yzc把twopoint写完后发现样例不对，再读cjb发现题意错了，sub上机写G。之后yzc想好了E的树型dp，上机'''E1y109'''。此前cjb让yzc抄了H的ac自动机板子，Gwa了一发，之后cjb上机写完了H，sub再次提交'''G2y141'''。cjb调过样例获得tle，yzc上机写构造题F，'''F1y161'''。cjb决定卡一下常数，'''H2y166'''。之后sub让yzc上机写好了I的判无解，之后sub和cjb讨论了I的二分求答案，yzc上机wa，调大范围还是wa，最后决定把二分范围开到long long，'''I3y193'''。sub读了K，想了个正确性存疑的贪心丢给yzc，决定上机刚M，之后发现失败。yzc想好了线段树要维护的东西，上机wa了，之后感觉贪心有问题，叉了很久，发现之前代码有个地方写错了，改了之后又交了还是wa，之后把一个更加科学的贪心改了之后终于'''K3y263'''。最后半小时试图做D失败。最后9题rk21，SJTU 11题rk5，NTU 11题rk6。
== 总结 ==
=== chenjb ===
D学到了新姿势，E今天读错题耽误了50min很可惜，不然可能有机会做多一题，主要还是节奏输掉了。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：暴力

 * B：分析表达式后建树，暴力check

 * C：枚举根号内的质因数，根号外的直接扫一遍。

 * D：需要先处理出去掉某一条边后，该边端点i到T的最短路径f[i]。为了求这个，我们先从T跑最短路，得到最短路树，因为如果边不在最短路树上，那么依然是最短路长度，否则的话，考虑将树上y到fa[y]该边去掉，则是在子树中取一个点，跳横挑边再往上到根，也就是dist[x]-dist[y]+edge[x,p]+dist[p]，我们可以先对于每个点求出最小的dist[x]+edge[x,p]+dist[p]，考虑非树边(x,p)，若x在z的子树内，p不在z的子树内，则该值就可以对z的f产生贡献。我们枚举每一条非树边，对于(x,y)，则将x到lca(x,y)之下的每个点都更新掉，用树链剖分实现。然后把所有的f[i]都减去dist[i]就得到真正的f[i]。最后可以二分答案，也可以从T向S跑最短路，要求更新的时候用max(d[x]+edge[p].adj,f[edge[p].adj])来更新则可以得到答案。

 * E：树型dp

 * F：梳子形的构造一定能够走遍所有的(奇数,奇数)的格子，从起点出发，暴力走直到走到最后一个*号。

 * G：mask代表当前硬币状态，大力判定点到线段距离即可。

 * H：用f[i]表示串[1..i]的合法方案数，用ac自动机来维护转移位置，先在ac自动机上走一次获得pos[i]，然后从pos[i]每次直接跳到合法的转移长度，这样效率是O(n^1.5^)的。注意常数要写优秀点，不然会tle。

 * I：1没有入度显然-1，f[i][j]表示以i为起点，走2^i^步能到哪些点，然后二分答案即可。

 * J：

 * K：显然答案是max(i下标被覆盖的次数+i-1)，线段树维护即可

 * L：直接计算每个状态是否合法广搜即可。两个两圆交区间求最短距离判定，求出关键点：每两圆交点，每个圆心在其他圆上的投影，每个交点在在其他圆上的投影，枚举取最小值即可。注意常数。

 * M：整理只需要考虑2*2,1*2,2*1三种单点和空行即可，容斥dp。
== 补题 ==

流水账

开场各自看题，感觉C能秒，讨论了一下，sub上机C1y19。yzc读了A，很sb，之后上机A1y24。发现有人过B，读了之后简单讨论了一下，yzc上机B1y47。之后感觉E是个点分治模板，cjb上机写了绝大部分，yzc把twopoint写完后发现样例不对，再读cjb发现题意错了，sub上机写G。之后yzc想好了E的树型dp，上机E1y109。此前cjb让yzc抄了H的ac自动机板子，Gwa了一发，之后cjb上机写完了H，sub再次提交G2y141。cjb调过样例获得tle，yzc上机写构造题F，F1y161。cjb决定卡一下常数，H2y166。之后sub让yzc上机写好了I的判无解，之后sub和cjb讨论了I的二分求答案，yzc上机wa，调大范围还是wa，最后决定把二分范围开到long long，I3y193。sub读了K，想了个正确性存疑的贪心丢给yzc，决定上机刚M，之后发现失败。yzc想好了线段树要维护的东西，上机wa了，之后感觉贪心有问题，叉了很久，发现之前代码有个地方写错了，改了之后又交了还是wa，之后把一个更加科学的贪心改了之后终于K3y263。最后半小时试图做D失败。最后9题rk21，SJTU 11题rk5，NTU 11题rk6。

总结

chenjb

D学到了新姿势，E今天读错题耽误了50min很可惜，不然可能有机会做多一题，主要还是节奏输掉了。

oipotato

subconscious

题解

  • A：暴力
  • B：分析表达式后建树，暴力check
  • C：枚举根号内的质因数，根号外的直接扫一遍。
  • D：需要先处理出去掉某一条边后，该边端点i到T的最短路径f[i]。为了求这个，我们先从T跑最短路，得到最短路树，因为如果边不在最短路树上，那么依然是最短路长度，否则的话，考虑将树上y到fa[y]该边去掉，则是在子树中取一个点，跳横挑边再往上到根，也就是dist[x]-dist[y]+edge[x,p]+dist[p]，我们可以先对于每个点求出最小的dist[x]+edge[x,p]+dist[p]，考虑非树边(x,p)，若x在z的子树内，p不在z的子树内，则该值就可以对z的f产生贡献。我们枚举每一条非树边，对于(x,y)，则将x到lca(x,y)之下的每个点都更新掉，用树链剖分实现。然后把所有的f[i]都减去dist[i]就得到真正的f[i]。最后可以二分答案，也可以从T向S跑最短路，要求更新的时候用max(d[x]+edge[p].adj,f[edge[p].adj])来更新则可以得到答案。
  • E：树型dp
  • F：梳子形的构造一定能够走遍所有的(奇数,奇数)的格子，从起点出发，暴力走直到走到最后一个*号。
  • G：mask代表当前硬币状态，大力判定点到线段距离即可。
  • H：用f[i]表示串[1..i]的合法方案数，用ac自动机来维护转移位置，先在ac自动机上走一次获得pos[i]，然后从pos[i]每次直接跳到合法的转移长度，这样效率是O(n1.5)的。注意常数要写优秀点，不然会tle。
  • I：1没有入度显然-1，f[i][j]表示以i为起点，走2i步能到哪些点，然后二分答案即可。
  • J：
  • K：显然答案是max(i下标被覆盖的次数+i-1)，线段树维护即可
  • L：直接计算每个状态是否合法广搜即可。两个两圆交区间求最短距离判定，求出关键点：每两圆交点，每个圆心在其他圆上的投影，每个交点在在其他圆上的投影，枚举取最小值即可。注意常数。
  • M：整理只需要考虑2*2,1*2,2*1三种单点和空行即可，容斥dp。

补题

附加文件