ww3113306

摘要： "中文题面" 题目中有个k的限制比较麻烦，我们稍微转换一下，令$g[i][j]$表示第$i$位，第$j$个字母，能否在k的范围内匹配上。 那么这个数组可以由类似滑动窗口的方式来解决： 新定义一个数组$T[i][j]$表示S串中第$i$个字母是不是$j$，如果是则为1，反之为0.(注意与原题面中的T串 阅读全文

摘要： 题意： $n$个数，有$m$个操作，形如： 1,将$x_i$​改成$val_i$​ 2,将$x_i$加上$val_i$​ 3,将$x_i$​乘上$val_i$ 其中第$i$个操作的编号为$i$. 现在你可以从中选择最多$k$个操作(不能重复选),并按一定顺序执行，使得$\prod_{i = 1}^{ 阅读全文

摘要： 题意： $n$个物品，每个物品有一个价格，买一个高价格的物品，可以选择免费得到一个价格严格低于这个物品的物品。求得到$n$个物品的最小代价。 题解： 神仙贪心…… 题目要求求出最小代价，相当于求最多能免费拿的价格。 先考虑一个$n^2$的DP：将物品按价格从高到低排序。把相同价格的物品放在一起处理。 阅读全文

摘要： "题面" 题解： $$F_j = \sum_{i j}{\frac{q_iq_j}{(i j)^2}}$$ $$E_j = \sum_{i j}{\frac{q_i}{(i j)^2}}$$ 对式子的2个部分分别计算。 令$S_i = i^2$ $$\sum_{i j$就变成$i using nam 阅读全文

摘要： 多项式求逆 一些概念 多项式的度：对于一个多项式$A(x)$,称其最高项为这个多项式的度，记为$degA$ 多项式除法：对于多项式$A(x), B(x)$,存在唯一确定的$Q(x),R(x)$满足$$A(x) = Q(x)B(x) + R(x)$$ 其中$degR 1$的情况，设 $$B(x) = 阅读全文

摘要： [TOC] FFT 参考blog: "十分简明易懂的FFT（快速傅里叶变换）" "快速傅里叶变换(FFT)详解" (下面的图片是来自于这2篇博客里面的，仔细看可以发现右下角有水印……) 系数表示法 一个一元$n$次多项式$f(x)$可以被表示为：$$f(x) = \sum_{i = 0}^{n}a_ 阅读全文

摘要： 额……好像咕了 阅读全文

摘要： "题面" 题意：(感觉题面写的题意是错的?)有$n$种能量不同的圈，设当前拥有的圈的集合为$S$,则： 1，每天有$p$概率失去一个能量最小的圈。特别的，如果$S = \varnothing$,那么这个概率为0. 2，否则将得到一个满足$能量 \le S_{min}$的圈。 求$S$内的能量和大于$ 阅读全文

摘要： 题意：$n$个赌场，每个赌场有$p_{i}$的胜率，如果赢了就走到下一个赌场，输了就退回上一个赌场，规定$1$号赌场的上一个是$0$号赌场，$n$号赌场的下一个是$n + 1$号赌场，一旦到达$0$或$n + 1$号赌场就相当于退出赌局了。 定义统治区间$[l, r]$为从第$l$个赌场开始，到达第 阅读全文

摘要： (当时写这篇题解的时候，，，不知道为什么，，，写的非常冗杂，，，不想改了。。。) 题意：一张有n个点的图，其中每天第i个点到第j个点的边都有$P_{i, j}$的概率开放，每天可以选择走一步或者留在原地，求从1号点到n号点的最优期望值。题解： $f(x)$表示从$x$出发，走到$n$的最优期望时间。 阅读全文