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

  • CST2021F 3-1 Circuit
  • CST2021F 3-3 kth
  • CST2021F 3-5 Prefix
  • CST2021F 3-7 Sort

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

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

Problem White Box (20%) Black Box (80%)
CST2021F 3-1 Circuit (25%) 100 [100] -1
CST2021F 3-3 kth (25%) 100 [100] -1
CST2021F 3-5 Prefix (25%) 100 [100] -1
CST2021F 3-7 Sort (25%) 100 [100] -1

CST2021F 3-1 Circuit

[关键词] Trie 树

方案设计

$\forall i \in [0, n)$,需要一种支持以下操作的数据结构:

(1) 持有 $[\max(i-k-1, 0), \min(i+k+1, n-1)]$ 中所有的元件的输出信息;

(2) 可以查询这些信息中满足与 $data[i]$ 异或值最大的 $data[j]$ 的 $j$,其中 $i \ne j$。

(3) 在考虑 $i$ 结束,转向考虑 $i+1$ 的时候,可以快速地删除 $data[i-k-1]$ 的信息,加入 $data[(i+1)+k+1]$ 的信息。

而字典树,恰恰就能满足我们上述的需求,下面对其进行详细介绍。

字典树:规则

字典树的结点分非叶结点叶结点两种。事实上,我们可以用考虑有限转移自动机(DFA)的方式来考虑字典树。

非叶结点记录了所有终态经过它的串的个数,以及通过输入一个字符 $a\in\Sigma$​,可以转移到的下一个非叶结点或叶结点的位置。

叶结点记录了所有以它为终态的串的个数,同时维护了一个列表来按次序记录所有以该叶结点为终态的串的 ID。

我们定义,一个结点输入一个字符 $a\in \Sigma$​​ 后对应的结点存在,当且仅当该结点是非叶结点,同时该非叶结点可以通过字符 $a$ 转移到位置 $t$,且结点 $t$ 接受的终态经过 $t$ 或是以 $t$ 为终态的串的个数非零。

字典树:初始化

从这小节的讨论开始,我们只讨论 $\Sigma=\{0, 1\}$ 的情况。

字典树默认只有一个根节点,接受空串 $\epsilon$​,终态经过它的串的个数为 $0$​​,这里我们不将该根节点视为叶结点。

$\Sigma = \{0,1\}$​​ 的字典树的非叶结点只需记录其经过 $0$ 转移和 $1$ 转移后的到达结点,这里我们使用二叉树的记号,分别记作其左孩子和右孩子。

字典树:插入

考虑我们将插入 $64$ 位整数 $data[i]$。

我们从根节点出发,逐一考虑去接受该串的字符,遇 $0$ 则转向其左孩子,遇 $1$ 则转向其右孩子,若对应的孩子的位置不存在(注意这里与上述结点的存在不同,结点存在需要位置存在,且该位置的记录串数非零)则创建。同时我们将沿途所有的非叶结点的“终态经过它的串的个数”自增,终态叶结点的“以它为终态的串的个数”自增。最后,我们在终态叶结点的串列表中将该串的 ID $i$ 插入。在本题中由于我们考虑的窗口永远是从左向右滑动,我们可以保证插入的 ID $i$​ 一定是在列表的末尾,故我们只需插入到列表末尾即可。

字典树:删除

考虑我们将删除 $64$ 位整数 $data[i]$,同时我们断言 $data[i]$ 在此前一定被插入到树中。

我们从根节点出发,逐一考虑去接受该串的字符,遇 $0$ 则转向其左孩子,遇 $1$ 则转向其右孩子。我们将沿途所有的非叶结点的“终态经过它的串的个数”自减,终态叶结点的“以它为终态的串的个数”自减。最后,我们在终态叶结点的串列表中将该串的 ID $i$ 移除。在本题中由于我们考虑的窗口永远是从左向右滑动,我们可以保证删除的 ID $i$​ 一定是在列表的首位,故我们只需删除列表首位即可。

 字典树:查询

考虑我们将查询 $j$,使得 $i \ne j$ 且 $data[j]$ 与 $64$ 位整数 $data[i]$ 的异或值最大,其中 $j \in [\max(i-k-1, 0), \min(i+k+1, n-1)]$。

