K0u1e

Thinking will not overcome fear but action will.

2020流水账

瘫在椅子上闲来无事想睡又嫌早就来写写总结。确实是因为有什么事情告一段落了才想写总结，但我一时也说不上是因为 ICPC 2020 济南的结束还是 2020 的结束。 CCPC-wannafly Camp 我也是猛然间想起来在秦皇岛度过的这个寒冷但充实的这一周居然就发生在 2020 年，不过是在年初，却给了我已经过去许久岁月的感觉。大抵是因为我是个健忘的人，发生过的事情一概抛到脑后，一段时...

Posted by K0u1e on December 31, 2020

WPL与基本子串字典

呐，在 cf 板刷的时候遇到了类似的题，又被 @huanggs 问起了这道题，想着之前只是草草过了一遍挑了需要的一部分看,现在也忘得差不多了，就来重新捋一捋，大部分都是摘自陈孙立的集训队论文，证明就慢慢咕了吧。一些定义定义 1：若串 $S$ 和整数 $x$ 满足 $1\le x \le \vert S \vert $，且对于所有的 $1 \le i \le \vert S \vert...

Posted by K0u1e on April 7, 2020

浅谈FFT与NTT

本来觉得明明去年暑假里就学过了现在却忘得干干净净了真是太丢人了，看了zzy的ppt以后发现自己根本就没有学会过，这里%%%zzy。离散傅里叶变换设$a,b$分别为两个多项式的系数数组，类型为复数，度数界分别为$n$和$m$。现在要求多项式系数数组$c=a \cdot b$。这里不妨把$a,b$的度数界统一定为不小于$n+m-1$的$2$的幂次$n$。首先把$a$和$b$两数组...

Posted by K0u1e on March 28, 2020

Ozon Tech Challenge 2020

Div.1 + Div.2

题解 A - Kuroni and the Gifts 因为保证了$a$ 、$b$数组本身并没有相同元素，所以排序后输出即可。 B - Kuroni and Simple Strings 从左往右一直拿左括号从右往左一直拿右括号，显然到最后左边只剩右括号右边只剩左括号，只要这么拿一次就够了。 C - Kuroni and Impossible Calculation 当$n>...

Posted by K0u1e on March 4, 2020

Codeforces Round 625

Div. 1, based on Technocup 2020 Final Round

题解 A - Journey Planning 因为要保证$c_{i+1}-c_i=b_{c_{i+1}}-b_{c_i}$，即要满足$c_{i+1}-b_{c_{i+1}}=c_i-b_{c_i}$，那我们把所有$c-b_c$相等的$b_c$加到一起再找个最大值即可，注意$c-b_c$可能为负数。 B - Navigation System 反向建图，$bfs$求$t$到每个点的最...

Posted by K0u1e on March 2, 2020

AOJ2736-Longest Shortest Path

题意传送门给定一张$n$个点$m$条边的带权的有向图，边$i$的权值为$d_i$，你可以以$c_ix$的代价使边$i$的权值增加$x$，但是总代价不得超过$P$，问增加边权后从点$s$到点$t$的最短路的最大值为多少。分析首先可以根据原问题列出如下线性规划问题： \[\max \quad p_t-p_s\\ s.t. \quad p_v-p_u\le x_e+d_e \\ \...

Posted by K0u1e on March 1, 2020