PYYZ 摸底测 Day2 总结
link
T1 数学题
Problem
给 nnn，有 abc=nabc=nabc=n，其中 a,b,ca,b,ca,b,c 均为质数且有 a≤b≤ca\leq b\leq ca≤b≤c，求 bbb。
100%→10≤n≤1014100\% \rightarrow 10\leq n\leq 10^{14}100%→10≤n≤1014
1s/128MB1\text{s}/128\text{MB}1s/128MB
Solution
分解质因数即可，注意一下同一个因数出现两次以上的情况。
时间复杂度 O(n)\mathcal{O}(\sqrt n)O(n)。
Summary
100pts100\text{pts}100pts
T2 子序列
Problem
给出一个长度为 nnn 的序列 aia_iai，找出一个子序列使得其和对 mmm 取模后的值最大，输出这个值。
100pts→1≤n≤35,1≤m,ai≤109100\text{pts}\rightarrow 1\leq n\leq 35,1\leq m,a_i\leq 10^9100pts→1≤n≤35,1≤m,ai≤109
1s/ ...
PYYZ 摸底测 Day1 总结
link
T1 三值的排序
Problem
给出一个长为 nnn 的、仅含 1,2,31,2,31,2,3 的序列 aia_iai，求排序所需的最小交换次数（不要求相邻）。
100%→n≤1000100\% \rightarrow n\leq 1000100%→n≤1000
1s/128MB1\text{s}/128\text{MB}1s/128MB
Solution
提前预处理每个数值有几个，然后扫一遍所有 111 应当在的位置：
如果扫到 111，不管。
如果扫到 222，扫 222 应当在的位置。
如果扫到了，交换，答案 +1+1+1。
如果没扫到，扫在 333 应当在的位置，交换，答案 +1+1+1。
如果扫到 333，类似于 222。
然后扫一遍 222 应当在的位置，操作类似于 111。
时间复杂度 O(n2)\mathcal{O}(n^2)O(n2)。
Summary
出现了经典的复制下来然后后面忘了改后面的情况，100pts→90pts100\text{pts}\rightarrow 90\text{pts}100pts→90pts。
T2 日记
...
基础数论复习概览
同步于 博客园 和 洛谷博客。
由于各网站之间 LaTeX\LaTeXLATEX 及 Markdown 渲染方式的差异，故不保证除博客园外的排版完好，对于排版有明显不正确的地方请以博客园为主。
质数 约数 同余 组合
见初等数论及组合数学入门复习概览。
矩阵乘法
前置知识：
矩阵：在 OI 中，一个 n×mn\times mn×m 的矩阵可视为一个 n×mn\times mn×m 的二维数组，其数学本质为一个向量，对于一个 n×mn\times mn×m 的矩阵 AAA，表示为：
A=[a1,1a1,2⋯a1,ma2,1a2,2⋯a2,m⋮⋮⋱⋮an,1an,2⋯an,m]A = \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots ...
初等数论及组合数学入门复习概览
同步于 博客园 和 洛谷博客。
由于各网站之间 LaTeX\LaTeXLATEX 及 Markdown 渲染方式的差异，故不保证除博客园外的排版完好，对于排版有明显不正确的地方请以博客园为主。
质数
定义：无法被任何除了 111 及其本身的自然数整除的数。
性质：
[1,n][1,n][1,n] 内大约有 nlnn\frac{n}{\ln n}lnnn 个质数，即每 lnn\ln nlnn 个数就大约有一个质数。
判断质数
试除法：
时间复杂度 O(n)\mathcal{O}(\sqrt{n})O(n)。
1234567bool isPrime(int n){ if (n<2) return 0; int k=sqrt(n); F(i,2,k) if (!(n%i)) return 0; return 1;}
质数筛
埃氏筛：
对于每个整数，显然其倍数都不是质数。
扫描所有数，每扫到一个没被标记的数，该数即为质数，随后标记该数的倍数为约数。
同时，对于当前的质数 xxx，因为小于 x2x^2x2 的 ...