2020-team2-029

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,600px)]]

= 概述 =

 solved: 7/12

 rank: 4

= 流水账 =

开场G题卡常,'''H1Y28''','''G4Y33''','''D1Y43''','''J1Y52'''。

cxt去做A，写完后提交WA，于是cxt让pb帮忙验一下做法，然后发现问题。这时yyc讲了几个题的题意，cxt发现B生成函数快速幂一下就行，'''B1Y98'''。pb修出了A，'''A2Y110'''。

yyc去推C的分类讨论，推完后给队友讲了一下又去想L，想出一个半平面交做法，于是开始写。写到一半cxt想起还有一个K题签到题(???)，于是换cxt写K，中途发现没那么简单，于是两人轮流上机，'''K2Y233'''。

最后yyc也没调出L，获得了-7的好成绩。

= 总结 =

=== pb： ===
队友太猛了，狂拿一血，这场好像在划水，G虽然有卡常的原因但还有一发corner case导致的wa，感觉写这种题还是容易讨论错。

然后几个难一点的题最后自己也没开出来，也没怎么帮到队友，感觉还是得提升一下自己的水平。

=== Creatix： ===
一支队不止一个几何手也挺好的吧。
准备和队长一起好好练几何。

写B的时候从听题到给两个队友各讲一遍算法到ac共27min，挺顺利的。

写完A题，然后一wa马上跑路……还好pb哥哥带飞，发现我合并操作不够彻底（这就是ACM的快乐之处吧，呜呜呜队友别怪我甩锅）。

对不起队长，没有好好完成过C的任务。

因为我确实觉得K好写……而且我应该真的没写太久吧……实际机时应该1 hour？我觉得要不是我自己吓自己还会更快……wa的那一发确实也怪题意不清，真的不太算我的锅。

K过了真开心，这场抢了两个一血。

如果我们计算几何再强一点就好了呢……~~传统计算几何弱队~~……就有时间做C了。

其实如果可以的话，不如我写计算几何，队长去写C。

光从专业的角度来说，我写计算几何还有一点优势，毕竟我有工图

[[Image(欸嘿.png,400px)]]

upd1：试了一下补E题……4小时过去了……cxt阵亡。gtm LCT切来切去连来连去，gtm LCT维护所有虚儿子信息，gtm 6k的细节题……

[[Image(趴.jpg,200px)]]

upd2：终于过E了。gtmd，我忘了LCT上的splay自带一个rev的tag，然后访问的时候没有pushdown。好久没像这样调题目调这么久了。11：15->16：19。

upd3：学了好久计算几何后，挺轻松地把L过了（58行）。坐在家里我啃着鸡排边想边写大概花了1hour，不算快。分类讨论以及计算方法详见题解处。


=== yyc： ===

为什么要抄那个怪怪的板子...为什么要写半平面交（最开始以为会少很多特判，和后来发现由于线不包含端点于是该判的还是要判...辣鸡分类讨论

