集训二（递归递推）知识点-Seo优化-塔城地区网站建设公司

1.B2004

这道题主要考输出格式

常见考点：

保留指定小数位数
cout << fixed << setprecision(3) << x << endl;
数字按固定宽度输出，不足补前导零或空格
cout << setfill('0') << setw(4) << num << endl; // 输出 0012
cout << setfill(' ') << setw(4) << num << endl; // 输出 " 12"（右对齐）
cout << left << setw(4) << num << endl; // 输出 "12 "（左对齐）

setw 仅对下一个输出项有效，每次都需要设置。
setfill 和 left/right 是持久的。

以八进制、十六进制形式输出，可能要求带前缀（如 0x）或不带。
int a = 255;
cout << hex << a << endl; // 输出 ff
cout << showbase << hex << a << endl; // 输出 0xff
cout << uppercase << a << endl; // 输出 0XFF
cout << dec << a << endl; // 恢复十进制
科学计数法与定点小数
double x = 123.456;
cout << scientific << x << endl; // 输出 1.234560e+02
cout << fixed << x << endl; // 输出 123.456000

3.B2147

这题用到了第一题的setprecision，同时还用到了数学函数，这里补充一下关于setprecision的知识，同时回顾一下常见的数学函数吧

setprecision(n)

当setprcision(n)不与fixed / scientific连用时，表示n位有效数字，整数位也在其中
当setprecison(n)与fixed / scientific连用时，表示精度为n位，也就是保证n位小数

常见的数学函数

5.P1226 【模版】快速幂

快速幂的作用是快速求出a^b的值，实现思路可以看这道题的题解，讲的非常好，这里我把代码放上来用于快速回顾

#include<iostream>usingnamespacestd;intmain(){longlonga,b1,p;cin>>a>>b1>>p;longlongans=1,base=a,b=b1;//初始准备//ans是最终答案，base是权值，初始是底数的1次方while(b!=0){//关键1：b二进制右移直到为0if(b&1){//关键2：当b末位为1时ans=ans*base%p;//乘上权值，记得取模//关键3：(A+B) mod b = (A mod b + B mod b) mod b//(A×B) mod b= ((A mod b) × (B mod b)) mod b}base=base*base%p;//关键4：因为右移，权值进位b>>=1;//记得右移且赋值}printf("%ld^%ld mod %ld=%ld\n",a,b1,p,ans);return0;}

6.B3860

类似读完论文参考文献的题，主要考察递归以及去重条件
这题去重可以用set容器和bool数组标记法，以后遇到类似的可以参考这俩个思路
我看答案没递归，用的双端队列deq和set，也是不错的思路
这题可以回顾一下输入输出解绑加速

加速输入输出流

//（1）ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);//（2）可以用0替换这两个关键字ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

使用前：

为了保证 C++ 的 cin/cout 与 C 的 printf/scanf 可以混用且输出顺序正确，标准库会让两者保持同步，这导致 cin/cout 在每次操作时都要额外检查并刷新缓冲区，效率较低

使用后：

cin/cout 独立使用自己的缓冲区，不再与 C 流同步，速度会显著提升（可能快几倍甚至几十倍）。但代价是不能混用 cin/cout 和 printf/scanf，否则输出结果可能乱序或丢失

7.P1162

染色题考的是搜索，我的做法是把正方形输入到(1,1)~(n,n)，然后外面再加一圈0，从(0,0)开始搜索把所有遇到的外围0改成2
现在我看到了另一种做法，思路是遍历矩阵的每个格子，当遇到一个未被访问的 0 时，启动一次 DFS。DFS 会将该格子及其所有相邻的 0（上下左右）标记为一个独立的连通区域，并为该区域分配一个唯一的 id（从 3 开始递增）。同时，DFS 还会判断该区域是否触及矩阵边界：

如果搜索过程中遇到边界（越界），则返回 false，表示该区域连通到了外部，不被完全包围。
如果遇到 1 或已经标记过的同区域格子，则返回 true，表示该方向被障碍或已访问区域阻挡。
通过逻辑与（&=）组合四个方向的返回值，只要有一个方向触及边界，最终结果即为 false。

感觉还是我的方法简单

8.P1010

题意是把数字拆成如1315=2¹⁰+2⁸+2⁵+2+1=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
的形式
我用的是二进制右移找到所有的2ⁿ，再递归分解n拼接字符串

遇到了一个查了好久的bug：&运算符优先级低于==

复习一下运算符优先级吧顺便

运算符优先级

我看题解的思路是用pow和log2函数写的，我这个其实更偏向于不会用数学函数写出来比较绕的答案，贴上大佬代码膜拜一下

#include<iostream>//不解释#include<cmath>//其中有log2(x)和pow(x,y)函数，具体作用往下看usingnamespacestd;voiddivide(intx){boolflag=false;//...判断是否是第一个，如果是的话就不输出加号while(x!=0){intt=int(log2(x));/* log2(x)这个函数求以2为底x的对数，例如log2(8)返回3，因为2^3=8 而这里把返回值强制转换为int是为了找到离x最近又小于x的能表示为2^k的数 例如int(log2(137))就能返回7，而2^7=128，恰为离137最近的能表示为2^k的数 */if(flag)cout<<"+";//开头不输出加号if(t==1)cout<<"2";//如果这一项是1，输出2，不递归elseif(t==0)cout<<"2(0)";//如果这一项是0，输出2(0)，不递归else{cout<<"2(";divide(t);//递归一层，把括号里的数分解输出cout<<")";}x-=pow(2,t);//继续处理下一项flag=true;}}intmain(){intn;cin>>n;divide(n);return0;}

log2函数

计算以 2 为底的对数，C++11 起，x 必须 >0
注意本题用了log2强制转成了int

doublelog2(doublex);floatlog2(floatx);longdoublelog2(longdoublex);doublelog2(IntegralType x);// 整型参数会转换为 double

集训二（递归递推）知识点