输入输出

任务：cout格式化输出

使用printf()完成格式化输出 ~

任务：超级大的整数的输入处理，比如，1234567899876543211234567893216549870，这个数输入，如何写代码

string str; cin>>str; for(int i=0;i<str.length();i++){ //访问str[i]的内容 //若进行计算，需要str[i]-'0' }

任务：C++11中，string对象不能直接输出到cout?

能输出，自己把endl写成end了

任务：格式化输出一串数字，每个数字之间有空格，第一个数字之前和最后一个数字之后不允许有空格

int array[10]; for(int i=0;i<10;i++){ if(i!=0)cout<<" "; //输出数组元素array[i] cout<<array[i]; }

cout输出' - '和" - "的区别

语法

long 和 long long的区别

int ，长度是4 Byte，范围[-2^31, 2^31-1]， long int ，长度是4 Byte，范围[-2^31, 2^31-1]， long long int，长度是8 Byte，范围[-2^63, 2^63-1]。

string的length()和size()的区别

坑1

algorithm中sort接口的使用

坑2

常见代码段

判素数

bool isPrime(int a){ for(int i=2;i*i<=a;i++）{ if(a%i==0)return false; } return true; }

素数筛

#define MAX_N 1000000 int prime[MAX_N + 5]; void init_prime() { for (int i = 2; i * i <= MAX_N; i++) { if (prime[i]) continue; for (int j = i * i; j <= MAX_N; j += i) { prime[j] = 1; } } for (int i = 2; i <= MAX_N; i++) { if (prime[i] == 0) prime[++prime[0]] = i; } return ; }

a+b>c 为真时，值为true，假时，值为false

(a+b>c?"true":"false")

二分

#include<iostream> #include<algorithm> using namespace std; int a[100]; int x; int binaryB(int l, int r){//单调递增序列a中，>=x的最小的一个，即x或x的后继 while(l<r){ int mid=(l+r)>>1; if(a[mid]>=x)r=mid; else l=mid+1; } return a[l]; } int binaryS(int l, int r){//单调递增序列a中，<=x的最小的一个，即x或x的后继 while(l<r){ int mid=(l+r+1)>>1; if(a[mid]<=x)l=mid; else r=mid-1; } return a[l]; } int main(){ for(int i=0;i<100;i++)a[i]=(100-i)*2; for(int i=0;i<100;i++)cout<<a[i]<<" "; cout<<endl; sort(a, a+100); for(int i=0;i<100;i++)cout<<a[i]<<" "; cout<<endl; x=77; cout<<binaryB(0,99)<<endl; cout<<binaryS(0,99)<<endl; return 0; }

编辑距离

class Solution { public: bool isOneEditDistance(string s, string t) { int lens=s.size(), lent=t.size(); int ** dp = (int **)malloc(sizeof(int*)*(lens+1)); for(int i=0;i<lens+1;i++){ dp[i] = (int *)malloc(sizeof(int *)*(lent+1)); for(int j=0;j<lent+1;j++)dp[i][j]=0; } //vector<vector<int>> dp(lens+1, vector<int>(lent+1, 0)); for(int i=0;i<lens+1;i++)dp[i][0]=i; for(int j=0;j<lent+1;j++)dp[0][j]=j; for(int i=1;i<lens+1;i++){ for(int j=1;j<lent+1;j++){ dp[i][j] = min(dp[i-1][j-1]+1, min(dp[i-1][j]+1, dp[i][j-1]+1)); if(s[i-1]==t[j-1])dp[i][j]=min(dp[i][j], dp[i-1][j-1]); } } bool ret = (dp[lens][lent]==1)?true:false; for(int i=0;i<lens+1;i++){ free(dp[i]); } free(dp); return ret; } };

各种暴力，用于DP

指数型枚举

#include<iostream> #include<vector> using namespace std; vector<int> chosen; int n; int cnt=0; void calc(int x){ if(x==n+1){ //for(int i=0;i<chosen.size();i++)cout<<chosen[i]<<" "; //cout<<endl; cnt++; return; } calc(x+1); chosen.push_back(x); calc(x+1); chosen.pop_back(); } int main(){ cin>>n; calc(1); cout<<cnt; return 0; }

组合型枚举

#include<iostream> #include<vector> using namespace std; vector<int> chosen; int n; int m; int cnt=0; void calc(int x){ if(chosen.size()>m || chosen.size()+(n-x+1)<m){ return; } if(x==n+1){ //for(int i=0;i<chosen.size();i++)cout<<chosen[i]<<" "; //cout<<endl; cnt++; return; } calc(x+1); chosen.push_back(x); calc(x+1); chosen.pop_back(); } int main(){ cin>>n>>m; calc(1); cout<<cnt; return 0; }

排列型枚举

#include<iostream> #include<algorithm> using namespace std; int cnt=0; int main(){ int n, p[10]; cin>>n; for(int i=0;i<n;i++)p[i]=i; sort(p,p+n); do{ //for(int i=0;i<n;i++)cout<<p[i]<<" "; //cout<<endl; cnt++; }while(next_permutation(p, p+n)); cout<<cnt<<endl; return 0; }

其他

任务：统计一个数组中，每个数组元素出现的次数

#include<map> using namespace std; string str; map<char, int> m;//无需初始化，可直接插入 for(int i=0;i<str.length();i++){ m[str[i]]++; } //至此，m中已经为str每个字符记录了对应的出现次数 for(int i=0;i<m.size();i++){ cout<<m[i]<<endl; }

任务：整数的逐位访问

int sum; //...... string str = to_string(sum);//sum的最高位对应str[0]，以此类推 for(int i=0;i<str.length();i++){ //访问str[i]的内容 }

一次性读完包含空格的字符串

#include <stdio.h> char s[10005] = {0}; gets(s);

以上是c的写法，下边是c++的写法

string str; getline(cin, str);