内含以下题目的实验报告:

  • CST2021F 1-1 A+B Problem
  • CST2021F 1-2 Graphics
  • CST2021F 1-3 Filename
  • CST2021F 1-4 Risk

这里不提供任何解题代码,仅将解题的白盒报告归档处理。

本博文仅做参考使用,任何可能影响您查重结果的行为请您后果自负!

Problem White Box (20%) Black Box (80%)
CST2021F 1-1 A+B problem (25%) 100 [100] -1
CST2021F 1-2 Graphics (25%) 100 [100] -1
CST2021F 1-3 filename (25%) 100 [100] -2
CST2021F 1-4 Risk (25%) 100 [100] -1

CST2021F 1-1 A+B Problem

[关键词] 模拟,压位

方案设计

思路来源

​ 先来考虑小学二年级学过的十进制乘法。

​ 如 $73 * 27$,我们的运算实际上是进行了…

​ 而我们再考虑导致现有的高精度加法模板 TLE 的原因,$O(n|a||b|)$ 的算法对于 $n=500, |a|=|b|=5000$ 的最坏情况,与 $1s$ 内允许进行的运算次数,只差了一个常数级别.

​ 因此我们的优化可以有两个思考方向,其一是进行常数级别的复杂度优化,另一是寻找更为高效的算法。这里斟酌考虑后选择了前者,而关于后者的相关实现留作报告中的【后续的优化方向】部分呈现。

​ 而怎么去优化这个常数呢?我们可以考虑通过增加数据的存储与运算进制,来减少 $O(n|a||b|)$ 中 $|a|, |b|$ 的值,最终达到时间上的优化效果。举个例子,如果我们以 $10^4$ 为进制,那么复杂度在某种程度上就变成了 $O(n\frac{|a|}{4} \frac{|b|}{4})$。(虽然常系数可能有所增长)

​ 同时还注意到,类似于位运算,加法,乘法等这种操作是较为节省时间的,而进行除法,取模的操作较为费时。因此我们尽可能避免每进行一次循环就进行进位处理的实现方式,因为处理进位可能需要大量的求余和求商运算。

具体实现

​ 使用 BigInteger 类对大整数进行封装。其中的数据采用 __uint128_t 类型来进行存储,单个 data 可以储存上限为 $2^{128}-1$ 大小的值. 而最终数据存储和乘法运算采用的进制为 $10^{16}$.

读取数据

​ 大整数的读取按照以下方式进行。

  1. 预读取阶段:将一个大整数的所有位读到一个栈结构中.

  2. 处理阶段

    每次出栈最多 $16$ 位大整数,并从整数的逻辑最左端到逻辑最右端不断进行 $s_i \leftarrow (s_i<<3)+(s_i<<1); s_i \leftarrow s_i+val;$ 的操作。

    然后将每 $16$ 位处理的结果 $s_i$ 按照逻辑倒序排列成一个数组。

数据相乘

​ 大整数的相乘主要是进行对十进制乘法的模拟。

  1. 结果计算

    我们记 $r$​ 为计算后的结果,我们可以得到:

  2. 取模进位

    其中 $e$ 代表进制数,即 $10^{16}$.

正确性证明

[证明] 在结果计算时,__uint128_t 不会发生溢出.

考虑 $r_i$​,设单个数据在计算过程中所记录的最大数据的上界为 $M$.

于是数据不会发生溢出,先计算再取模来优化计算效率是安全的.

过程记录

问题调试

// First version: reading a big integer
data[size] = data[size] << 1 + data[size] << 3; // *= 10
data[size] += currVal;

进行逐行调试与中间变量逐 Bit 输出后发现运算符优先级出了问题.

对拍验证

为了测试边界数据的运行情况,撰写了数据生成程序.

import random

f = open('data.in', 'w+', encoding='utf-8')
g = open('answer.out', 'w+')
len = 500
f.write(str(len) + '\n')
for i in range(len):
    a = random.randint(10**2-1000, 10**5000-1)
    b = random.randint(10**2-1000, 10**5000-1)
    f.write(str(a) + ' ' + str(b) + '\n')
    g.write(str(a*b) + '\n')

f.close()
g.close()

然后就可以通过在控制台进行…

g++ main.cpp -o main

python3 datagen.py
time ./main < data.in > data.out
diff data.out answer.out

# 输出
./main < data.in > data.out  0.33s user 0.04s system 53% cpu 0.683 total

来进行程序运行时间和正确性的检测.

