这是本文档旧的修订版!
solved by JJLeo
给定一个长度为奇数的序列,每次对一个区间进行升序排序或降序排序,问最后中间的数是啥。
二分答案,然后将其它数字与他的大小关系变成$0$或$1$,使用线段树对$01$进行排序,最后看中间位置的数是否满足条件即可。
solved by
solved by Bazoka13
一个2000*2000的矩阵,给定$n$条线段,询问这些线段一共经过多少个格子
枚举横坐标,计算纵坐标然后染色即可
solved by
upsolved by
solved by Bazoka13
重排一个序列,使得相邻两项差的绝对值的最小值最大
根据二分的想法推出应该是选择n/2个连续元素后放到奇数位,从结束位置开始循环放到偶数位,但是这种情况只适用于奇数,在自己$hack$了自己的做法后,尝试偶数就直接从中间分开进行插值居然过了(?)
solved by Bazoka13
给定一个集合,每个元素都有相应权值,求权值和第$k$小的子集
利用优先队列,每次取出最小的元素后将最贵的换成更贵的或者直接加入更贵的
solved by 2sozx
给定一个第一象限简单多边形,问一条从原点出发的直线最多将多边形分成多少块。$n\le10^5$
首先忽略掉三点共线的点,这样的点是没有意义的,之后对剩余的点进行极角排序,让直线逆时针扫这些点,将这些点分成四种情况。
solved by Bazoka13
每次选两个叶子节点染色,并将其路径上所有节点涂黑,进行该操作直到不存在两个路径上节点全为白色的叶子节点,求最小操作数
显然每个子树可以拿出来一个与尽可能远的叶子节点进行配对,而剩下的叶子节点可能会存在必须进行配对的,那就可以分情况考虑
upsolved by JJLeo
给定一个$01$序列,每次操作可以将一个字符移动到任意一个位置,问$k$次操作可以得到的连续$0$的最大长度。
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多开了几分钟