K0u1e

Thinking will not overcome fear but action will.

WPL与基本子串字典

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

浅谈FFT与NTT

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

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>...

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$到每个点的最...

AOJ2736-Longest Shortest Path

题意 传送门 给定一张$n$个点$m$条边的带权的有向图,边$i$的权值为$d_i$,你可以以$c_ix$的代价使边$i$的权值增加$x$,但是总代价不得超过$P$,问增加边权后从点$s$到点$t$的最短路的最大值为多少。 分析 首先可以根据原问题列出如下线性规划问题: 令$f_e$为第一类限制的对偶变量,$y$为第二类限制的对偶变量。 原问题可化成其对偶问题: 可以发现...