\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年11月12日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\definecolor{mygray}{rgb}{0.4,0.4,0.4}
\definecolor{mygreen}{rgb}{0,0.8,0.6}
\definecolor{myorange}{rgb}{1.0,0.4,0}

\lstset{
    basicstyle=\footnotesize\sffamily\color{black},
    basicstyle=\tt,
    keywordstyle=\color{purple}\bfseries,
    commentstyle=\color{mygray},
    numbers=left,
    numbersep=5pt,
    numberstyle=\tiny\color{mygray},
    showspaces=false,
    showstringspaces=false,
    stringstyle=\color{myorange},
    tabsize=2,
    backgroundcolor=\color[RGB]{245,245,244}
}

\begin{document}

\textbf{Q1.}

(1)

\begin{lstlisting}[language=c++]
struct Node {
    int left;
    int right;
    bool flag;
    Node() : left(-1), right(-1), flag(true) {}
    Node(int l, int r) : left(l), right(r), flag(true) {}
};

int solve(vector<int> &x) {
    int count = 0;
    vector<Node> nodes(x.size());
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < x.size(); i++) {
        if (i > 0 && x[i] == x[i - 1] + 1) {
            pq.push(make_pair(x[i], i));
        } else if (i < x.size() - 1 && x[i] == x[i + 1] + 1) {
            pq.push(make_pair(x[i], i));
        }
        nodes[i].left = i > 0 ? i - 1 : -1;
        nodes[i].right = i < x.size() - 1 ? i + 1 : -1;
        nodes[i].flag = true;
    }

    while (!pq.empty()) {
        pair<int, int> n = pq.top();
        pq.pop();

        if (nodes[n.second].flag &&
            (nodes[n.second].left >= 0 &&
                 x[nodes[n.second].left] == n.first - 1 ||
             nodes[n.second].right >= 0 &&
                 x[nodes[n.second].right] == n.first - 1)) {
            count++;
            nodes[n.second].flag = false;
            if (nodes[n.second].left >= 0) {
                nodes[nodes[n.second].left].right = nodes[n.second].right;
            }
            if (nodes[n.second].right >= 0) {
                nodes[nodes[n.second].right].left = nodes[n.second].left;
            }
            if (nodes[n.second].left >= 0 && nodes[n.second].right) {
                if (x[nodes[n.second].left] == 
                            x[nodes[n.second].right] + 1) {
                    pq.push(make_pair(x[nodes[n.second].left],
                                      nodes[n.second].left));
                } else if (x[nodes[n.second].right] ==
                           x[nodes[n.second].left] + 1) {
                    pq.push(make_pair(x[nodes[n.second].right],
                                      nodes[n.second].right));
                }
            }
        }
    }
    return count;
}
\end{lstlisting}

分析如下，第一轮循环复杂度为 $O(n)$，第二轮循环最多也只需 $O(n)$，因此最坏时间复杂度为 $O(n)$.

(2.1)
\begin{proof}
    假如存在 $x_j=x_i+1,|j-i|>1$，且 $x_i$ 是 $\mathbf{x}$
    中当前能够删去的最大元素，则 $x_j$ 的相邻元素均不等于 $x_j-1$，
    假如操作 $\mathbf{x}$ 可以得到 $x_i$ 和 $x_j$ 相邻，则需
    将 $x_{i+1},\ldots,x_{j-1}$ 删除，因为每删除一个元素，均
    有相邻元素比被删除元素更小，且最初删除的元素本身比 $x_i$ 小，
    故也比 $x_j$ 小，因而在 $x_i$ 和 $x_j$ 中间，不论删除多少元素，
    最终总会留下一个元素比 $x_i$ 和 $x_j$ 更小，且不能删去，因此
    $x_i$ 和 $x_j$ 不能相邻.
\end{proof}

