试题内容请前往CCF官网查看：
CCF-CSP计算机软件能力认证考试
http://118.190.20.162/home.page
阅读本题解前，您应当了解下列知识：
- 线段树 教程
- 差分 教程
- C++ STL容器 教程
- 二叉堆 教程
这是一份以C++代码编写的CSP 专业组 202203题解。
请注意这不是CSP-S/J的中学生竞赛的题解。
由于作者并非计算机专业科班出身，水平有限，并非每一题都能完整的解答，能够提供完整解答的也不一定是最优方案，望周知。
现将模拟测试系统中的得分列举如下：
| 题目 | 得分 | 时间 | 内存 |
|---|---|---|---|
| 未初始化警告 | 100 | 140ms | 2.875MB |
| 出行计划 | 100 | 109ms | 5.933MB |
| 计算资源调度器 | 100 | 31ms | 3.105MB |
| 通信系统管理 | 100 | 1.734s | 57.13MB |
| 博弈论与石子合并 | 100 | 31ms | 3.101MB |
基础题。
遵循题面上给出的提示即可。注意“无需考虑第 j j j条赋值语句本身是否也有右值未初始化的问题”。（尽管我不太理解这一点）
时间复杂度 O ( k ) O(k) O(k)。
#include基础题。这里提供两种方法。
对于每一个场所，其预计进入时间为 x x x，核酸有效期是 y y y，则持有报告时间 t ∈ [ x − y + 1 , y ] t\in[x-y+1,y] t∈[x−y+1,y]的核酸证明可以进入该场所。则对于每个场所，我们对区间 [ x − y + 1 , y ] [x-y+1,y] [x−y+1,y]加 1 1 1，表示对于该区间的所有时间点，持有该时间点的核酸报告可以进入的场所数量都加1。对于每个询问 x x x，直接查询时间 x + k x+k x+k的场所数量即可。
此即区间修改，单点查询，可以考虑使用线段树。
时间复杂度大约是 O ( m l o g N ) , N = t + k ≤ 4 × 1 0 5 O(mlogN),N=t+k \le 4\times 10^5 O(mlogN),N=t+k≤4×105。
#include但是，仔细观察题意，容易发现所有的修改都在查询之前，这时候用差分时空复杂度更低，代码量也更小。
时间复杂度大约是 O ( n + N + m ) , N = t + k ≤ 4 × 1 0 5 O(n+N+m),N=t+k \le 4\times 10^5 O(n+N+m),N=t+k≤4×105。
#include中等题。
众所周知，CSP的第3题不算很难，但总是很麻烦，细节很多，调试时间会比较长。
类图 各类成员与方法简述node 计算节点{
int load : 该节点已有的计算任务数量
int inArea : 该节点所在可用区
int id : 该节点编号
set apps : 该节点上计算任务所属应用
operator< : 为stl-set设计的运算符重载 (const node &x)
}
area 可用区{
set nodes : 该可用区上的计算节点
set apps : 该可用区上计算任务所属应用
addLoad : 对iterator指向的节点添加appID应用的计算任务 (iterator, appID)
}
MyCloud {
int n : 计算节点数量
int m : 可用区数量
vector areas : 所有可用区
不考虑计算任务反亲和性时向atArea可用区添加appID应用的计算任务：
allocAnyNodeInCertainArea(int appID,int atArea)
强制考虑计算任务反亲和性时向atArea可用区添加appID应用的计算任务：
allocConditonalNodeInCertainArea(int appID,int atArea,int notWithApp)
向atArea可用区添加appID应用的计算任务：
allocNodeInCertainArea(int appID,int atArea,int notWithApp)
不考虑计算任务反亲和性时向validAreasID可用区范围添加appID应用的计算任务：
allocAnyNodeInRandomArea(int appID,vector &validAreasID)
强制考虑计算任务反亲和性时向validAreasID可用区范围添加appID应用的计算任务：
allocConditonalNodeInRandomArea(int appID,vector &validAreasID,int notWithApp)
向validAreasID可用区范围添加appID应用的计算任务：
allocNodeInRandomArea(int appID,vector &validAreasID,int notWithApp,bool mustNotWithApp)：
处理一条输入的计算任务组：
allocResOnce(int appID,int atArea,int withApp,int notWithApp,bool mustNotWithApp)
}
每次添加计算任务时，调用allocResOnce，检查是否指定了“计算节点亲和性”。如果指定了，则检查该可用区是否有计算节点和“计算任务亲和性”，并调用allocNodeInCertainArea；反之，通过“计算任务亲和性”找出所有可用区，并调用allocNodeInRandomArea。
在方法allocNodeInCertainArea中，检查是否指定了“计算任务反亲和性”，并据此调用不考虑反亲和性的allocAnyNodeInCertainArea或强制考虑反亲和性的allocConditionalNodeInCertianArea。
在方法allocAnyNodeInCertainArea中，由于我们使用set存储节点信息并且重载了<运算符以指定其排序规则，因此其first元素即为计算任务最少且编号最小的计算节点，修改即可。需要注意，不能直接通过first()指针修改，而应该裁剪出该元素，修改之再重新插入。具体代码见area::addLoad()方法。
在方法allocConditionalNodeInCertainArea中，由于需要考虑反亲和性，不能直接取用first元素，需要从头遍历找到第一个满足反亲和性的计算节点，再进行修改。
allocNodeInRandomArea，allocAnyNodeInRandomArea和allocConditionalNodeInRandomArea方法的思想与alloc***NodeInCertainArea系列方法相似，只是要多一个在所有可能的可用区中再取最小节点的步骤，此处从略。
读入时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，单次查询时间复杂度不超过 O ( n l o g n ) O(nlogn) O(nlogn)，总查询次数 Σ f i ≤ 2000 \Sigma f_i \le 2000 Σfi≤2000，时间复杂度 O ( n Σ f i l o g n ) O(n\Sigma f_i logn) O(nΣfilogn)。
代码#include中等题。
“有效期”的处理注意到每条申请存在“有效期”，我们可以把一条申请分为“额度增加”和“额度减少”两个 *** 作。“额度增加”立即生效，“额度减少”到指定日期才生效。这里存在一个问题：如何知道当天会发生哪些额度减少的 *** 作？
法一（代码中采用的方法）：采用优先队列（priority_queue，也就是堆）来解决这个问题。利用优先队列维护一个以“额度减少” *** 作日期为关键字的小根堆，每天开始时，比较当天日期与堆顶“额度减少” *** 作的日期，如果日期一致，我们使堆顶出堆并执行“额度减少” *** 作，直至堆顶日期大于当前日期。
法二（更好的方法）：开一个长度
1
0
5
10^5
105的数组，数组元素为vector，用于存放每天发生的“额度减少” *** 作。每天访问对应下标的vector并逐一执行“额度减少” *** 作即可。
法一占用空间不超过
O
(
A
)
O(A)
O(A)，时间复杂度带一个log，法二占用空间不超过
O
(
m
+
A
)
O(m+A)
O(m+A)，时间复杂度则没有log。
显然， 1 ≤ n , m ≤ 1 0 5 , 1 ≤ A , B ≤ 2 × 1 0 5 1\le n,m \le 10^5, 1\le A,B \le 2\times 10^5 1≤n,m≤105,1≤A,B≤2×105的范围意味着我们不能用一个 1 0 5 × 1 0 5 10^5\times 10^5 105×105二维数组来维护各机器之间的通信额度，时空复杂度均不能满足要求。
因此我们需要设计一个数据结构，满足：1. 能快速查找该机器最大额度（用于查询主要通信对象） 2. 能快速查找与特定机器的通信额度（用于实现“额度增加”与“额度减少” *** 作）。
对于某台机器，我们可以用map离散化存储每台机器的通信额度。但仅用一个map则在查询“通信主要对象”时需要遍历整个map，速度较慢。或者我们用set维护通信额度，其中set的每个元素表示该机器的一个通信对象及对应额度（写一个struct并重载运算符来实现按照额度降序排序），则我们可以
O
(
1
)
O(1)
O(1)查询该机器的“通信主要对象”，但在增加和减少额度时必须遍历set才能确定某个通信对象的既有额度。笔者出于偷懒考虑，同时维护了上述map和set，以达到“博采众长”的目的。具体实现请见代码。
关于通信孤岛，我们容易知道：
- 一台机器额度增加时，它一定不再是通信孤岛；
- 一台机器只有在额度减少时，才有可能变成通信孤岛；
因此，我们在执行“额度增加”与“额度减少” *** 作时，顺便检查该机器是否时“通信孤岛”即可。具体而言，维护一个通信孤岛集合set，初始时集合中包括所有机器，“额度增加”时erase对应机器，“额度减少”时检查额度是否下降至
0
0
0，并insert到该集合中，查询通信孤岛数量时，调用size()方法即可。
我们记 p a i r ( x ) pair(x) pair(x)为 x x x的所在“通信对”的另一台机器。每次额度增减 *** 作涉及 u , v u,v u,v两台机器，考虑通信对，则至多涉及 { u , v , p a i r ( u ) , p a i r ( v ) } \{u,v,pair(u),pair(v)\} {u,v,pair(u),pair(v)}这些机器。
维护一个通信对集合set，保证pair.first小于pair.second，防止重复。每次额度增减 *** 作前，先删除
u
,
v
u,v
u,v机器对应的通信对（如果有）， *** 作后再计算新的通信对，如果有则加入即可。查询通信对数量时，调用size()方法即可。
- 定义每台机器的“通信主要对象”为当前时刻与该机器的每日可用额度最大的机器（如果有并列，则取其中编号最小的机器）；
- 由于不同申请的效果是可以叠加的，且单次申请额度
1
≤
x
≤
1
0
9
1\le x \le 10^9
1≤x≤109，总共申请次数
A
≤
2
×
1
0
5
A\le 2 \times 10^5
A≤2×105，因此额度最大可能到
2
×
1
0
14
2\times 10^{14}
2×1014，请务必开
long long；
笔者由于不注意审题，上述问题各错一次。交了3次才成功。
代码#include中等题。参考了这篇题解，在此表示感谢。
我们从直觉上可以体会到：小Z只需合并石子而无需丢弃石子，小C只需丢弃石子而无需合并石子。
小Z想让石子最多，那么他肯定不会丢石子。你可能会想，如果小C先把边上的石子合并起来，再一次性丢掉，会不会是更优解呢？实际上效果是一样的，譬如我们先合并最左边的两堆石子，再丢掉（2次 *** 作）和连续2次丢掉最左边的石子（也是2次 *** 作）基本是等价的，因此只要丢石子就可以了。
（实际上这里应该提供严谨的证明，但是由于笔者数学水平有限，不会证，只能提供一些直观的解释。总之，上述粗体字是正确合理的结论。）
我们采用数学归纳法，并以小Z先手为例来讨论问题。
- 设当前有2堆石子，小Z直接合并即可；
- 设当前有4堆石子， a 1 , a 2 , a 3 , a 4 a_1,a_2,a_3,a_4 a1,a2,a3,a4，小Z合并两堆石子后还剩3堆，小C一定扔不掉中间那一堆，因此小Z合并 a 2 a_2 a2和 a 3 a_3 a3一定不会被扔掉，最后小Z可以得到 a 2 + a 3 + m i n { a 1 , a 4 } a_2+a_3+min\{a_1,a_4\} a2+a3+min{a1,a4}，另外两种可能分别是 a 2 + m i n { a 1 , a 3 + a 4 } a_2+min\{a_1,a_3+a_4\} a2+min{a1,a3+a4}以及 a 3 + m i n { a 1 + a 2 , a 4 } a_3+min\{a_1+a_2,a_4\} a3+min{a1+a2,a4}，显然 a 2 + a 3 + m i n { a 1 , a 4 } a_2+a_3+min\{a_1,a_4\} a2+a3+min{a1,a4}是最大的。因此小Z一定会从中间合并。
- 设当前有3堆石子，
a
1
,
a
2
,
a
3
a_1,a_2,a_3
a1,a2,a3。如果
a
1
>
a
3
a_1>a_3
a1>a3，
a) 小Z合并后得到 a 1 + a 2 , a 3 a_1+a_2,a_3 a1+a2,a3，显然 a 1 + a 2 > a 3 a_1+a_2>a_3 a1+a2>a3，小C扔掉前一堆，剩 a 3 a_3 a3；
b) 小Z合并后得到 a 1 , a 2 + a 3 a_1,a_2+a_3 a1,a2+a3，然后小C扔掉其中大的那一堆，剩 m i n { a 1 , a 2 + a 3 } min\{a_1,a_2+a_3\} min{a1,a2+a3}。但由于 a 1 > a 3 , a 2 + a 3 > a 3 a_1>a_3,a_2+a_3>a_3 a1>a3,a2+a3>a3，剩下的石子一定比a)情况多；
因此应该合并 a 2 , a 3 a_2,a_3 a2,a3；同理不难发现， a 1 < a 3 a_1a1<a3时，应该合并 a 1 , a 2 a_1,a_2 a1,a2； a 1 = a 3 a_1=a_3 a1=a3时，两种合并方式没有差异。 - 设当前有
2
k
(
k
>
2
)
2k (k>2)
2k(k>2)堆石子，每堆数量依次记作
a
1
,
a
2
,
.
.
.
,
a
k
,
a
k
+
1
,
.
.
.
,
a
2
k
a_1,a_2,...,a_k,a_{k+1},...,a_{2k}
a1,a2,...,ak,ak+1,...,a2k，小Z合并中间的石子意味着合并了
a
k
a_k
ak与
a
k
+
1
a_{k+1}
ak+1，此时还剩
a
1
,
a
2
,
.
.
.
,
a
k
+
a
k
+
1
,
.
.
.
,
a
2
k
a_1,a_2,...,a_k+a_{k+1},...,a_{2k}
a1,a2,...,ak+ak+1,...,a2k这
(
2
k
−
1
)
(2k-1)
(2k−1)堆石子，显然小C会扔掉
a
1
a_1
a1和
a
2
k
a_{2k}
a2k中更多的那堆石子。此时剩下
(
2
k
−
2
)
(2k-2)
(2k−2)堆石子。这种情况最终会归纳到情况1。
实际上，在这种情况下，最后留下的那堆石子一定是长度为 ( k + 1 ) (k+1) (k+1)的一段石子数量之和，我们只要求
m i n i = 1 , 2 , . . . , k { ∑ j = i i + k a j } \underset{i=1,2,...,k}{min}\left\{\ \sum_{j=i}^{i+k} a_j\right\} i=1,2,...,kmin{ j=i∑i+kaj}
时间复杂度 O ( n ) O(n) O(n)。 - 设当前有 ( 2 k + 1 ) ( k > 1 ) (2k+1) (k>1) (2k+1)(k>1)堆石子，每堆数量依次记作 a 1 , a 2 , . . . , a k , a k + 1 , a k + 2 , . . . , a 2 k , a 2 k + 1 a_1,a_2,...,a_k,a_{k+1},a_{k+2},...,a_{2k},a_{2k+1} a1,a2,...,ak,ak+1,ak+2,...,a2k,a2k+1，由于该情况最终归纳于情况2，因此小Z无论合并哪一堆石子，总是有可能被小C扔掉。我们调整一下 *** 作顺序，令小Z先连续合并 k k k次石子，再让小C连续扔掉 k k k次石子，最后剩下1堆石子。小Z连续 k k k次合并相当于把数列切成 ( k + 1 ) (k+1) (k+1)段，分段求和，小C会连续扔掉 k k k次石子即求这 ( k + 1 ) (k+1) (k+1)个和中的最小值，而小Z希望这个最小值最大。
最小值最大和最大值最小问题通常使用二分答案的方法来解决。应用“二分答案”的充分条件是：
(1) 所求答案
A
∈
[
L
,
R
]
A\in[L,R]
A∈[L,R]；
(2) 任意
x
∈
[
L
,
A
]
x\in[L,A]
x∈[L,A]均为合法值而任意
x
∈
(
A
,
R
]
x\in(A,R]
x∈(A,R]均为非法值，或任意
x
∈
[
L
,
A
)
x\in[L,A)
x∈[L,A)均为非法值而任意
x
∈
[
A
,
R
]
x\in[A,R]
x∈[A,R]均为合法值;
(3) 存在某种算法判断任意
x
∈
[
L
,
R
]
x\in[L,R]
x∈[L,R]是否为合法值；
在这个问题中，我们记所求答案——即最后剩下的石子数——为 A A A，显然 A ∈ [ m i n { a 1 , a 2 , . . . , a n } , a 1 + a 2 + . . . + a n ] A\in[min\{a_1,a_2,...,a_n\},a_1+a_2+...+a_n] A∈[min{a1,a2,...,an},a1+a2+...+an]，简便起见也可以认为答案范围是 [ 1 , 1 0 9 ] [1,10^9] [1,109]。
我们称一个值 x x x是“合法”的，当且仅当答案为 x x x时，这 ( 2 k + 1 ) (2k+1) (2k+1)段石子一定可以被分割为连续的 d d d段，满足 d > k d>k d>k且每一段的和都大于等于 x x x；
通过上述范围和合法性判断算法，我们可以很容易的设计出情形4的解答，详见代码。
总的时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。
细心的读者可能会想到：“合法”的值，就一定可以通过小C和小Z的游戏得到吗？（假设两人未必是绝顶聪明的）不一定。显然，一个“合法”的 x x x，只有在满足**至少有一段的和为 x x x**的情况下，才是可能通过游戏得到的。我们称满足上述条件的 x x x为潜在答案。
假设我们找到了一个合法值 x x x，但是它不是潜在答案（取不到等号），那么我们记每一段和的最小值为 x ′ x' x′，显然有 x ′ > x x'>x x′>x，而且我们容易发现 x ′ x' x′也必然是合法值。因此，最大的“合法”值一定是一个“潜在答案”。
小C先手时，必定会扔掉左右两堆中更大的那一堆，然后转化到小Z先手的情况。
#include欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）