复杂度分析

时间复杂度

我们记字符串 $a, b$ 的长度分别为 $|a|,|b|$.

进行压位本质上是对于 $O(n|a||b|)$​ 的时间复杂度进行常数上的优化,时间复杂度还是由乘法运算的双重循环所决定的 $O(n|a||b|)$​​​.

空间复杂度

程序使用的空间主要用来存储 $a,b,result$ 三个 BigInteger 类的对象.

而 $a,b,r$ 三个变量可以被循环利用.

因此空间复杂度可以近似地看作为 $O(|a|+|b|+|a||b|)$​. (考虑到 $|a| \equiv 0$​ 的情况)

CST2021F 1-2 Graphics

[关键词] 平面解析几何,快速排序,二分查找

方案设计

思路分析

唯一的连接方式

[证明] 对于 $x, y$ 轴上的点列 $X=\{ x_1, \cdots, x_n \}$ 与 $Y=\{y_1, \cdots, y_n\}$,满足如果 $i \lt j$,那么 $x_i<x_j, y_i \lt y_j$,那么将它们按题述方式连接的方式唯一。

​ (1) 假设存在 $i \lt j$​,满足 $x_i$​ 与 $y_j$​​ 相连.

​ 由 $|Y| \lt + \infin$​ 我们可以得出,$\exist u,v \in[1,n], \ u \lt v$​,$y_u$​ 与​ $x_v$​ 相连。

​ 考虑 $\frac{x}{x_i} + \frac{y}{y_j} = 1$​ 与 $\frac{x}{x_v} + \frac{y}{y_u} = 1$ 两条直线,可知它们在第一象限有交点.

​ (2) 假设存在 $i \lt j$​,满足 $x_v$​ 与 $y_u$​ 相连. 同 (1) 我们也可知不成立.

​ 于是我们得出结论,唯一的连接方式为 $x_i$ 与 $y_i$​ 相连,而验证可知这种情况下,两条直线在第一象限确实没有交点。

判断点与直线的位置关系

​ 我们接下来考虑点 $(x_0, y_0)$​​ 与直线 $\frac{x}{a} + \frac{y}{b} = 1$​ 的位置关系. ($x_0, y_0, a,b \gt0$)

​ 联立$\begin{cases} \frac{x}{a} + \frac{y}{b} = 1 \\ y=\frac{y_0}{x_0}x\end{cases}$​,我们可以解得交点的横坐标为 $x_{intersection}=\frac{abx_0}{ay_0+bx_0}$​.

​ (1) 如果点 $(x_0, y_0)$​​​ 在直线左侧,即 $x_00$​​​.

​ (2) 如果点 $(x_0, y_0)$ 在直线上,同理可知 $\Delta = 0$.

​ (3) 如果点 $(x_0, y_0)$ 在直线右侧,同理可知 $\Delta < 0$.

​ 综上,如果我们对直线按照 $x_i$ 升序的次序排序,可知对应的 $\Delta$ 值先负后正.

​ 而我们可以通过二分查找第一个大于 $0$ 的值所在的位置,确定有有多少条直线在给定点的左方或在直线上。

具体实现

  • 给定没有单调性的点列后,如何找到线段的连接关系?快速排序
  • 找到连接关系后如何判断给定点与直线的相互位置?使用$\Delta$判据
  • 如何找到有多少条直线在给定点的左方或在直线上?二分查找

过程记录

​ 本题是对《程序设计基础》课程中传统的排序和查找算法的有效复习。

复杂度估算

时间复杂度

快速排序的平均时间复杂度为 $O(nlgn)$,但是在最坏情况下可能会有 $O(n^2)$ 的特例。

单次二分查找的时间复杂度为 $O(lgn)$,而总共进行了 $m$ 次,即查找的时间复杂度近似为 $O(mlgn)$。

因此,程序的时间复杂度约为 $O(nlgn+mlgn)$。

空间复杂度

程序的存储主要是用来存储 $X,Y$ 两个点列,而快速排序是原地排序算法,这里不需考虑其占用的可能空间。因此空间复杂度为 $O(n)$。

CST2021F 1-3 Filename

[关键词] 动态规划,滚动数组

方案设计

思路分析

动态规划

​ 把字符串 $A$ 变成字符串 $B$ 所需的修改次数,很容易就能想到【最长公共子序列】这道模板题。记 $|S|$ 为字符串 $S$ 的长度,那么 把字符串 $A$ 变成字符串 $B$ 所需的修改次数 $e$ 满足 $e = |A|-|LCS|+|B|-|LCS| = |A|+|B|-2|LCS|$​.

