【c++算法刷题笔记】——洛谷1

2020/2/14-2/16

1. 循环提取一个数的每一位数字

while (d > 0) //d=0跳出循环 {x=d%10; //x每次为d的个位数 d = d / 10; //相当于d每次舍去个位数 }

2. c++new创建动态二维数组

int *a=new int[n]; //创建动态一维数组 int(* a)[2] = new int[n][2]; //创建动态二维数组[n][m]m必须为const常量

3. 洛谷上的一道题：

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2,…,L都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式：第一行有2个整数 L(1$\le$ L $\le$ 10000)和 M(1$\le$ M$\le$ 100)M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。
接下来的M行每行包含2个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式：1个整数，表示马路上剩余的树的数目。

#include<iostream> using namespace std; int main() {int L, n;cin >> L >> n;int* a = new int[L]; for (int i = 0; i <=L; i++)a[i] = 1; //让a数组元素全为1表示这里有树int(* b)[2] = new int[n][2];for (int i = 0; i <n; i++) //输入M个区域{for (int j = 0; j < 2; j++)cin >> b[i][j];}for (int i = 0; i < n; i++){for (int j = b[i][0]; j <= b[i][1]; j++) a[j] = 0; //在M区域范围的a令为0，表示树已经被砍}int sum = 0;for (int i = 0; i <= L; i++){sum += a[i];}cout << sum << endl; //输出a中1的个数即为剩余的树return 0; }

4. 洛谷上一道题P1553 数字反转（升级版）中坑人的数：

0.00 0/111 0000/123 0% //这个坑死我了 12.00000

5. 回文数判断：
洛谷：P1217 [USACO1.5]回文质数 Prime Palindromes总结
回文质数优化：除了 11 以外的回文质数一定是奇数位数
一个整数如果奇数位的数字和等于偶数位的数字和，则其能被11整除。
偶数位数的回文数都能被11整除。所以除了 11 以外的回文质数一定是奇数位数

bool hui(int n) {unsigned i=n;unsigned m=0;while(i>0){m=m*10+i%10; //每次提取个位数然后乘以10在接着提取个位数i/=10;}return m==n; }

6.万能开头文件：

#include<bits/stdc++.h>//万能头文件

7.质数判断（高效）：
大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；
一个博主对质数判断的总结下面代码是这个博主写的，贴贴过来作为笔记

bool isPrime_3( int num ) {//两个较小数另外处理if(num ==2|| num==3 )return 1 ;//不在6的倍数两侧的一定不是质数if(num %6!= 1&&num %6!= 5)return 0 ;int tmp =sqrt( num);//在6的倍数两侧的也可能不是质数 在6两边的数不可能被2 3 4整除所以从5开始以6为步长for(int i= 5;i <=tmp; i+=6 )if(num %i== 0||num %(i+ 2)==0 )return 0 ;//排除所有，剩余的是质数return 1 ; }

7.有点爱上递归的简洁洛谷P1028 数的计算：
我们要求找出具有下列性质数的个数(包含输入的自然数$n$)：
先输入一个自然数$n$($n$$\le$ $1000$),然后对此自然数按照如下方法进行处理

不作任何处理;

在它的左边加上一个自然数,但该自然数不能超过原数的一半;

加上数后,继续按此规则进行处理,直到不能再加自然数为止.

输出$1$个整数，表示具有该性质数的个数
发现：$f[i]=f[1]+f[2]+f[3]+...+f[i/2];$$i$为奇数时$f[i]=f[i-1]$当i为偶数时$f[i]=f[i-1]+f[i/2];$（通项公式做差可以求出）

#include<iostream> using namespace std; int main() {int f[1001];int n;cin >> n;f[1] = 1;for (int i = 2; i <= n; i++){f[i] = f[i - 1];if (i % 2 == 0)f[i] += f[i / 2];}cout << f[n];return 0; }

8.对于不安全情况的处理：

#define _CRT_SECURE_NO_WARNINGS //或者 #pragma warning(disable:4996)

9.填充以及输出位数：

#include<iomanip> cout<<setiosflags(ios::left)<<setfill('*')<<setw(5)<<endl; //左对齐（默认右对齐），每个输出位占5，不够以'*'填充（默认以空格填充） cout<<setiosflags(ios::fixed)<<setprecision(2); //保留两位小数

前两天刷了刷洛谷，感觉已经刷不动了。算法知识为0，开始恶补算法！！！

总结

以上是生活随笔为你收集整理的【c++算法刷题笔记】——洛谷1的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。