The secret of being a bore is to tell everything

0%

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

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

阅读全文 »

题意

有一个由$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$的自然数,都可以写成质数次方的积,且这些质数从小到大排列后,仅存在这一种分解方式。

换句话说,每个$n>1$,都有唯一一种分解方式$\prod_{k} p_k^{\alpha_k} = n$。

阅读全文 »

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

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

阅读全文 »

题意

一开始有一个整数$n(n\leq 10^{15})$,你可以执行以下操作$k(k\leq 10^4)$次:把$n$替换成$n$的任意一个约数(包括$1$和$n$),假设每个约数都有相同概率被选中。现在问你$k$次操作后剩下这个数的期望值是多少。

阅读全文 »

题意

一个$N \times M (N, M \leq 10^9)$的地图上有$W (W \leq 10^5)$棵树。对于图上没有树的点,如果在这个点上下左右都至少有$k (1 \leq k \leq 10)$个点,那么它会贡献${L\choose{k}} * {R\choose{k}} * {U\choose{k}}* {D\choose{k}}$点虔诚度,问这个地图上所有虔诚度之和模$2147483648$(有毒)的值。

阅读全文 »

学算法一年了,做了很多题,但是对于二分法这块一直不是很明白。 有时候遇到二分答案的问题经常要调好长时间才能写对,有些时候就是看别人二分是怎么写的就照抄,但是并不清楚为什么这么写是对的。今天总结了一下二分法的几种情况以及它们的思路。

阅读全文 »