杂七杂八的零碎知识

• • • 格式输入
    • 数据范围
    • 闰年
    • 上取整
    • 内存
    • 倒转字符串
    • 最大公约数
    • 最大公倍数
    • substr
    • 树
    • 完全二叉树的层序遍历
    • 并查集
    • 小顶堆
    • 欧几里得算法
    • 扩展欧几里得算法
    • 素数
    • 中国剩余定理
    • count函数
    • 优先队列
    • 图
    • • Floyed
      • dijskra
      • 改进的dijskra
      • spfa
      • kruskal
      • prime
    • 整行输入
    • 归并排序和逆序对数量
    • 快速排序
    • string与char数组/数据类型与string的转换
    • 前缀和
    • 二分
    • 26进制
    • 进制转换

int get_time(){
	string line;
	getline(cin, line);
	if(line.back() != ')') line += " (+0)";
	int h1, m1, s1, h2, m2, s2, d;
	sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1, &m1,&s1, &h2,&m2,&s2,&d);
	return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
}

int main(){
	int x = 0;
	scanf("%d", &x);
	int y = x / 10000, m = x % 10000 / 100, d = x % 100;
	int first_huiwen = 1;
	while(1 = 1){
		next_day(y, m, d);
		spring(nums, "%d%02d%02d", y, m, d);
		if(nums[0] == nums[7] && nums[1] == nums[6] 
			&& nums[2] == nums[5] && nums[3] == nums[4]){
				if(first_huiwen){
					printf("%sn", nums);
					first_huiwen = 0;
				}
			}
		if(nums[0] != nums[1] && nums[0] == nums[2] && nums[1] == nums[3])
			printf("%sn", nums);
			break;
	}
	
	
	return 0;
}

int 的范围2 * 10 ^ 9

int: 4byte = 32 bit 有符号signed范围：2^31-1 ~ -2^31即：2147483647 ~ -2147483648无符号unsigned范围：2^32-1 ~ 0即：4294967295 ~ 0

long: 4 byte = 32 bit 同int型

double: 8 byte = 64 bit 范围：1.79769e+308 ~ 2.22507e-308

long double: 12 byte = 96 bit 范围： 1.18973e+4932 ~ 3.3621e-4932

float: 4 byte = 32 bit 范围： 3.40282e+038 ~ 1.17549e-038

long long的最大值：9223372036854775807（>10^18）
long long的最小值：-9223372036854775808
unsigned long long的最大值：18446744073709551615

__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808

unsigned __int64的最大值：18446744073709551615

1. 年份不能被100整除，但是可以被4整除
2. 年份可以被400整除

ceil函数返回double类型，可以强制转换

或者写成==(a + b - 1) / b==

（a % b + b）% b 保证返回的正数

MB = 1024 KB = 1024 * 1024 Byte

1MB = 8 Mb

Byte = 8 bit（位）

int 4byte

char 1byte

long long 8byte

float 4byte

double 8byte

string s;
reverse(s.begin(), s.end());

__gcd()

最小公倍数=a*b/最大公因数

int gcd(int a, int b){
 return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b){
 return a * b / gcd(a, b);
}

string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = “56789”

string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = “567”

给定一棵二叉树的后序遍历和中序遍历，输出前序代码

#include 
using namespace std;
int post[35],in[35];
void helper(int root,int start,int end){
	if(start > end) return ;
	int l = start;
	while(l < end && in[l] != post[root]) l++;
	printf("%d ",post[root]);
	//end-l为当前右孩子的个数，root - (end - l) - 1则为当前左子树的根
	helper(root - (end - l) - 1,start,l-1);
	//root-1位当前右子树的根
	helper(root-1,l+1,end);
}
int main(){
	int n;
	cin>>n;
	for(int i = 0;i < n;i++) cin>>post[i];
	for(int i = 0;i < n;i++) cin>>in[i];
	helper(n-1,0,n-1);
	return 0;
}

给定一棵二叉树的后序遍历和中序遍历，输出层序代码

