DAY -2
请输入文本。
DAY -1
请输入文本。
DAY 0
请输入文本
DAY 1
OI 赛制。
好,开始先看题。
T1 很显然,整体循环变换,单点改整体查。文明哥平衡树秒了。
T2 叽里咕噜说什么呢。
T3 n≤500n\le 500n≤500,感觉有点不可做(?
T4 俩数组,求区间和是否回文,感觉像字符串哈希。切完 T1T2 就开它。
T1 直接预处理所有数的和,整体循环就加个偏移。样例过了,直接交不管它。用时 10min。
T2 重新读一遍题:环形,nnn 个点,距离,机器人,跳跃,每次跳跃灵敏度不小于距离,跳跃完灵敏度 +1+1+1,求出发点使初始灵敏度最小。
好,有个很显然的结论:如果初始点是 iii 的话,初始灵敏度最小值为 maxj=0n−1A(i+j−1) mod n+1−i\max_{j=0}^{n-1} A_{(i+j-1)\space \text{mod}\space n+1}-imaxj=0n−1 A(i+j−1) mod n+1 −i。
环转链,对每个点加个懒标记 −i-i−i,单调队列区间求和,最后加上 iii 求最小值即可。时间复杂度 O(n)O(n)O(n)。
样例过了,写了个暴力对拍没问题,应该能过的。交了,用时 60min。
好的来到 T4。
不对啊哈希只能 O(nlogn)O(n\log n)O(nlogn) 求是否存在啊。哦哦哦哦哦可以二分。直接双老哥启动。
写代码ing。。。
欸卧槽反着的怎么求。哦哦哦直接求逆元就行了。但是模数得是质数。那就取 109+710^9+7109+7 吧。
疯狂地写+调代码 1h 。。。
不是我的答案怎么是 1 啊
哦,如果 lll 可以,l−1l-1l−1 不一定可以,不满足单调性了啊……
欸等等,l−2l-2l−2 一定可以!!!又可以了,把奇偶分开二分就行了!
噢噢噢噢噢噢噢噢非绝热i高房价无人机如果加热管结果i就 感觉热狗评估价格估计刚刚进入 就监管机构就尴尬加热破i热加工人i机构i就给人家破i估计热给金额皮结果i热感觉破i机构i给及公共i派个人机构i如果人家热狗i加热哦及个人隔热经过人工i金额破基金认购 ij给哦加热锅加热机构i结果热键ijrei 哦i积分ijg钢结构i干净给样例过了!!!!!!!!!!!!
光速写了个暴力,对拍了 3×1063\times 10^63×106 组 n=10n=10n=10 的随机数据,没出问题。
看看 n=105n=10^5n=105 的纯随机运行结果是多少。
什么???9万???
换个乘数试试
丸啦答案不一样
直接根据原做法光速写了个三模哈希(109+7,998244353,100000310^9+7,998244353,1000003109+7,998244353,1000003)。
唉……终于正常了。。。。。答案是 999。只不过为啥运行 5s 啊。。。。。。
以为是三模哈希的问题,卡了三次常没一个成功的,最终放弃了,选择相信 ACGO 评测机。
太累了,T3 懒得想正解了,打个贪心乱搞得了。
DAY 1.14514
出结果了,T4 不负众望地 TLE 了。
100+100+4+72=276100+100+4+72=276100+100+4+72=276,这个史成绩甚至还登上 rk1 了。