SCOI2024 题面
bunH2O
·
·
个人记录
造福后人。
D1T1：
给定 n 个 s_i 和 m 个 t_j，其中 s_i 和 t_j 是字符串。
构建一个新的字符串序列 p，其中 p_{(i-1)\times m+j}=s_i+t_j，'+' 表示拼接。
定义 f(i,j) 表示 p_i 在 p_j 中的出现次数，求 \sum\limits_{i=1}^{n\times m}\sum\limits_{j=1}^{n\times m}f(i,j) 。
---
D1T2：
平面上有 $n$ 个点。对于平面上任意一个实数点对 $(x,y)$，将这 $n$ 个点按照到 $(x,y)$ 的距离从小到大排序，若编号为 $i$ 的点排名为 $j$，则称 $(x,y)$ 是关于 $(i,j)$ 好的。
对于所有 $(i,j)$，求出所有关于 $(i,j)$ 好的点组成的图形与一个固定矩形的交的面积大小。
$1\leq n\leq 200$。
---
D1T3：
有 $n$ 个敌人，敌人有血条 $a_i$ 和爆炸伤害 $b_i$。你每次可以动用技能击杀一名敌人，随后该敌人会爆炸。当一个敌人爆炸时，会对所有活着的敌人造成 $b_i$ 的爆炸伤害，也即令 $a_j\leftarrow a_j-b_i$。若 $a_i$ 变为 $0$ 或负数，则该敌人死亡随后爆炸。问你至少要动用多少次技能。
然而你不知道 $b_i$ 具体是多少，只知道其在一个区间 $[l_i,r_i]$ 内。对于所有的 $\{b_i\}$，求出最少动用技能次数之和。
$1\leq n\leq 20,1\leq l_i\leq r_i\leq 15,1\leq a_i\leq 300$。
---
D2T1：
给定 $n$ 个字符集为 $0\sim9$ 的字符串，定义一次操作 $(a,x,b,y)$ 为交换第 $a$ 个字符串的第 $x$ 个字符和第 $b$ 个字符串的第 $y$ 个字符，需要保证 $(a,x)\neq (b,y)$。
一共将执行 $k$ 次操作，每次操作从所有的合法操作中随机等概率选取。进行完所有操作后，将所有字符串视为十进制数，随后将他们相乘，乘积即为最后的结果，求结果的期望对 $10^9+7$ 取模。
$1\leq n\leq 100,1\leq m\leq 10^7,0\leq k\leq 10^9$。其中 $m$ 表示所有字符串的长度之和。
---
D2T2：
给定一个大小为 $n\times m$ 的网格图 $G=(V,E)$，边有边权。
定义该图的一个生成子图 $G'=(V,E')$ 是合法的，当且仅当任意一条（不存在也合法）从 $(1,1)$ 到 $(n,m)$ 的路径上边权的 $\gcd$ 均为 $1$。
特别的，共有 $q$ 次修改操作，每次修改一条边的边权，保证修改前该条边的边权为 $1$。求每次操作后的合法生成子图的 $|E'|_{\max}$，**本题强制在线**。
读入格式如下：给定两个数 $x$ 和 $y$，表示将第 $x\oplus lstans$ 条边的边权改为 $y\oplus lstans$，$lstans$ 表示上次查询的结果，初始为 $0$。
$1\leq n\times m\leq 3\times 10^5,1\leq q\leq 10^5,1\leq V\leq 10^9$。其中 $V$ 表示边权的最大值。
---
D2T3：
你有一个 $n\times m$ 的网格图，其中共有 $(n-1)\times m+(m-1)\times n$ 条边。你需要用以下三种图形覆盖所有的边。
图形 1：选择一个 $1\times 1$ 的方格，将该方格的一组邻边覆盖，不难发现共有 $2$ 条边被覆盖。
图形 2：选择一个 $1\times 2$ 的矩形，将该矩形的一组邻边覆盖，不难发现共有 $3$ 条边被覆盖。
图形 3：选择一个 $2\times 1$ 的矩形，将该矩形的一组邻边覆盖，不难发现共有 $3$ 条边被覆盖。
求最少的覆盖次数，使每条边恰好被覆盖一次。
本题有多测。
$1\leq \sum{(n\times m)}\leq 5\times10^5$。