2017-Sp65-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
 * 题目来源：Petrozavodsk Winter Training Camp 2018: AtCoder Contest
 * 现场&Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7364/standings/
== 流水账 ==
开场各自看题，讨论起了E和I，后发现有人过A，sub看了看，发现是签到题，和yzc讲了，yzc上机，'''A1y23'''。之后三个人讨论了一下比较多人过的K，一开始sub给出一种贪心，cjb提出了反例，后来结合以前做过的一个题，先分配给所有块一个度数，之后排序输出前tot-2小之和就好，yzc上机'''K1y39'''。sub给出了一个F的做法，yzc上机后过不了样例，三个人讨论了一下，cjb给了一个比较科学的想法，yzc上机获得wa，sub继续分析，但是后来发现yzc写错了，改正后'''F2y82'''。此时场上E和I都比较多人过，三个人先讨论了一下I，yzc最后提出了一个分块的做法，就让他上机写，cjb读其他题，sub想E。yzc写完之后获得tle，本地跑也比较慢，就让sub先上机写着E。不久后cjb提出可以调整块大小，调整了以后从tle 4变成了tle 35只好放弃。sub继续写E，yzc表示能够把分块改成线段树，就又上机写I，之后第35个点变成了wa，对拍，调eps都卡不过去，挣扎了很长一段时间。之后sub写完了E，获得wa，三个人讨论了一下，发现了sub的问题，封榜后'''E2y250'''，最后50min cjb想卡I题，yzc和sub讨论D，都没什么进展。最后榜上rk29，thu、pku和fdu都过了7-8个题，福大过了5个，一队和我们题数相当。
== 总结 ==
=== chenjb ===
不应该让I耽误做法比较确定的E太多时间，保有太大的侥幸心理想卡I，浪费了许多时间，算是个以后要注意的细节。但是I不会做也真的是因为我们套路见得太少了....可能zju的队都有这个问题.....好好补题多总结，技不如人就只能多练多学了。和woodcube学长交流了之后，另一个总结的地方就是弃题弃得很不干净，这样还不如不弃....要习惯这种感觉。
=== oipotato ===
I题不懂套路，还被榜骗了，过题人数2小时之后就没怎么动过，毕竟是一个懂套路就秒的题，还是姿势水平太低。D题读完题没读读入描述，一口大锅。
=== subconscious  ===
yzc真垃圾题意没读完。我们和强队差距还是太远了，感觉啥都不会？
== 题解 ==
  * C：
   * 题意：给出一个整点三角形，输出其内部一个整点，不存在输出-1 -1。10000次询问。
   * 题解：取最靠近某条边a的直线（其向量可以通过exgcd得到，即（x,y）使ax+by=1），在直线上找到最接近临边b的整点，判定是否在内部即可。可以证明该点不在三角形内时三角形内不存在整点。
  * D：
   * 题意：添加操作添加一个二元组(w,v)，删除操作删除w最小的那个二元组。每一次操作之后都执行一次询问操作(l,r)，找到w的和在模MOD意义下属于区间[l,r]的所有可行的二元组集合中，v之和最大的，无解输出-1。给定的二元组w递增，强制在线。
   * 题解：两个栈，添加一个二元组时，加入第一个栈。删除操作时，若第二个栈为空，则第一个栈不断弹栈并加入第二个栈，否则直接弹第二个栈的栈顶。两个栈在加入一个元素之后都能很方便的用O(MOD)的DP来得到模意义下的v的最大值。询问时用一个单调队列将两个栈的答案合并即可。
 * H：
   * 题意：给出一棵2000个点的树，树上权值是[1,n]的整数且互不相同，每一次可以选择点x到根的路径进行一次shift，要求不超过25000步使得所有a[x]=x。
   * 题解：做法可牛逼了，每次选择树上最外层的一堆单链，将里面不在自己的位置的点找到，然后每次选择深度最深的一个点往上shift一下，如果shift到根，就shift到所应在链的合适位置，待到最外层的单链都归位后，就将这些单链从树上删去，然后重复该流程即可，复杂度很科学(???)。
 * I：
   * 题意：一个序列，维护区间加，区间整除，区间最大值。
   * 题解：区间最大值和最小值相差小于等于1时才做整除，差为1时要么相当于区间减要么都变成一个值。复杂度暂时还不会证明，势能分析似乎是两个log。一个log的标解见Nightfall。
 [[BR]] [[BR]]* [https://wiki-nightfall.icpc-camp.org/Day4 Solution by Nightfall]
== 补题 ==
 * B 
 * ~~C~~ by sub
 * ~~D~~ by yzc
 * G ???
 * ~~H~~ by cjb
 * ~~I~~ by yzc
 * J ???

• 题目来源：Petrozavodsk Winter Training Camp 2018: AtCoder Contest
• 现场&Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7364/standings/

流水账

开场各自看题，讨论起了E和I，后发现有人过A，sub看了看，发现是签到题，和yzc讲了，yzc上机，A1y23。之后三个人讨论了一下比较多人过的K，一开始sub给出一种贪心，cjb提出了反例，后来结合以前做过的一个题，先分配给所有块一个度数，之后排序输出前tot-2小之和就好，yzc上机K1y39。sub给出了一个F的做法，yzc上机后过不了样例，三个人讨论了一下，cjb给了一个比较科学的想法，yzc上机获得wa，sub继续分析，但是后来发现yzc写错了，改正后F2y82。此时场上E和I都比较多人过，三个人先讨论了一下I，yzc最后提出了一个分块的做法，就让他上机写，cjb读其他题，sub想E。yzc写完之后获得tle，本地跑也比较慢，就让sub先上机写着E。不久后cjb提出可以调整块大小，调整了以后从tle 4变成了tle 35只好放弃。sub继续写E，yzc表示能够把分块改成线段树，就又上机写I，之后第35个点变成了wa，对拍，调eps都卡不过去，挣扎了很长一段时间。之后sub写完了E，获得wa，三个人讨论了一下，发现了sub的问题，封榜后E2y250，最后50min cjb想卡I题，yzc和sub讨论D，都没什么进展。最后榜上rk29，thu、pku和fdu都过了7-8个题，福大过了5个，一队和我们题数相当。

总结

chenjb

不应该让I耽误做法比较确定的E太多时间，保有太大的侥幸心理想卡I，浪费了许多时间，算是个以后要注意的细节。但是I不会做也真的是因为我们套路见得太少了....可能zju的队都有这个问题.....好好补题多总结，技不如人就只能多练多学了。和woodcube学长交流了之后，另一个总结的地方就是弃题弃得很不干净，这样还不如不弃....要习惯这种感觉。

oipotato

I题不懂套路，还被榜骗了，过题人数2小时之后就没怎么动过，毕竟是一个懂套路就秒的题，还是姿势水平太低。D题读完题没读读入描述，一口大锅。

subconscious

yzc真垃圾题意没读完。我们和强队差距还是太远了，感觉啥都不会？

题解

• C：
  • 题意：给出一个整点三角形，输出其内部一个整点，不存在输出-1 -1。10000次询问。
  • 题解：取最靠近某条边a的直线（其向量可以通过exgcd得到，即（x,y）使ax+by=1），在直线上找到最接近临边b的整点，判定是否在内部即可。可以证明该点不在三角形内时三角形内不存在整点。
• D：
  • 题意：添加操作添加一个二元组(w,v)，删除操作删除w最小的那个二元组。每一次操作之后都执行一次询问操作(l,r)，找到w的和在模MOD意义下属于区间[l,r]的所有可行的二元组集合中，v之和最大的，无解输出-1。给定的二元组w递增，强制在线。
  • 题解：两个栈，添加一个二元组时，加入第一个栈。删除操作时，若第二个栈为空，则第一个栈不断弹栈并加入第二个栈，否则直接弹第二个栈的栈顶。两个栈在加入一个元素之后都能很方便的用O(MOD)的DP来得到模意义下的v的最大值。询问时用一个单调队列将两个栈的答案合并即可。
    • H：
  • 题意：给出一棵2000个点的树，树上权值是[1,n]的整数且互不相同，每一次可以选择点x到根的路径进行一次shift，要求不超过25000步使得所有a[x]=x。
  • 题解：做法可牛逼了，每次选择树上最外层的一堆单链，将里面不在自己的位置的点找到，然后每次选择深度最深的一个点往上shift一下，如果shift到根，就shift到所应在链的合适位置，待到最外层的单链都归位后，就将这些单链从树上删去，然后重复该流程即可，复杂度很科学(???)。
    • I：
  • 题意：一个序列，维护区间加，区间整除，区间最大值。
  • 题解：区间最大值和最小值相差小于等于1时才做整除，差为1时要么相当于区间减要么都变成一个值。复杂度暂时还不会证明，势能分析似乎是两个log。一个log的标解见Nightfall。

* Solution by Nightfall

补题

• B
• C by sub
• D by yzc
• G ???
• H by cjb
• I by yzc
• J ???

附加文件

• 1.png by chenjb
• china.en.pdf by chenjb
• editorial-2.pdf by chenjb