${\scr\color{Orchid}{\text{生于尘埃，溺于人海，死于理想高台。}}}$ 题目链接:ColorfulSlimes ${\scr\color{Cyan}{\text{Solution}}}$ 分析 思路：挺神奇的$dp$ 一个比较显然的结论：最小值的方案中第$2$种操作最多用$n-1$次 证明大概就是一个数用$n-1$次一定会变成另一个数 下面说说$dp$的思路： $dp[i][j]$表示能用最多$j$次第$2$种操作能变成$a_i$的最小值 假设$a_k$所有可以用最多$j$次第$2$种操作能变成$i$的最小值，则$dp[i][j]=a_k$ 举个栗子： 314 对...

Atcoder链接：Coins Luogu链接：Coins $\scr{\color{BlueViolet}{Solution}}$ 观察数据，发现$\cal{n}\le3000$，说明$Ο(\cal{n^2})$可过,容易想到DP。 用$\cal{dp[i][j]}$表示抛完第$\cal{i}$个硬币时，有$\cal{j}$个硬币正面朝上的概率。  考虑$\cal{dp[i][j]}$如何转移，易发现有以下两种情况，（当前正面朝上概率为$\cal{p_i}$）： 本次抛得硬币是正面：抛到正面概率乘抛完第$\cal{i-1}$个硬币后，有$j-1$个硬币朝上的概率。 本次抛得硬币...

CF链接：LeastPrefixSum Luogu链接：Least PrefixSum ${\scr\color{CornflowerBlue}{\text{Solution}}}$ 先来解释一下题意： 给定一个数组，问最少把多少个数变成相反数，使得$\forall\cal{i}$,$\sum_{k=1}^ia_k$$\le$ $ \sum_{k=1}^ma_k$ 发现对于所有数据点，$\cal{n}\le2\times10^5$，说明需要$Ο(\cal{n\logn})$或者$O(\cal{n})$的算法。 分析一下题目，发现要分成$\cal{i}>\c...

Loj链接：接竹竿 ${\scr\color{SkyBlue}{\text{Solution}}}$ 题目大意： 给定一个数组，每次加入一种颜色的数，可以取走与它颜色相同的两个数之间的所有数，问最后取走的所有数中最大和是多少 分析： 第一眼看到的是二分答案，但不知道二分的check()函数怎么写。 没办法，考虑DP（其实是因为我贪心写挂了） DP如果可以，那么要至少要满足一下几个条件： DP前面的选择情况不影响后面的选择情况（前不影响后） DP可以转移 时间、空间复杂度等可以以后慢慢优化啦！  尝试一下？ 尝试列出转移方程： $$dp[i]=max\begin{cases}dp...

前言 这是给c党的一点福利吧！（python根本不用写高精度） 对于一个懒懒的，不想写高精的人（就是我），每次都会遭遇到答案爆$long$ $long$的危险 比如说这道题： 题目传送门 最后的$23-25$的两个点，$long$ $long$甚至$unsigned$ $long$ $long$都无法满足，难道真的要手打高精度了吗？ 不，我们有$\_$$\_$$int$$128$！ 那么这到底是什么可以吃吗 ？ 关于$\_$$\_$$int$$128$ 先来看看一些常见的整数变量能存的范围与占用的字节： 类型名称 占用字节 存储范围 ...

Luogu链接：上帝造题的七分钟2/花神游历各国 ${\scr\color{ForestGreen}{\text{Solution}}}$ 题目大意 支持两种操作： 区间开方（向下取整） 区间求和 分析 发现线段树容易实现区间求和，考虑区间开方操作 其实并没有什么思路 我们发现了一个很显而易见神奇的事情,如果对一个正整数进行无限多的开方且下取整操作，最后这个数一定会变成$1$ 然后用计算器计算一下，发现$1$$10^{12}$里的一个数，最多开方$6$次，就能变成$1$ 所以一共最多只用修改$6\timesn$次，发现这是可以承受的 所以就很简单啦！维护区间最大值，如果区间内所有数都小于等...

CF链接：AlmostIdentityPermutations Luogu链接：AlmostIdentityPermutations ${\scr\color{Cyan}{\text{Solution}}}$ 前言 这好像是一道能用数学秒掉的题目 但由于我喜欢DP过菜，我们用DP来解决这个问题 分析 $dp[i][j]$表示在$i$个数里有$j$个数位置满足$a[i]i$ 答案很简单，就是$\sum_{i=n-k}^{n}dp[n][i]$ 接下来考虑状态如何转移 $dp[i][j]$可以由$dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]$转移而来 从$dp[i−1...

Lucas定理： 主要是求$C_{n}^{m}$在模$p$情况下($mod\,p$)(一般$p$较小，而$n,m$较大的情况) 公式: $C_{n}^{m}≡ C_{n\,mod\,p}^{m\,mod\,p}\timesC_{n/p}^{m/p} (mod\,p)$ 证明以后补吧 就以这题来说明具体解法： 题目 LuoguP3807【模板】卢卡斯定理/Lucas定理 Code: //From:201929 include<bits/stdc.h> defineLlonglong usingnamespacestd; Lpq[100005]; Ln,m,mod...