#include 
using namespace std;
int post[35],in[35],res[10010];
void helper(int root,int start,int end,int index){
	if(start > end) return ;
	int l = start;
	while(l < end && in[l] != post[root]) l++;
	res[index] = post[root];
	helper(root - (end - l) - 1,start,l-1,2*index+1);
	helper(root-1,l+1,end,2*index+2);
}
int main(){
	int n;
	cin>>n;
	for(int i = 0;i < n;i++) cin>>post[i];
	for(int i = 0;i < n;i++) cin>>in[i];
	helper(n-1,0,n-1,0);
	int cnt = 0;
	for(int i = 0;i < 10010;i++){
		if(cnt == n-1 && res[i] != 0)
		{
			cout< 
完全二叉树的层序遍历 
#include
using namespace std;

#define N 100009
int a[N],tr[N];
int t=1;
int n;
void dfs(int u)
{
	if(u>n) return ;
	//左右根 
	dfs(u*2);
	dfs(u*2+1);
	cin>>tr[u];
}
int main()
{  
     
     cin>>n;
     //for(int i=1; i<=n; i++) scanf("%d",a+i);
     dfs(1);
     for(int i=1; i<=n; i++)
     {
     	cout< 
并查集 
#include 
using namespace std;

int F[105];
int Mp[105][105];
int get_far(int x){
    return F[x] == x ? x : F[x] = get_far(F[x]);
}
void Union(int x,int y){
    int a = get_far(F[x]),b = get_far(F[y]);
    if(a != b)
        F[a] = b;
}
 
int main()
{
    int n,m,k;
    while(cin>>n>>m>>k){
        for(int i = 0;i <= n;i ++)  F[i] = i;
        int x,y,v;
        for(int i = 1;i <= m;i ++){
            cin>>x>>y>>v;
            Mp[x][y] = Mp[y][x] = v;
            if(v == 1)
                Union(F[x],F[y]);
        }
        int judge1,judge2;
        for(int i = 1;i <= k;i ++){
            cin>>judge1>>judge2;
            if(Mp[judge1][judge2] == 1)  cout<<"No problem"< 
小顶堆 
 
 
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子结点的值。
 小顶堆是指每个父亲结点的值小于等于孩子结点的值，每个结点的值都是以它为根结点的子树的最小值。
 
 
#include
#include
#include
#include
 
欧几里得算法 
计算最大公约数gcd(a,b) = gcd(b,a%b)
 
a是非负整数
 
d|a 表示d是a的因子，d整除a
 
任何整数都是0的因子
 
//递归法
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
//
int gcd(int a,int b){
	int r;
	while(b != 0){
		 r = a % b;
		 a = b;
		 b = r;
	}
	return a;
}
int lcm(int a, int b){
  return a * b / gcd(a, b);
}
 
gcd(a,0) = |a|
 
扩展欧几里得算法 
 
 
ax+by=c有整数解=>gcd(a,b)|c
 
 
int exgcd(int a,int b,int &x,int &y){
  if(b == 0){
    x = 1;
    y = 0;
    return a;
  }
  else{
    int r = exgcd(b,a%b,x,y);
    int t = x;
    x = y;
    y = t - a/b * y;
    return r;
  }
}

void ex_gcd(int a,int b,int &x,int &y,int &d){
  //d是最大公约数
  if(!b) {
    x = 1;
    y = 0;
    d = a;
  }else{
    ex_gcd(b,a%b,y,x,d);
      y -= x *(a/b);
  }
}
 
素数 
const long long N = 1000010;
int prime[N];//dp[]为0时是素数
int dp[N] = {1,1,0},tot;
void init(){
  for(long long i = 2; i < N; i++){
    if(dp[i]) continue;
    prime[tot++] = i;//记录素数
    for(long long j = i; j * i < N; j++){
      dp[i * j] = 1;//凡是一个素数的倍数不为素数
    }
  }
}
 
中国剩余定理 
count函数 
#include 
using namespace std;

int main()
{
    string s= "abcdefgaabbccd";
    int num =count(s.begin(),s.end(),'a');
    cout< 
优先队列 
priority_queue< type, container, function >
//升序队列
priority_queue ,greater > q;
//降序队列（默认）
priority_queue ,less >q;
 
 
 
和队列基本操作相同:
 
 
 
top 访问队头元素
 
 
empty 队列是否为空
 
 
size 返回队列内元素个数
 
 
push 插入元素到队尾 (并排序)
 
 
emplace 原地构造一个元素并插入队列
 
 
pop 弹出队头元素
 
 
swap 交换内容
 
pair的比较，先比较第一个元素，第一个相等比较第二个
 
 
 
图 
 
Floyed 
#include
using namespace std;
int n,m,q;
const int N = 1100;
int d[N][N];
void Floyed(){
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(d[i][k] + d[k][j] < d[i][j])
					d[i][j] = d[i][k] + d[k][j];
			}
		}
	}
}
int main(){
	cin >> n >> m >> q;
	memset(d,0x3f,sizeof d);
	for(int i = 1; i <= n; i++)
		d[i][i] = 0;
	int u,v,w;
	while(m--){
		cin >> u >> v >> w;
		if(u == v) d[u][v] = d[v][u] = 0;
		else d[u][v] = d[v][u] = min(int(d[u][v]),w);
	}
	Floyed();
	while(q--){
		cin >> u >> v;
		if(d[u][v] >= 0x3f) cout <<"-1" << endl;
		else cout << d[u][v] << endl;
	}
	return 0;
}
 
dijskra 
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
int num[510];
int MAP[1010][1010];
bool vis[510];
int minlen;
int n,m,s,d;
int ans[510];//s到各个点的最短路径
int path[1010];//保存当前路径
int ansPath[1010];//保存最优路径
int cnt;//最短路径的个数
int maxNum;//最大救援数量
int ss;//最优路径的城市个数
void dijskra(int s){
    for(int i = 0; i < n; i++){
        MAP[i][i] = 0;
        ans[i] = MAP[s][i];
    }
    vis[s] = 1;
    int v,pos;
    for(int i = 1; i < n; i++){
        v = 0;
        pos = INF;
        for(int j = 0; j < n; j++){
            if(!vis[j] && ans[j] < pos){
                pos = ans[j];
                v = j;
            }
        }
        vis[v]  = 1;
        for(int i = 0; i < n; i++)
            ans[i] = min(ans[i],ans[v] + MAP[v][i]);
    }
    
    minlen = ans[d];
}
void dfs(int s,int len,int sum,int step){
    path[step] = s;
    if(len > minlen)
        return;
    if(s == d && len == minlen){
        cnt ++;
        if(sum > maxNum){
            maxNum = sum;
            ss = step;
            memcpy(ansPath,path,sizeof ansPath);
        }
        return;
    }
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            vis[i] = 1;
            dfs(i,len+MAP[s][i],sum + num[i],step+1);
            vis[i] = 0;
        }
    }
}
int main(){
    cin >> n >> m >> s >> d;
    for(int i = 0; i < n; i++)
        cin >> num[i];
    int x,y,t;
    memset(MAP,INF,sizeof MAP);
    for(int i = 0; i < m; i++){
        cin >> x >> y >> t;
        MAP[x][y] = MAP[y][x] = min(t,MAP[x][y]);
     }
      
	dijskra(s);
	memset(vis,0,sizeof vis);
	vis[s] = 1;
	dfs(s,0,num[s],0);
	cout << cnt << " " << maxNum << endl;
    for(int i = 0; i <= ss; i++){
    	cout << ansPath[i];
    	if(i!=ss)
    		cout << " ";
	}
    return 0;
}
 
改进的dijskra 
#include
using namespace std;
const int N = 1e6;
long long int dis[N];
bool st[N];
int n,m;
typedef pair PII;
struct edge{
	int v,w;
};
vector e[N];
void dijstra(){
	memset(dis,0x3f,sizeof dis);
	priority_queue,greater> pq;
	dis[1] = 0;
	pq.push({0,1});
	while(pq.size()){
		PII node = pq.top();pq.pop();
		long long dist = node.first;
		int u = node.second;
		
		if(st[u]) continue;
		st[u] = true;
		for(int i = 0; i < e[u].size();i++){
			int v = e[u][i].v;
			if(e[u][i].w + dis[u] < dis[v]){
				dis[v] = e[u][i].w + dis[u];
				pq.push({dis[v],v});
			}
		}
	}
	return ;
}
int main(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c);
		e[a].push_back({b,c});
	}
	dijstra();
	for(int i = 1; i <= n; i++){
		if(dis[i] >= 0x3f) cout << "-1" << " ";
		else cout << dis[i] << " ";
	}
	return 0;
}
 
spfa 
#include 
#include 
#include 

using namespace std;

const int N = 2200, M = N * 50;

int n;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];

int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()  // 求1号点到n号点的最短路距离
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q[tt ++ ] = 1;
    st[1] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}


