2024.9.7

本文主要是介绍2024.9.7，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写了一套质量真的真的很高的模拟赛题

T1 A. 数正方体

时间限制: 1 s   内存限制: 1024 MB   测评类型: 传统型

T1 数正方体

题目描述

众所周知，正方形有 4 个点,4 条边；正方体有 4 个点，12 条边，6 个面，定义点为零维基础图形，线段为一维基础图形，正方形为二维基础图形，正方体为三维基础图形…，那么请问，一个 n 维基础图形包含多少个 m 维基础图形呢 (m≤n)

多次询问，输出对 998244353 取模。

第一行输入一个正整数 T 表示数据组数。

下接 T 行，每行两个自然数 n,m，描述一组数据。

输出 T 行，每行一个数字表示答案。

对于全部数据，$T\le 105,0\le m\le n\le 10^5$

样例：

样例输入

7
3 0
3 1
3 2
3 3
48545 1
77625 77624
93574 83513

样例输出

8
12
6
1
223544257
155250
424453971

数据范围

对于全部数据，$T\le 10^5,0\le m\le n\le 10^5$。

• 存在 $10\%$ 的数据满足 $m=1$
• 存在 $10\%$ 的数据满足 $m=n-1$
• 存在 $10\%$ 的数据满足 $m=2$
• 存在 $10\%$ 的数据满足 $m=n-2$

数学结论题，结论很优美

m 维基础图形在 n 维基础图形上的表现为，某些维取值相同，剩下维取值唯一（是个 m 维基础图形）
答案就是 $\left(\begin{array}{c}n\\ n-m\end{array}\right)2^{n-m}$

有很多种推导方式，可以直接考虑组合方案，也可以大表找规律，甚至可以通过定义使用线性代数推导。。。

非常的开拓思路

---

T2 B. 数连通块

时间限制: 1 s   内存限制: 1024 MB   测评类型: 传统型

题目描述

给定一个森林，每个点都有一定概率会消失，一条 $(u,v)\in \mathbb{E}$ 的边存在的条件是，$u$ 存在且 $v$ 存在

有若干次询问，每次给定 $[l,r]$，然后把下标不在 $[l,r]$ 的点都删掉后，问剩余点和所有边构成的图的联通块个数的期望

输入

第一行三个整数 $n,m,q$，分别表示点的个数和边的个数和询问次数

之后 $n$ 行，第 $i$ 行有两个整数 $a_i,b_i$，表示第 $i$ 个点存在的概率是 $\frac{a_i}{b_i}$

之后 $m$ 行，每行有两个整数 $u,v$，表示存在一条连接 $u$ 和 $v$ 的边，保证无重边无自环

之后 $q$ 行，每行两个整数 $[l,r]$，表示一次询问

输出

对于每一次询问，输出一行一个整数表示答案，输出对 $10^9+7$ 取模

样例输入

2 1 1
1 1
1 1
1 2
1 2

样例输出

1

数据范围

对于 $10\%$ 的数据，保证 $n=10$

对于另外 $10\%$ 的数据，保证 $q=1$

对于所有数据，保证：$1\le n\le 10^5,0\le m<n,1\le q\le 10^5,1\le a_i\le b_i\le 10^5$

考虑到森林中连通块个数的 $T$ 满足：$T=n-m$

> 证明：每添加一条边，就会合并两个连通块，相应的，连通块的个数就会少一个 > 根据期望的线性性，可得：$E(T)=E(n)-E(m)$

于是问题就转化为了计算 $E(n)$ 和 $E(m)$

为了方便起见，设 $p_u$ 表示 $u$ 的存在的概率

于是对 $p_u$ 做前缀和数组 $S_p$ 后，可得 $E(n_{[l,r]})=S_{p_r}-S_{p_{l-1}}$

之后只需要考虑 $E(m)$ 如何计算，显然有：

$$E(m_{[l,r]})=\sum _{(u,v)\in \mathbb{E}\wedge u\in [l,r]\wedge v\in [l,r]}{p}_u\cdot p_v$$