由贪心策略,如果我们每步均朝向异或值最大的方向走,即遇 $0$ 走 $1$,遇 $1$ 走 $0$(如果可能的话,这种可能性由对应的结点存在蕴含),我们最终得到的异或值便一定是最大的。

也就是说,我们的查询过程可以概述如下:

从根节点出发,逐一去考虑接受该串的字符,遇 $0$ 若右孩子存在则转向右孩子,不然转向左孩子;遇 $1$ 若左孩子存在则转向左孩子,不然转向右孩子。这样不断进行下去势必会达到一个终态,而这个我们要做的便是输出这个终态叶结点的接受串 ID 列表中第一个 $id$(满足 $id \ne i$​)。

过程记录

输入有毒。输入有毒。输入有毒。最初一版使用 getchar() 读取 $64$ 位字符串,结果满满的是 WA,一个点都不给过。初步推断可能是输入文件以 \r\n 结尾而程序只考虑了以 \n 结尾的情况。换用 scanf() 后便解决了问题,而这个问题竟然喜提 PA3 中 Debug 时间最久的问题

解决过程大致是首先为了控制变量,排除算法实现过程的具体问题,做了以下两个操作:

(1) 撰写了对拍器 check.py(见附 1),但是本地的数据怎么测都是 AC。

(2) 撰写了 Trivial.cpp(见附 2),读入部分没变(事实上,最初我认为是后续字典树处理写出了问题,于是想写个最简单的版本交上去看下测试数据的规模),使用最平凡的 $O(nk)$ 的算法处理问题,最终发现还是爆零。目光转向读入部分,改用 scanf 后 Trivial 算法拿到了 40/50(自然会喜提 TLE),然后是将新的读入复制回 main.cpp,前后两次拿到了 50/50, 90/90, 完结撒花

复杂度分析

从时间上来看,每个结点最多被插入一次,查询一次,删除一次,这些操作的时间复杂度均是正比于树高 $h=O(64)=O(1)$,而对于 $n$ 个结点,我们有时间复杂度是 $O(n)$。

字典树的每个结点可能对应 $64$​​ 位整数的位表示中的一个字符。也就是说,最多有 $O(64n)=O(n)$​​ 量级的结点个数。而这些结点有小部分是可以复用的。具体来说,根据鸽巢原理,我们设读入 $k$​​ 个字符后,才会出现 $2^k>n$​​,解得 $k\ge19$​​。也就是说,我们可以考虑一种极端的情况,树深度 $depth \le 19$​​ 时为满树,而树深度 $depth \ge 20$​​ 时为单链,这种情况下最多的结点个数为 $\sum_{i=0}^{19}2^i+(64-19)n\approx 2.410^7=24M$​​​。

我们的叶结点共有 $O(n)$​ 个,同时每个叶节点都需要维护 1 个列表,因此列表的个数也是 $O(n)$​​ 个,列表的元素的总个数也是 $O(n)$。综上,空间复杂度为 $O(n)$。

而这题还是有卡常的嫌疑的,也就是说虽然是 $O(n)$​ 量级,但是空间复杂度还是可能有可能会超限,具体分析如下:($n=5*10^5$)

  • 非叶结点,24M * 12Byte = 288M.
  • 列表条目,0.5M * 12Byte = 6M.
  • 叶结点,0.5M * 20Byte = 10M.
  • $64$ 位整数的数据,0.5M * 8Byte = 4M.
  • 合计 308M < 512M.

附录

附 1: check.py

import io
import time
import datetime
import random
import subprocess
import numpy as np

IN = ''
OUT = ''

