省选游寄
szh_AK_all
·
·
生活·游记
Day -\inf
打了几场省选模拟赛，最后打的一场是湖北重现赛，得分 85+15+25，A 题被卡常了/ll。
Day 0
老爸不辞辛苦开车 4\sim5h，最终我们到达了上饶。
很棒，没有梦回 noip 生病。
晚上没有复习，到了酒店直接睡觉，竟让蚊子饱餐了一顿。
Day 1
早上老爸打死了四只蚊子，很牛。
吃完饭抵达考场。
$8:30$：题面来了，开 T1。
要不要枚举最终数字个数 $m$ 再判断哪些数字可能是中位数？好像可以 dp。
真有病，不如直接枚举每个数字判断它是否可以做为中位数。
可以判断吗，诶好像可以。
首先记录一定比它小/大的数字个数的上下界以及小于等于/大于等于它的数字的上下界。然后判个交集再判个大小就完了。
小于等于/大于等于它的数字的上下界根本没用啊，计算时一直都是把这两个玩意加在一起的。
这下是 $O(nw)$ 的了，显然离散化。
$9:30$:哇离散化怎么 WA 了，哦哦好像离散化要换个骚一点的写法。
$10:00$:很好，第二个大样例前面都对了，后面大数字错了。
原来忘开 `long long` 了。
好了，小一点的大样例过了，现在不就直接套个线段树吗。我真是太智慧了，考前敲了一份线段树的板子/kx。
大样例过了，但是跑了 2s，我真是太愚蠢了，换成树状数组，好的，算是过了。
（赛后：为什么我没想到前缀和。。）
$11:30$:开 T2，神奇的题目，神奇的范围。
$12:00$:还不慌，继续思考部分分。
$12:30$:再想想，根号分治能做吗？主席树能做吗？bitset 能做吗？
啥玩意！
$13:00$:慌了，赶紧打暴力，打完开 T3。
$13:30$:树的特殊性质是不是对每个深度贪心一下就行了，开写。
$13:40$:电脑怎么点不动了，woc！！呼叫监考老师，好的重启了。
$13:45$:我 T3 代码呢？草，赶紧重写，完了假了，赶紧打暴力。
$13:55$:终于打完了，我怀着激动的心测大样例，最终悬着的心终于死了，样例没过。
交了，离场。
估分：$100+20+0=120$。
大忌，就这实力还想翻盘？
## Day $2
吃了包子和油条，然后进考场。
$9:00$:想了一堆贪心，但都怀疑是假的，感觉对 $t,t-abs(a-b)$ 啥的都假的离谱。
$9:30$ 不管了，既然是贪心，那就乱搞吧，写了五种排序，起初好像写了按照 $t$ 排序的贪心，但忘记了后面有没有改掉。
显然所有物品在任意时刻的位置都是递增的，所以处理时可以使用线段树。当前物品移到目标位置会使前或后一段区间内的物品移动，这个移动显然是一个等差数列。
$11:00$ 写完了，但是为什么大样例中答案为 `No` 的我会判为 `Yes`。
哦原来是操作假了，赋值等差数列我直接写了赋值为同一个数。
我好像不会赋值等差数列啊，不管了，反正也是假做法，开 T2。
$11:30$ 好难，打暴力。
打完了，但是暴力的复杂度甚至也是错的。
又想了很久。
$12:00$ 开 T3，特殊性质 B 是不是有猫腻啊，胡了个式子但是假了。于是打起暴力。
暴力打完了，于是观察特殊性质。
没观察出来，但是发现特殊性质好像可以 $n^2$ 递推，不过时间快到了，走人，再见！
$[0,?]+[0,12]+[0,8]=[0,?]$。
人人都做出来 Day2 T1，这下可以退役了。
赛后发现我的乱搞做法和正解很像，而区间赋值等差数列只需要让用下标搞一搞就行了。
菜，就多练。