立体防御
To Misaka16172:\text{To Misaka16172:}To Misaka16172:
如果你飘了:
在打上那个分段之前,永远不要觉得自己有某个分段的实力,“场数不够” “之前没发挥好掉分了” 都不能作为借口。
做题数量甚至 rating 都并不与赛场表现成正比。
多找找你和周围其他人的差距。
如果你颓了:
世界上没有好打的逆风局,阶段性的挫折几乎是必然的。
无论上限如何,先相信自己的下限。
向前看,不要老是羡慕年龄比自己小的选手。
其他选手的水平都是动态的,在“找找与周围人的差距”之前不妨先与自己对比。
一场比赛并不能给你下定义,即使是正式比赛也是如此。
最后,在 whk 上多花点时间,有时间的话可以给自己找点别的事干。同时,注意身体状况和心理状况也是极为必要的。
Codeforces / AtCoder 刷题记录
日常训练模式已经改为 Misaka’s Daily,因此本页面已经弃用。原内容如下。
Codeforces / AtCoder 做题记录 since 2023.12
从 2024/1/26 开始记录每一道题的罚时。
评分标准:1-10:
1表示代码照着题解打的
5以下代表思路主要由题解启发
7以下代表思路细节参考了题解
8代表参考了讨论区或者下载了数据
9代表看了算法标签
10表示完全独立完成
距离 NOIp 2024 还有\text{距离\ NOIp\ 2024\ 还有}
距离 NOIp 2024 还有
Codeforces
*难度未定:
*[1300,1500]:
CF1914E *1400 9\color{green}99
CF1850F *1300 10\color{green}1010
CF1913C *1300 10\color{green}1010
CF1907D *1400 9\color{green}99
CF1915F *1500 10\color{green}1010
CF1916C *1200 5\color{orange}55
CF1922C ...
P2318 虚拟内存 题解
P2318 [HNOI2005] 虚拟内存 题解
前言
这远古题怎么还能交题解。
思路
考虑使用数据结构直接模拟题目操作,这里直接使用线段树。
线段树的下标代表内存空间,每个节点里存两个 int 和一个 pair,两个 int 分别代表当前节点里有几个下标已经有数了,另一个只在叶子节点有用,代表当前节点存储的数是多少;pair 第一维代表访问次数,第二维代表插入时间。同时开一个 map,记录某个数在内存里的下标。
模拟过程如下:
若当前数在 map 里有值,则将线段树上其对应下标处加 111,同时答案加 111,否则继续下一步;
使用线段树上二分找出一个还没有被占用的下标,若能找到这样的下标,则将其修改为当前值,同时更新 map 里的下标,否则继续下一步;
若当前所有下标都被占用,则在线段树上查询访问次数最少、插入时间最早的下标,将该位置之前对应的值在 map 里的下标置为 000,并在线段树上修改为当前值。
细节详见代码。
代码
123456789101112131415161718192021222324252627282930313233343536373839 ...
ABC358G AtCoder Tour 题解
[ABC358G] AtCoder Tour 题解
思路
思路是简单的,使用分层图的思想递推地求出对于每个格子走了 k≤n×mk\leq n\times mk≤n×m 步之后最大的价值(记为 valx,y,kval_{x,y,k}valx,y,k,递推式为 valx,y,k=max{valx′,y′,k−1+ax,y},∣x′−x∣+∣y′−y∣≤1val_{x,y,k}=\max\{val_{x',y',k-1}+a_{x,y}\},|x'-x|+|y'-y|\leq 1valx,y,k=max{valx′,y′,k−1+ax,y},∣x′−x∣+∣y′−y∣≤1),记 mk=min(k,n×m)mk=\min(k,n\times m)mk=min(k,n×m),最后答案则是 max{valx,y,mk+ax,y×(k−mk)}\max\{val_{x,y,mk}+a_{x,y}\times (k-mk)\}max{valx,y,mk+ax,y×(k−mk)},时间复杂度 O(n2m2)\mathcal{O}(n^2m^2) ...
P10564 [ICPC2024 Xi'an I] Rubbish Sorting 题解
P10564 [ICPC2024 Xi’an I] Rubbish Sorting 题解
思路
观察到 ∣s∣|s|∣s∣ 只有 555,于是考虑状态压缩。
可以枚举一个位数为当前字符串长度的二进制数 ststst,每一位代表这一位是否进行匹配。然后我们就可以根据 ststst 再进行一次状压,把字符串压成一个 272727 进制的数,每一位 ≥1\geq 1≥1 时代表字母,是 000 则代表这一位没有被匹配。这个数的最大大小为 ∑i=0426i<1.5×106\sum^{4}_{i=0}26^i<1.5\times 10^6∑i=0426i<1.5×106,可以直接开数组统计。
插入时,我们把字符串对应的所有状态曾经对应过的 xxx 取 min\minmin,查找时按匹配度从大到小查询,如果当前答案不为 inf 就直接输出,这题就做完了,复杂度 O(2∣s∣∣s∣×q)。\mathcal{O}(2^{|s|}|s|\times q)。O(2∣s∣∣s∣×q)。
代码
1234567891011121314151617181920212223242526272 ...
AtCoder Beginner Contest 355 - E Guess the Sum 题解
[ABC355E] Guess the Sum 题解
前言
非常好交互题,使我的思维旋转。大概是最近几场 abc 里唯一一道比较值得带脑子做的 E 题。
思路
按照题意模拟后,可以画出一张允许被查询的区间的示意图:
你会发现这个东西长得跟线段树很像,但如果把线段树的递归查询函数照葫芦画瓢写上就会发现 WA 了三分之二的测试点,原因则是交互次数不能保证最优,比如说图里的 [1,7][1,7][1,7] 实际上只用查 [0,7],[0,0][0,7],[0,0][0,7],[0,0] 两次,用这种方法需要查 [1,1],[2,3],[4,7][1,1],[2,3],[4,7][1,1],[2,3],[4,7] 三次。
上面的乱搞给了我们一个启示,那就是最优的询问次数很可能小于 logn\log nlogn,从而我们可以推断,我们需要使用的询问方式并不是一种基于复杂度分析的通用策略(因为不管什么固定策略都不会比 log\loglog 的询问复杂度更优秀了),而是会根据输入动态调整的。此时可以开始考虑如何转化题意,使问题更加可做。
转化
看了官方题解的应该都知道是把询问转化成图上的边 ...
CCPC 2024 北京市赛打铁记
CCPC 2024 北京市赛打铁记
前言
没想到自己参加的第一场 ACM/ICPC 正式比赛竟然会在高中。
Day 0
机房用 SEERC 2018 的题出了场模拟赛。
我们队只切了三个题,说实话表现比较惨。隔壁小朋友 hyf 他们的队伍竟然切了 6 题,能不能每一队都发一个小朋友来 carry。
切掉的三个题里只有 E - [SEERC2018] Fishermen 是我自己做出来的,明明是签到题还花了好久时间。zzj 写掉了 [B - SEERC2018] Broken Watch 和 C - [SEERC2018] Tree,思路是 cyx 和 zzj 两个人一块想出来的,我参与的比较少。唉还是只能靠队友带飞。赛时还和 cyx 想了 D - [SEERC2018] Space Station 和 H - [SEERC2018] Modern Djinn,但是毫无结果。
赛后一翻题解,卧槽 H 正解怎么是个随机化,有病吧。J 明明这么可爱场上却没人做,应该是被题面吓跑了。
希望今天的发挥能给明天涨点 rp。
Day 1
昨天晚上没睡好,可能也有一部分是【数据删除】的缘故,早上不到 ...
CF1930C Lexicographically Largest 题解
CF1930C Lexicographically Largest 题解
前言
很有意思的一道题。
做法参考了 CF 官方题解。
思路
考虑进行一次操作会对其他元素造成的影响。
删除 aia_iai 会使其右边的所有元素下标减少 111,而我们的任务是让最后得到的集合 SSS 字典序最大,所以我们希望每个数的下标都尽量不要减少。
但问题在于 SSS 并不是一个可重集,故我们不能直接从右往左执行操作,因为这样给 SSS 带来的元素虽然是最大的,但可能会出现重复的情况,例如样例里的 2 1,如果先删右边的 111 再删 222 就会带来两个重复的 333,去重后字典序小于答案 3 2。
于是我们可以考虑每个数的下标减小了几次,记作 ci (0≤ci<i)c_i\ (0\leq c_i<i)ci (0≤ci<i),则任务就变成了对于每个 aia_iai 找到最小的 cic_ici,使得对于任意 j<ij<ij<i,ai+i−ci≠aj+j−cja_i+i-c_i≠a_j+j-c_jai+i−ci=aj+j−cj。发现无论求解 cic ...
Sth.
第一次弄了一点自己能听下去的东西。
虽然风格与某首歌很雷同就是了。
Here.
很短,不怎么好听,但也算是一个不算交代的交代。