int main()
{
    n = 2021;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
        for (int j = max(1, i - 21); j <= min(n, i + 21); j ++ )
        {
            int d = gcd(i, j);
            add(i, j, i * j / d);
        }

    spfa();
    printf("%dn", dist[n]);
    return 0;
}
 
kruskal 
#include
using namespace std;
const int N = 1100;
int n,m;
int a[N],b[N],c[N],p[N]; 
struct edge{
	int i,j;
	double w;
}e[N];
int find(int x){
	if(p[x] != x)
		return find(p[x]);
	return x;
}
bool cmp(edge a,edge b){
	return a.w < b.w;
}
void kruskal(){
	sort(e,e+m,cmp);
	int cnt = 0;
	double res = 0;
	for(int i = 1; i <= N; i++)
		p[i] = i;
	for(int i = 0; i < m; i++){
		int u = e[i].i,v = e[i].j;
		double w = e[i].w;
		int fu = find(u),fv = find(v);
		if(fu == fv) continue;
		p[fu] = fv;
		res += w;
		cnt ++;
	}
	if(cnt < n - 1) cout << "impossible";
	else printf("%.2f",res);
	return ;
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> c[i];
		for(int j = 1; j < i; j++){
			int t1 = a[i] - a[j],t2 = b[i] - b[j],t3 = c[i]-c[j];
			double dis = sqrt(t1 * t1 + t2 * t2) + t3 * t3;
			e[m++] ={i,j,dis};
		}
	}
	kruskal();	
	return 0;
}
 
