常用头文件，宏定义
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<stack>#include<deque>#include<unordered_set>using namespace std;#define ll long long#define mp make_pair#define ff first#define ss second#define pub push_back#define pob pop_back()#define pof pop_front()#define all(v) (v).begin(), (v).end()const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int dx[4] = {-1, 0, 1, 0};const int dy[4] = {0, 1, 0, -1};const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};priority_queue<int, vector<int>, greater<int> > pq;vector<int> l[250], r[250];vector<pair<int, int> > ans;int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
unordered_map，这个是哈希map，需要引用
欧几里得算法（辗转相除法）（用于求最大公约数）
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }ll lcm(ll a,ll b) { return (a / gcd(a, b)) * b; }
常量E，PI
double PI=acos(double(-1));// PI的值=反余弦函数 -1.0为Pi， 1为0。double e=exp(double(1)); // e的值
错排问题公式
floor(n!/e+0.5) //错排个数floor(n!/e+0.5)/x //错排概率
大数除法模拟
int num=0,id=0;for(int i=0; i<s.size(); i++) {num=num*10+(s[i]-'0');if(id||num>=x) {ans[id++]=num/x;num%=x;}}
getline用法
string s;getline(cin,s);//记得吃掉它之前的回车char s2[3000];getchar();cin.getline(s2,3000);
函数找最大元素 函数找最小元素
C++ *max_element()函数找最大元素 *min_element()函数找最小元素 STL算法
阶乘位数
#include<stdio.h>#include<math.h>int digit_stirling(int n){double PI=acos(double(-1));// PI的值=反余弦函数 -1.0为Pi， 1为0。double e=exp(double(1));//e的值return floor(log10(sqrt(2*PI*n))+n*log10(n/e))+1;}
叉乘求任意多边形面积
N：多边形的顶点数目
返回值：多边形面积
注意：
支持多边形，凹凸多边形都可
多边形顶点输入顺序按顺时针排序
struct Point{
double x,y;
}p[N];
int n;
double polygonarea(){
int i,j;
double area = 0;
for(i = 0;i < n;++i){
j = (i+1)%n;
area += p[i].x*p[j].y;
area -= p[i].y*p[j].x;
}
area /= 2.0;
return (area<0?-area:area);
}
位运算 ^异或
含义 Pascal语言 C语言 Java
按位与 a and b a & b a & b
按位或 a or b a | b a | b
按位异或 a xor b a ^ b a ^ b
按位取反 not a ~a ~a
左移 a shl b a << b a << b
带符号右移 a shr b a >> b a >> b
无符号右移 a>>> b
中文名 异或 外文名 exclusive OR
数学符号 ⊕
英文简称 xor
程序符号 ^
异或运算的性质：
任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。
- a ^ a = 0
- a ^ b = b ^ a
- a ^b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
- d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
- a ^ b ^ a = b.
- 若x是二进制数0101，y是二进制数1011；
则x^y=1110
只有在两个比较的位不同时其结果是1，否则结果为0
即“两个输入相同时为0，不同则为1”！
全排列函数
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
string str = "aaabbc";
int n = 0;
while (next_permutation(str.begin(), str.end())){
cout << str << " ";
n++;
}
cout << "\n"
<< n << endl;
return 0;
}
向上取整，向下取整
#include <math.h>
#include <stdio.h>
#include <iostream>
int main(){
double number = 123.45;
double down, up;
down = floor(number);
up = ceil(number); //只考虑是否有小数，不考虑小数是多少
printf("原数%5.2lf\n", number); //123.45
printf("向上取整%5.2lf\n", down); //123.00 返回小于等于 value 的下一个整数
printf("向下取整%5.2lf\n", up); //124.00 返回大于等于 value 的下一个整数
return 0;
}
map的使用
#include <stdio.h>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
map<string,int> m;
map<string,int>::iterator it;
int main() {
int n,k;
scanf("%d%d",&n,&k);
char c[50];
int kk;
for(int i=0; i<n; i++) {
scanf("%s %d",c,&kk);
if(kk<k) {
kk=k;
}
m[c]+=kk;
}
int mm;
scanf("%d",&mm);
for(int i=0; i<mm; i++) {
scanf("%s",c);
if(m[c]==0){
printf("No Info\n");
}else{
printf("%d\n",m[c]);
}
}
return 0;
}
// for(it=m.begin(); it!=m.end(); it++)
// cout<<it->first<<" "<<it->second<<endl;
string 使用字符串翻转，带空格字符串输入
string s;
getline(cin,s);
reverse(s.begin(),s.end());
cout<<s<<endl;
return 0;
分式化简
求两个分数的最小公倍数
解题思路就是首先调用最大公约数函数将两个分数分别化简，然后调用最小公倍数函数求出分子的最小公倍数作为最终结果的分子,
调用最大公约数函数求出分母的最大公约数最为最终结果的分母，最后再调用最大公约数函数将所得结果化简输出即为相遇周期。
快速求幂 （递归）
int f(int m,int n){ //m^n
if(n==1) return m;
int temp=f(m,n/2);
return (n%2==0 ? 1 : m)*temp*temp;
}
快速求幂（位运算）
int pow3(int x,int n){
if(n==0) return 1;
else {
while((n&1)==0){
n>>=1;
x*=x;
}
}
int result=x;
n>>=1;
while(n!=0){
x*=x;
if(n&1) result*=x;
n>>=1;
}
return result;
}
printf总结
%d 是输出十进制整数 d是decimal的缩写
%2d要求输出数据为两位，大于两位则原样输出，例如2.，123，遇到2会补一个空格（输出2位），看到123会输出123
只有这两种格式
%m.ns：输出字符串，m指定输出宽度，n表示字符串的前n个字符输出到屏幕，如果m>n则需要补空格，例如%5.3s表示输出宽度是5，而字符实际只输出3个则需要补空格2个
%m.nf：m表示找整个浮点数输出宽度，n表示小数输出的宽度。例如%5.2f 输出一个58.6238，
那么实际输出的是58.62，注意了，m是整个数据要输时候的宽度。
%02d:默认情况下，数据数据宽度不够2位是用空格填补的，但是因为2d前面有0，表示，数据宽度不足时用0填补，例如%03d输出 12，那么实际输出到屏幕的是012.
素数筛
素数判断 时间复杂度O(sqrt(n)/3)
bool isPrime(int n) {
if (n == 1) return false;
if (n == 2 || n == 3) return true;
if (n % 6 != 1 && n % 6 != 5) return false;
for (int i = 5; i * i <= n; i += 6)
if (n % i == 0 || n % (i + 2) == 0) return false;
return true;
}
原始 时间复杂度O(n*sqrt(n))
bool isprime(int n) {
int i;
for (i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
普通筛——埃拉托斯特尼(Eratosthenes)筛法 时间复杂度O(nloglogn)
const int maxN = 1e5+5;
bool number[maxN+5];
void isprime()
{
int i,j;
memset(number,true,sizeof(number));
for(i=2;i<=maxN;i++)
{
if(number[i])
{
for(j=2;j*i<=N;j++)
number[i*j]=false;
}
}
}
线性筛——欧拉Euler筛
/*
prime[]数组中的素数是递增的,当i能整除prime[j]，那么i*prime[j+1]这个合数肯定被prime[j]乘以某个数筛掉。
因为i中含有prime[j],prime[j]比prime[j+1]小，即i=k*prime[j]，那么i*prime[j+1]=(k*prime[j])*prime
[j+1]=k’*prime[j]，接下去的素数同理。所以不用筛下去了。因此，在满足i%prime[j]==0这个条件之前以及第一次
满足改条件时,prime[j]必定是prime[j]*i的最小因子。
*/
const int maxN = (int) 1e7 + 6;
bool number[maxN];
int prime[maxN];
inline void isPrime() {
int c = 0;
memset(number, true, sizeof(number));
number[0] = number[1] = false;
for (int i = 2; i < maxN; i++) {
if (number[i]) {
prime[c++] = i;
}
for (int j = 0; j < c && prime[j] * i < maxN; j++) {
number[prime[j] * i] = false;
//保证每个合数只会被它的最小质因数筛去，因此每个数只会被标记一次
if (i % prime[j] == 0) {
break;
}
}
}
// for (i = 0; i < c; i++) {
// cout << prime[i] << " ";
// }
}
int main() {
isPrime();
}
若有收获，就点个赞吧
0 人点赞
