C++知识点捕捉

1.对于提高cin运行时间代码：

ios::sync_with_stdio(false); cin.tie(0);//cin.tie(nullptr);

减少运行时间           ，scanf永远的神

13倍 
  
 
  
 
  
 
  
 
  
 
  ，……………………………………

2           、提高读入时间的代码：

inline int max(int x,int y){return x>y?x:y;} inline int min(int x,int y){return x<y?x:y;} inline int abs(int x){return x>0?x:-x;} inline void swap(int &x,int &y){int t=x;x=y;y=t;} inline int read() { int x=0,f=1;char ch=getchar(); while (ch<0||ch>9){if (ch==-) f=-1;ch=getchar();} while (ch>=0&&ch<=9){x=x*10+ch-48;ch=getchar();} return x*f; }

3 
  
 
  
 
  
 
  
 
  
 
  、字符串输入带空格的











，只能使用数据类型是char型的           。

const int N=100005; char a[N]; cin.getline(a,N); scanf读入string字符串 提示 
  
  
  
  
  
，一定不要scanf和cin同时用 
  
  
  
  
  
 ，一次选用一种

 


 


 


 


 


 ，必须 
  
 
  
 
  
 
  
 
  
 
  。

4结构体的运用语句

struct Edge { int a,b,w; bool operator<(const Edge& W) const { return w<W.w;//升序 } }edges[M]; 降序：W.w<w;注意不可改变< 赋值：edges[i]={a,b,w};

5 万能头文件

能不用就不用 
 
 
 
 
 
，也会耗费时间 
   
   
   
   
   
 ，最好记住所用函数具体的库 由于C语言没有命名空间
 

 

 

 

 

 ，头文件并不存放在命名空间中
 

 

 

 

 

 
，因此在C++程序文件中如果用到带后缀．h的头文件时           ，不必用命名空间











。只需在文件中包含所用的头文件即可 #include<bits/stdc++.h>

6 sort与cmp

struct sno { int x,y,z,w,d; }q[305]; bool cmp(sno a,sno b) { if(a.w>b.w) return 1; else if(a.w<b.w) return 0; else { if(a.x>b.x) return 1; else if(a.x<b.x) return 0; else { if(a.d>b.d) return 0; else return 1; } } } //主函数：sort(q,q+n,cmp);

7.int范围

-2147483648 ~ 2147483647 2^32=4294967296 2^31=2,147,483,648

8.二分查找

只针对有序序列 
  
  
  
  
  
。

9. c++自带函数耗时长

能不用就不用 

 
 

 
 

 
 

 
 

 
 

 ，要不然就自己写一个 
  
  
  
  
  
 。比如memset

10.vector 创建二维数组 && 三维数组

二维数组 统一赋值 vector<vector<int> > d(n+1,vector<int> (n+1,INF)); INF设置初始值











，注意不要超过int类型                 ，否则会溢出 
 
 
 
 
 
 
 
 
 
 
 ，溢出就可能负一个负值

 


 


 


 


 