class Judger:
    def generateInputData(self):
        global IN, OUT
        IN = ''
        OUT = ''
        n = 10
        k = 2
        IN = f'{n} {k}\n'
        
        dataList = [random.randint(0, 2**64-1) for i in range(n)]
        rawList = [bin(data)[2:].zfill(64) for data in dataList]
        print(dataList)
        print(rawList)
        for raw in rawList:
            IN += f'{raw}\n'
        
        for index, data in enumerate(dataList):
            left = index - k - 1
            if left < 0:
                left = 0
            right = index + k + 1
            if right > n-1:
                right = n-1
            
            currMaxIndex = -999
            currMaxValue = -999
            for i in range(left, right+1):
                if (i == index):
                    continue
                if (dataList[i] ^ data) > currMaxValue:
                    currMaxIndex = i
                    currMaxValue = (dataList[i] ^ data)
            OUT += f'{currMaxIndex}\n'
        
        return IN

    def getAnswer(self):
        global OUT
        return OUT.strip()
    
    def judge(self, name, judgeAns=True):
        print('\n\nCompiling...')
        try:
            subprocess.check_output(['g++', '-O2', '-std=c++14', '-w', f'{name}', '-o', 'main'])
        except subprocess.CalledProcessError as e:
            return 'CE'
        
        print('Generating testing data...')
        data = self.generateInputData()
        
        print('Running...')
        try:
            time1 = time.time()
            cppout = subprocess.check_output(['./main'], input=bytes(data, 'utf-8'), timeout=2.0)
            cppout = cppout.decode('utf-8').strip()
            time2 = time.time()
        except subprocess.TimeoutExpired:
            f = open(f'check-{datetime.datetime.now().strftime("%Y-%m-%d-%H-%M-%S")}.log', 'w+', encoding='utf-8')
            f.write(f"Time Limit Exceeded\n")
            f.write("-------------IN--------------\n")
            f.write(data + '\n')
            f.close()
            return f'Time Limit Exceeded (2.000s)'
        except subprocess.CalledProcessError as e:
            f = open(f'check-{datetime.datetime.now().strftime("%Y-%m-%d-%H-%M-%S")}.log', 'w+', encoding='utf-8')
            f.write(f"Runtime Error (signal {e.returncode})\n")
            f.write("-------------IN--------------\n")
            f.write(data + '\n')
            f.close()
            return f'Runtime Error (Signal {e.returncode})'
        if judgeAns:
            # print(cppout)
            # print("↑ cppout ↓ ans")
            print('Generating testing answer...')
            ans = self.getAnswer()
            # print(ans)
            
            print('Judging...')
            try:
                cppout_ = cppout.split('\n')
                ans_ = ans.split('\n')
                if (len(cppout_) != len(ans_)):
                    raise BaseException(-1)
                for i in range(len(cppout_)):
                    if (cppout_[i].strip() != ans_[i].strip()):
                        raise BaseException(i)
            except BaseException as e:
                f = open(f'check-{datetime.datetime.now().strftime("%Y-%m-%d-%H-%M-%S")}.log', 'w+', encoding='utf-8')
                f.write(f"Wrong Answer on line {e}\n")
                f.write("-------------IN--------------\n")
                f.write(data + '\n')
                f.write("-------------CPPOUT--------------\n")
                f.write(cppout + '\n')
                f.write("-------------ANS--------------\n")
                f.write(ans + '\n')
                f.close()
                return 'Wrong Answer'
            return f'Accepted ({round(time2 - time1, 3)}s)'

        else:
            return f'Program exited successfully ({round(time2 - time1, 4)}s)'
        

j = Judger()
for i in range(1000):
    print(j.judge('trivial.cpp', judgeAns=True))

附 2: Trivial.cpp

#define ull unsigned long long
#include <cstdio>
int n, k;

ull data[500001] = {0};

int main() {
    scanf("%d %d\n", &n, &k);
    for (int i = 1; i <= n; ++i) {
        char c = getchar();
        while (c == '0' || c == '1') {
            data[i] <<= 1;
            data[i] += c - '0';
            c = getchar();
        }
    }

    for(int i = 1; i <= n; ++i) {
        
        int l = i-k-1;
        if(l < 1) l = 1;
        int r = i + k + 1;
        if(r > n) r = n;
        
        ull currMax = 0;
        ull currMaxIndex = l != i ? l : (l + 1);

        for(int T = l; T <= r; ++T) {
            if(T == i) {continue;}
            if ((data[T]^data[i])>currMax) {
                currMax = data[T] ^ data[i];
                currMaxIndex = T;
            }
        }
        printf("%d", currMaxIndex-1);
        if(i != n) puts("");
    }

    return 0;
}