prime 
#include
using namespace std;

const int N = 1100;
double mp[N][N];
bool vis[N];
double dis[N];
int n,m;
int a[N],b[N],c[N];
double prime(int s){
	memset(dis,0x3f,sizeof dis);
	for(int i = 1; i <= n; i++){
		dis[i] = mp[s][i];
	}
	dis[s] = 0;
	vis[s] = 1;
	double ans = 0;
	while(1){
		int v = -1;
		for(int u = 1; u <= n; u++){
			if(!vis[u] && (v == -1 || dis[u] < dis[v])){
				v = u;
			}
		}
		if(v == -1) break;
		vis[v] = true;
		ans += dis[v];
		for(int u = 1; u <= n; u++){
			dis[u] = min(dis[u], mp[u][v]);//注意这里是更新成u到v的距离
      ///每次找出最小距离距离(指距离最小生成树的距离
		}
	}
	return ans;
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> c[i];
		for(int j = 1; j < i; j++){
			int t1 = a[i] - a[j],t2 = b[i] - b[j],t3 = c[i]-c[j];
			double dist = sqrt(t1 * t1 + t2 * t2) + t3 * t3;
			mp[i][j] = mp[j][i] = dist;
		}
		
	}
	cout << prime(1);	
	return 0;
}
 
整行输入 
#include
#include
#include
#include

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
    int cnt;
    cin >> cnt;
    string line;
    getline(cin, line);
    
    while(cnt--){
        getline(cin, line);
        stringstream ssin(line);//重点是这里读入
        while(ssin >> a[n]) n++;
    }
    sort(a, a + n);
    int res1, res2;
    for(int i = 1; i < n; i++) {
        if(a[i] == a[i - 1]) res2 = a[i];
        else if(a[i] >= a[i - 1] + 2) res1 = a[i] - 1;
    }
    cout << res1 << ' ' << res2 << endl;
    return 0;
}
 
归并排序和逆序对数量 
#include
using namespace std;
const int N = 100010;
int n, a[N],tmp[N];
long long merge_sort(int l, int r){
	if(l >= r) return 0;
	int mid = l + r >> 1;
	long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
	
	int k = 0,i = l,j = mid + 1;
	while(i <= mid && j <= r){
		if(a[i] <= a[j]) tmp[k++] = a[i++];
		else{
			tmp[k++] = a[j++];
			res += mid - i + 1;
		}
	}
	while(i <= mid) tmp[k++] = a[i++];
	while(j <= r) tmp[k++] = a[j++];
	
	for(int i = l,j = 0; i <= r; i++, j++) a[i] = tmp[j];
	return res;
}
int main(){
	cin >> n;
	for(int i = 0; i < n; i++) scanf("%d",&a[i]);
	cout << merge_sort(0, n - 1) << endl;
	return 0;
} 
 
