「琐记」NOIP 2020 考前

📅 Last Updated: 2020-11-30
📊 Word Count: 338
⏱️ Estimated Reading Time: 2 minutes
📄 PDF 📝 Source

NOIP 考前听到的一些算法，如果 NOIP 失利，这些算法可能这辈子也学不到了……算是留下一点点纪念吧…

分治乘法

(A×10base+B)×(C×10base+D)(A \times 10^{base} + B) \times (C \times 10^{base} + D)

= $ A C ^{base + base} + (AD + BC) ^{base} + BD$

= $ A C ^{base + base} + ((A + B)(C + D) - (AC + BD)) ^{base} + BD$

复杂度为 T(n)=3×T(n2)+O(n)=O(nlog⁡23)≈O(n1.58)\mathcal{T}(n) = 3 \times \mathcal{T}(\frac{n}{2}) + \mathcal{O}(n) = \mathcal{O}(n^{\log_2{3}}) \approx \mathcal{O}(n^{1.58})

分数规划例题

给出一张无向图，每个边两种权值 (a,b)(a, b) ，定义一棵树的权值为

∑i∈Tai∑i∈Tbi\frac{\sum_{i \in T}\limits{a_i}}{\sum_{i \in T}\limits{b_i}}

求最大权值。

二分答案是什么，设二分的值为 LL。

∑i∈Tai∑i∈Tbi≥L\frac{\sum_{i \in T}\limits{a_i}}{\sum_{i \in T}\limits{b_i}} \ge L

∑i∈Tai≥L×∑i∈Tbi\sum_{i \in T}\limits{a_i} \ge L \times \sum_{i \in T}\limits{b_i}

∑i∈T(L×bi−ai)≤0\sum_{i \in T}\limits{(L \times b_i - a_i)} \le 0

将权值赋值为 L×bi−aiL \times b_i - a_i 求最小生成树是否小于 00，即可。

[国家集训队]阿狸和桃子的游戏

https://www.luogu.com.cn/problem/P4643

《一道防AK的好题》 and 《卡常数》

强制在线，数据加密对解题有帮助

CDQ 分治例题

COGS 577 蝗灾

组合数取模

  • 递推一行 / 一列 考虑展开组合数通项公式，线性递推一行 / 一列
  • 预处理阶乘，阶乘逆。
  • Lucas 定理
  • 计算 n!n! 中素数 pp 的次数 : calc(n) = n / p + calc(n / p)
  • 非素数 CRT 合并。

第 k 小子集和

给出一个大小为 nn 的集合，定义子集权值为子集元素之和，求第 kk 小子集和。 n≤30n \le 30，k<2nk < 2^{n} meet in the middle。暴力求出两边 2152^{15} 个值，双指针合并。

BZOJ ISN

给出长度为 nn 的序列 AA ，如果 AA 不是递增序列，需要删除一些数字，直到为递增序列，问方案数 9824435398244353。 动态规划 + 树状数组 + 容斥原理

Pilling Up

NULL.

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 4ff5c12edd16eac168168696f0a472e98bb14f89cbe8197bdd9936ff0ccf6df9
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_「琐记」NOIP-2020-考前.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「琐记」NOIP-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.../769bdab95b.pdf.md', '-o', 'cache/769bdab95b.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] Not rendering RawBlock (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={「琐记」NOIP 2020 考前},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「琐记」NOIP 2020 考前}
  \author{Jiayi Su (ShuYuMo)}
  \date{2020-11-30 21:01:04}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  NOIP 考前听到的一些算法，如果 NOIP
  失利，这些算法可能这辈子也学不到了……算是留下一点点纪念吧…
  
  \subsection{分治乘法}\label{ux5206ux6cbbux4e58ux6cd5}
  
  \((A \times 10^{base} + B) \times (C \times 10^{base} + D)\)
  
  = \$ A C \times 10\^{}\{base + base\} + (AD + BC) \times 10\^{}\{base\}
  + BD\$
  
  = \$ A C \times 10\^{}\{base + base\} + ((A + B)(C + D) - (AC + BD))
  \times 10\^{}\{base\} + BD\$
  
  复杂度为
  \(\mathcal{T}(n) =  3 \times \mathcal{T}(\frac{n}{2}) + \mathcal{O}(n) = \mathcal{O}(n^{\log_2{3}}) \approx \mathcal{O}(n^{1.58})\)
  
  \subsection{分数规划例题}\label{ux5206ux6570ux89c4ux5212ux4f8bux9898}
  
  给出一张无向图，每个边两种权值 \((a, b)\) ，定义一棵树的权值为
  
  \[\frac{\sum_{i \in T}\limits{a_i}}{\sum_{i \in T}\limits{b_i}}\]
  
  求最大权值。
  
  二分答案是什么，设二分的值为 \(L\)。
  
  \(\frac{\sum_{i \in T}\limits{a_i}}{\sum_{i \in T}\limits{b_i}} \ge L\)
  
  \(\sum_{i \in T}\limits{a_i} \ge L \times \sum_{i \in T}\limits{b_i}\)
  
  \(\sum_{i \in T}\limits{(L \times b_i - a_i)} \le 0\)
  
  将权值赋值为 \(L \times b_i - a_i\) 求最小生成树是否小于 \(0\)，即可。
  
  \subsection{{[}国家集训队{]}阿狸和桃子的游戏}\label{ux56fdux5bb6ux96c6ux8badux961fux963fux72f8ux548cux6843ux5b50ux7684ux6e38ux620f}
  
  https://www.luogu.com.cn/problem/P4643
  
  \subsection{《一道防AK的好题》 and
  《卡常数》}\label{ux4e00ux9053ux9632akux7684ux597dux9898-and-ux5361ux5e38ux6570}
  
  强制在线，数据加密对解题有帮助
  
  \subsection{CDQ 分治例题}\label{cdq-ux5206ux6cbbux4f8bux9898}
  
  COGS 577 蝗灾
  
  \subsection{组合数取模}\label{ux7ec4ux5408ux6570ux53d6ux6a21}
  
  \begin{itemize}
  \tightlist
  \item
    递推一行 / 一列 考虑展开组合数通项公式，线性递推一行 / 一列
  \item
    预处理阶乘，阶乘逆。
  \item
    Lucas 定理
  \item
    计算 \(n!\) 中素数 \(p\) 的次数 :
    \texttt{calc(n)\ =\ n\ /\ p\ +\ calc(n\ /\ p)}
  \item
    非素数 \texttt{CRT} 合并。
  \end{itemize}
  
  \subsection{第 k 小子集和}\label{ux7b2c-k-ux5c0fux5b50ux96c6ux548c}
  
  给出一个大小为 \(n\) 的集合，定义子集权值为子集元素之和，求第 \(k\)
  小子集和。 \(n \le 30\)，\(k < 2^{n}\)
  \texttt{meet\ in\ the\ middle}。暴力求出两边 \(2^{15}\)
  个值，双指针合并。
  
  \subsection{BZOJ ISN}\label{bzoj-isn}
  
  给出长度为 \(n\) 的序列 \(A\) ，如果 \(A\)
  不是递增序列，需要删除一些数字，直到为递增序列，问方案数 \(98244353\)。
  动态规划 + 树状数组 + 容斥原理
  
  \subsection{Pilling Up}\label{pilling-up}
  
  NULL.
  
  \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)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 79.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [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)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 79.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  [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.