​ 但是再一看,最长公共子序列的常用的 $O(n^2)$ 的算法和优化后的 $O(nlgn)$ 自然是不可能满足题目中 $n,m$ 的数据范围的。而如果我们仔细将这道题与模板题加以对比就能发现,我们多获得的条件就是所允许的最大修改代价 $k$. 而添加的条件,自然是作为我们优化算法效率的突破口

​ 我们还是沿用 $LCS$​ 问题中定义的状态,设 $f[i][j]$​ 代表目标字符串的前 $i$​ 个字符 $B[1, i]$​ 与待修改字符串的前 $j$​ 个字符 $A[1, j]$​ 所含有的公共子序列的长度。我们的状态转移方程为:

​ 但是我们需要考虑 $k$​ 的作用。我们断言,如果存在 $i,j$ 使得 $f[i][j]$ 对应的修改次数大于 $k$,那么由 $f[i][j]$ 递推来的答案一定不符合题目最大修改次数的要求。这是因为如果两个字串序列的修改代价就已经大于 $k$,两个整串之间的修改代价一定是随着 $i, j$ 而单调递增,也必不可能不大于 $k$.

​ 于是我们在递推的时候就可以尝试更改我们的策略。我们可以直接将递推边界设置为 $max((i-k)-1, 1)$ 与 $min(n, (i+k)+1)$。这是因为在递推边界外的 $f$ 值,至少对我们关心的答案没有影响。为了不影响递推公式的通用性,我们可以将递推边界上的值置为 $0$.

滚动数组

​ 但是我们接下来又会遇到一个问题,就是经过计算,$mn$​ 大小的状态记录数组显然会超过内存限制。这时我们可以使用动态规划时常见的操作,也就是滚动数组。由于我们的状态记录数组在每次状态转移时只涉及到两行间的关系,于是我们完全可以将数组开成 $2*n$ 的大小。然后在每次需要读取或写入 $f[i][j]$ 的值时,我们即寻找 $f[i\&1][j]$,其中 $i\&1$ 代表 $i\%2$.

样例分析

image-20210920112305557

(图为模拟运行 LCS 后的结果)

过程记录

对拍验证

​ 因为最后忘了特判 $|A|+|B|-2|LCS| >k$ 将结果置为 $-1$​ 导致九成测爆了 Wrong Answer. 于是写了对拍程序验证。对拍程序使用最平凡的递归算法。但是竟然能想起来特判,写题的时候却不起来。

import random
import os
import subprocess

def solve(ori, des):
    if(ori == '' or des == ''):
        return 0
    n = len(ori)
    m = len(des)
    if ori[n-1] == des[m-1]:
        return solve(ori[0:n-1], des[0:m-1]) + 1
    else:
        return max(solve(ori[0:n-1], des), solve(ori, des[0:m-1]))

for i in range(1000): # 1000 Test cases
    charList ="ab"
    
    n = 20
    m = 20
    k = 18

    ori = [random.choice(charList) for i in range(n)]
    ori = "".join(ori)
    des = [random.choice(charList) for i in range(n)]
    des = "".join(des)

    g = open('testdata.in', 'w+')
    g.write(str(n) + ' ' + str(m) + ' ' + str(k) + '\n')
    g.write(ori + '\n')
    g.write(des)
    g.close()
    
    a = subprocess.check_output(["./main < testdata.in"], shell=True)
    answer = int(a) #cpp
    
    l = solve(ori, des)
    l = n+m-2*l
    if l > k:
        l = -1
    print(f"[Answer {answer} L {l}]")
    assert(answer == l)

​ 跑了一次就能拿到 AssertionError,然后发现了程序中的错误并后悔自己浪费了一次九成测。以下是程序修改后对拍程序的运行效果截图。

image-20210920115702668

复杂度分析

时间复杂度

由 $k$ 的限制和字符串长度的关系,我们得出时间复杂度为 $O(mk)$.

空间复杂度

新开辟的空间主要用来存储两个字符串,以及字符串对应的状态。因此空间复杂度为 $O(n+m)$.

CST2021F 1-4 Risk

[关键词] 单调队列,归并排序,二分查找

方案设计

思路分析