(2.2)
\begin{proof}
    取 $\varphi$ 为如下函数，若 $d$ 为以 $x_i$ 起始的合法删除
    序列，则 $\varphi(d)=d$；若 $d$ 不以 $x_i$ 起始，则对 $d$
    的起始元素 $x_d$，如果有它的相邻元素为 $x_d+1$，则转为以 $x_d+1$
    起始，循环这样做，直到没有一个恰比其大1的相邻元素，假设此时
    的起始元素为 $x_d'$，若 $x_d'$ 就是 $x_i$，则已经得到
    $\varphi(d)$，而如果 $d_d'$ 不是 $x_i$，且已经没有恰大1的相
    邻元素，则先从该处起始和先从 $x_i$ 处开始并不会缩短删除序列
    的长度，则取 $\varphi(d)$ 为交换一下顺序之后的结果即可.

    由以上分析可知，总存在 $\varphi:D\to D'$，使得 $\forall d\in D$，
    $\varphi(d)$ 不短于 $d$.
\end{proof}

(3) 好像用 (1) 中的算法也可以？

\hrulefill\medskip

\textbf{Q2.}

(1) 先遍历一遍 $x_1,\ldots,x_n$，得到前缀和 $s_1,\ldots,s_n$，
其中 $s_i=\sum_{j=1}^{i}x_j$，取 $s_0=0$，再遍历一遍，计算出
$i^*=\underset{k\leqslant i\leqslant n}{\arg\max}\{s_i-s_{i-k}\}$，
也可以在一次循环中就完成这个计算，最后只需从第 $i^*$ 间宿舍开
始，往序号小的方向依次进入，即可得到能缴获的电脑数量最大值
$s_{i^*}-s_{i^*-k}+\frac{k(k-1)}{2}$.

(2)
\begin{proof}
    在 $k\leqslant n$ 时，如果重复进入一间已经搜过的宿舍，则
    只能缴获从上次进入到此次进入的天数那么多台电脑，而进入未
    搜过的宿舍，不但从一开始到此次进入的天数那么多台电脑，还能
    缴获原本在这里的电脑，因此每次都进入一间未搜过的宿舍，能缴
    获的电脑数量一定不会减少.

    而一共 $k$ 天，新买的电脑数一共 $1+\cdots+k-1=\frac{k(k-1)}{2}$
    台，这是固定的，只需最大化连续的 $k$ 间宿舍原本电脑数即可.
    使用前缀和来计算这个最大值，正确性显然，时间复杂度最坏为 $O(n)$.
\end{proof}

(3) 考虑 $k'=k\mod n$ 是 $k$ 除以 $n$ 的余数，则只需先从第 $k'$
间宿舍开始，往第1间宿舍方向搜索，搜到底后再向另一端搜索，反复
重复，直到搜到第 $k$ 天，可以得到最大值为 $\sum_{i=1}^{n}x_i+nk-\frac{n(n+1)}{2}$.

(4)
\begin{proof}
    因为 $k>n$，因此可以在搜完全部宿舍后再返回继续搜索.

    而经过 $k$ 天，总共会有 $\sum_{i=1}^{n}x_i+nk$ 台电脑
    被藏在宿舍中，使用当前的方法可以最多剩下 $\frac{n(n+1)}{2}$
    台电脑.

    假如不这样做，最终停的位置设为 $m$，则不妨设最后是从1扫到
    $m$ 的，左侧剩下 $1+2+\cdots+m$ 台电脑，而另一端剩下的
    电脑数会比 $(m+1)+\cdots+n$ 更多，因为之前来到此处时已
    经是至少 $2m$ 天前了，因而使用当前算法可以取到剩余电脑
    下界.
\end{proof}

\hrulefill\medskip

\textbf{Q3.}

(1) 只需在最坏 $O(n\lg n)$ 时间复杂度内对输入序列进行排序即
可，可以使用堆排序，最终需要的结果为递增的排序结果.

(2) 只需在最坏 $O(n\lg n)$ 时间复杂度内对输入序列进行排序即
可，可以使用堆排序，最终需要的结果为递减的排序结果.