板子还是自己搞一个吧，会少很多今天这样怪怪的情况。
= 题解 =

 * A：显然，若两个数列都单调递减，我们只要按顺序归并就好了。同时，我们注意到，若ai中有两个相邻位置(x, y)满足ax < ay，他们应该一起被选，即他们可以被合并，然后成为他们的加权平均数。

 * B：考虑令[x^k^]G=a(n-k)，再令F=(1 + x + x^2^ + ... + x^l-1^)^m^ * G，则ans[i]=[x^n-i^]F 

 * C：

 * D：

 * E：用LCT维护树的结构。不失一般性，我们假设某一次交换时a[i] < a[i + 1]。则我们分两步走：
   * 删除a[i]：显然a[i]没有右儿子，把a[i]的左儿子接在a[i]的父亲上，然后把a[i]从父亲那边切除。
   * lemma1：在笛卡尔树上，(a[i] ... a[i + 1])在树上所构成的一条链权值单调。proof：考虑笛卡尔树建树过程。我有很棒的证明但是懒得写。
   * 把a[i]插入(a[i + 1] ... a[i + 2])在树上所构成的一条链里。由lemma1，我们通过makeroot+access可以获得一个键值有序的splay，在上面二分即可。

  然后是一些小经验：如果你发现执行一些从道理上讲没有用的操作改变了答案，想一想是不是忘记pushdown了……

  以及，LCT如果要维护虚儿字信息只要在ACCESS和LINK和CUT的地方注意一下就好，挺简单的。
 * F：

 * G：考虑一个序列的GCD其实等价于最小的数，以及所有数减去最小的数的值这n个数的gcd。故先求出所有的差的gcd，再调整最小值使其最小且合法。'''要写快读！'''

 * H：签到。枚举每位放什么元素，后面能够调整的位数即为后面两串有多少位置不同。

 * I：

 * J：容易发现相邻位置之间的大小关系不会发生改变。把点分为三类：极小值点，极大值点，一般点。极小值点的减小不受任何点约束，于是先修改为0。
 极大值点不对其他点产生约束，所以最后修改。其余的一般点，则必然被一个极小值点和一个极大值点包夹，显然它的最终答案取决于它旁边的那个极小值点。

 * K：直接dp(x， i)表示第x天卖了coin，卖完后共卖了i次的最大收益。转移显然。
 用类似单调队列的东西（实际上是list）去优化，每个点保存dp值，时间，以及x到今天的最小c，注意合并c相同的点以确保复杂度，另外注意时刻维护单调队列符合要求。

 * L：首先注意到，一个位置能看到黑边等价于他能看到黑边的某一个端点（理由：若该位置能看到黑边的任意一部分则其一定能看到黑边端点，因为白边的遮挡段是连续的）
   * 点和线段有四种位置关系。1：点不在线段所表示的直线上。2：点在直线上，但不在闭线段上。3：点和线段端点重合。4：点在开线段上。
   * 那么开始分讨（以下分讨的顺序不可调换）
     * 若有一个黑端点为4类型：inf
     * 若有一个黑端点为3：另一个为 1：inf; 另一个为 2：0。
     * 若有一个黑端点为2：0
     * 那么两个黑端点都为 1。若两个点在黑边所在直线的两边：0。否则，对每个白边端点求出黑边与其夹角的较小值，则我们就知道了所求三角形的一边边长（即白边长度）和两个角，这之后再判断inf或算出面积就很容易了

[/wiki/2020-team2 返回]

概述

solved: 7/12

rank: 4

流水账

开场G题卡常,H1Y28,G4Y33,D1Y43,J1Y52。

cxt去做A，写完后提交WA，于是cxt让pb帮忙验一下做法，然后发现问题。这时yyc讲了几个题的题意，cxt发现B生成函数快速幂一下就行，B1Y98。pb修出了A，A2Y110。

yyc去推C的分类讨论，推完后给队友讲了一下又去想L，想出一个半平面交做法，于是开始写。写到一半cxt想起还有一个K题签到题(???)，于是换cxt写K，中途发现没那么简单，于是两人轮流上机，K2Y233。

最后yyc也没调出L，获得了-7的好成绩。

总结

pb：

队友太猛了，狂拿一血，这场好像在划水，G虽然有卡常的原因但还有一发corner case导致的wa，感觉写这种题还是容易讨论错。

然后几个难一点的题最后自己也没开出来，也没怎么帮到队友，感觉还是得提升一下自己的水平。

Creatix：

一支队不止一个几何手也挺好的吧。

准备和队长一起好好练几何。

写B的时候从听题到给两个队友各讲一遍算法到ac共27min，挺顺利的。

写完A题，然后一wa马上跑路……还好pb哥哥带飞，发现我合并操作不够彻底（这就是ACM的快乐之处吧，呜呜呜队友别怪我甩锅）。

对不起队长，没有好好完成过C的任务。

因为我确实觉得K好写……而且我应该真的没写太久吧……实际机时应该1 hour？我觉得要不是我自己吓自己还会更快……wa的那一发确实也怪题意不清，真的不太算我的锅。

K过了真开心，这场抢了两个一血。

如果我们计算几何再强一点就好了呢……~~传统计算几何弱队~~……就有时间做C了。

其实如果可以的话，不如我写计算几何，队长去写C。

光从专业的角度来说，我写计算几何还有一点优势，毕竟我有工图

