P5664 [CSP-S2019] Emiya 家今天的饭

idea:

先容斥，将原问题转化为总方案减去不合法的方案。用乘法原理快速计算总方案，再寻找到一个漂亮的性质，利用 $dp$ 计算出不合法方案。 $dp$ 进行一步优化，减去无用状态。

简化题意：

P3214 [HNOI2011] 卡农

打表找规律失败了。。。

参考题解第一篇。

其实就差一步的思路。

P3978 [TJOI2015]概率论

参考 $rqy$ 的题解（第一篇）：

设 $f_n$ 表示 $n$ 个节点的树的形态数， $g_n$ 表示 $n$ 个节点的所有树的叶子总数。

首先看 $f$ ：

Part1. 快速幂（写给CTR）

问题：给定 $a,b,p$ ，求出 $a^b\mod p$ 。

对于这个问题，有一个显然的解法：将答案初始化为 $1$ ，我们循环 $b$ 次，每次都将答案乘上 $a$ ，并模个 $p$ 。显然地，此方法时间复杂度为 $O(b)$ 。

• Splay是一种平衡树，能做到单次查询均摊复杂度为 $O(\log n)$ 。

• 容易忘的东西： $lazytag$ 未清零。。。 $son(x,0)$ 忘记套 $sz()$ 。。。 $splay()$ 忘记更新根节点。。。 $maintain$ 忘记。。。倒是 $splay$ 每次都记得写。。。

1.$vector$

定义：

vector<typename> name 来声明一个空的 $vector$ 。

我们来进行一些学习：

数据结构：

栈

队列

首先，可以感性地发现挪馅饼时出现负值不会影响最终答案，只要最终方案是非负的就行了。

所以，我们不妨规定，一个盘子只能从右边一个盘子拿馅饼，或者向右边一个盘子放馅饼。

我们用 $f_{i,j,k}$ 表示前 $i$ 盘放 $j$ 张馅饼，第 $i$ 盘放 $k$ 张馅饼的最小花费。不难发现 $f_{i,j,k}$ 可以转移到 $f_{i+1,j+p,p}$ 。

P8251 [NOI Online 2022 提高组] 丹钓战

题意十分明白（这次NOI Online题意给得实在是太舒服了），不再赘述。

其实一开始我以为要利用 $a_i\neq a_j$ 来做文章，后面发现好像并不需要。

前面两位大佬用的都是 $O( n^2 \log n)$ 的树状数组解法，所以我想提出一个$ O(n^2) $ 的解法，欢迎指出问题。

首先，冒泡排序（或是英文题面中的插入排序）需要交换的次数就是逆序对的个数。

怎么证明呢？其实很好理解。我们假设所有数都加上了 $1$ ，也就是原数组变成了 $1...n$ 的一个排列。当你交换 $a_i$ 和 $a_{i+1}$ 时，这两个数肯定是一对逆序对。而同时这两个数又是挨在一起的，所以 $1...i-1$ 的所有数往后的逆序对不会改变， $i+2...n$ 往前的逆序对也不会改变，相当于就干掉了一个逆序对。所以每次交换干掉一个逆序对，也就是说逆序对的个数就是要交换的个数。