CSP 2020 联赛
退役有感。 # 比赛经历 ## A
开场看到题目就知道这道题可能会浪费我很长时间,但是这是第一题,如果简单题没有做出来,排名肯定不理想了。
主要是不知道后面题目的难度,而且这道题显然是一道不需要动脑子的题目,所以树立了无论如何都要把这道题拿满分的观念。(也许是对的,但是可能结果不尽人意)
首先这道题一定是一个模拟题,放在第一题的位置,而且题目流程相对复杂,没有考虑时间复杂度上的问题,感觉是模拟整个过程就完全可以通过,就直接上手开始写的。
一开始没有完整的思路,就是想到哪里写道哪里,没有仔细思考怎么做比较好写,浪费了很多时间。一直没有注意部分分,写起来比较迷茫。大约到了
1
小时左右注意到了部分分,发现如果
O(n)
预处理 +
O(1)
询问。就有
80pts
这一部分大概只需要
5
分钟就可以写完,然后注释掉之前写的垃圾,5
分钟写完了
O(n)
做法。还是没看后面的题目,坚持着第一题必须拿满分的信念,继续做剩下的
20pts。剩下的
20pts
询问在 的数量级在
109
左右。逐年眺的话大概每次需要
⌊365109⌋=2739626
次运算
不是很确定能不能通过。然后发现这个年份显然可以二分,然后预处理的部分已经包含了所有特殊情况,对闰年的判断条件容斥了一下感觉可以做到
O(1)
check,虽然预处理了,但是细节仍然很多,处理了很久,终于在大概在开始
2h
的时间里通过了大样例。但是没有对拍,因为线性预处理不可能过,而且样例已经包含了所有的情况。主要是时间已经很不够用了,后面还有三道题,时间剩下不到
2h
,基本上已经确定要退役了。直接放弃听天人命了。
后来想了一下,题目要求
105
询问,询问数量级为
109。我这个做法好像能做到
106
询问,单次询问数量级
1018。所以我在考场上写二分是在炫技吗……最后检查了几个特使情况,自己觉得挺稳的,中间该开
long long
的地方都已经开过了,后来发现数据里面的读入数据就已经超过
int
了。还是丢了10pts。
B
冷静了
10min
,确定了虽然已经完蛋但是还要好好打的想法。开始飞速读题,读了一遍感觉这直接做就可以了吧……以为是读错题了,然后又读了一遍,感觉确实是一个大水题啊……
开始写代码,这时候已经很紧张了,写错很多次,感觉这种状态写出来的东西会出问题,但是顾不了那么多了。大概
7min
写完了,调试了一下样例用了
5min
左右。然后通过了最大的样例。还剩下大概
1h
多一点的时间,剩下两道最难题目,仍然很迷茫,但是感觉已经
200pts
到手了。
光顾着写没注意这题的复杂度,我的实现很简陋,复杂度只能做到
O(nlogn)
,但是数据范围是
106
感觉应该能过,就没有继续优化。
后记:评测的时候,出题人卡满了
O(nlogn)
,根本过不去。而且最后需要特判答案是否溢出,根本没注意那里。最后输出的数字可能是
264
。计算机中无符号64位整形最大是
264−1。所以这个情况需要计算器算好
264
,然后当成字符串输出。然后我觉得太恶心了。
C
第一眼看题的时候,感觉这道题和正睿的一道题非常相似,(其实这道题的大概20pts的部分分可以直接用正睿的那个题的方法做),但是只有
50min
了,后来又去看了看
D
题,D题有20的分数n<4这一部分分应该很简单。权衡了一下决定好好写
C
题。C
题的部分分特别多(20pts
暴力 +
20pts正睿做法
+
10pts线段树模板
=
50pts
),然后赶紧开始写。后来呢,第一档分数,状态极差,完全没心情,特别紧张,写了
40min
才过了样例。最后只剩下
10min
了,监考老师都开始准备收拾东西了……我哭了……感觉这种状态下
10min
写双标记线段树有点扯。算了退役了……
最后检查了文件夹,一遍一遍测了样例和文件读写。还剩下5min想了想回去怎么好好学文化课……沮丧之极。难受的在于
还能拿到的但是没时间写的分数大概是50分左右,时间,时间,时间。唉……
后来发现其实这个
C
题挺思路很好想,这个题不能直接套用正睿的做法关键在于乘法和加法操作不能合并,如果展开操作,这个操作数量是O(n2)级别的,既然不能展开,那正解一定是考虑每单个操作的贡献,这些在考场上第一眼就能看出来的,但是由于很多原因都没有仔细想下去。感觉如果时间充足我能想出来。
其实也不能怨出题人题目排布有问题,其实是自己没好好权衡题目难度,紧张情况下没办法保证代码质量。之后问了冯友和,虽然他
C
题最后只剩下了
40min,但是他在比赛快结束的
40min
中写完了
5min写完了暴力,5min
写完了线段树,5min写完了拓扑排序,我一个暴力最后都快不知道我写的是啥了……还是要多加练习啊。
今后注意
- 还是应该仔细的阅读全部试题,就算第一题比较恶心人,也不会像这次比赛那样做第一题用时很长就感觉自己菜到无可救药。
- 最简单的题目也要注意部分分,能够给你实现上的简便提示。
- 不要紧张,写的时候好好调整心态,思考每一种可能的最坏情况,认真解决。
- 根本原因是不熟练,如果能保证代码写完就不出错,就不会出现什么时间不够用的情况。
- 代码方面:注意
long long
可以局部#define int long long
,#undef int
,保证不会溢出。注意最坏情况下程序可能的出错。在时间允许的情况下优化复杂度。
- 估分
260
实际
175
还是不要对自己的代码太有信心,忘开一个
long long
就送退役了……
- 之后还是要多做思维难度大的题,毕竟C题没有在40min里想出来QAQ。
🔗 Source Hash:
716b0005a24102dd262644c02673a0e6c4e198e73e9026c39f52294cfc19acfe
Build Logs
Build Log - Filtered
================================================
📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes
• All build status and error messages are kept intact
🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]
================================================
html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「比赛总结」「CSP-2020」退役有感.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「比赛总结」「CSP-2020」退役有感.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT:
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.
====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../0b5feb9114.pdf.md', '-o', 'cache/0b5feb9114.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT:
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawInline (Format "html") ""
[INFO] [makePDF] Temp dir:
.../[temp]
[INFO] [makePDF] Command line:
xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
("TEXINPUTS",".../[temp]
("TEXMFOUTPUT",".../[temp]
("SHELL","/bin/bash")
("PWD",".../[user]/projects/blog")
("HOME",".../[user]
("LANG","zh_CN.UTF-8")
("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\PassOptionsToPackage{space}{xeCJK}
\documentclass[
]{article}
\usepackage{xcolor}
\usepackage[a4paper,margin=2cm]{geometry}
\usepackage{amsmath,amssymb}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\usepackage{iftex}
\ifPDFTeX
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
\usepackage{unicode-math} % this also loads fontspec
\defaultfontfeatures{Scale=MatchLowercase}
\defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
\usepackage{lmodern}
\ifPDFTeX\else
% xetex/luatex font selection
\setmainfont[]{Latin Modern Roman}
\ifXeTeX
\usepackage{xeCJK}
\setCJKmainfont[]{AR PL UKai CN}
\fi
\ifLuaTeX
\usepackage[]{luatexja-fontspec}
\setmainjfont[]{AR PL UKai CN}
\fi
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{setspace}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
\KOMAoptions{parskip=half}}
\makeatother
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
% \usepackage{xeCJK}
% \setCJKmainfont{AR PL UKai CN}
% \usepackage{unicode-math}
\setmathfont{Latin Modern Math}
\usepackage{bookmark}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same}
\hypersetup{
pdftitle={「CSP 2020」退役有感},
pdfauthor={Jiayi Su (ShuYuMo)},
hidelinks,
pdfcreator={LaTeX via pandoc}}
\title{「CSP 2020」退役有感}
\author{Jiayi Su (ShuYuMo)}
\date{2020-11-11 21:42:33}
\begin{document}
\maketitle
\setstretch{1.3}
CSP 2020 联赛
退役有感。 \# 比赛经历 \#\# A
开场看到题目就知道这道题可能会浪费我很长时间,但是这是第一题,如果简单题没有做出来,排名肯定不理想了。
主要是不知道后面题目的难度,而且这道题显然是一道不需要动脑子的题目,所以树立了无论如何都要把这道题拿满分的观念。(也许是对的,但是可能结果不尽人意)
首先这道题一定是一个模拟题,放在第一题的位置,而且题目流程相对复杂,没有考虑时间复杂度上的问题,感觉是模拟整个过程就完全可以通过,就直接上手开始写的。
一开始没有完整的思路,就是想到哪里写道哪里,没有仔细思考怎么做比较好写,浪费了很多时间。一直没有注意部分分,写起来比较迷茫。大约到了
\(1\) 小时左右注意到了部分分,发现如果 \(\operatorname{O}(n)\) 预处理 +
\(\operatorname{O}(1)\) 询问。就有 \(80pts\) 这一部分大概只需要 \(5\)
分钟就可以写完,然后注释掉之前写的垃圾,\(5\) 分钟写完了
\(\operatorname{O}(n)\)
做法。还是没看后面的题目,坚持着第一题必须拿满分的信念,继续做剩下的
\(20pts\)。剩下的 \(20pts\) 询问在 的数量级在 \(10^9\)
左右。逐年眺的话大概每次需要
\(\lfloor \frac{10^9}{365} \rfloor = 2739626\) 次运算
不是很确定能不能通过。然后发现这个年份显然可以二分,然后预处理的部分已经包含了所有特殊情况,对闰年的判断条件容斥了一下感觉可以做到
\(O(1)\)
check,虽然预处理了,但是细节仍然很多,处理了很久,终于在大概在开始
\(2\)h
的时间里通过了大样例。但是没有对拍,因为线性预处理不可能过,而且样例已经包含了所有的情况。主要是时间已经很不够用了,后面还有三道题,时间剩下不到
\(2\)h ,基本上已经确定要退役了。直接放弃听天人命了。
后来想了一下,题目要求 \(10^5\) 询问,询问数量级为
\(10^9\)。我这个做法好像能做到 \(10^6\) 询问,单次询问数量级
\(10^{18}\)。所以我在考场上写二分是在炫技吗……最后检查了几个特使情况,自己觉得挺稳的,中间该开
\texttt{long\ long}
的地方都已经开过了,后来发现数据里面的读入数据就已经超过 \texttt{int}
了。还是丢了\(10pts\)。
\subsection{B}\label{b}
冷静了 \(10\)min
,确定了虽然已经完蛋但是还要好好打的想法。开始飞速读题,读了一遍感觉这直接做就可以了吧……以为是读错题了,然后又读了一遍,感觉确实是一个大水题啊……
开始写代码,这时候已经很紧张了,写错很多次,感觉这种状态写出来的东西会出问题,但是顾不了那么多了。大概
\(7\)min 写完了,调试了一下样例用了 \(5\)min
左右。然后通过了最大的样例。还剩下大概 \(1\)h
多一点的时间,剩下两道最难题目,仍然很迷茫,但是感觉已经 \(200pts\)
到手了。
光顾着写没注意这题的复杂度,我的实现很简陋,复杂度只能做到
\(O(n\operatorname{log}n)\) ,但是数据范围是 \(10^6\)
感觉应该能过,就没有继续优化。
后记:评测的时候,出题人卡满了 \(O(n\operatorname{log}n)\)
,根本过不去。而且最后需要特判答案是否溢出,根本没注意那里。最后输出的数字可能是
\(2^{64}\) 。计算机中无符号64位整形最大是
\(2^{64}-1\)。所以这个情况需要计算器算好 \(2^{64}\)
,然后当成字符串输出。然后我觉得太恶心了。
\subsection{C}\label{c}
第一眼看题的时候,感觉这道题和正睿的一道题非常相似,(其实这道题的大概\(20pts\)的部分分可以直接用正睿的那个题的方法做),但是只有
\(50\)min 了,后来又去看了看 \(D\) 题,\(D\)题有\(20%
\)的分数\(n < 4\)这一部分分应该很简单。权衡了一下决定好好写 \(C\)
题。\(C\) 题的部分分特别多(\(20pts\) 暴力 + \(20pts\)正睿做法 +
\(10pts\)线段树模板 = \(50pts\)
),然后赶紧开始写。后来呢,第一档分数,状态极差,完全没心情,特别紧张,写了
\(40\)min 才过了样例。最后只剩下 \(10\)min
了,监考老师都开始准备收拾东西了……我哭了……感觉这种状态下 \(10\)min
写双标记线段树有点扯。算了退役了……
最后检查了文件夹,一遍一遍测了样例和文件读写。还剩下\(5\)min想了想回去怎么好好学文化课……沮丧之极。难受的在于
还能拿到的但是没时间写的分数大概是\(50\)分左右,时间,时间,时间。唉……
后来发现其实这个 \(C\)
题挺思路很好想,这个题不能直接套用正睿的做法关键在于乘法和加法操作不能合并,如果展开操作,这个操作数量是\(O(n^2)\)级别的,既然不能展开,那正解一定是考虑每单个操作的贡献,这些在考场上第一眼就能看出来的,但是由于很多原因都没有仔细想下去。感觉如果时间充足我能想出来。
其实也不能怨出题人题目排布有问题,其实是自己没好好权衡题目难度,紧张情况下没办法保证代码质量。之后问了冯友和,虽然他
\(C\) 题最后只剩下了 \(40\)min,但是他在比赛快结束的 \(40\)min 中写完了
\(5\)min写完了暴力,\(5\)min
写完了线段树,\(5\)min写完了拓扑排序,我一个暴力最后都快不知道我写的是啥了……还是要多加练习啊。
\section{今后注意}\label{ux4ecaux540eux6ce8ux610f}
\begin{itemize}
\tightlist
\item
还是应该仔细的阅读全部试题,就算第一题比较恶心人,也不会像这次比赛那样做第一题用时很长就感觉自己菜到无可救药。
\item
最简单的题目也要注意部分分,能够给你实现上的简便提示。
\item
不要紧张,写的时候好好调整心态,思考每一种可能的最坏情况,认真解决。
\item
根本原因是不熟练,如果能保证代码写完就不出错,就不会出现什么时间不够用的情况。
\item
代码方面:注意\texttt{long\ long}可以局部\texttt{\#define\ int\ long\ long},\texttt{\#undef\ int},保证不会溢出。注意最坏情况下程序可能的出错。在时间允许的情况下优化复杂度。
\item
估分 \(260\) 实际 \(175\) 还是不要对自己的代码太有信心,忘开一个
\texttt{long\ long} 就送退役了……
\item
之后还是要多做思维难度大的题,毕竟\(C\)题没有在\(40\)min里想出来QAQ。
\end{itemize}
\end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
restricted \write18 enabled.
entering extended mode
(.../input.tex
LaTeX2e <2023-11-01> patch level 1
L3 programming layer <2024-01-22>
(.../article.cls
Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
(.../[system]
(.../xcolor.sty
(.../color.cfg)
(.../xetex.def)
(.../[system]
(.../geometry.sty
(.../keyval.sty)
(.../ifvtex.sty
(.../iftex.sty)))
(.../amsmath.sty
For additional information on amsmath, use the `?' option.
(.../amstext.sty
(.../amsgen.sty))
(.../amsbsy.sty)
(.../amsopn.sty))
(.../amssymb.sty
(.../amsfonts.sty))
(.../unicode-math.sty
(.../expl3.sty
(.../l3backend-xetex.def))
(.../unicode-math-xetex.sty
(.../xparse.sty)
(.../l3keys2e.sty)
(.../fontspec.sty
(.../fontspec-xetex.sty
(.../fontenc.sty)
(.../fontspec.cfg)))
(.../fix-cm.sty
(.../ts1enc.def))
(.../unicode-math-table.tex)))
(.../lmodern.sty)
(.../xeCJK.sty
(.../ctexhook.sty)
(.../xtemplate.sty)
(.../xeCJK.cfg))
(.../upquote.sty
(.../textcomp.sty))
(.../microtype.sty
(.../etoolbox.sty)
(.../microtype-xetex.def)
(.../microtype.cfg))
(.../setspace.sty)
(.../parskip.sty
(.../kvoptions.sty
(.../ltxcmds.sty)
(.../kvsetkeys.sty)))
(.../bookmark.sty
(.../hyperref.sty
(.../kvdefinekeys.sty)
(.../pdfescape.sty
(.../pdftexcmds.sty
(.../infwarerr.sty)))
(.../hycolor.sty)
(.../auxhook.sty)
(.../nameref.sty
(.../refcount.sty)
(.../gettitlestring.sty))
(.../pd1enc.def)
(.../intcalc.sty)
(.../puenc.def)
(.../url.sty)
(.../bitset.sty
(.../bigintcalc.sty))
(.../atbegshi-ltx.sty))
(.../hxetex.def
(.../stringenc.sty)
(.../rerunfilecheck.sty
(.../atveryend-ltx.sty)
(.../uniquecounter.sty)))
(.../bkm-dvipdfm.def))
(.../xurl.sty)
No file input.aux.
*geometry* driver: auto-detecting
*geometry* detected driver: xetex
(.../mt-LatinModernRoman.cfg)
Package hyperref Warning: Rerun to get /PageLabels entry.
(.../omllmm.fd)
(.../umsa.fd)
(.../mt-msa.cfg)
(.../umsb.fd)
(.../mt-msb.cfg)
Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
(xeCJK)
(xeCJK) Try to use `\setCJKmonofont[<...>]{<...>}' to define
(xeCJK) it.
[1]
LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
(Font) using `TU/ARPLUKaiCN(0)/m/n' instead on input line 150.
[2] (.../input.aux)
LaTeX Font Warning: Some font shapes were not available, defaults substituted.
LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
)
Output written on .../input.pdf (2 pages).
Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
Package hyperref Warning: Rerun to get /PageLabels entry.
LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
restricted \write18 enabled.
entering extended mode
(.../input.tex
LaTeX2e <2023-11-01> patch level 1
L3 programming layer <2024-01-22>
(.../article.cls
Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
(.../[system]
(.../xcolor.sty
(.../color.cfg)
(.../xetex.def)
(.../[system]
(.../geometry.sty
(.../keyval.sty)
(.../ifvtex.sty
(.../iftex.sty)))
(.../amsmath.sty
For additional information on amsmath, use the `?' option.
(.../amstext.sty
(.../amsgen.sty))
(.../amsbsy.sty)
(.../amsopn.sty))
(.../amssymb.sty
(.../amsfonts.sty))
(.../unicode-math.sty
(.../expl3.sty
(.../l3backend-xetex.def))
(.../unicode-math-xetex.sty
(.../xparse.sty)
(.../l3keys2e.sty)
(.../fontspec.sty
(.../fontspec-xetex.sty
(.../fontenc.sty)
(.../fontspec.cfg)))
(.../fix-cm.sty
(.../ts1enc.def))
(.../unicode-math-table.tex)))
(.../lmodern.sty)
(.../xeCJK.sty
(.../ctexhook.sty)
(.../xtemplate.sty)
(.../xeCJK.cfg))
(.../upquote.sty
(.../textcomp.sty))
(.../microtype.sty
(.../etoolbox.sty)
(.../microtype-xetex.def)
(.../microtype.cfg))
(.../setspace.sty)
(.../parskip.sty
(.../kvoptions.sty
(.../ltxcmds.sty)
(.../kvsetkeys.sty)))
(.../bookmark.sty
(.../hyperref.sty
(.../kvdefinekeys.sty)
(.../pdfescape.sty
(.../pdftexcmds.sty
(.../infwarerr.sty)))
(.../hycolor.sty)
(.../auxhook.sty)
(.../nameref.sty
(.../refcount.sty)
(.../gettitlestring.sty))
(.../pd1enc.def)
(.../intcalc.sty)
(.../puenc.def)
(.../url.sty)
(.../bitset.sty
(.../bigintcalc.sty))
(.../atbegshi-ltx.sty))
(.../hxetex.def
(.../stringenc.sty)
(.../rerunfilecheck.sty
(.../atveryend-ltx.sty)
(.../uniquecounter.sty)))
(.../bkm-dvipdfm.def))
(.../xurl.sty)
(.../input.aux)
*geometry* driver: auto-detecting
*geometry* detected driver: xetex
(.../mt-LatinModernRoman.cfg)
(.../omllmm.fd)
(.../umsa.fd)
(.../mt-msa.cfg)
(.../umsb.fd)
(.../mt-msb.cfg)
Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
(xeCJK)
(xeCJK) Try to use `\setCJKmonofont[<...>]{<...>}' to define
(xeCJK) it.
[1]
LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
(Font) using `TU/ARPLUKaiCN(0)/m/n' instead on input line 150.
[2] (.../input.aux)
LaTeX Font Warning: Some font shapes were not available, defaults substituted.
)
Output written on .../input.pdf (2 pages).
Transcript written on .../input.log.