upd1：试了一下补E题……4小时过去了……cxt阵亡。gtm LCT切来切去连来连去，gtm LCT维护所有虚儿子信息，gtm 6k的细节题……

upd2：终于过E了。gtmd，我忘了LCT上的splay自带一个rev的tag，然后访问的时候没有pushdown。好久没像这样调题目调这么久了。11：15->16：19。

upd3：学了好久计算几何后，挺轻松地把L过了（58行）。坐在家里我啃着鸡排边想边写大概花了1hour，不算快。分类讨论以及计算方法详见题解处。

yyc：

为什么要抄那个怪怪的板子...为什么要写半平面交（最开始以为会少很多特判，和后来发现由于线不包含端点于是该判的还是要判...辣鸡分类讨论

板子还是自己搞一个吧，会少很多今天这样怪怪的情况。

题解

A：显然，若两个数列都单调递减，我们只要按顺序归并就好了。同时，我们注意到，若ai中有两个相邻位置(x, y)满足ax < ay，他们应该一起被选，即他们可以被合并，然后成为他们的加权平均数。
B：考虑令[x^k]G=a(n-k)，再令F=(1 + x + x² + ... + x^l-1)^m * G，则ans[i]=[x^n-i]F
C：
D：
E：用LCT维护树的结构。不失一般性，我们假设某一次交换时a[i] < a[i + 1]。则我们分两步走：
- 删除a[i]：显然a[i]没有右儿子，把a[i]的左儿子接在a[i]的父亲上，然后把a[i]从父亲那边切除。
- lemma1：在笛卡尔树上，(a[i] ... a[i + 1])在树上所构成的一条链权值单调。proof：考虑笛卡尔树建树过程。我有很棒的证明但是懒得写。
- 把a[i]插入(a[i + 1] ... a[i + 2])在树上所构成的一条链里。由lemma1，我们通过makeroot+access可以获得一个键值有序的splay，在上面二分即可。

然后是一些小经验：如果你发现执行一些从道理上讲没有用的操作改变了答案，想一想是不是忘记pushdown了……

以及，LCT如果要维护虚儿字信息只要在ACCESS和LINK和CUT的地方注意一下就好，挺简单的。

F：
G：考虑一个序列的GCD其实等价于最小的数，以及所有数减去最小的数的值这n个数的gcd。故先求出所有的差的gcd，再调整最小值使其最小且合法。要写快读！
H：签到。枚举每位放什么元素，后面能够调整的位数即为后面两串有多少位置不同。
I：
J：容易发现相邻位置之间的大小关系不会发生改变。把点分为三类：极小值点，极大值点，一般点。极小值点的减小不受任何点约束，于是先修改为0。

极大值点不对其他点产生约束，所以最后修改。其余的一般点，则必然被一个极小值点和一个极大值点包夹，显然它的最终答案取决于它旁边的那个极小值点。

K：直接dp(x， i)表示第x天卖了coin，卖完后共卖了i次的最大收益。转移显然。

用类似单调队列的东西（实际上是list）去优化，每个点保存dp值，时间，以及x到今天的最小c，注意合并c相同的点以确保复杂度，另外注意时刻维护单调队列符合要求。

L：首先注意到，一个位置能看到黑边等价于他能看到黑边的某一个端点（理由：若该位置能看到黑边的任意一部分则其一定能看到黑边端点，因为白边的遮挡段是连续的）
- 点和线段有四种位置关系。1：点不在线段所表示的直线上。2：点在直线上，但不在闭线段上。3：点和线段端点重合。4：点在开线段上。
- 那么开始分讨（以下分讨的顺序不可调换）
  - 若有一个黑端点为4类型：inf
  - 若有一个黑端点为3：另一个为 1：inf; 另一个为 2：0。
  - 若有一个黑端点为2：0
  - 那么两个黑端点都为 1。若两个点在黑边所在直线的两边：0。否则，对每个白边端点求出黑边与其夹角的较小值，则我们就知道了所求三角形的一边边长（即白边长度）和两个角，这之后再判断inf或算出面积就很容易了

附加文件

Rank.png by Creatix
Submissions.png by Creatix
欸嘿.png by Creatix
Computational Geometry.pdf by Creatix
计算几何题面.pdf by Creatix
趴.jpg by Creatix