CST2021F 3-3 kth

[关键词] 堆,偏序关系,归并排序

方案设计

偏序关系

首先我们可以回忆出针对一维数组寻找第 $k$​ 大元素问题的解决方案。我们可以将原数组直接建小顶堆后,第 $k$​ 次 pop 出的元素即为所求,时间复杂度为 $O(n+k*\log n)$​​。而稍微再仔细考虑我们的建堆过程,实际上我们是将这一维数组中的所有元素之间建立起一种偏序关系。没错,偏序关系,这也是接下来我们讨论的重点。

二维情况

再来考虑针对两个数组的情况。首先我们可以固定某个 $X$ 元素,将 $Y$ 元素的顺序排序;然后固定某个 $Y$ 元素,将 $X$ 元素进行排序。这里排序的意思是说,找到一个序列 $(new_1, new_2, \cdots, new_n)$,使得 $X_{new_i} = sorted(X)[i]$。之后我们便可以记 $X[i]:=X_{new_i}=sorted(X)[i]$.

针对两个数组的情况,我们记 $(i,j)$ 表示值 $X[i]+Y[j]$。可以对于 $(i_1, j_1)$ 与 $(i_2, j_2)$,我们有:

  • $(i_1,j_1) \le (i_2, j_2)$, if $i_1 \le i_2$ and $j_1 \le j_2$.

由于我们的内存有限,我们能放在堆中的元素是有限的。所以我们要想出一种组织这些元素的方式,使得每个元素能且仅能出现在小顶堆中一次,也就是说,我们要建立一种新的偏序关系 $M$​​,使得 $\forall (i,j)$, 集合 $\{(x,y)\ |\ (x,y) \le_M (i,j) \ \and\ (x,y)\ne(i,j) \}$ 有最大元 $(m,n)$,即当且仅当 $(m,n)$ 出堆,$(i,j)$ 才能入堆,且这种偏序关系满足如果 $(x,y) \le_M(i,j)$,那么 $(x,y) \le (i,j)$​​​​。

对于数组有两个维度的情况,我们可以构造偏序关系 $M$ 如下图:

image-20211130004938307.png

对于某个顶点 $(i,j)$,可以验证从比它小的元素指向它的边的入度均为 $1$(根节点除外),此即保证了每个元素都能入堆(当在新的偏序关系下,比它小的元素的极大值出堆,即当与它直接相连但比它小的那个顶点出堆,注意这里的“小”均为在新的偏序关系下),且每个元素仅能入堆一次。

于是我们便可以首先将 $(1,1)$ 推入小顶堆中,然后每 pop 一次,将其出边对应的结点推入堆中。这样 pop $k$ 次后得到的 $(x,y)$​ 即为所求。

三维情况

在三个数组的情况,我们采用与上述类似的记号,而建立的偏序关系如下图:

image-20211130005405726.png

于是我们便可以首先将 $(1,1,1)$​​ 推入小顶堆中,然后每 pop 一次,将其出边对应的结点推入堆中。这样 pop $k$​​ 次后得到的 $(x,y,z)$​​ 即为所求。

过程记录

  • 首先对原有的 X,Y,Z 数组进行归并排序,具体来说是找到上述的 $X$​

  • 编写 Index 类模拟上述定义的索引 tuple。可以简单地通过重载运算符来实现两个 Index 之间的比较(调用交互库函数)。

  • 注意按照上述拓扑关系建立 Index 之间的新偏序关系,以保证所有顶点能且仅能被推入堆中一次。

复杂度分析

从时间上来说,归并排序所需时间复杂度为 $O(n \log n)$​。注意到上述所有结点最多有 3 条出边,即运行 $k$​ 次上述操作后,可以保证堆中的结点数不超过 $3*k=O(k)$​。对于这样的堆,运行 $k$​ 次 pop,$O(3k)$​ 次 insert,我们有时间复杂度为 $O(k \log k)$​​​。​于是总体时间复杂度为 $O(n \log n + k \log k)$。