快速排序 
void quick_sort(int *num,int l,int r){
	//如果小于等于1个数据元素·直接返回结束快排函数 r为数组元素总个数
	if(l+1>=r){
		return ;
	}
	int first=l,last=r-1,key=num[first];
	while(first=key){
			--last;
		}
		//如果值小于 key分界值 交换 
		num[first]=num[last];
		while(first 
string与char数组/数据类型与string的转换 
#include
#include
#define sMAX 110
using namespace std;
long long n,m,a[MAX][MAX];
long long dp[MAX][MAX];
 
int main()
{
	//char数组转string
	char c1[]="asdf";
	string s1(c1);//法一 
	string s2;//法二 
	s2=c1;
	cout<a2;
	cout<
 
前缀和 

 子矩阵和
 
#include
#include
#include
#include

using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N],S[N][N];

int main(){
    scanf("%d %d %d",&n, &m, &q);
    for(int i = 1; i <=n ; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d",&a[i][j]);
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j];
        }
    }
    while(q--){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d",&x1, &y1, &x2, &y2);
        printf("%dn",S[x2][y2] - S[x2][y1-1] -S[x1-1][y2] + S[x1-1][y1-1]);
    }
    return 0;
}
 
二分 
lower_bound(查找的起始位置，查找的终止为止，需要查找的数 )是返回第一个大于等于需要查找的数的数的地址
 比如，要a[]数组中，从[1,n]中第一个大于s的数的下标
 pos=lower_bound(a+1,a+n+1,s)-a;
 upper_bound(查找的起始位置，查找的终止为止，需要查找的数 )是返回第一个大于需要查找的数的数的地址
 注意上面的两种用法都需要原数组是小到大排列的有序数组
 
可以通过修改比较器，查找第一个小于或小于等于某个数的地址
 数组需要从大到小排列
 首先需要比较函数
 bool cmp(const int &a, const int &b){return a > b;}
 比如，要a[]数组中，从[1,n]中第一个小于s的数的下标
 pos=lower_bound(a+1,a+n+1,s，cmp)-a;
 也可以不写cmp函数，将所有cmp的位置换成greater() 去掉/，int显示不了
 
往左找
 
	while (l < r)
    {
        int mid = l + r >> 1;	//(l+r)/2
        if (check(mid))  r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }

 
往右找
 
	while (l < r)
    {
        int mid = l + r + 1 >> 1;	//(l+r+1)/2
        if (check(mid))  l = mid;
        else r = mid - 1;
    }

 
二分查找&二分答案
 
26进制 
#include
using namespace std;
typedef long long LL;
string solve(int n, int r){
	string res;
	while(n){
		int t = n % r;
		n = (n - 1) / r;
		if(t == 0)
		 t = r;
		res += 'A' + t - 1;
	}
	return res;
}
int fun(int k, char c){
	return (c - 'A' + 1) * pow(26,k);
}
int main(){
//	int n;
//	cin >> n;
//	string ans = solve(n,26);
//	reverse(ans.begin(), ans.end());
//	cout << ans; 
	string s;
	cin >> s;
	int l = s.length();
	int ans = 0;
	for(int i = 0; i < l; i++){
		ans += fun(l - i - 1, s[i]);	
	} 
	cout << ans;
	return 0;
}

 
进制转换 
#include
using namespace std;
typedef long long LL;
int toDecimal(string s, int r){
	int ans = 0;
	for(int i = 0; i < s.size(); i++){
		char t = s[i];
		if(t >= '0' && t <= '9') ans = ans * r + (t - '0');
		else ans = ans * r + t - 'a' + 10;
	}
	return ans;
}
int main(){
//	函数方法 
//	char buffer[20] = "10549"; 
//	char *stop;
//	int ans = strtol(buffer, &stop, 8);//任意2-36进制转十进制 
//	cout << ans;

	int num = 1000;
	char str[100];
	_itoa(num,str,16);//十进制转任意2-36进制 
	cout << str;
//	自定义函数方法 
//	string s = "5E";
//	int radix = 16; 
//	int res = toDecimal(s, radix);
//	cout << res;
	return 0;
}