算法笔记—刷题遇到的小知识点（知识点杂）
由数据范围反推算法复杂度以及算法内容
具体细节参考详细分析博客
C++快读快写
一般scanf，printf可以应对大部分的题，但一道题目数据量特别大，就要用到快读快写模板
通过读入字符而后来转成数字，而原理就是读入字符比数字快。读入后用ASCII码处理成数字，这样就很快了。基本的快读就像这样：
#include <iostream>
using namespace std;
typedef long long LL;
inline LL read()// 注意参数返回类型
{
LL x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void write(LL x)// 注意参数
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int main()
{
int a = read();
write(a);
return 0;
}C++关于数组的常用函数
- C++ 数组求和 使用自带的库函数 accumulate 的方法 首先：accumlate 所在头文件是：
accumulate ( 形参1 , 形参2 , 形参3 ) 前两个形参指定要累加的元素范围，第三个形参则是累加的初值
以及静态数组和动态数组求最大值最小值
int main() {
int a[] = {1, 2, 3, 4, 5};
vector<int> v({1, 2, 3, 4, 5});
// 普通数组
int minValue = *min_element(a, a + 5);
int maxValue = *max_element(a, a + 5);
int sumValue = accumulate(a, a + 5, 0);
// Vector数组
int minValue2 = *min_element(v.begin(), v.end());
int maxValue2 = *max_element(v.begin(), v.end());
int sumValue2 = accumulate(v.begin(), v.end(), 0);
cout << minValue << endl;
cout << maxValue << endl;
cout << sumValue << endl << endl;
cout << minValue2 << endl;
cout << maxValue2 << endl;
cout << sumValue2 << endl << endl;
return 0;
}- 复制函数 copy(first,last,result) 可用于字符串 或者数组 将first到last区间的元素复制到result中：
代码如下
#include <bits/stdc++.h>
using namespace std;
int main()
{
int myints[]= {10,20,30,40,50,60,70};
vector<int> myvector;
myvector.resize(7);
copy ( myints, myints+7, myvector.begin() );
for(int i=0; i<myvector.size(); i++)
cout<<myvector[i]<<" ";
cout<<endl;
return 0;
} #include <bits/stdc++.h>
using namespace std;
int main()
{
char s[24]="123456789";
char s1[24]="";
copy(s,s+5,s1);
cout<<s1<<endl;
return 0;
} #include <bits/stdc++.h>
// 可以动态到静态
using namespace std;
int main()
{
// int myints[]= {10,20,30,40,50,60,70};
// vector<int> myvector;
// myvector.resize(7);
// copy ( myints, myints+7, myvector.begin() );
// for(int i=0; i<myvector.size(); i++)
// cout<<myvector[i]<<" ";
// cout<<endl;
// return 0;
vector<int> myvector= {10,20,30,40,50,60,70};
int a[100];
copy ( myvector.begin() ,myvector.end(), a);
for ( int i = 0 ; i < myvector.size() ;i++)
{
cout << a[i]<< " ";
}
return 0;
}- 容器填充函数 fill(first,last,value)将区间first到last区间全部初始为value
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> v(8);
fill(v.begin(), v.end(), 1);// fill(v.begin(),v.begin()+4,1)
for(int i = 0 ; i < v.size() ; i++ )
cout << v[i] << " ";
cout << endl;
return 0;
}- 字符串转整形的两种方式 可以用atoi或者stoi，atoi的效率高一些
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str="1234";
int a=atoi(str.c_str());
int b=stoi(str);
cout << a << endl;
cout << b << endl;
return 0;
}- c++中超好用的截取部分字符串的函数substr();，要求从指定位置开始，并具有指定的长度。
#include<iostream>
using namespace std;
int main()
{
string str="hello";
str=str.substr(2);//第二个参数为0，表示从原串下标为2的字符开始截取到完。
cout<<str<<endl;
string str1="abcdefghijk";
str1=str1.substr(3,5);//从原串下标为3的字符开始截取5个字符，即defgh
cout<<str1<<endl;
return 0;
}快速乘
快速乘就是将两个要相乘的一个数变成二进制的形式进行运算。为什么要用快速乘？当两个大数进行相乘进行取模（ab%c）时，运算ab可能会爆long long的范围，这种情况就要用到快速乘了。
为什么快速乘不会爆范围呢？乘法容易爆范围，但是由于过程中不断取模，所以加法不会爆范围。
主要代码：
个人觉得这个快速乘和快速幂是十分相似的，主要代码也很相似：
long long int ksc(long long int n,long long int m,long long int c)
{
long long int res=0;
while(m)
{
if(m&1)
res=(res+n)%c;//是加不是乘，理由同下
n=(n+n)%c;//是加不是乘，快速幂里面才是乘
m=m/2;
}
return res;
}举个例子：
描述
a*b%p的值
格式
输入格式
输入a b p
a，b在long long的范围内
输出格式
a*b%p
样例
样例输入 Copy
2 4 3
样例输出 Copy
2
这就是一个非常典型的快速乘的例子：
#include<stdio.h>
long long int ksc(long long int n,long long int m,long long int c)
{
long long int res=0;
while(m)
{
if(m&1)
res=(res+n)%c;
n=(n+n)%c;
m=m/2;
}
return res;
}
int main()
{
long long int a,b,p,sum;
scanf("%lld %lld %lld",&a,&b,&p);
sum=ksc(a,b,p);
printf("%lld",sum);
return 0;
}自定义排序的一些总结
C++ 中sort是默认升序排列；
bool cmp (int a, int b) {
if (a < b) return true;
return false;
}上述代码可以简化为：
bool cmp (int a, int b) {
return a < b;
}升序代码：
bool cmp_up(int a, int b)
{
if(a < b)
return true;
else
return false;
}降序代码
bool cmp_down(int a, int b)
{
if(a > b)
return true;
else
return false;
}注意
*.当返回值为true时，第一个参数放在前面，第二个参数放在后面; false则反之
*当a = b时，必须要返回fasle
即符合排序规则才返回true，其他情况均返回fasle！
若cmp为true，则sort不调换传入的两个参数的位置，反之，sort会调换之。
下面代码有助于理解如何写比较函数：
#include<algorithm>
using namespace std;
struct node//结构体定义
{
int a;
int b;
int c;
};
bool cmp(node x,node y)//这个cmp是先按照a进行升序排序，
//如果a相同然后对b降序排序，
//如果b相同最后对c升序排序
{
if(x.a!=y.a)
return x.a<y.a;
if(x.b!=y.b)
return x.b>y.b;
if(x.c!=y.c)
return x.c<y.c;
}输入10个整数，彼此以空格分隔。重新排序以后输出(也按空格分隔)，要求:
1.先输出其中的奇数,并按从大到小排列；
2.然后输出其中的偶数,并按从小到大排列。
代码：
//充分发挥sort的能力嘛，cmp中就可以把所有逻辑写清楚了
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int x,int y)
{
if(x&1 && y&1) //如果是奇数就大到小
return x>y;
if(x%2==0 && y%2==0) //好像用位运算判断偶数不好使？？
return x<y;
if(x&1) //奇数在前
return true;
else
return false;
}
int main()
{
int array[10];
while(scanf("%d",&array[0])!=EOF)
{
for(int i = 1; i < 10; i++)
scanf("%d",&array[i]);
sort(array,array+10,cmp); //sort很强的啊
for(int i = 0; i<9; i++)
printf("%d ",array[i]);
printf("%d\n",array[9]);
}
return 0;
}洛谷经典自定义排序例题（附大佬代码）
bool cmp(node a,node b){
if(a.year != b.year)
return a.year < b.year;//如果出生年份不相等便直接按照年份进行排序
else{
if(a.mon != b.mon) return a.mon < b.mon;//年份相等月份不相等
else if(a.day == b.day && a.mon == b.mon) return a.level > b.level;//同年同月同日生 便把后输入的排在前面
else if(a.day != b.day && a.mon == b.mon) return a.day < b.day;//同年同月不同日
}
} bool cmp(node a,node b)
{
if(a.n<b.n)return 1;//先比年
if(a.n>b.n)return 0;
if(a.n==b.n)
{
if(a.y<b.y)return 1;//再比月
if(a.y>b.y)return 0;
if(a.y==b.y)
{
if(a.r<b.r)return 1;//再比日
if(a.r>b.r)return 0;
if(a.r==b.r)
{
if(a.num>b.num)return 1;//最后比编号
else return 0;
}
}
}
}数据类型范围
经常遇到范围是263，取模264的这种题目。遇到这种限制条件时就要想到用unsigned long long类型。可以简洁地声明为typedef unsigned long long ull。这样，如果ull类型的整数溢出了，就相当于取模264了。因为ull的范围是[0,264-1]。
详细参考：
(1条消息) C语言 打印short、long、long long 和unsigned类型_食人的小草的博客-博客_c语言打印long类型
C++数字转字符串 to_string()
to_string() 可以将整数、浮点数等数字转换为字符串并返回得到的字符串(注意：只有支持C++11标准的编译器才可以编译成功)to_string() 可以将整数、浮点数等数字转换为字符串并返回得到的字符串(注意：只有支持C++11标准的编译器才可以编译成功)
#include<iostream>
using namespace std;
int main()
{
int n = 541;
cout << "整数变字符串：" + to_string(n) << endl;
double d = 62.122;
cout << "浮点数变字符串：" + to_string(d) << endl;
}判断是否是回文数
bool isSymm ( int n)
{
int k = 0 ;
int j = n;
while(j > 0)
{
k = k * 10 + j % 10;
j /= 10;
}
if ( k == n) return true;
else return false;
}>> 和 除 2 的区别
-
n为非负数时，>> 1和/ 2的结果是一样的
-
n为负数且还是偶数时，>> 1和/ 2的结果是一样的
-
n为负数且还是奇数时，>> 1和/ 2的结果是不一样的
等比数列与等差数列
getline注意事项
getline函数用于读取整行字符串。遇到回车停止读入，因此getline函数遇到换行符会自动结束读取操作。注意：当用getline函数读取字符串时，若缓冲区内有换行符，需要先清除缓冲区中的换行符。执行cin>>n后输入回车程序会自动结束。因为程序将缓冲区中的数字读入到内存n的位置处，回车符还停留在缓冲区中，当getline函数读取缓冲区中字符时遇到换行符直接结束，没有读取字符串，相当于空串。
为了避免这种问题，可以用cin.ignoe()消除缓冲区中内容，包括换行符。在cin>>n;语句后面加入
cin.ignore();
求绝对值
abs()函数和fabs()函数 头文件为cmath，分别用于整数和浮点数的取绝对值
注意 ： min 或者 max 函数必须都为 int ， 或者都为 double ，必须保证变量类型一致。