imicola 杂项练习笔记3
杂项练习笔记3

杂项练习笔记3

1,135 字 · 约 3 分钟

两个数组大小(字典序比较)

描述:
我们称序列 {a1​,⋯,an​}\{ a_1​,⋯,a_n​ \} 比序列 {b1​,⋯,bn​}\{ b_1​,⋯,b_n​ \} “小”,如果存在1≤k≤n1\leq k \leq n 满足 ai=bia_i = b_i​ 对所有 i<ki<k 成立,且 ak​<bka_k​ < b_k​。
核心规则是:

  1. 从第一个元素开始逐项比较两个序列的对应位置;
  2. 若在第 k 个位置首次出现 ak≠bka_k \ne b_k​,则通过 ak​ 和 bk​ 的大小关系直接判定整个序列的大小(ak​<bk​ 时序列 {ai​} 更小);
  3. 若所有对应位置均相等,则较短的序列视为更小(但题目中隐含比较的序列长度相同)。

代码实例:

//通过cmp函数返回sort的cmp值
//排序的是较小数组放前方

bool cmp(vector<int> a , vector<int> b)
{
	for(int i = 0; i < min(a.size(),b.size()) ; i++){
		if(a[i] != b[i]) return a[i] < b[i];
	}
	return a.size() < b.size();
}
//返回的cmp参数会使sort函数由大到小排列

bool cmp_big(vector<int> a,vector<int> b)
{
	for(int i = 0; i < min(a.size(),b.size()) ; i++){
		if(a[i] != b[i]) return a[i] > b[i];
	}
	return a.size() > b.size();
}
cpp

最大连号数问题

题目描述见最大连号数问题,在二分章节,我们介绍了一种O(log⁡n)O(\log n)的解法,现在我们介绍一种O(1)O(1)的解法

  • 要使最大的连号数最小,我们将尽量均分每个连号数
  • 当我们将kk个人分成尽可能多的段时,每段之间的空房间可以有效减少最大连号数。最多可以分割的段数为m=n−k+1m = n - k + 1,因为每段之间至少需要一个空房间
  • 则最大连号数为 ⌈kn−k+1⌉\left \lceil \frac{k}{n-k+1} \right \rceil
  • 代码表示则为ans = n/(n - k + 1)

数论(平方差)

  • 给定一个数 kk ,对任意正整数 y , x(y≥x)y\,,\,x \quad (y \ge x) 若 kmod  4=2k\mod 4 = 2,则k≠y2−x2k \ne y^2 - x^2

扩展 费马定理

  • 给定一个数 kk ,存在正整数 p,qp , q 使 k=q2+p2k = q^2 + p^2 ,kk 的存在定理:
    • 若kk的所有质因数分解的为AA如果有其中元素 aimod  4=3a_i \mod 4 = 3 且该元素的指数幂次为偶数,则证明该数可以被平方和构造
  • 使用下面代码,能帮助我们在 O(n)O(\sqrt{n})时间复杂度下检查某一个数是不是平方和数
bool checkpowersum(int n)
{
	unordered_map<int,int> nprime;
	for(int i = 2 ; i <= n/i ;i++) {
		while(n % i == 0) {
			nprime[i]++;
			n /= i; 
		}
	}
	if(n > 1) {
		nprime[n]++;
	}
	for(auto &&[prime,num] : nprime){
		if(prime % 4 == 3 && num % 2 != 0){
			return 0;
		}
	}
	return 1;
}
cpp

平方数之差

一个数nn能表示为两个平方数之差,当且仅当 n≢2(mod4)n \not\equiv 2\pmod 4 ,也就是说只有形式如 n=4k+2n = 4k + 2 的数不能被表示

如何快速找到呢?

对于奇数,直接有 (n+12)2−(n−12)2=k\left(\frac{n + 1}{2}\right)^{2} - \left(\frac{n - 1}{2}\right)^{2} = k

对于n≡0(mod4)n \equiv 0 \pmod 4 有: (n4+1)2−(n4−1)2=k\left(\frac{n}{4} + 1\right)^{2} - \left(\frac{n}{4} - 1\right)^{2} = k

方法(方差与二分)

对一组数据我们对其方差有:

D(x)=E(x2)−E2(x)D(x) = E(x^2) -E^2(x)
对于一组数据我们快速计算其方差就可以用前缀和的方式提前算好E(x)E(x)和E(x2)E(x^2)

数论2n2^n的最高位为k时n的取值

当n满足下述方程时成立,方程表现形式如下

⌊{n⋅log⁡102}−log⁡10k⌋=0\left\lfloor \{n \cdot \log_{10} 2\} - \log_{10} k \right\rfloor = 0
其中{x}\{x\}表示取x小数部分,⌊x⌋\left\lfloor x \right\rfloor表示对该数向下取整
PoofPoof:

推论1 :对一般整数p=knp = k^n,其最高位表示为⌊10{nlog⁡10k}⌋\left\lfloor10^{\{n\log_{10}k\}}\right\rfloor
Poof1Poof_1:
对p=knp = k^n两边同时取10的对数:

log⁡10​p=nlog⁡10​k=m+f\log_{10}​p=n\log_{10}​k=m+f
其中 m=⌊nlog⁡10​k⌋m=⌊n\log_{10}​k⌋ 为整数部分,f=nlog⁡10​k∈[0,1)f={n\log_{10}​k}\in[0,1) 为小数部分
则p=knp = k^n可以被分解为
p=km+f=km ⋅ kfp = k^{m + f} = k^m \, \cdot \, k^f
显然 f={nlog⁡10k}f = \{n\log_{10}k\}, 且kmk^m为一个10的次幂整数,而且我们不难得出kf∈[0,10)k^f \in [0,10)
所以⌊kf⌋\lfloor k^f \rfloor即为最高位的数字
推论1得证
则我们可以得到 2n=⌊10{nlog⁡102}⌋2^n = \left\lfloor10^{\{n\log_{10}2\}}\right\rfloor
拆去取底有
\begin{split} \iff &k \leq 10^{\{n\log_{10}2\}} < k+1 \\ \iff &\log_{10}k \leq \{n\log_{10}2\} < \log_{10}{(k+1)} \\ \iff & 0 \leq {n\log_{10}2} - \log_{10}k < \log_{10}{(k+1)} - \log_{10}k \\ \iff &\left\lfloor \{n \cdot \log_{10} 2\} - \log_{10} k \right\rfloor = 0 \\ &&\mathcal{Q.E.D.} \end{split}

二分 + 前缀和

知识关联

0 反向链接 · 1 提及笔记
局部关系图谱 悬停高亮 · 点击跳转