CF5E 题解

$\text{Description}$

环上有 $n$ 个点，每个点有高度，定义两个点能互相看到当且仅当存在一段端点为该两点的圆弧内任意点高度都不超过该两点。求能相互看见的点对数。

$1\le n\le 10^6$

POI2018 水箱 题解

$\text{Description}$

已知有一个 $n\times m\times H$ 的长方体，对于水平面上的相邻两格间，会有一堵厚度忽略不计的墙，从最低一层开始，到第 $h_{i,j}\ge 1$ 层。

定义一种装水方式是合法的，当且仅当：

1. 某一个格子装了水，则它是最低一层的格子或者其竖直向下的格子装了水。
2. 某一个格子装了水，则它在水平面上的相邻四个格子要么是水，要么中间有堵墙。

求有多少种合法的装水方式，对 $10^9+7$ 取模。

$n\times m\le 5\times 10^5,H\le 10^9$

$\text{Description}$

CF316D 题解

$\text{Description}$

给定一个序列 $\{t_n\},\forall i,t_i\in\{1,2\}$。问有多少个排列 $p$ 满足 $[1,2,\cdots,n]$ 可以通过有限制地交换任意两位置的数得到，其中第 $i$ 个位置至多只能被交换 $t_i$ 次。

$1\le n\le 10^6$

$\text{Description}$

有一片景区有 $n$ 个景点，景点间的道路组成一棵 $n$ 个点的树，相邻景点间道路长度相同。有 $m$ 条观光路线，分别位于树上的路径 $(u_1,v_1),(u_2,v_2),\cdots,(u_m,v_m)$，第 $i$ 条观光路线上有 $a_i$ 辆互不相同的车。张三要跟随旅行团来到景区，旅行团的集合区域也是一条路径 $(s,t)$。张三想要依次坐 $K$ 趟车，每次可以选择任意路线上的任意一辆车。我们称景点 $t$ 在路径 $s$ （无论 $s$ 是观光路线还是集合区域）的服务范围内，当且仅当 $t$ 到 $s$ 上任意一点的距离都不超过 $s$ 的长度。称所有在服务范围内的景点的集合为一条路径的服务范围。他希望坐车的方案满足以下要求：

1. 乘坐的每辆车所属观光路线的服务范围都包含集合区域的服务范围。
2. 任何一个不在集合区域的服务范围内的景点都不会同时在乘坐的每辆车所属观光路线的服务范围内。

张三得知旅行团有 $q$ 套可能的集合区域 $(s_i,t_i)$，他希望你帮他计算出对于每种集合区域的方案，他可能的乘车方案数分别有多少。方案数对 $1000003$ 取模。

CF1080E 题解

$\text{Description}$

给定一个由小写字母组成的矩形，我们称其的一个子矩形是美丽的，当且仅当其任意行任意排列字符后，任意行或任意列都为回文串。

求该矩形的子矩形中，有多少个是美丽的。

$1\le n,m\le 250,|\Sigma|=26$

CF1080F 题解

$\text{Description}$

给定 $n$ 个集合，每个集合里有若干条线段，共有 $k$ 条，$m$ 次询问，每次给定 $a,b,x,y$，询问编号在 $[a,b]$ 内的集合是否都有一条线段在 $[x,y]$ 内。

$1\le n,m\le 10^5,1\le k\le 3\times 10^5$

CF1082G 题解

$\text{Description}$

给定一个 $n$ 点 $m$ 边无向图，边有边权 $b_i$，点有点权 $a_i$，要求选出一个点集，使得其导出子图的边权和减其点权和最大。

$1\le n,m\le 10^3$

CF990G 题解

$\text{Description}$

给定一棵点带权无根树，对于每个 $k\in[1,2\cdot 10^5]$，求出有多少个无序点对 $(x,y)$ 满足 $x$ 到 $y$ 的简单路径上的所有节点的点权的 $\gcd$ 为 $k$。

$1\le n,a_i\le 2\cdot 10^5$

CF1083E 题解

$\text{Description}$

给定 $n$ 个左下角在 $(0,0)$，四边与 $x,y$ 轴平行的矩形（以右上角顶点的形式给出），保证两两不包含，每个矩形有一个权值 $a_i$，试选出若干个矩形，使得其面积并减去权值和最大。

$1\le n\le 10^6,1\le x_i,y_i\le 10^9,0\le a_i\le x_iy_i$