比赛链接

solved by JJLeo

给定一个长度为奇数的序列，每次对一个区间进行升序排序或降序排序，问最后中间的数是啥。

二分答案，然后将其它数字与他的大小关系变成$0$或$1$，使用线段树对$01$进行排序，最后看中间位置的数是否满足条件即可。

upsolved by

solved by Bazoka13

一个2000*2000的矩阵，给定$n$条线段，询问这些线段一共经过多少个格子

枚举横坐标，计算纵坐标然后染色即可

upsolved by JJLeo

给定一棵$n$个节点的树，每次等概率地选择一个节点，获得该节点所在连通块大小的权值，然后删除这个节点及其相连的边，重复$n$次操作，求期望权值。$(n \le 10^5)$

考虑两个点$u,v$之间的贡献，只有当$u$到$v$路径上$v$是第一个删除的点，$v$才能对$u$产生$1$的贡献，设路径长度为$d$，则概率为$\dfrac{1}{d+1}$。因此答案转化为树上不同长度的路径各有多少条，其中长度为$0$的路径（即自己对自己的贡献）只用算一遍，长度大于$0$的路径要算两边（两者对互相都有贡献）。

具体做法为淀粉质+FFT，如果对于某一个分治中心，一个子树一个子树合并，很容易就被菊花图+一条超长链卡出TLE。因此需要使用容斥的思想，将所有子树的的贡献全部加在一起，只做一次FFT，这样会多算出每个子树内部自己和自己合并出来的答案，只需要处理每个子树过程中，将其内部的贡献做一次FFT减掉即可。这样FFT多项式的总长度是$O(n\log n)$的，因此总复杂度为$O(n\log^2 n)$。

upsolved by

solved by Bazoka13

重排一个序列，使得相邻两项差的绝对值的最小值最大

根据二分的想法推出应该是选择n/2个连续元素后放到奇数位，从结束位置开始循环放到偶数位，但是这种情况只适用于奇数，在自己$hack$了自己的做法后，尝试偶数就直接从中间分开进行插值居然过了(?)

solved by Bazoka13

给定一个集合，每个元素都有相应权值，求权值和第$k$小的子集

利用优先队列，每次取出最小的元素后将最贵的换成更贵的或者直接加入更贵的

solved by 2sozx

给定一个第一象限简单多边形，问一条从原点出发的直线最多将多边形分成多少块。$n\le10^5$

首先忽略掉三点共线的点，这样的点是没有意义的，之后对剩余的点进行极角排序，让直线逆时针扫这些点，将这些点分成四种情况。
在扫到 $1,2$ 类点的时候块数会直接减一加一；扫到 $3,4$ 类点的时候继续移动块数会减一加一，但是刚扫到的时候并不会直接改变，可以通过叉积判断这四种情况。然而样例中给了一种特殊的情况。

此时下面这条线的两个点会被一起枚举到，并且此时的直线与这条线段重合，因此我们要避免重复计数的情况，取叉积的时候只在一侧添加等号。重合时还有一种情况时没有贡献的，只要调整叉积等号的取法即可，即如果一侧被计算到了，另一侧要减去，如果一侧没被计算到，另一侧也不会被计算到。

solved by Bazoka13

每次选两个叶子节点染色，并将其路径上所有节点涂黑，进行该操作直到不存在两个路径上节点全为白色的叶子节点，求最小操作数

显然每个子树可以拿出来一个与尽可能远的叶子节点进行配对，而剩下的叶子节点可能会存在必须进行配对的，那就可以分情况考虑

• 如果叶子节点数为1的子树多于2，就拿出来两个配对
• 如果叶子节点数为2的子树多于1，就拿出来一个配对
• 如果叶子节点数为1的子树多于1并且存在叶子节点数为2的子树，就拿出来将二者配对
• 显然剩下的叶子节点最多给父亲传递两个叶子节点

upsolved by JJLeo

给定一个$01$序列，每次操作可以将一个字符移动到任意一个位置，问$k$次操作可以得到的连续$0$的最大长度。

最优方案一定是将一个区间里的$1$挪出去然后再把一些$0$挪进来。
然后我就莫名其妙将$01$绑定了，然后就莫名WA 4，直接葬送这把。
设$sum_0,sum_1$分别为$0,1$的前缀和，答案为$\min(sum_0[n],sum_0[i]-sum_0[j]+k-(sum_1[i]-sum_1[j])$，要求区间内$sum_1[i]-sum_1[j] \le k$，直接单调队列即可。

0min：开局分题
10min：MJX发现C是签到冲C
33min：MJX WA，CSK冲G
46min：CSK AC，ZYF冲A
55min：ZYF AC A,MJX继续冲C
83min：MJX WA2，换CSK写C，MJX ZYF看J
167min：J WA4，CSK冲I
186min：CSK AC I，ZYF继续看J，MJX看H，CSK 看F
230min：CSK WA
232min：MJX AC H，继续看J
285min：CSK AC F，一起看J
295min：CSK想到了正解冲J
till end ：CSK没写完，由于inque多开了几分钟

• MJX要尽量避免精度问题
• CSK码力不够，最后五分钟有清晰思路的题都没有写出来，要继续锻炼
• ZYF全场梦游，J题看了三小时都没做出来，导致最后就差这一题，亏炸。下次要敢于换写法，不要沉迷于奇奇怪怪的做法。