(3.1)
\begin{proof}
    对任意一个 $\mathbf{x}$ 的排列 $\mathbf{y}$，只要存在 $y_{i+1}\lesssim y_i$，
    因为 $y_{i+1}\lesssim y_i$ 是 $f(\mathbf{y'})\geqslant f(\mathbf{y})$
    的充分条件，其中 $\mathbf{y'}$ 是将 $\mathbf{y}$ 中 $y_i,y_{i+1}$ 交换得到
    的排列，因此交换之后总能使 $f$ 的值不减少，而对于 $\mathbf{z}$，
    其满足 $z_1\lesssim z_2\lesssim\cdots\lesssim z_n$，已经
    没有可以交换而使 $f$ 增大的元素对，因此 $f$ 在 $\mathbf{z}$
    处取最大值.
\end{proof}

\begin{proof}
    下面对 (1) 证明正确性. 对一个排列 $\mathbf{y}$，$\mathbf{y'}$
    是将 $\mathbf{y}$ 中 $y_i,y_{i+1}$ 交换得到的排列，则有
    $y_{i+1}\leqslant y_i$ 条件下，$f(\mathbf{y'})-f(\mathbf{y})=iy_{i+1}+(i+1)y_i-iy_i-(i+1)y_{i+1}=y_i-y_{i+1}\geqslant 0$，
    即 $y_{i+1}\leqslant y_i$ 是 $f(\mathbf{y'})\geqslant f(\mathbf{y})$ 的充分条件，
    由结论，得证.
\end{proof}

\begin{proof}
    下面对 (2) 证明正确性. 对一个排列 $\mathbf{y}$，$\mathbf{y'}$
    是将 $\mathbf{y}$ 中 $y_i,y_{i+1}$ 交换得到的排列，则有
    $y_{i+1}\geqslant y_i$ 条件下，$f(\mathbf{y'})-f(\mathbf{y})=\max\{0,y_{i+1}-i\}+\max\{0,y_i-(i+1)\}-\max\{0,y_i-i\}-\max\{0,y_{i+1}-(i+1)\}$，
    若 $i+1\leqslant y_i$ 或 $y_{i+1}\leqslant i$，则 $f(\mathbf{y'})-f(\mathbf{y})=0$，
    而如果有 $y_i<i+1<y_{i+1}$，则 $f(\mathbf{y'})-f(\mathbf{y})\geqslant i+1-y_i$，
    如果有 $y_i<i<y_{i+1}$，则 $f(\mathbf{y'})-f(\mathbf{y})\geqslant 1$，
    因此总有 $f(\mathbf{y'})\geqslant f(\mathbf{y})$，由结论，得证.
\end{proof}

(3.2)
按照 $\max\{a_1,b_2\}\leqslant\max\{a_2,b_1\}$ 来进行排序，也就
是如果 $y_1=\langle a_1,b_1\rangle,y_2=\langle a_2,b_2\rangle$，
则 $y_1$ 应排序在 $y_2$ 前面. 这样按堆排序即可，最坏时间复杂度 $O(n\lg n)$.

\begin{proof}
    对一个排列 $\mathbf{y}$，$\mathbf{y'}$
    是将 $\mathbf{y}$ 中 $y_i,y_{i+1}$ 交换得到的排列，则有
    $\max\{a_{i+1},b_i\}\leqslant\max\{a_i,b_{i+1}\}$，
    只需考虑 $t_{i+1}(\mathbf{y'})$ 和 $t_{i+1}(\mathbf{y})$ 的
    差别.
    $t_{i+1}(\mathbf{y'})=\max\{t_{i-1}(\mathbf{y})+b_{i+1}+b_i,\sum_{j=1}^{i-1}a_j+a_{i+1}+b_{i+1}+b_i,\sum_{j=1}^{i+1}a_j+b_i\}$，
    $t_{i+1}(\mathbf{y})=\max\{t_{i-1}(\mathbf{y})+b_i+b_{i+1},\sum_{j=1}^{i-1}a_j+a_i+b_i+b_{i+1},\sum_{j=1}^{i+1}a_j+b_{i+1}\}$，
    因此 $t_{i+1}(\mathbf{y'})-t_{i+1}(\mathbf{y})=\max\{a_{i+1},b_i\}-\max\{a_i,b_{i+1}\}$，
    因此 $\max\{a_{i+1},b_i\}\leqslant\max\{a_i,b_{i+1}\}$
    是 $t_n(\mathbf{y'})\leqslant t_n(\mathbf{y})$ 的充分条件.
\end{proof}

\hrulefill\medskip

\textbf{Q4.}

(1.1) 字符串 $s=$``$(\star)$''，如果优先匹配星号，则剩下一个
左括号不能继续匹配，但原本可以让 $\star$ 替换为空，可以匹配.

(1.2) 字符串 $s=$``$\left(\star()\right.$''，如果先匹配左侧最左边的左括号，
则剩下一个左括号右侧没有别的符号可以匹配，但原本可以让$\star$
替换为右括号，可以匹配.

(1.3) 字符串 $s=$``$\left(\star\left(\star\right.\right.$''，
如果第二遍扫描中先匹配左侧最左边的左括号，则剩下一个左括号右侧
没有别的符号可以匹配，但原本可以让两个 $\star$ 替换为右括号，
可以匹配.

(1.4)
\begin{lstlisting}[language=c++]
struct Node {
    int left;
    int right;
    bool flag;
    Node() : left(-1), right(-1), flag(true) {}
    Node(int l, int r) : left(l), right(r), flag(true) {}
};

bool solve(string &s) {
    vector<int> pstack, sstack;
    vector<Node> nodes(s.size());
    int temp;
    for (int i = 0; i < s.size(); i++) {
        nodes[i].left = i > 0 ? i - 1 : -1;
        nodes[i].right = i < s.size() - 1 ? i + 1 : -1;
        nodes[i].flag = true;
        if (s[i] == '(') {
            pstack.push_back(i);
        } else if (s[i] == '*') {
            sstack.push_back(i);
        } else if (s[i] == ')') {
            if (pstack.size() > 0) {
                temp = pstack.back();
                pstack.pop_back();
            } else if (sstack.size() > 0) {
                temp = sstack.back();
                sstack.pop_back();
            } else {
                return false;
            }
            nodes[temp].flag = false;
            nodes[i].flag = false;
            if (nodes[temp].left >= 0)
                nodes[nodes[temp].left].right = nodes[temp].right;
            if (nodes[temp].right >= 0)
                nodes[nodes[temp].right].left = nodes[temp].left;
            if (nodes[i].left >= 0)
                nodes[nodes[i].left].right = nodes[i].right;
            if (nodes[i].right >= 0)
                nodes[nodes[i].right].left = nodes[i].left;
        }
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        if (!nodes[i].flag)
            continue;
        if (s[i] == '(')
            return false;
        if (s[i] == '*' && pstack.size() > 0) {
            temp = pstack.back();
            pstack.pop_back();
            nodes[temp].flag = false;
            nodes[i].flag = false;
            if (nodes[temp].left >= 0)
                nodes[nodes[temp].left].right = nodes[temp].right;
            if (nodes[temp].right >= 0)
                nodes[nodes[temp].right].left = nodes[temp].left;
            if (nodes[i].left >= 0)
                nodes[nodes[i].left].right = nodes[i].right;
            if (nodes[i].right >= 0)
                nodes[nodes[i].right].left = nodes[i].left;
        }
    }
    return true;
}
    
\end{lstlisting}

分析可知，两遍扫描，每遍最多 $O(n)$，因此总的最坏时间复杂度为 $O(n)$.

(2)
\begin{proof}
    感觉正确性挺显然的，不知道咋证.
\end{proof}

\end{document}