于是可以把每一条$(u,v)\in \mathbb{E}$ 的边看成一个点$(u,v)$，它的权值是 $p_u\cdot p_v$

之后相当于询问一个矩形内的点的权值和，这显然就是一个二维数点问题，离线后树状数组统计即可。

重点是将问题转化成二维数点问题，转化的合理性与期望的线性性密切相关：线性性不一定一定要考虑加和，减肥同样适用

---

T3 C. 数大模拟

时间限制: 2 s   内存限制: 1024 MB   测评类型: 传统型

题目描述

有 $n$ 个连续的格子，一开始某些格子上有棋子，假设格子从 $1$ 到 $n$ 进行编号。

你需要进行 $k$ 轮操作，每一轮操作如下：

• 选中所有满足“其左侧相邻的是空格子”的棋子，
• 将这些棋子向左移动一格。

比如，对序列1001101进行一轮操作后，会变为1010110（其中 $1$ 表示这个格子上有一个棋子，$0$ 表示这是一个空格子）。

请输出操作 k$k$ 轮后，每个格子上是否有士兵（即输出一个长度为 $n$ 的序列，表示方式与上文相同）。

注：如果有两个相邻格子上都有棋子，那么靠右的棋子不会在这一轮操作中移动。

输入格式

第一行两个整数 $n,k$，分别表示格子总数与操作轮数。

第二行 $n$ 个整数 { a n } \{a_n\} {an​}，其中 $a_i$ 表示从左往右第 $i$ 个格子是否有棋子（表示方式与上文相同）。

输出格式

一行 $n$ 个整数 { b n } \{b_n\} {bn​}，其中 $b_i$ 表示操作 $k$ 轮后，从左往右第$i$ 个格子是否有棋子（表示方式与上文相同）。

测试样例

样例输入1

6 2
0 1 1 0 1 1

样例输出1

1 1 0 1 1 0 

样例输入2

4 4
0 1 0 1

样例输出2

1 1 0 0

数据范围

对于 $30\%$ 的数据，满足 $n,k\le 1000$

对于额外 $20\%$ 的数据，满足 $n\le 1000$

对于 $100\%$ 的数据，满足 $1\le n,k\le 10^6$

考虑到20分的暴力有特殊性质，当轮数大于长度时，所有棋子都可以到终点

下面考虑正解

有一个长度为 $n$ 的 $01$ 序列，假设它叫做 $a$，下标从 $1$ 开始 > > 一共要进行 $k$ 轮操作，在每一轮中，你需要求一个 $b$ 序列，满足： > > 若有 $a_i=0$ 且 $a_{i+1}=1$，则 $b_i=1$ 且 $b_{i+1}=0$，否则$b_i=a_i$ > > 之后用 $b$ 序列替换 $a$ 序列

举个例子：

0 1 1 0 1 1 （初始局面）
1 0 1 1 0 1 （第一轮）
1 1 0 1 1 0 （第二轮）
1 1 1 0 1 0 （第三轮）
1 1 1 1 0 0 （第四轮）

考虑先把已经归位的 $1$ 删除，也就是把序列一开始的前缀 $1$ 都删掉

那么对于每一个棋子，都有一个目标距离，即最终序列的位置

显然这个最早的归位时间是最后一个棋子的归位时间

对于一个棋子，它前面每有一个棋子，则会对它产生晚归位 $1$ 单位时间的影响

反之，它前面每有一个空格，则会对它产生早归位 $1$ 单位时间的影响

于是就有一个求得最晚归位时间的代码了，当然也同时可以得知每个棋子的归位时间

int getlen() {int res = 0;for(int i = 1 ; i <= n ; ++ i) {if(mp[i] == 0) {int tag = 0, tot = 0;for(int j = i ; j <= n ; ++ j) {if(mp[j] == 1) {++ tot;res = max(res, (j - i + 1) - tot + tag);}if(mp[j] == 0) {-- tag;} else {++ tag;}if(tag < 0) {tag = 0;}}break;}}return res;
}

