2017-Sp184-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb想到了B，然而lcm似乎要分治FFT，于是抄了一个给sub，sub上机RE了，然后cjb想到了牛逼的corner case，'''B1y46'''。cjb想出了C的做法，丢给yzc，帮他抄了个treap，'''C1y69'''。然后cjb又帮sub抄了个最小圆覆盖，sub上机因为函数没有返回值RE2次后wa了。yzc和cjb推了G，yzc上机也wa了。sub上机fix，'''I4y133'''。cjb上机写D，三分一直PE，很难受，换了一种终于'''D4y177'''。之后cjb上机写J，写完打印调试，yzc上机写H，wa了好多发，cjb上机debug，'''J1y264'''。之后cjb重新推了G的逻辑，还是wa，yzc和sub找到了牛逼corner case，结果还是wa，cjb最后10min决定重写倍增，然后'''G2y296'''。赛后看数据找到了最后一种corner case，H passed。
== 总结 ==
=== chenjb ===
感觉还是要注意代码细节，感觉这个G就像是wf的B一样，然而我重写之后过了....然后debug J的时候有点不耐烦，要检讨。gtmyzc，走点心啊QAQ
=== oipotato ===
我是演员
=== subconscious  ===

== 题解 ==
 * A：

 * B：问一下lcm(1..n)-1就可以知道答案是ret+1了，要用分治FFT求解，注意特判n=1的情况。

 * C：对于[x+1..2x]直接暴力插入，对于>2x的直接打标记维护平衡树。

 * D：直接三分。

 * E：

 * F：

 * G：统计出路径上长度、偶数的数量、最小偶数的值，以及全局边权和的奇偶性，根据这几个参数分类讨论即可。

 * H：把边界及和边界八连通所有黑块，然后把八连通相邻白块删掉，有corner case：如果有对角的两个点被删了，并且另一个对角有星号，就要把星号对面删了，删完之后对每个联通块直接统计答案，输出最大值。

 * I：最小圆覆盖，注意long double精度，跑出来之后大力判定是否合法。

 * J：将每个点拆成连边不同light个点，然后每个点按亮度从小到大连w=0的边，原有的边f[i][light]向f[j][light]连w=cost的边，然后d[i][0/1]表示i这个点，是否到过2的最短路径，dijkstra即可。

 * K：

流水账

出门各自看题，cjb想到了B，然而lcm似乎要分治FFT，于是抄了一个给sub，sub上机RE了，然后cjb想到了牛逼的corner case，B1y46。cjb想出了C的做法，丢给yzc，帮他抄了个treap，C1y69。然后cjb又帮sub抄了个最小圆覆盖，sub上机因为函数没有返回值RE2次后wa了。yzc和cjb推了G，yzc上机也wa了。sub上机fix，I4y133。cjb上机写D，三分一直PE，很难受，换了一种终于D4y177。之后cjb上机写J，写完打印调试，yzc上机写H，wa了好多发，cjb上机debug，J1y264。之后cjb重新推了G的逻辑，还是wa，yzc和sub找到了牛逼corner case，结果还是wa，cjb最后10min决定重写倍增，然后G2y296。赛后看数据找到了最后一种corner case，H passed。

总结

chenjb

感觉还是要注意代码细节，感觉这个G就像是wf的B一样，然而我重写之后过了....然后debug J的时候有点不耐烦，要检讨。gtmyzc，走点心啊QAQ

oipotato

我是演员

subconscious

题解

  • A：
  • B：问一下lcm(1..n)-1就可以知道答案是ret+1了，要用分治FFT求解，注意特判n=1的情况。
  • C：对于[x+1..2x]直接暴力插入，对于>2x的直接打标记维护平衡树。
  • D：直接三分。
  • E：
  • F：
  • G：统计出路径上长度、偶数的数量、最小偶数的值，以及全局边权和的奇偶性，根据这几个参数分类讨论即可。
  • H：把边界及和边界八连通所有黑块，然后把八连通相邻白块删掉，有corner case：如果有对角的两个点被删了，并且另一个对角有星号，就要把星号对面删了，删完之后对每个联通块直接统计答案，输出最大值。
  • I：最小圆覆盖，注意long double精度，跑出来之后大力判定是否合法。
  • J：将每个点拆成连边不同light个点，然后每个点按亮度从小到大连w=0的边，原有的边f[i][light]向f[j][light]连w=cost的边，然后d[i][0/1]表示i这个点，是否到过2的最短路径，dijkstra即可。
  • K：
附加文件