对原数组进行排序的归并排序数组辅助空间为 $O(n)$​,堆开辟的空间大小为 $O(3k)=O(k)$​。总空间复杂度为 $O(n+k)$。

CST2021F 3-5 Prefix

[关键词] KMP next[] 表,动态规划

方案设计

关键概念定义

这里我们采用一种与题目和课堂讲义上不同的字符串及 next[] 表表示方式,具体介绍如下:

  • 对于长度为 $n$ 的串 $S$,记之为 $S[1…n]$​. (Index starts from 1)
  • 记 $next[j]$​ 表示 $S[1…j]$​​ 中最大自匹配的真前缀和真后缀的串长,也就是说,与讲义中偏重 Pattern String 下一次移动到的位置不同,我们更加侧重的是这个长度值。举个例子:
i 0 1 2 3 4 5 6
raw[i] * a a b a a b
next[i] -1 0 1 0 1 2 3

可以证明,这种 next[] 表与讲义上的 next[] 表只偏差了一个 offset。

next[] 表的构建

根据我们的定义,$next[j]$​​ 代表 $S[1…j]$​​ 中最大自匹配的真前缀和真后缀的串长,而这个真前缀便是 $S[1…next[j]]$​。

于是,在我们采用递推的方式计算 $next[j+1]$​ 时,我们要寻找的是 $S[1…j+1]$​ 中最大自匹配的真前缀和真后缀的串长。

我们已知 $S[1…t]$​ 与 $S[j-t+1… j]$​ 是匹配的,这里 $t \in \{next[j], next[next[j]], next[next[next[j]]] \cdots\} =: T_j$​

于是,我们便可以逐个考虑序列 $T_j$ 中的元素:

  • 如果 $S[j+1]$​​ 与 $S[t+1]$​​ 相等,我们便找到了 $S[1…j+1]$​​ 的一个最大的自匹配的真前缀与真后缀,此即 $next[j+1] \leftarrow t+1$.
  • 不然,我们转而考虑这个序列的下一个元素。

由于这个序列最后必然收敛于通配符 *,算法必定终止。

动态规划求前缀出现次数

考虑串 aabaabaab,定义 $dp[j]$ 表示 $S[1…j]$ 的所有真前缀与真后缀相匹配的次数。可得下表:

i 0 1 2 3 4 5 6 7 8 9
raw[i] * a a b a a b a a b
next[i] -1 0 1 0 1 2 3 4 5 6
dp[i] - 0 1 0 1 2 1 2 3 2

归纳可证明:

最后我们的答案还需要考虑整个子串自匹配的情况,即 $S[1…j]$ 在 $S[1…n]$ 中出现过一次,$\forall j \in [1, n]$.

于是答案便是 $n + \sum_{i=1}^ndp[i]$.

过程记录

  • 通过引入通配符 * 这个哨兵结点,可以有效地进行递推。
  • 需要用 long long 来存储答案数值。
  • 同时记录 $raw, next, dp$ 会导致内存溢出,因为 $(1+4+8)*20M = 260M > 256M.$
    • 首先想到的解决方案是,由于答案的大小不会超过 $(20M)^2=4e14$,而 $\log_2(4*10^{14})=2+\frac {14} {\lg2} \approx 49$,使用 $56$ 个 bit 便可以将其储存。
      • 于是我们可以撰写自己的 int56 类,在 get 与 set 对应整数的时候将 long long 通过位运算拆成 char, short, int 三部分(7 Byte)。
      • 经过此种优化之后,内存用量为 $240M$,便有了通过的可能。
    • 但是转而一想,数据结构并不是汇编程序设计。
      • 事实上我们按照上述解题思路不难得出,我们是先算出了 $next$ 数组中的所有值,然后根据 $next$ 数组的值去递推 $dp$ 数组。
      • 事实上,我们可以考虑只建立一个 $next$​ 数组,为 long long 类型,首先在其中算出所有 $next_j$,然后根据这个 $next_j$ 计算 $dp_i$,实行就地覆盖的方法,并不会影响答案的结果。

复杂度分析

KMP 的 next[] 表构建过程时间复杂度为 $O(n)$,之后根据 $next$ 递推 $dp$ 与累加求和的复杂度均为 $O(n)$。于是时间复杂度为 $O(n)$。

