ACM中问题的简单记录(自留)-cindahy

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

作用

这一行代码的主要作用是在c++中关闭输入输出流的同步，以提高程序的执行效率。

关闭c++输入输出流与c标准库的输入输出函数的同步，提高程序执行效率。
解绑输入输出流，cin.tie(0)和cout.tie(0)可以取消cin和cout之间的绑定，提升效率。

注意事项

不能再用c标准库中的输入输出函数如scanf和printf函数。
不能再用cout<<endl,而改为cout<<'\n'。

左右对齐

cout<<setw(5)<<std::right<<i;

STL

介绍

STL(Standard Template Library,标准模板库)，提供了六大组件：容器、算法、迭代器、仿函数、适配器、空间配置器。

pair函数

定义

类模板：template <class T1, class T2> struct pair

pair(int,char*)p(1,"cindahy");

访问

p.first=1;
p.second="cindahy";

赋值

p=make_pair(1,"cindahy");

算法

dp（动态规划）

介绍

实际上就是把大化小，把大问题转化成小问题，且小问题之间通常可以用递推关系表示。通常用来求解最值（最优、最大、最小、最长）问题。步骤为拆分子问题，把子状态记录在dp中，找到递推关系，在子状态的基础上求解之后的问题。
相关例题。

代码运行：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[505][505]={0};//dp存储word1前i个数据到word2前j个数据需要的步骤数
        for(int i=0;i<=word1.length();i++){
            dp[i][0]=i;//这里0个数据的情况也要计算在内。
            //表示word1前i个数据需要删除i次变成word2的0个数据
        }
        for(int i=0;i<=word2.length();i++){
            dp[0][i]=i;
        }
        for(int i=1;i<=word1.length();i++){
        	//dp存储word1前i个数据到word2前j个数据需要的步骤数
            for(int j=1;j<=word2.length();j++){
                if(word1[i-1]==word2[j-1]){//i-1时word1有i个数据
                    dp[i][j]=dp[i-1][j-1];//此时在dp[i-1][j-1]的基础上不需要操作
                }
                else{
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    //后面的三个值依次为删除，添加和更改一个值，选取其中最小操作数+1为dp[i][j]。
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
};

回溯算法-组合问题

树的思想

vector<int>p;
vector<vector<int>>q;
void comb(int n, int r,int index)
{
	if(p.size()==r){
		q.push_back(p);
		return;
	}
	for(int i=index;i<=n;i++){
		p.push_back(i);
		comb(n,r,i+1);
		p.pop_back();
		
	}
}

全排列问题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+5;
void perm(int *a,int k,int m){
	if(k==m){
		for(int i=0;i<=m;i++){
			cout<<a[i]<<' ';
		}
		cout<<'\n';
	}
	else{
		for(int j=k;j<=m;j++){
            if(j==0){
                perm(a,k+1,m);
            }
            else{
				int t=a[j];
				for(int p=j-1;p>=k;p--){
					a[p+1]=a[p];
				}
				a[k]=t;
				perm(a,k+1,m);
				for(int p=k+1;p<=j;p++){
					a[p-1]=a[p];
				}
				a[j]=t;
				
            }
		}
	}
}
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=1;i<=n;i++){
		a[i-1]=i;
	}
	perm(a,0,n-1);
	return 0;
	
}