​ 分析题目后,我们的需求是需要多次查询 $Cases$ 数组中位于 $[L_i, R_i]$ 的最大值,其中保证 $L_i$ 单调递增,$R_i=i-1$​​​。而我们可以根据单调队列这种数据结构来实现这种需求,将在下面介绍。在计算好每一天对应的风险评估值,也就是对应区间 $Cases$ 的最大值之后,我们对风险评估值数组进行排序,然后使用二分查找就能找到对于任意的 $e = p,q$,数组中小于 $e$ 的元素个数.

单调队列

声明:本节内容根据题目提示,在复习参考单调队列相关知识后写成。
提交的 main.cpp 中代码均为原创,不存在任何复制粘贴抄袭的行为

​ 我们应实现具有以下功能的单调递减队列.

​ 比如,对于测试 $Cases$ 输入 {0, 1000, 1000, 800, 900}.

Index 区间 对应 Queap 的值
0: Enqueue [0] {0}
1: Enqueue [0 1000] {1000}
2: Enqueue [0 1000 1000] {1000, 1000}
3: Enqueue [0 1000 1000 800] {1000, 1000, 800}
4: Enqueue [0 1000 1000 800 900] {1000, 1000, 900}
5: Dequeue [1000 1000 800 900] {1000, 1000, 900}
6: Dequeue [1000 800 900] {1000, 900}
7: Dequeue [800 900] {900}

​ 记 $q$ 为单调递减队列,即对于所有 $[Leftbound, rightbound)$ 中的位置 $i,j$,命题 $(i<j) \rightarrow (q[i] \ge q[j])$ 成立.

  1. Enqueue

​ 在将 $e$ 插入队列时…

  • 使用 $[Leftbound, rightbound)$​ 内二分查找找到位置 $i$​​​
    • 使得 $i = \inf\{i \ |\ q[i]<e\} \ (Leftbound \le i \le Rightbound)$​​​​
  • $q[i] \leftarrow e$​, $Rightbound \leftarrow i+1$
  1. Dequeue

​ 在考虑将 $e$ 移出队列时…

  • 如果 $e$​ 是区间最大值,那么必有 $e=q[Leftbound]$​ ,只需 $Leftbound \leftarrow Leftbound+1$​;
  • 如果 $e$​ 不是区间最大值,那么在后续的序列中,一定存在大于 $e$​ 的元素,$e$​ 一定在之前被覆盖.
  1. Get

    考虑获取当前区间的最大值,只需要返回队列中最大的元素,也就是 $q[Leftbound]$​.

具体实现

​ 单调队列使用一个线性结构实现,并保证长度上限为 $n$.

​ 归并排序与二分查找手打模板即可.

过程记录

对拍测试

使用规模最大的测例进行测试。

f = open('data.in', 'w+', encoding='utf-8')
ans = ''
leng = 1000000
f.write(str(leng) + '\n')
for i in range(leng, 0, -1):
    f.write(str(i) + ' ')
f.write('\n')
for i in range(1, leng+1):
    f.write(str(i) + ' ')
f.write('\n')
T = 100000
f.write(str(T) + '\n')
for i in range(T):
    f.write('0 10000000000000\n')
    ans += '0 1000000\n'

g = open('answer.out', 'w+')
g.write(ans)
g.close()

f.close()
c7w@cc7w /mnt/e/Project/Homework/DSA/PA1/4-Risk : python3 check.py
c7w@cc7w /mnt/e/Project/Homework/DSA/PA1/4-Risk : time ./main < data.in > cpp.out
c7w@cc7w /mnt/e/Project/Homework/DSA/PA1/4-Risk : diff cpp.out answer.out

./main < data.in > cpp.out  0.36s user 0.11s system 43% cpu 1.091 total

复杂度分析

时间复杂度

设单调队列的长度为 $s$,则 Enqueue 过程的时间复杂度为 $O(lgs)$,Dequeue 过程的时间复杂度为 $O(1)$.

在最坏的情况下,将 $Cases$ 数组中的所有元素都入队,复杂度约为 $O(nlgn)$.

将风险评估值数组 $Measure$ 中的所有元素排序,复杂度 $O(nlgn)$.

之后执行 $2T$ 次二分查找,复杂度为 $O(Tlgn)$.

综上,时间复杂度为 $O(nlgn+Tlgn)$.

空间复杂度

程序所用的空间主要是单调队列的 $O(n)$,$Cases, \ Measure$ 以及归并排序的缓冲数组 $Buffer$ 数组的 $O(n)$,因此总体的空间复杂度为 $O(n)$.