2021暑假训练dp优化题解 AC Codes A - GTY's birthday gift 矩阵优化dp 给出序列 $a$ ，每次从序列选两个数相加后，将新数加入序列 $a$ 问操作 $k$ 次后序列的和最大为多少 序列和最大，每次选当前最大和次大相加， $dp[i]=d[i-1]+dp[i-2]$ ，由于 $k$ 范围大，无法直接模拟。考虑到…

题目来源：ACL Beginner Contest F - Heights and Pairs。 给定一个大小为 $2N$ 的数组 $H$ ，要求将 $H$ 中的元素两两匹配，使得恰好构成 $N$ 个数对 $(H_i,H_j)$ 满足 $H_i\neq H_j$ 。 $N\leq 50000, H_i\leq 100000$ 。 首先容易想到通过容…

多项式基本操作 多项式加法、减法 有手就行。 多项式乘法 一句话概括，就是FFT。 这是整个多项式章节中最基础的一部分：如何用FFT将两个 $n$ 度的多项式乘法优化到 $O(n\log n)$ 的时间复杂度。 洛谷模板题：P3803 【模板】多项式乘法（FFT），P4245 【模板】任意模数多项式乘法 。 在多项式乘法中，有两个核心问题，加法卷积…

本文主要讨论形式幂级数在解决数学问题以及算法竞赛问题的思维，因此并不会涉及形式幂级数运算的编程实现。 例题引入 [admonition title="问题1" color="indigo"]有 $3$ 个集合 $A=\{2,3\}, B=\{2,4\},C=\{3,5,7\}$ ，现在要求从三个集合中各选择恰好一个元素 $a,b,c$ 使得 $a+…

压位BFS 一个 $n$ 个点，$m$ 条边的有向图，当所有边权均为 $1$ 时，求任意两点之间的最短路。 $n\leq 1000,m\leq \frac{n(n-1)}{2}$ 。 多源最短路是一个经典问题，显然可以通过floyd算法在 $O(n^3)$ 的复杂度下求解。同时，考虑到本题中一个特殊的条件：所有边权均为 $1$ ，本题也可以通过01…

小球盒子模型总结 题目链接：洛谷十二重计数法。 设有 $n$ 个球，$k$ 个盒子： 球之间互不相同，盒子之间互不相同，可以空盒 根据乘法原理，答案就是 $k^n$ 。 球之间互不相同，盒子之间互不相同，每个盒子至多装一个球 相当于每个球找一个没有被选过的盒子放进去，答案是 $k^{\underline{n}}$ ，即 $k(k-1)\cdots(…

2021暑假训练组合数学题解 十二重计数法 小球盒子模型大合集 小球盒子模型总结。 「SDOI2016」排列计数 错位排列签到题 求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$ 。 显然就是 $\binom{n}{m}D_{n-m}$ ，$D_i$ 表示 $i$ 的错位排列数量。 C…

2021“MINIEYE杯”中国大学生算法设计超级联赛（3） AC Codes 1003 Forgiving Matching FFT做带通配符的字符串匹配。看这里。 1004 Game on Plane 显然Alice应该尽量让选出的直线互不平行，而Bob要选出平行数量最多的直线。所以把直线变成最简化的向量排序就行了。 1007 Photosho…

2021牛客暑期多校训练营4 AC Codes B. Sample Game C. LCS 构造 $3$ 个长度为 $n$ 的字符串 $s_1,s_2,s_3$ ，使得 $LCS(s1,s2)=a,LCS(s2,s3)=b,LCS(s1,s3)=c$ ，$a,b,c$ 是给定的数字且 $a,b,c\leq n$ 。LCS是最长公共子序列。 先提取公…

2021牛客暑期多校训练营3 AC代码 B. Black and white 首先尽可能要减少我们选择的点的个数，然后思考本题的条件：如果一个矩形的三个角都有已被选择的点，那么剩下的那个点将被自动选择；这个条件实际上说明了一个事实，我们选择的点集不含有偶数环。同时注意到这个网格图可以建图为一个二分图，因此本题只需要在二分图上跑最小生成树。 C. M…