杂项练习笔记3
两个数组大小(字典序比较)
描述:
我们称序列 比序列 “小”,如果存在 满足 对所有 成立,且 。
核心规则是:
- 从第一个元素开始逐项比较两个序列的对应位置;
- 若在第 k 个位置首次出现 ,则通过 ak 和 bk 的大小关系直接判定整个序列的大小(ak<bk 时序列 {ai} 更小);
- 若所有对应位置均相等,则较短的序列视为更小(但题目中隐含比较的序列长度相同)。
代码实例:
//通过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最大连号数问题
题目描述见最大连号数问题,在二分章节,我们介绍了一种的解法,现在我们介绍一种的解法
- 要使最大的连号数最小,我们将尽量均分每个连号数
- 当我们将个人分成尽可能多的段时,每段之间的空房间可以有效减少最大连号数。最多可以分割的段数为,因为每段之间至少需要一个空房间
- 则最大连号数为
- 代码表示则为
ans = n/(n - k + 1)
数论(平方差)
- 给定一个数 ,对任意正整数 若 ,则
扩展 费马定理
- 给定一个数 ,存在正整数 使 , 的存在定理:
- 若的所有质因数分解的为如果有其中元素 且该元素的指数幂次为偶数,则证明该数可以被平方和构造
- 使用下面代码,能帮助我们在 时间复杂度下检查某一个数是不是平方和数
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平方数之差
一个数能表示为两个平方数之差,当且仅当 ,也就是说只有形式如 的数不能被表示
如何快速找到呢?
对于奇数,直接有
对于 有:
方法(方差与二分)
对一组数据我们对其方差有:
对于一组数据我们快速计算其方差就可以用前缀和的方式提前算好和
数论的最高位为k时n的取值
当n满足下述方程时成立,方程表现形式如下
其中表示取x小数部分,表示对该数向下取整
:
推论1 :对一般整数,其最高位表示为
:
对两边同时取10的对数:
其中 为整数部分, 为小数部分
则可以被分解为
显然 , 且为一个10的次幂整数,而且我们不难得出
所以即为最高位的数字
推论1得证
则我们可以得到
拆去取底有
\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 提及笔记反向链接0
暂无其他笔记引用本篇
提及笔记1
局部关系图谱
悬停高亮 · 点击跳转