空间上,使用 $raw$​ 与 $next$​ 数组均为 $O(n)$​ 大小,最大内存使用量为 $20M*9=180M<256M$。

CST2021F 3-7 Sort

[关键词] 归并排序, 四路归并

方案设计

首先由题目测试数据给出的 $n$ 和 $k$ 的大小关系我们可以果断摒弃掉最坏情况为 $O(n^2)$ 的冒泡排序,选择排序等等算法。这些算法即使在一次能比较的数的个数上进行了优化,这也只是常数级别的,并不能撼动其数量级的地位。

目光自然转向了复杂度为 $O(n \log n)$ 的快速排序和归并排序上。我们要做的,便是利用比较器一次可以比较三个数的性质,对这些复杂度已经达到理论下界的算法进行常数级别的优化。

这里由于归并排序的稳定性,所以首选的是归并排序。首先我们自然可以想到的是,模仿二路归并的具体实现,如果比较器一次可以比较三个数,那么我们可以尝试实现三路归并,这样需要求解的递推方程为 $Cmp(n) = 3*Cmp(\frac n 3) + n$​,这是基于每经过一次比较,我们就可以确定三路中的最小元素,并将其从三路中取出,放置于数组的对应位置​。

但是如果我们代入 $n=3^k$​​ 对该方程求解,我们得出 $a_k=(k+1)3^k$​​,其中 $a_k=Cmp(3^k)$​​,此即 $Cmp(n) \sim n\log_3n$​​。代入 $n=10^6$ 我们有 $Cmp(n) \approx 7.6*10^7$。不能满足我们对 $limit$ 的要求。

于是想法转移到能否更加 exploit 比较器返回的结果中包含的信息。具体来说,在三路归并中,每次比较都能返回 $a<b<c$,我们只运用到了 $a<b$, $a<c$ 这两个部分,并没有利用到 $c$​ 是三者的最大值这么一个条件。而一旦 $c$ 是最大值,由于有 $b<c$,可以保证在下次的比较过程中,$c$ 一定不是三者中的最小值。这竟然退化成了 $b,c,d$ 比较,实际上我们用比较器只比较了 $b, d$ 的二路归并的情况。

于是再进一步,我们考虑可以使用四路归并,便可以尽力 exploit 比较器的返回信息。具体来说,和上述想法相似,对于待合并数组 $a,b,c,d$,一旦我们在 $a,b,c$ 中比较得到 $a<b<c$,在下一次比较选择最小值时,我们便可以忽略掉 $c$,只比较 $next(a), b,d$,其正确性由 $b<c$,即 $c$ 一定不是最小值保证。

这样需要求解的递推方程为 $Cmp(n) = 4Cmp(\frac n 4) + n$​,此即 $Cmp(n) \sim n\log_4n$​。代入 $n=10^6$​ 我们有 $Cmp(n) \approx 9.97*10^6<limit_n$​。

过程记录

四路归并的具体实现过程中,递归过程与二路归并类似,而重点在于四路合并的过程。具体来说,我们可以先在 $a,b,c,d$ 四个数组中选取前三个数组 $a,b,c$ 做一次比较,将三者中的最大值的数组信息记录在一个全局变量 nextBypass 中。

然后我们便可以进入循环,每次比较除了该全局变量 nextBypass 记录的数组的剩下三个数组的首元素的相对大小信息,然后将三者中的最大值所在的数组信息更新给全局变量 nextBypass,而将最小值写入最终的合并后数组中,直到四路中某个数组耗竭,退化成上述平凡的三路归并的情况,进而退化成更加平凡的二路归并的情况,进而退化成更加更加平凡的数组拷贝的情况。

复杂度分析

四路归并中,时间复杂度方程与 $Cmp(n) = 4*Cmp(\frac n 4) + n$ 同构,即 $T(n) = O(n \log_4 n)$。而我们在上文也证明了比较次数 $Cmp(n) = O(n \log_4 n)$。

在空间上,主要开辟的是 $a,b,c,d$ 四个数组的辅助空间,空间复杂度为 $O(n)$。