 。 >>注意一定要有空格> >,要不然会成cout>>,旧的编译器会报错

















，牛客就会报错 单独赋值 std::vector g2(m,std::array<int,3>{1,2,3}); 创建非矩形的二维数组 比如 1 1 2 1 2 3 这种类型的二维数组 //未对vector进行初始化赋值           ，默认为0 vector < vector<int> >f(m); //创建一个二维数组 
  
 
  
 
  
 
  
 
  
 
  ，m行











，然后使用resize对每行的长度进行重置 for(int i=0;i<m;i++) { f[i].resize(n); } 三维数组 单独赋值 std::vector dp(m+1, std::array<std::array<int,3>,3>{1,2,3,4,5,6,7,8,9}); 统一赋值 int m=20,n=20,p=20; std::vector< std::vector < std::vector<int> > > g1(m,std::vector< std::vector<int> >(n,std::vector<int>(p,1))); 同样可以创建非矩形的三维数组 std::vector<std::vector <std::vector<int> > > g3(m); for(int i=0;i<m;i++) { g3[i].resize(n); } for(int i=0;i < m;i++) { for(int j = 0;j < n;j++) { g3[i][j].resize(p); } } 实例代码 #include<bits/stdc++.h> #define INF 1e9 int main() { int m = 19; std::vector dp(m+1, std::array<std::array<int,3>,3>{1,2,3,4,5,6,7,8,9}); std::cout << dp[11][0][0] <<" "; std::cout << dp[18][0][1] <<" "; std::cout << dp[19][0][2] <<" "; std::cout << dp[10][1][0] <<" "; std::cout << dp[13][1][1] <<" "; std::cout << dp[15][1][2] <<" "; std::cout << dp[12][2][0] <<" "; std::cout << dp[17][2][1] <<" "; std::cout << dp[14][2][2] <<"\n"; int n = 20; std::vector g2(m,std::array<int,3>{1,2,3}); std::cout << g2[2][0]<<" "; std::cout << g2[2][1]<<" "; std::cout << g2[2][2]<<"\n"; std::vector < std::vector<int> > g(m,std::vector<int>(n,INF)); std::cout << g[10][0] <<" "; std::cout << g[11][1] <<" "; std::cout << g[12][2] <<"\n"; //未对vector进行初始化赋值 
  
  
  
  
  
，默认为0 std::vector < std::vector<int> > f(m); //创建一个二维数组 
  
  
  
  
  
 ，m行

 


 


 


 


 


 ，然后使用resize对每行的长度进行重置 for(int i = 0; i < m; i++) { f[i].resize(n); } std::cout << f[1][0] <<" "; std::cout << f[2][1] <<" "; std::cout << f[3][8] <<"\n"; int p=20; std::vector< std::vector < std::vector<int> > > g1(m,std::vector< std::vector<int> >(n,std::vector<int>(p,1))); std::cout << g1[11][0][0] <<" "; std::cout << g1[18][0][1] <<" "; std::cout << g1[16][0][2] <<"\n"; std::vector<std::vector <std::vector<int> > > g3(m); for(int i = 0; i < m; i++) { g3[i].resize(n); } for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { g3[i][j].resize(p); } } std::cout << g3[11][0][0] <<" "; std::cout << g3[18][0][1] <<" "; std::cout << g3[16][0][2] <<"\n"; return 0; } 运行结果 1 2 3 4 5 6 7 8 9 1 2 3 1000000000 1000000000 1000000000 0 0 0 1 1 1 0 0 0

11.强制类型转化

1ll*m*n,1ll相当于 long long 类型下的1 
 
 
 
 
 
， 所以1ll*m*n=long long 类型下的m*n

12.建立long long长度的数组技巧

map<ll,ll>a

13.一种主函数内部定义函数方式---方便使用vector及时创建数组时使用

必须引进头文件#include<functional> function<void(int, int, bool)> search = [&](int L, int R, bool odd) { while (L <= R) { int mid = L + R >> 1; int len = 2 * mid - (odd ? 1 : 0); bool answer = 0; for (int l = 1, r = l + len - 1; r <= n; ++l, ++r) { ULL Lres = LHash[r] - LHash[l - 1] * P[len]; ULL Rres = RHash[l] - RHash[r + 1] * P[len]; if (Lres == Rres) { answer = 1; int i = l + (len + 1) / 2 - 1; ans = max(ans, len / 2 + same[i]); } } if (answer) { L = mid + 1; } else R = mid - 1; } };//注意分号

14.字符串读入的注意点---有关于从下标1开始读取

char a[N][N]; for(int i=1;i<=n;i++) { cin>>a[i]+1;//相当于坐标从1开始 
   
   
   
   
   
 ，但是原来的0下标位存储的是/0,所以如果读a[i]
 

 

 

 

 

 ，那么一定会截止
 

 

 

 

 

 
，读到/0就结束           ，注意这里是第二维从1开始 

 
 

 
 

 
 

 
 

 
 

 ，但是我们读a[i]的话











，是从第二维的0下标位去读取                 ，所以什么也读不出来 }

15.数组初始化

16.时间复杂度