1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
| \documentclass[fontset=windows,12pt,a4paper,UTF8]{ctexart}
\usepackage{fancyhdr}
\usepackage{fontspec}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[colorlinks]{hyperref}
\usepackage{listings}
\usepackage{makecell}
\usepackage{multirow}
\usepackage{tabularx}
\geometry{left=2.54cm,right=2.54cm,top=2.54cm,bottom=2.54cm}
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\providecommand{\sub}[1]{
$ $ \\
\fontsize{13pt}{24pt}\selectfont\textbf{【#1】}
\normalsize
\phantomsection
\addcontentsline{toc}{subsection}{#1}$ $\vspace*{12pt}\par
}
\providecommand{\bfzh}[1]{\CJKunderdot{\textbf{#1}}}
\providecommand{\bfcd}[1]{\emph{\textbf{#1}}}
\providecommand{\problem}[2]{
\newpage
\pagestyle{fancy}
\lhead{\footnotesize\CName} \rhead{\footnotesize \TestName \ #1（#2）}
\cfoot{\footnotesize 第 \thepage 页 \qquad 共 \tpage \color{black} 页}
\phantomsection
\addcontentsline{toc}{section}{#1（#2）}
\begin{center}
\fontsize{18pt}{24pt}
\selectfont\textbf{#1}（#2）
\end{center}
\normalsize
}
\lstset{
basicstyle={\color{black}\fontspec{Consolas}},
numberstyle={\footnotesize\color[RGB]{128,128,128}\fontspec{Consolas}},
keywordstyle={\color{blue}\fontspec{Consolas}},
rulecolor=\color{blue},
numbers=left,
frame=single,
}
\setmonofont{Consolas}
\def\CName{Name}
\def\TestName{第一试}
\def\CAName{A}
\def\AName{a}
\def\CBName{Boy}
\def\BName{boy}
\def\CEName{Third}
\def\EName{third}
\def\tpage{\color{blue}{5} }
\begin{document}
\pagestyle{fancy}
\lhead{\footnotesize \CName} \rhead{\footnotesize\TestName}
\cfoot{\footnotesize 第 \thepage 页 \qquad 共 \color{blue}\tpage \color{black} 页}
\thispagestyle{empty}
\begin{center}
\fontsize{22pt}{24pt}\selectfont\textbf{\CName}\vspace{9pt}
\fontsize{24pt}{24pt}\selectfont CCF NOI 2021\vspace{6pt}
\fontsize{22pt}{24pt}\selectfont\textit{\TestName}\vspace{6pt}
\fontsize{15pt}{24pt}\selectfont\textbf{时间：}2021 \textbf{年} 1 \textbf{月} 1 \textbf{日} 08:00 $\sim$ 13:00\vspace{12pt}
\normalsize
\begin{tabularx}{\textwidth}{|X|X|X|X|}
\hline
题目名称 & \CAName & \CBName & \CEName \\
\hline
题目类型 & 交互型 & 通信型 & 传统型 \\
\hline
目录 & \texttt{\AName} & \texttt{\BName} & \texttt{\EName} \\
\hline
可执行文件名 & \texttt{\AName} & \texttt{\BName} & \texttt{\EName} \\
\hline
输入文件名 & \texttt{\AName.in} & \texttt{\BName.in} & \texttt{\EName.in} \\
\hline
输出文件名 & \texttt{\AName.out} & \texttt{\BName.out} & \texttt{\EName.out} \\
\hline
每个测试点时限 & 1.0 秒 & 1.0 秒 & 1.0 秒 \\
\hline
内存限制 & 256 MB & 256 MB & 512 MB \\
\hline
子任务数目 & 10 & 20 & 25 \\
\hline
测试点是否等分 & 是 & 是 & 是 \\
\hline
\end{tabularx}
\end{center}
提交源程序文件名
\begin{center}
\begin{tabularx}{\textwidth}{|X|X|X|X|}
\hline
对于 C++ 语言 & \texttt{\AName.cpp} & \texttt{\BName.cpp} &\texttt{\EName.cpp} \\
\hline
\end{tabularx}
\end{center}
编译选项
\begin{center}
\newcolumntype{Y}{>{\centering\arraybackslash}X}
\begin{tabularx}{\textwidth}{|>{\setlength{\hsize}{.471\hsize}}X|>{\setlength{\hsize}{1.529\hsize}}Y|}
\hline
对于 C++ 语言 & \texttt{-O2} \\
\hline
\end{tabularx}
\end{center}
$ $ \\
\fontsize{13pt}{24pt}\selectfont\textbf{【注意事项（请仔细阅读）】}
\normalsize
\phantomsection
\addcontentsline{toc}{subsection}{注意事项（请仔细阅读）}
\begin{enumerate}
\tightlist
\item 选手提交的源程序必须存放在\bfzh{已建立}好的，且\bfzh{带有样例文件和下发文件}的文件夹中，文件夹名称与对应试题英文名一致。
\item 文件名（包括程序名和输入输出文件名）必须使用英文小写。
\item C++ 中函数 main() 的返回值类型必须是 int，值必须为 0。
\item \bfzh{对于因未遵守以上规则对成绩造成的影响，相关申诉不予受理}。
\item 若无特殊说明，结果比较方式为\bfzh{忽略行末空格、文末回车后的全文比较}。
\item 程序可使用的栈空间大小与该题内存空间限制一致。
\item 在终端中执行命令 \texttt{ulimit -s unlimited} 可将当前终端下的栈空间限制放大，但你使用的栈空间大小不应超过题目限制。
\item 每道题目所提交的\bfzh{代码文件大小限制为 100KB}。
\item 若无特殊说明，输入文件与输出文件中同一行的相邻整数均使用一个空格分隔。
\item 输入文件中可能存在行末空格，请选手使用更完善的读入方式（例如 scanf 函数）避免出错。
\item 直接复制 PDF 题面中的多行样例，数据将带有行号，建议选手直接使用对应目录下的样例文件进行测试。
\item 使用 std::deque 等 STL 容器时，请注意其内存空间消耗。
\item 请务必使用题面中规定的的编译参数，保证你的程序在本机能够通过编译。此外\bfzh{不允许在程序中手动开启其他编译选项}，一经发现，本题成绩以 0 分处理。
\end{enumerate}
\problem{\CAName}{\AName}
\bfzh{这是一道交互题。}
\problem{\CBName}{\BName}
\bfzh{这是一道通信题。}
\problem{\CEName}{\EName}
\sub{题目描述}
Test
\sub{输入格式}
从文件 \bfcd{\EName.in} 中读入数据。
\sub{输出格式}
输出到文件 \bfcd{\EName.out} 中。
\sub{样例 1 输入}
\begin{lstlisting}
7 4
1 2 1
1 3 2
3 4 3
3 5 4
3 6 5
6 7 6
3 2 7 1
5 2 4 7 3 6
2 2 4
1 7
\end{lstlisting}
\sub{样例 1 输出}
\begin{lstlisting}
16
22
6
0
\end{lstlisting}
\sub{样例 1 解释}
Test
\sub{样例 2}
见选手目录下的 \bfcd{\EName/\EName2.in} 与 \bfcd{\EName/\EName2.ans}。
该样例约束与测试点2 $\sim$ 5 一致。
\sub{样例 3}
见选手目录下的 \emph{\textbf{\EName/\EName3.in}} 与 \emph{\textbf{\EName/\EName3.ans}}。
该样例约束与测试点8 $\sim$ 10 一致。
\sub{样例 4}
见选手目录下的 \bfcd{\EName/\EName4.in} 与 \bfcd{\EName/\EName4.ans}。
该样例约束与测试点11 $\sim$ 13 一致。
\sub{样例 5}
见选手目录下的 \bfcd{\EName/\EName5.in} 与 \bfcd{\EName/\EName5.ans}。
该样例约束与测试点17 $\sim$ 20 一致。
\sub{数据范围}
本题共 $25$ 个测试点，每个测试点 $4$ 分。每个测试点的数据规模和相关限制见下表。
\begin{center}
\begin{tabular}{ @{}c|c|c|c|c|c@{} }
\Xhline{2pt}
测试点 & $n$ & $m$ & $k_i$ & $\sum k_i$ & 特殊性质\\
\Xhline{1.2pt}
$1$ & $\le 5$ & $\le 5$ & \multirow{2}{*}{$\le n$} & $\le 20$ & \multirow{3}{*}{无}\\
\cline{1-3}\cline{5-5}
$2\sim 5$ & $\le 10^3$ & $\le 10^3$ & & $\le 5\times 10^3$&\\
\cline{1-5}
$6\sim 7$ & $=999996$ & \multirow{3}{*}{$\le 10^5$} & $=2$ & $\le 2\times 10^5$&\\
\cline{1-2}\cline{4-6}
$8\sim 10$ & $=999997$ & & \multirow{5}{*}{$\le n$} & \multirow{3}{*}{$\le 5\times 10^5$}&A\\
\cline{1-2}\cline{6-6}
$11\sim 13$ & $=999998$ & & & &B\\
\cline{1-3}\cline{6-6}
$14\sim 16$ & $=999999$ & $\le 10$ & & &\multirow{3}{*}{无}\\
\cline{1-3}\cline{5-5}
$17\sim 20$& $\le 2\times 10^5$ & $\le 10^5$ & & $\le 10^6$ &\\
\cline{1-3}\cline{5-5}
$21\sim 25$& $\le 10^6$ & $\le 10^6$ & & $\le 5\times 10^6$ &\\
\Xhline{2pt}
\end{tabular}
\end{center}
对于所有数据，保证 $1\le m,n \le 10^6$，$1\le k_i,u_i,v_i,p_i\le n$，$1\le \sum k_i \le 5\times 10^6$，$0 \le w \le 10^9$。保证图连通，且不存在重边和自环。
表中特殊性质栏中变量的含义如下：
\begin{itemize}
\tightlist
\item A: $\forall i \in [1,n),u_i=i,v_i=i+1$。
\item B: $\forall i \in [1,n],u_i=1$。
\end{itemize}
\end{document}
|