本次报告撰写人：WilliamZH
题目：202203，第25次CCFCSP
使用语言：C++
题目 1：未初始化警告
题目描述：
$k$ 条赋值语句，$n$个变量：$a_1,a_2,…, a_n$ ，常量$a_0$ 。
第 $i$ 条赋值语句为 $a_{x_i}=a_{y_i}$
输出多少条赋值语句右值未被初始化。
$0<n,k≤10^5$
题解：
解法一：
用一个数组标记常量和变量。将已初始化的变量标记为1，未初始化标记为0。常量初始化为1.
注意：需要先判断右值是否初始化，再初始化左值。
时间复杂度$O(n)$，空间复杂度$O(n)$, 期望得分100.
1 |
|
题目 2：出行计划
题目描述：
$t$ 时刻做核酸，$t+k$ 时刻得到结果。
若要求持 $c$ 个单位时间结果，则 $t+k$ 到 $t+k+c-1$ 时刻得到的结果可用。
$n$ 项出行计划，第 $i$ 项为：$t_i$ 时刻进入场所，该场所要求 $c_i$ 个单位时间内的核酸结果。
$m$ 个查询：在 $q_m$ 时刻做了核酸，可满足多少项出行计划。
$0<n,m,k≤10^5$，$0<t_i,c_i,q_m\leq2\times 10^5$
题解：
解法一：
用一长度为$2N$的数组存储每个出行计划可进入的核酸时间，每个查询依次与每个计划的最早时间和最晚时间对比。
时间复杂度$O(mn)$，空间复杂度$O(n)$，期望得分70.
1 |
|
解法二：
用一个 $vector$ 记录每个计划可以进入的时刻，对于每个计划：数组$[t-c+1,t]$的位置$+1$。
直接查询数组$[q+k]$位置的值即为所求。
注意：$vector$ 需要开到$3N$ 大小，$q+k$可到$3\times10^5$
时间复杂度$O((n+m)logn)$，空间复杂度$O(n)$，期望得分100
1 |
|
1 |
|
题目 3：计算资源调度器
题目描述：
三种标准需求，每次三选若干。
- 计算节点亲和性
计算任务必须在指定可用区上运行。 - 计算任务亲和性
计算任务必须和指定应用的计算任务在同一可用区上运行。 - 计算任务反亲和性（必须满足/尽量满足）
计算任务不能和指定应用的计算任务在同一个计算节点上运行。
一旦选择了一个计算节点，就固定下来不再变动，并且在此后的选择中，不再考虑这个计算任务的要求。
对每个计算任务，选择计算节点的方法是：1. 过滤阶段 2. 排序阶段 - $f_i$ : 表示要接连启动 $f_i$ 个所属应用和要求相同的计算任务，其中 $f_i$>0；
- $a_i$ ：表示这 $a_i$ 个计算任务所属应用的编号；
- $na_i$ ：表示计算节点亲和性要求。当 $na_i=0$ 时，表示没有计算节点亲和性要求；否则表示要运行在编号为 $na_i$ 的可用区内的计算节点上；
- $pa_i$ ：表示计算任务亲和性要求。当 $pa_i=0$ 时，表示没有计算任务亲和性要求；否则表示必须和编号为 $pa_i$ 的应用的计算任务在同一个可用区运行；
- $paa_i$：表示计算任务反亲和性要求。当 $paa_i$=0 时，表示没有计算任务反亲和性要求；否则表示不能和编号为 $paa_i$ 的应用的计算任务在同一个计算节点上运行；
- $paar_i$ ：表示计算任务亲和性要求是必须满足还是尽量满足，当 $paa_i=0$ 时，$paar_i$ 也一定为 $0$；否则 $paar_i$=1 表示“必须满足”，$paar_i$=0 表示“尽量满足”。
$0<m\leq n\leq 1000, 0<g\leq \sum_{i=1}^gf_i\leq 2000, 0<A_{max}\leq 10^9$
题解：
解法一：
构造结构$node$ :
- $id$表示节点编号，$zone$表示节点所在可用区，$num$表示节点运行任务数量。
- 用$bool$数组$app$表示每个节点运行的应用，$app[i]=1$表示应用 $i$ 运行。
用二维$bool$数组 $apply[a][b]$ 表示可用区$a$运行应用$b$。
数组$C1[i]$ 记录是否满足节点亲和性和任务亲和性，数组$C2[i]$ 记录是否满足反亲和性。
每个$func$ 函数调用前，将数组$C1$ 和$C2$ 初始化为$0$。
时间复杂度$O(n^2)$, 空间复杂度$O(A^2)$, 期望得分$50$。
（对于一半的数据，$A_{max}$可达$10^9$, 数组下标越界，导致运行错误）
1 |
|
解法二：
对解法一进行空间优化：
使用$set$ 容器替换一维$bool$ ，若运行应用$a$ ，则$set.count(a)>0$
使用$map$ 容器替换二维数组，则无需开辟$A*A$的数组; $map[a][b]$ 表示可用区$a$ 运行应用$b$, 运行则值为$1$
时间复杂度$O(n^2log\ n)$, 空间复杂度$O(n)$, 期望得分$100$.
1 |
|
题目 4：通信系统管理
题目描述：
$n$ 台计算机，$u,v,x,y$ 表示机器$u$ 和$v$ 的每日可用额度增大$x\ MB/day$，持续$y$ 天.
定义每台机器的“通信主要对象”：
当前时刻与该机器的每日可用额度最大的机器（如果有并列，则取其中编号最小的机器）；
如果一台机器与任何机器的每日可用额度均为 $0$ ，则称其为“通信孤岛”，并认为其没有“通信主要对象”；如果两台机器 $x$ 和 $y$ 互为“通信主要对象”，则称它们是一个“通信对”。
- 每天开始时，先接受若干个额度申请，你需要依次处理这些申请；
- 接收若干个查询某台机器的“通信主要对象”的请求；求出此时的“通信孤岛”和“通信对”各有多少。
$1\leq n,m\leq 10^5, 1\leq A,B\leq 2\times 10^5, 1\leq u,v\leq n, 1\leq x\leq 10^9, 1\leq y\leq m$
题解:
解法一：
每日额度有效期可以看成一个激活与反激活的过程，反激活即在该天将额度减去。
维护额度最大值，用$set$ 以额度为关键字作降序排列，把$x$ 和$v$ 变成一个 （node） 压入到$set$ 里，再开一个数据结构记录$pair<u，v>$ 时$x$ 的值；保证可以通过$v$ 访问，也能通过$v$ 求最大值。
注：无论给谁加额度，都是给$u，v$ 两个同时加。
在每次新增每日额度时，维护通信孤岛和通信对的数量。
时间复杂度$O(nlog\ n)$, 期望得分$100$
1 |
|
题目 5：博弈论与石子合并
题目描述：
$n$ 堆石子，第$i$ 堆有$a_i$ 个石子
三种操作：
- 合并两堆相邻的石子
- 扔掉目前最靠左的一堆石子
- 扔掉目前最靠右的一堆石子
小 c 希望这堆石子尽量少，小 z 则希望这堆石子尽量多。
$k=0$ 表示小 c 先操作，$k=1$ 表示小 z 先操作。
问最后这堆石子的大小是多少。
$1\leq n\leq 10^5, 0\leq k\leq 1, a_i>0, \sum^n_{i=1}a_n\leq 10^9$
题解：
解法一：
- 小 c 先手（0）+奇数堆和小 z 先手（1）+偶数堆等价，即最后一次都是合并剩余两堆；
$n=2k+1, k=1,2…$ ，小 c 移去左右最大的一堆，小 z 合并$a_k, a_{k+1}$ 两堆。则最终都是$k+1$ 堆的和。 - 小 c 先手+偶数堆和小 z 先手+奇数堆等价，即最后一次都是移去最大堆；
- 我们本已处在最中间最安全的位置，由于我们的操作，会使合并的石子堆位于偏左或偏右的状态，这对于我们来说就是不安全、危险的位置，因为一旦小c发觉你合并的数量多的时候，他就想方设法把你合并的石子堆扔掉。因为你无论怎么合并，小c总有办法把你合并的给扔掉，这样就不能保证合并的石子堆最大并且保留到最后。
小 c 操作$\frac {n}{2}$ 次，若找到一个石子数$x$，存在大于$\frac {n}{2}$ 堆的$x$，则最后总能留下$x$。$x$ 即为所求。
用二分法求$x$。
时间复杂度$O(nlog\ n)$，期望得分$100$
1 |
|