那么可以发现一个性质：一个棋子的晚归位时间是 $O(n)$ 级别的

回到这个题，利用之前的打表程序再发掘一下性质

不妨让每个棋子互不相同，也就是标上标号：

0 1 2 0 3 4 （初始局面）
1 0 2 3 0 4 （第一轮）
1 2 0 3 4 0 （第二轮）
1 2 3 0 4 0 （第三轮）
1 2 3 4 0 0 （第四轮）

去掉 0$0$：

  1 2   3 4 （初始局面）
1   2 3   4 （第一轮）
1 2   3 4   （第二轮）
1 2 3   4   （第三轮）
1 2 3 4     （第四轮）

显然有一个规律，对于数字 i$i$ 的最后位置的这一竖条，考虑转移到 $j=i+1$，那么就相当于先从 $(1,j)$ 往左下角一直走，直到撞上 $i$，然后把 $i$ 剩余的一段往下平移一格，然后往右平移一格

显然这个是对的，因为最终的路线一定是先撞上上一个棋子，然后和它错开一个时间格后如此操作

那么也就可以解释一开始的打表的规律了：空格会代替你撞上一次，非空格就会让你撞上一次

虽然说是要平移，但考虑每次只平移一格，而且总的轮数不会超过$O(n)$，所以可以用一个线段树来维护这个东西，同时用一个 $offset$ 维护一下当前区间，于是只需要支持区间赋值上一个等差数列，区间加一，单点查询

对于查询第一次撞到哪，既可以在线段树上维护最大值，也可以二分后在线段树上跑（虽然是 $O({\log }^{2}n)$ 的，但也能通过）

附上算法：

1. 找到 1 <= j <= len，满足 i - j + 1 == a[offset + 1 + j] + 1
2. 把 a[offset + 1] ~ a[offset + j] 按照 i, i - 1, i - 2, ... 的值填充
3. 把 a[offset + j + 1] ~ a[offset + len] 都 +1
4. ans[a[offset + k + 1]] = 1

实际上是模拟双端队列，手写一个 $deque$ 就行了，时间复杂度 $O(n)$

---

T4 D. 数字符串

时间限制: 1 s   内存限制: 1024 MB   测评类型: 传统型

题目描述

有一个长度为 $n$ 的字符串 $S$，对于每一个整数 $i(1\le i\le n)$，求有多少个 $x$ 满足：

1. $1\le x\le i$
2. $S[1,x]=S[i-x+1,i]$
3. $x\ge i-x+1$
4. $x-(i-x+1)+1\equiv 0(\mathrm{mod}k)$

以上满足条件的 x$x$ 的数量记作 Fi$F_i$

输出 ${\prod }_{i=1}^n(F_i+1)\text{ mod }998244353$

输入格式

第一行一个由小写字母构成的字符串。

第二行一个整数 $k$，表示题目描述中的常数 $k$；

输出格式

一行一个整数表示答案。

样例输入

abababac
2

样例输出

24

样例解释

$F$ 依次为：0 1 0 1 0 2 0 1

数据范围

subtask测试

对于 $30$ 分的数据，满足 $|S|\le 1000$

对于额外 $20$ 分的数据，满足 $S$ 只由单一小写字母组成

对于所有数据，满足 $1\le k\le |S|\le 10^6$，并且 $S$ 仅由小写字母组成。

直接考虑求出next数组后暴力

因为数据范围的缘故，这样作时可以的

我们建立前缀树，然后在树上作差分即可

发现题目主要卡在了树上差分部分，因为对前缀树操作不熟悉，不知道怎么作差分

---

这套题质量真的很高，题目有不同解法，能开通不少思路

部分分的设计也很有思维含量

有没有见过的套路：期望线性性的反向应用，二维数点的转化，在前缀树上操作

这篇关于2024.9.7的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---