我想吃士力架 | CSP 游记
本来还想着退役呢。
前情提要：
去年逛游记时看到一个大佬打 S 组时打一道题吃一根士力架。
Day -2~-1
这两天学校搞运动会，但是教练还要求我们晚上
教练还让我们早上把电脑带学校里订正，于是在别人运动会时狠狠爽了一把（事实是我没摸鱼，倒是有个机房耻辱玩游戏被年级委员抓了）。
Day 0
没比赛，
OI 倒是学了快三年，怎么连绿题都切不了。要 AFO 了。
晚上在床上哭了。
Day 1
早起打车去 FJ 福州。
到了考点，发现都来得比我晚（？）。等其它同学陆陆续续到了后聊了聊，就进考场了。
发现考场是我第一次考 J 组的地方，心里有点惊喜，又有点失落。讲个有始有终吧。
上善若水。
考 J 组时试了试把记录写代码里。
T1
/*
欸t1怎么这么水
拿个vector装吧懒得手写了
欸不是大样例怎么挂了
算了大样例懒得对了
手写吧
10:31打了一个Hash发现大样例没挂
不是这要是挂了我也是神人了
*/T2
/*
？请输入文本
n和m好大
请输入文本
孩子们我是推式子题
CCF我们真爱你口牙
10:33不是这个东西真的有必要对拍吗
不对这是连暴力都没得打的题
欸我有一计我推一下O(1)式子看看能不能过
简单推了一下发现第x个数的坐标是(\lfloor\frac{x}{n+1}\rfloor+[(n+1)|x]，x%(n+1)-[(n+1)|x])
ok小样例炸了
哦是向上取整
还少了一个非和减法 和其他东西
ok小样例过了
ok第三个炸了
算了好复杂，还要分类讨论，不写了
反正是可以O(n)的
*/ T3
/*
终于有点有思考含量的题了。
令dp[i]表示序列1~i的答案
n^2dp正确性包过。
考虑优化，想着推斜率（？）
哦可以贪心选取，一个i一定是选位置最接近他的j
哦哦哦有a^b=c，\notexist d\not=b， a^b=c
一看a是10^6级别的
所以可以直接记 pos[i]表示最右边的一个j，使i^sum[pos[i]]=K
然后没了。
欸一个i所更新的pos只对后面有效哦哦哦
线段树（？）
ok换一下顺序就可以了
欸怎么第五个样例挂了
哦这时候dp[i]表示的是以i为结尾有一个序列的最大值
所以要记一个maxdp。
10：52孩子们我回来打对拍了
算了暴力不会打，随便测点数据吧
但愿没问题
欸这题是不是可以打状压（？）
*/T4
/*
孩子们9:30t4我来了
他这个多边形边数没限制那我不就可以直接排序后枚举最大值
那问题就转化成了求序列1~i-1中有多少个子序列S，使sum a_{S_j}>a_i
记dp[i]表示1~i的答案
好难统计
欸不对n和a都是5000级别的
那我就可以直接记dp[i][j]表示1~i中子序列和>=j的序列数
哦哦不对我可以直接记=j就好了
然后树状数组统计一下答案不就好了
欸好严峻的问题
sum a<=25000000
炸了
欸如果直接记 dp[i][j]表示1~i中子序列和>=j的序列数好像也可以直接求啊
ok小样例过了 ，树状数组都不用了
欸忘取模了
拿下
去打对拍了
11:00孩子们我回来了
我想吃士力架
这次比赛怎么这么水
不行我不能说大话
但愿不会爆0
希望下午不要太难
不然我就afo了
去上厕所的路上看到ljf都快睡上了
11：22算了打个指数级的暴力对拍吧
11:33ok对拍了几组都没问题
*/我想吃士力架。
预计得分
中午去下午考场附近的一家店吃了饭，只能说一份意面比拳头小卖
在饭店靠着 Penguin（同学） 浅眯了一会儿。
下午紧张死了，因为好像教练之前一直说“S 没 1= 就退役”这种话。我有 1= 的实力吗？
士力架忘买了，倒是获得了同学送的小块德芙。
进了考场，不敢在代码里写记录了（怕没时间）。
人杰地灵（好吧其实我都没看到这玩意是监考老师已经解压好后的文件发给我们的）。
T1 一眼贪心，但是我考场犯唐了啊啊啊啊啊啊一直想着反悔可能不止反悔一次（比如枚举到
转战 T2，发现不会做，打了个暴力+特殊性质就跑了，此时剩下不到 1h。
看了 T3 发现更不会做，然后想着可以直接打个 Hash 表
调试了好久终于过了样例。此时没时间了。于是我又没看到 T4 的题面(同去年)。
预估成绩
我想吃士力架。
Day ?
成绩出来了，J 组
一看代码 T2 文件忘开了
当时大概还剩
2 分钟，然后我突然想测一下 T2，然后关了文件，造了个类似这样的样例:3
1 2 3 4 5 6 7 8 9
是的孩子们我忘记是输入两个数了，虚空调试 1 分钟后文件忘开回去了。
T4 数组小了，怒失 108 分。
S 组 T1 炸到
就是这 1= 拿的一点水准都没有。
我想吃士力架，但是感冒了。