solution.tex

\documentclass[11pt,a4paper,oneside]{article}
% \usepackage{luatexja-fontspec}
\usepackage{ctex}
\usepackage{xeCJKfntef,xcolor}
\usepackage{parallel}
\usepackage{clrscode3e}
\usepackage{lastpage}
\usepackage{tikz}
\usepackage{tipa}
\usepackage{amsfonts}
\usepackage{minted}
\usepackage[bookmarks=true]{hyperref}
\hypersetup{unicode = true}
\usetikzlibrary{arrows.meta,
                quotes}
\usepackage[english]{babel}
\setCJKmainfont{FandolSong-Regular.otf}[BoldFont=FandolHei-Regular.otf,ItalicFont=FandolFang-Regular.otf]
\setmonofont{Inconsolata}

\renewcommand{\theFancyVerbLine}{\ttfamily
\textcolor[rgb]{0.5,0.5,0.5}{\scriptsize
\oldstylenums{\arabic{FancyVerbLine}}}}

\usepackage{indentfirst}
\usepackage{amsmath}
\usepackage{geometry}
\geometry{left=2.5cm,right=2.5cm,top=2cm,bottom=2cm}

\setlength{\parindent}{2em}
\linespread{1.25}

\newcommand{\bfemph}[1]{\CJKunderdot{\textbf{#1}}}
\renewcommand{\emph}[1]{\bfemph{#1}}
\newcommand{\D}{\mathrm d}

\usepackage{fancyhdr}  % Header and Footer formatting
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\setlength{\headheight}{18pt}
\renewcommand{\sectionmark}[1]{\markright{#1}}
\renewcommand{\subsectionmark}[1]{\markright{#1}}

\lhead{“科大国创杯” 2021 年安徽省青少年信息学科普日活动}
\chead{}
\rhead{初中组题解}
\lfoot{\small 安徽 \, 合肥}
\cfoot{\small 第 \thepage\ 页  \hspace{2em} 共 \pageref*{LastPage} 页}
\rfoot{2021.4.10}

\begin{document}

\begin{center}
  \textbf{\huge “科大国创杯” \\ 2021 年安徽省青少年信息学科普日活动}\\
    {\LARGE \textit{初中组题解}\\\vspace{1em}}
    {\Large 比赛时间：2021 年 4 月 10 日 14:00–18:00}
  \end{center}
% \author{rushcheyo}
% \date{}
% \maketitle

\section{超市购物（shopping）}

直接模拟即可，可参见标程。

\section{坑（hole）}

设 $l_i,r_i$ 是第 $i$ 只跳蚤到左边/右边最近坑的距离，没坑则为 $+\infty$。

假设我们的操作向左最多移动 $L$ 步，向右最多移动 $R$ 步，那么该操作方案能杀死所有跳蚤的充要条件是对所有 $i$，要么 $L \ge l_i$ 或 $R \ge r_i$。同时，用 $L$ 个左和 $L+R$ 个右或 $R$ 个右和 $L+R$ 个左可以构造出一种操作方案。所以我们只需要在 $l_i$ 和 $0$ 中枚举 $L$，$r_i$ 和 $0$ 中枚举 $R$，判断合法并用 $\min(L,R)+L+R$ 更新答案即可。

进一步的，我们将跳蚤按 $l_i$ 排序，枚举 $L=l_j$，那么 $R$ 显然是 $r_{j+1},r_{j+2},\ldots,r_n$ 中的最大值，预处理即可。复杂度 $O(n \log n)$。

\section{收衣服（sort）}

考虑 DP。注意到第 $i-1$ 轮结束后，$[1,i-1]$ 位置上恰好是 $[1,i-1]$ 号衣服。于是我们设 $f_i$ 表示，第 $i$ 轮开始，$[i,n]$ 中取遍 $i,i+1,\ldots,n$ 的 $(n-i+1)!$ 种排列时的排序代价。

我们考虑枚举 $i$ 号衣服的位置为 $j$，那么需要付出 $w_{i,j}$ 的代价翻转 $[i,j]$。

那么从 $i+1$ 轮往后的代价是多少呢？其实就是 $f_{i+1}$。这是因为，考虑所有 $i,i+1,\ldots,n$ 的排列组成的集合，将其中每个元素翻转 $[i,j]$ 后集合并不变。

于是有 $f_i=\sum_{j=i}^n (w_{i,j}(n-i)!+f_{i+1})$。复杂度 $O(n^2)$。

\section{地铁（subway）}

设 $d_i$ 表示 $1$ 号车站到 $i$ 的顺时针距离，$x$ 表示整条地铁的总长度，那么一组 $\{d_i,x\}$ 合法的充要条件如下：

\begin{enumerate}
  \item $d_1=0$, $d_i,x$ 为正整数，且 $\forall 1 \le i < n,d_{i}-d_{i+1} \le -1,d_n \le x-1$；
  \item 对每个 1 类信息，若 $S_i < T_i$，$d_{S_i}-d_{T_i} \le -L_i$，否则 $d_{S_i}-d_{T_i} \le x-L_i$；
  \item 对每个 2 类信息，若 $S_i < T_i$，$d_{T_i}-d_{S_i} \le L_i$，否则 $d_{T_i}-d_{S_i} \le L_i-x$。
\end{enumerate}

根据差分约束理论，若 $x$ 给定，将所有变量当做点，一条 $a-b \le c$ 限制对应一条 $b \to a$ 边权为 $c$ 的单向边，则存在合法方案的充要条件是该图不存在负环。

那么图中的每个环都给出了一个关于 $x$ 的一次不等式，这说明 $x$ 的取值范围一定是个区间。

于是，我们可以分别求出 $x$ 的最大值和最小值，下面介绍怎么求 $x$ 的最大值。我们二分 $x_0$，将 $x=x_0$ 带入判断负环，如果不存在负环那合法，$x$ 的上界只会更大；如果存在负环，考虑任取一个负环，令 $k$ 表示其边权和前 $x$ 的系数。

\begin{itemize}
  \item $k=0$，那么显然无解；
  \item $k>0$，此时减小 $x$ 这个环只会负的更多，那么 $x$ 的上界比 $x_0$ 大；
  \item $k<0$，此时增大 $x$ 这个环只会负的更多，那么 $x$ 的上界比 $x_0$ 小。
\end{itemize}

这样我们可以二分出唯一可能的下界和上界 $l,r$，那么如果 $1 \le l \le r$ 且 $x=l,r$ 均合法答案便为 $r-l+1$，否则为 $0$（本题不可能），如果上界过大答案为 \texttt{-1}。判断负环用 Bellman–Ford 算法，点数 $O(n)$，边数 $O(n+m)$，总复杂度 $O(n(n+m) \log V)$，其中 $V$ 是值域。

\end{document}