杂项练习笔记3

杂项练习

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

描述：
我们称序列 $\{a_1,\cdots ,a_n\}$ 比序列 $\{b_1,\cdots ,b_n\}$ “小”，如果存在$1\le k\le n$ 满足 $a_i=b_i$​ 对所有 $i<k$ 成立，且 $a_k<b_k$​。
核心规则是：

1. 从第一个元素开始逐项比较两个序列的对应位置；
2. 若在第 k 个位置首次出现 $a_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();
}

最大连号数问题

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

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

Tip

• ceil在很高精度下会有精度丢失，我们用整数除法代替取整函数
• $\lceil \frac{a}{b}\rceil =\lfloor \frac{a+b-1}{b}\rfloor$
  即ceil((a*1.0)/b) == (a+b-1)/b

数论(平方差)

• 给定一个数 $k$ ,对任意正整数 $y,x(y\ge x)$ 若 $k\mathrm{mod}4=2$,则$k\ne y^2-x^2$

扩展 费马定理

• 给定一个数 $k$ ,存在正整数 $p,q$ 使 $k=q^2+p^2$ ,$k$ 的存在定理：
  • 若$k$的所有质因数分解的为$A$ 如果有其中元素 $a_i\mathrm{mod}4=3$ 且该元素的指数幂次为偶数，则证明该数可以被平方和构造
• 使用下面代码，能帮助我们在 $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;
}

方法(方差与二分)

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

$$D(x)=E(x^2)-E^2(x)$$

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

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

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

$$\lfloor \{n\cdot {\log }_{10}2\}-{\log }_{10}k\rfloor =0$$

其中$\{x\}$表示取x小数部分,$\lfloor x\rfloor$表示对该数向下取整
$Poof$：

推论1 ：对一般整数$p=k^n$，其最高位表示为$\lfloor 10^{\{n{\log }_{10}k\}}\rfloor$
$Poo{f}_1$:
对$p=k^n$两边同时取10的对数:

$${\log }_{10}p=n{\log }_{10}k=m+f$$

其中 $m=\lfloor n{\log }_{10}k\rfloor$ 为整数部分，$f=n{\log }_{10}k\in [0,1)$ 为小数部分
则$p=k^n$可以被分解为

$$p=k^{m+f}=k^m\cdot k^f$$

显然 $f=\{n{\log }_{10}k\}$, 且$k^m$为一个10的次幂整数，而且我们不难得出$k^f\in [0,10)$
所以$\lfloor k^f\rfloor$即为最高位的数字
推论1得证
则我们可以得到 $2^n=\lfloor 10^{\{n{\log }_{10}2\}}\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}

二分 + 前缀和