题解1628d game sum

### 总述 此题用区间 dp 解决，二维前缀和优化。 ### 朴素做法 **阶段**：自上而下数每一层。 **状态**：$dp_{i,l,r}$ 表示自上而下数第 $i$ 行中在 $[l,r]$ 摆积木的方案数。 **状态转移方程**：根据题意可知，若要在 $[l,r]$ 中摆积木，那么 $[l, ......

先注意到我们娱乐值损耗的多少只与最后一场电影有关系，所以假设最后一场电影看的下标为 $k$，那么最后就要减去 $d \times k$。 得出这个性质之后开个小根堆反悔贪心即可，首先 $a_i0$ 的，如果还没到 $m$ 场电影，我们就直接往里塞就可以，如果到了，我们就进行反悔操作，取出已选的贡献最 ......

首先这是一道很明显的换根 dp。 首先注意到要拼接数，所以我们可以先处理出 $num_i=10^{x}$，使得 $10^x > a_i > 10^{x-1}$，这样方便我们后面算贡献。 我们以这棵树为例子来推状态转移方程。 ![](https://cdn.luogu.com.cn/upload/im ......

首先考虑无解的情况，很明显 $a_n$ 必须为 $0$，否则没有解，因为如果最后一位为 $1$ 那么必须有 $n$ 这个数存在于 $b$ 序列中，而这种情况时不符合题意的。 然后考虑如何求解，先考虑一种比较特殊的情况，就是若干个 $1$ 后面接着一个 $0$，这里假设 $1$ 的数量有 $k$ 个， ......

设 $check_i$ 为 $1\sim n$ 中满足题意的数的数量。 显然答案为 $check_j-check_{i-1}$。 注意到 $check$ 能直接暴力求出来。 那么就可以先把 $10^6$ 范围内的所有质数求出来，然后所有数跑一遍，每个数都去旋转得出所有数后判断是否均为质数，记录下来。 ......

- 给定 $n$，求： $$\sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}$$ - 思路分析： 先化式子： $$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}&= \sum_{d= ......

## A 考虑在所有 $0$ 前添加正号，在 $1$ 前轮流添加正负号即可。 ## B 首先根据抽屉原理，我们可以取出最多的颜色，个数记为 $mx$，然后其余颜色可以填在 $mx$ 的两两中间，最少要有 $(mx-1)(k-1)$ 个空位。 但是只是必要的，而不是充分的。考虑有多个最大值的情况，发现 ......

[problem](https://www.luogu.com.cn/problem/P3888) & [blog](https://www.cnblogs.com/liangbowen/p/17664121.html)。 这怎么评到紫上去的啊？差不多就个上位绿吧 /qd。 首先出题人非常 low。 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1864E "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1864/E "CF 传送门") 感觉是很费脑子的题，可能是因为我没有脑子。 因为 ......

#### **[原题传送门](https://atcoder.jp/contests/arc080/tasks/arc080_c)** 题意：给定一个 $n$ 的排列 $a$ 和一个初始为空的序列 $b$。你每次需要在 $a$ 中选择一对相邻的数，把它们从 $a$ 中拿出来，并按原先的相对顺序插到 ......

# [HAOI2012] 高速公路 题解 [题目链接](https://www.luogu.com.cn/problem/P2221) 题目要求我们求期望，先考虑一下求期望的公式。 根据期望的定义得：期望费用 $E_v = \dfrac{所有可能路线的总费用}{所有可能路线的数量}$. 其中，所有可 ......

[problem](https://www.luogu.com.cn/problem/P2238) & [blog](https://www.cnblogs.com/liangbowen/p/17663441.html)。 kkk 的题解有一些地方是错的 /cf，所以写篇题解造福后人。 一眼 DP， ......

# [BJWC2010] 严格次小生成树 ## 题目描述 小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： ......

```cpp #include using namespace std; typedef long long ll; ll n,a[5000+10],b[5000+10],abpre[5000+10],absuf[5000+10],ans; int main(){ cin >> n; for(ll ......

# P5629 【AFOI-19】区间与除法 题解 由于题目中的运算是除法，所以对于一个数字 $x$，最多运算次数不会超过 $\lceil\log_{d}x\rceil$ 就会变成 $0$。 然后我们就可以在 $O(n\log C)$ 的时间复杂度内算出来每一个数字能被哪些原数消灭。 这样处理询问仍 ......

前言 最近学了一种新的数位dp的状态表示，打算应用到以前做过的数位dp的题目。如果我们对数$N$进行数位dp，以前的状态定义$f(i,j)$表示所有数位大小为$i$且最高位是数字$j$的数的个数，如果还有其他约束条件那么再补充相应的状态即可。而新的状态定义则是$f(i,1)$和$f(i,0)$，其中 ......

torch.sum()维度0，1，2。比如现在有$3\times\ 2\times3$的张量，理解为3个$2\times3$的矩阵。当dim=0，1，2时分别在哪个维度上相加[^文艺数学君]？下面是具体的矩阵 $$ [1,2,3]\\ [4,5,6]\\\\ [1,2,3] \\ [4,5,6]\\ ......

[题目链接](https://leetcode.cn/problems/3sum) 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nu ......

[销售基因链](https://www.luogu.com.cn/problem/P9196) ### 题目大意 给定 $n$ 个字符串，长度总和为 $m$，进行 $q$ 次询问，每次询问给定两个字符串 $p,s$，问所有的字符串中以 $p$ 为前缀且以 $s$ 为后缀的有多少个。 ### 思路分析 ......

​ 洛谷P5937 [CEOI1999]Parity Game ​ 本来是想练习一下离散化的，结果看到这道又有并查集又有离散化的题，于是就逝了逝，在阅读题解后， 发现自己对并查集和离散化认识有点问题，于是写下这篇笔记总结一下。 看到这种给出几个条件判断矛盾的题，便想到了两种常见思路，一种是拓扑排序， ......

# Shadow Mapping (Games202) ## 2-Pass Algorithm ### Pass 1. Render from Light Pass1需要知道光线能照射到的点，也就是从光源所在的视角去渲染模型，有哪些是能被渲染出，哪些会被遮挡住而不被渲染。 ![16928508543 ......

# [P2486 [SDOI2011] 染色](https://www.luogu.com.cn/problem/P2486) 神仙树剖题。 ## 题意 给你一棵树，每个点都有颜色，支持下面两种操作： * 路径染色。 * 路径颜色段数量查询。 ## 树剖部分 我们看到树上问题，不好处理，所以想办法给 ......

### 分析： 贪心算法。 有 $n$ 个客人。对于每一位客人，我们都要遍历一遍所有房间，找出最优入住房间编号。 设当前遍历的房间编号为 $j$。 分三种情况： 1. 左右两边的房间皆空，则为最优房间。 2. 左右两边只有一个房间有客人，则愤怒值加 $2$（因为有两个客人所以加 $2$）。 3. 左 ......

让人头大的数位DP。建议评蓝。个人认为不适合放ABC的F。 将三个数二进制拆分，使三个数异或为0相当于每个二进制位三个数中有0或2个是1。 所以考虑数位DP，设 $dp[i][m1][m2][m3][lim1][lim2][lim3]$ 为第 $i$ 位，三个数模 $a$ , $b$ , $c$ 分 ......

[题目链接](https://www.luogu.com.cn/problem/P9580) 挺好的博弈论题，这是一个跟官方题解不太一样的做法。 遇到这种组合游戏可以先考虑逆推胜负，把握一下规律，我们先从一个区间的胜负判断开始入手。 考察区间中最后一个数字的从属关系，如果它属于弈，因为 $a_i>0 ......

## 思路 考虑区间 DP。 设 $f_{i, j}$ 表示要刷到 $[i, j]$ 这一段的目标需要的最小次数。 对于 $f_{i, j}$， 如果 $color_i$ 与 $color_j$ 相等，那么再子区间合并的时候就可以少刷一次，即 $f_{i, j} = \min\limits_{k = ......

## 题意 题目给定了一个长度为$n$序列$a$与$m$个操作，操作一共有3种： 1.给定$x,y$，使$a_x$增加$y$。 2.给定$x$，使$a$中所有数全部乘上$x$。 3.给出k个数$c_1,c_2,...,c_k$，表示这个操作的任务是按照先后顺序执行编号为$c_1,c_2,...,c_ ......

## 思路 设 $f_{i, j, k}$ 表示从原点走到 $(i, j)$ 模 $m$ 后的乘积为 $k$ 的方案数。 状态转移：$f_{i, j, ka_{i, j} \bmod m} = f_{i - 1, j, k} + f_{i, j - 1, k}$ 统计答案：$f_{n, n, k}$ ......

## 思路 我们发现两种操作都不会影响字符之和。 考虑动态规划， 设 $f_{i, j}$ 表示在前 $i$ 位，可以达到和为 $j$ 的方案数。 有 $f_{i, j} = \sum\limits_{k = 0}^{25}f_{i - 1, j - k}$。 最后记得 $-1$，表示去除原始字符串 ......

# AT_agc030_d [AGC030D] Inversion Sum 题解 ## 题目大意 给你一个长度为 $n$ 的数列，然后给你 $q$ 次交换操作，你每次可以选择操作或者不操作，问所有情况下逆序对的总和。（$n, q \le 3000$） ## 分析 很容易想到 $dp$，但是发现不好直 ......