DAY -3
水了道可撤销并查集题,心态++。
DAY -2
看了看洛谷的 NOIP 模板测试,发现自己有十几个板子还没做过,吓哭了。
尝试做某神秘网站远古思维题目照片装裱,在找第一个的时候卡住了。
求数据结构:
一个数组内有两个元素 Ai,BiA_i,B_iAi ,Bi 。
每次查询给定 x,yx,yx,y,查询第一个 Ai≥xA_i\ge xAi ≥x 且 Bi≥yB_i\ge yBi ≥y 的元素,并删除这个元素。
第一个的定义是以 AiA_iAi 为第一关键字,BiB_iBi 为第二关键字从小到大的第一个。
算了明天再想。
DAY -1
在学校想了半天,发现自己的智商有 -350234。理由:昨天那道题线段树套 set 二分就能做了。
有点感冒,但问题不大。
做出来了。
DAY 0
给自己定了个规则:
* 一开始先看完 444 题,开好所有的文件。
* 从 T1 开始做。
* 每道题先思考 10s 正解,如果想不出来就开始拿部分分。
* 部分分从暴力分开始拿起,显然每道题暴力分加起来有 60∼80pts60\sim 80pts60∼80pts。
* 一定要想特殊性质。
* 写完代码一定要检查时间复杂度是否符合预期。否则像今年 S T1 80→5580\rarr 5580→55。
* 如果有大模拟,一定要先理清思路。
* 考试最后 30min 不写代码,写迷惑行为。 GD 省把这个 ban 了,只能被迫写代码了。
* 最后 15min 检查文件等。
DAY 1
开题。
T1 是啥糖果题,想了 10s 发现好像可以分成一个一个和两个两个,感觉挺简单。但先不急,打个爆搜先。
爆搜很简单,枚举每次选哪个糖果即可。O(n(m+1))O(n^{(m+1)})O(n(m+1)),可以过前 333 个点。其实我场上以为这个是 O(n2m)O(n2^m)O(n2m) 的,不过问题不大。
1h 打完爆搜,15+0+0+0=1515+0+0+0=1515+0+0+0=15。
T2 就上难度了。
题目就是介绍一道 010101 背包题,但是重量只能取 [1,2][1,2][1,2]。小 R 尝试使用一种常见的贪心解法解决。现给定每种物品的价值,请你求出有多少种情况小 R 的做法是最优解。
感觉有点难,应该绿上/蓝?
考虑做法如何才会假掉。
呃呃呃 10s 过了,先打暴力吧。
贪心方法就直接按题目模拟了,注意为了防止精度的一些问题,可以进行公式转化:
aiwi>ajwjaiwj>ajwi\frac{a_i}{w_i}\gt \frac{a_j}{w_j}\\ a_iw_j\gt a_jw_i wi ai >wj aj ai wj >aj wi
最优解直接背包。
这样单次判断就是 O(nm)O(nm)O(nm) 了,搭配枚举重量可以做到 O(nm2n)O(nm2^n)O(nm2n)。
1h30min,15+12+0+0=2715+12+0+0=2715+12+0+0=27。
T3 是给出一棵树,要你给每个点赋一个权值,使每个点的子树的 mex\text{mex}mex 的之和尽可能大。
有点难啊。蓝/紫吧。花了 5s 没想出来一点,剩下 5s 喝水(
打 O(n(n+2))O(n^{(n+2)})O(n(n+2)) 暴力竟然只能拿两个点,太惨了。
1h50min,15+12+8+0=3515+12+8+0=3515+12+8+0=35。
T4 是一个数列查询,但查询的东西很猎奇。
这个 qqq 有点奇怪,感觉应该是对着答案用什么神秘算法?不管了,反正我肯定不会磕这题正解的,打暴力。
我好菜啊,只能打 O(nq4)O(nq^4)O(nq4) 暴力。喜提 000 个点。
2h20min,15+12+8+0=3515+12+8+0=3515+12+8+0=35。暴力分比预期低不少。
开始推 T1。
感觉挺简单的,橙吧。那就直接按照上面的思路想正解得了。
注意到两个两个选的操作一定会用在同一种糖果。这就不用证明了吧。
所以剩下的都是选一个的。显然,选一个的糖果 xix_ixi 越小越好。
我们可以先按 xi+yix_i+y_ixi +yi 排序,然后把所有的 xix_ixi 放进堆(按 xix_ixi 排序然后找 xi+yix_i+y_ixi +yi 最小值也行),然后枚举对多少种糖果选一个,最后将剩下的值除以 x1+y1x_1+y_1x1 +y1 即可。O(nlogn)O(n\log n)O(nlogn)。
这种做法大样例全过,自己也对拍了约 2×1062\times 10^62×106 组,都正确。
那可以说做法是对的吧。
2h40min,100+12+8+0=120100+12+8+0=120100+12+8+0=120。
然后是 T2。
考虑怎样才能卡快速获得最优解。
观察样例:
> 注意:若 w1=w2=1,w3=2w_1=w_2=1,w_3=2w1 =w2 =1,w3 =2,则小 R 会依次购买第 2 颗和第 1 颗糖果,原价总和为 4,但小 R 可以只购买第 3 颗糖果,原价总和为 5。
再思考一下,发现如下结论:
在小 R 的基础上,将最后几个重量为 111 的弹出,使得剩下的容量为 222,然后用这个 222 买原价最高的容量为 222 的物品,取最大值就是最优解。
按照这个思路就可以通过分组排序+双指针轻松设计出来 O(nlogn)O(n\log n)O(nlogn) 的判断方法了。对 aia_iai 预先排序可以去掉这个 log\loglog,时间复杂度为 O(n2n)O(n2^n)O(n2n),可以过 555 个点。
3h10min,100+20+8+0=128100+20+8+0=128100+20+8+0=128。
那正解应该是 O(n2)O(n^2)O(n2) 的 DP 了,对吧……?
没时间想正解了,只能再找性质拼点了。
看一下特殊性质。
诶怎么还有 aia_iai 相等的点啊。这么送?
3h30min,100+24+8+0=132100+24+8+0=132100+24+8+0=132。
然后注意到有 m=2m=2m=2 的点。显然可能的解法就是取两个价值最大的重量为 111 的物品或一个价值最大的重量为 222 的物品。
首先考虑只有一个重量为 111 的物品的情况。假设这个物品为 i(i>2)i(i\gt 2)i(i>2),显然它必须满足 ai<a1a_i\lt a_1ai <a1 且 2×ai>a12\times a_i\gt a_12×ai >a1 。
然后考虑多个重量为 111 的物品的情况。按照上面的结论,我们可以知道,只需要找到前两个重量为 111 的物品就行,后面的物品重量不重要。O(n2)O(n^2)O(n2) 枚举即可。
4h10min,100+44+8+0=152100+44+8+0=152100+44+8+0=152。
然后看了看 T3 依然想不出来,所以转到 T4。
我发现我的暴力显然可以用 ST 表优化。但是只剩 20min 了,我牺牲了检查文件的时间调这题,但是到考试结束也没调出来。
最终成绩:100+44+8+0=152100+44+8+0=152100+44+8+0=152。
DAY 1+
什么?黄紫紫紫?
什么?黄紫黑紫?
什么?黄紫黑黑?
你是说我一个 CSP-S 刚一等的蒟蒻在黄紫黑黑的比赛中拿了 152???