AutumnKite's Blog

太久没更新博客，开一篇多项式相关的博客记一下多项式的一些基础操作吧。

题目传送门

题意

给定一个长度为 \(n\) 的序列 \(a\)，一次操作可以将序列中的某个数 \(+1\) 或 \(-1\)。

定义一个序列的差值为序列的最大值减去最小值得到的数。

求进行至多 \(k\) 次操作后序列差值的最小值。

\(n\le 10^5,a_i\le 10^9,k\le 10^{14}\)

题目传送门

题意

有一个大小为 \(n\) 的环，环上每个点有一个颜色（黑/白）。定义一次操作是，对于每个点 \(i\)，若他和他相邻的两个点中，白点多于黑点，则在新的环中， \(i\) 变成白色，否则变为黑色。

求进行 \(k\) 次操作后每个点的颜色。

\(n\le 2\times 10^5,k\le 10^9\)

题目传送门

题意

给定一棵 \(n\) 个点的树，你需要给每个点染一个 \(1\sim k\) 的颜色，使得树上所有长度为 \(k\) 的路径都恰好包含 \(k\) 种颜色。

\(n\le 2\times 10^5\)

题目传送门

题意

有一个 \(n\times m\) 的黑白矩阵，初始时是全白的。有 \(q\) 次操作，每次操作形如 \(a_i,l_i,r_i\)，表示把 \(a_i\) 行的 \(l_i\) 列到 \(r_i\) 列的格子反转颜色。

每次操作后，你要找出 \(x_1,y_1,x_2,y_2\)，满足 \(x_1 < x_2,y_1 < y_2, col(x_1,y_1)=col(x_2,y_2),col(x_1,y_2)=col(x_2,y_1),col(x_1,y_1)\ne col(x_1,y_2)\)。若不存在则输出 \(-1\)。

\(n,m\le 2000,q\le 5\times 10^5\)

题目传送门

题意

有一个大小为 \(m\) 的环，还上有 \(n\) 个点有工作单位，并且有 \(n\) 个点上住着一个人。你需要为每个人分配一个工作单位，使得所有人到工作单位的距离之和最短。输出一个方案。

\(m\le 10^9,n\le 2\times 10^5\)

题目传送门

题意

构造一个 \(2n-1\) 个节点的树，满足 \(\forall i\in [1,n] : dis(2i-1,2i)=d_i\)，\(dis(x,y)\) 表示树上 \(x\) 到 \(y\) 的距离，\(d_i\) 是给定的。

\(n\le 10^5\)

题目传送门

题意

给定一个 \(n\times m\) 的地图，每个格子要么是障碍，要么是空格。你可以把除 \((1,1)\) 和 \((n,m)\) 外的若干个格子变成障碍，求使得 \((1,1)\) 到 \((n,m)\) 没有路径最少需要把几个格子变成障碍。

\(3\le n\cdot m\le 10^6\)

题目传送门

题意

求满足以下条件的长度为 \(n\) 的非负整数序列 \(a_1,a_2,a_3,\cdots,a_n\) 的方案数 \(\bmod 10^9+7\) 的值：

1. \(l\le \sum_{i=1}^n a_i\le r\)；
2. 将序列从大到小排序后，记为 \(a_1',a_2',a_3',\cdots,a_n'\)，满足 \(a_m'=a_{m+1}'\)。

\(1\le m < n\le 3\times 10^5,1\le l,r\le 3\times 10^5\)

题目传送门

题意

一个 \(H\times W\) 的矩阵，有 \(n\) 个位置有卡片，每张卡片上有个数字 \(a_i\)。你可以在每行拿走一张卡片，然后在每列拿走一张卡片，求拿走的卡片的 \(a_i\) 之和的最大值。

\(1\le H,W,n,a_i\le 10^5\)