The secret of being a bore is to tell everything

0%

欢迎,这里是DXTsT,又名小裙子。
这个博客用来记录一些算法,黑科技等等,反正就是杂七杂八的东西。
在别的地方写过的文章,都会陆续搬到这里来,包括fs49.org

注意,本博客的所有题解代码都不保证能够直接提交AC,只是截取了部分核心代码,能不能AC还是要靠自己!

阅读全文 »

题意

给你一个字符串$S(|S|\leq 50)$,以及$m$个操作,这些操作可以分为:

  1. 在任意位置增加一个字符$x$
  2. 删除一个字符$x$
  3. 将字符$x$改变成字符$y$

每个操作都有一个代价$c_i$,求最少需要多少代价把$S$变成回文串。

阅读全文 »

题意

给你一个长度为$n$的集合,集合中每个元素是$[0,1]$之间的概率,代表第$i$个元素有$p_i$的概率变成1。求如何选择这个集合的一个子集,使得最后只有一个数为$1$的概率最大,输出这个概率。

阅读全文 »

题意

有一个由$1-n(n\leq 100)$构成的数列,其中部分被删除(删除的元素由$0$代替),请用被删除的元素补全这个数列,使这个数列中相邻元素奇偶性不同的对数最少。

阅读全文 »

题意

有$n (n\leq 3\times10^5)$个任务需要被完成,你可以把这些任务全部分成任意多组,每组内的任务必须连续。同组任务会在同一时刻完成,所花时间为$\sum_{i=l}^{r}t_i$,同时每组任务开始有一个预热时间$s$。任务$i$完成的费用为完成时间乘以$c_i$,求如何分组能让费用最小。

阅读全文 »

欧拉筛/线性筛

之前的素数判定中,我们曾使用埃拉托斯特尼筛法(Sieve of Eratosthenes),进行素数的筛选。但是这个算法的时间复杂度是$O(n\log{\log{n}})$的,因为每个数都被它筛了它的素因子个数那么多次。

阅读全文 »

定义:对于一个大于$1$的正整数$p$,如果$p$是质数/素数,那么对于所有$a|p$,$a$要么是$1$,要么是$p$。

那么对于一个数$x$,我们如何让计算机去判定它是不是质数/素数呢?

阅读全文 »