devbox
喵喵爱编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法笔记——胡凡_算法笔记胡凡

作者：喵喵爱编程 | 2024-07-23 00:15:19

赞

踩

算法笔记胡凡
  1. /* 日期差值 */
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  5. int main()
  6. {
  7.     int time1,time2;
  8.     int y1,d1,m1,y2,d2,m2;
  9.     cin>>time1>>time2;
  10.     if(time1>time2){
  11.         swap(time1,time2);
  12.     }    
  13.     y1=time1/1000,m1=time1%10000/100,d1=time1%100;
  14.     y2=time2/1000,m2=time2%10000/100,d2=time2%100;
  15.     int ans=1;
  16.     while(y1<y2 || m1<m2 || d1<d2){
  17.         d1++;
  18.         if((y1%4==0 &&y1%100!=0) || ( y1%400==0)){
  19.             month[2]=29;
  20.         }else{
  21.             month[2]=28;
  22.         }
  23.         if(d1==month[m1]+1){
  24.             m1++;
  25.             d1=1;
  26.         }
  27.         if(m1 == 13){
  28.             y1++;
  29.             m1 = 1;
  30.         }
  31.         ans++;
  32.     }
  33.         cout<<ans;
  34. }

将P进制数x转化为十进制数y:

  1. int product = 1 , y = 0;
  2. while( x != 0)
  3. {
  4.      y += (x%10)*product;
  5.      x = x / 10;  
  6.      product = product * P;
  7. }
  8. cout<<y<<;

将十进制 y 转换为 Q 进制数 z

  1. int z[10], num = 0;
  2. do{
  3.     z[num++] = y % Q ;
  4.     y = y / Q ;
  5. }while(y != 0);
  6. for(int i = num - 1 ; i >= 0 ;i--){
  7.     cout<<z[i];
  8. }

考虑到 2**3*5*7*11*13*17*19*23*29 就已经超过了 int 范围 ，因此只需要质数数组大小为10 就可以了

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int prime[10]={2,3,5,7,11,13,17,19,23,29};
  4. int main()
  5. {
  6.     int m;
  7.     int a[101];
  8.     cin>>m;
  9.     int k=0,num=0;
  10.     while(m!=1)
  11.     {
  12.         if(m%prime[k]!=0){
  13.             k++;
  14.         }else{
  15.             a[num++]=prime[k];
  16.             m/=prime[k];
  17.         }
  18.     } 
  19.     for(int i=0 ;i<num;i++){
  20.         cout<<a[i]<<" ";
  21.     }
  22. }

大数据的存储

如果A和B是有着1000个数位的整数 ， 恐怕就没有办法用已有的数据类型来表示了，这时就只能老实去模拟加减乘除的过程

存储

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct bign{
  4.     int d[1000];
  5.     int len;
  6.     bign()  //每次定义结构体变量时，都会自动对该变量进行初始化 
  7.     {
  8.         memset(d,0,sizeof(d));
  9.         len = 0;
  10.     }
  11. };
  12. bign change(char str[]){    //将整数转换为 bign 
  13.     bign a;
  14.     a.len = strlen(str);
  15.     //整数的高位变成数组的低位 
  16.     //这样方便比较两个bign变量的大小 ， 或者加减
  17.     for(int i=0 ; i<a.len ; i++){
  18.         a.d[i] = str[a.len - i -1] -'0';    //逆着赋值    
  19.     }
  20.     return a;
  21. } 
  22. int main()
  23. {
  24.     char s[1001];
  25.     cin>>s;
  26.     bign a=change(s); 
  27. }

高精度加法

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct bign{
  4.     int d[1000];
  5.     int len;
  6.     bign()  //每次定义结构体变量时，都会自动对该变量进行初始化 
  7.     {
  8.         memset(d,0,sizeof(d));
  9.         len = 0;
  10.     }
  11. };
  12. bign change(char str[]){    //将整数转换为 bign 
  13.     bign a;
  14.     a.len = strlen(str);
  15.     //整数的高位变成数组的低位 
  16.     for(int i=0 ; i<a.len ; i++){
  17.         a.d[i] = str[a.len - i -1] -'0';    //逆着赋值    
  18.     }
  19.     return a;
  20. } 
  21. bign add(bign a ,bign b){
  22.     bign c;
  23.     int carry = 0;  // carry 是进位
  24.     for(int i = 0 ; i < a.len || i < b.len ;i++){
  25.         int temp =a.d[i] + b.d[i] +carry;
  26.         c.d[c.len++] = temp % 10 ;
  27.         carry = temp / 10;
  28.     }
  29.     if(carry != 0){  //遍历到最后一位 ， 如果最后进位不为 0 ，则直接赋给结果的最高位 
  30.         c.d[c.len++] = carry ;
  31.     } 
  32.     return c;
  33. } 
  34. int main()
  35. {
  36.     char s1[1001],s2[1001];
  37.     cin>>s1>>s2;
  38.     bign a=change(s1);
  39.     bign b=change(s2);
  40.     bign c=add(a,b);
  41.     for(int i = c.len-1 ;i >= 0 ;i--){
  42.         cout<<c.d[i];
  43.     }    
  44. }

高精度减法

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct bign{
  4.     int d[1000];
  5.     int len;
  6.     bign()  //每次定义结构体变量时，都会自动对该变量进行初始化 
  7.     {
  8.         memset(d,0,sizeof(d));
  9.         len = 0;
  10.     }
  11. };
  12. bign change(char str[]){    //将整数转换为 bign 
  13.     bign a;
  14.     a.len = strlen(str);
  15.     //整数的高位变成数组的低位 
  16.     for(int i=0 ; i<a.len ; i++){
  17.         a.d[i] = str[a.len - i -1] -'0';    //逆着赋值    
  18.     }
  19.     return a;
  20. } 
  21. bign sub(bign a ,bign b){
  22.     bign c;
  23.     int carry = 0;
  24.     //155
  25.     //127
  26.     for(int i = 0 ; i<a.len || i<b.len ;i++){
  27.         if(a.d[i] < b.d[i]){
  28.             a.d[i+1]--;        //向高位借位 
  29.             a.d[i] += 10;        //当前位加 10 
  30.         }
  31.         c.d[c.len++]=a.d[i] - b.d[i]; 
  32.     }
  33.     while(c.len-1 >= 1 && c.d[c.len - 1] == 0){
  34.         c.len--;    //去除高位的 0 ，同时至少保留一位最低位 
  35.     }
  36.     return c; //注意返回 
  37. } 
  38. int main()
  39. {
  40.     char s1[1001],s2[1001];
  41.     cin>>s1>>s2;
  42.     bign a=change(s1);
  43.     bign b=change(s2);
  44.     bign c=sub(a,b);
  45.     for(int i = c.len-1 ;i >= 0 ;i--){
  46.         cout<<c.d[i];
  47.     }    
  48. }

高精度与低精度的乘法

  1. /* 高精度乘法*/ 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. struct bign{
  5.     int d[1000];
  6.     int len;
  7.     bign()  //每次定义结构体变量时，都会自动对该变量进行初始化 
  8.     {
  9.         memset(d,0,sizeof(d));
  10.         len = 0;
  11.     }
  12. };
  13. bign change(char str[]){    //将整数转换为 bign 
  14.     bign a;
  15.     a.len = strlen(str);
  16.     //整数的高位变成数组的低位 
  17.     for(int i=0 ; i<a.len ; i++){
  18.         a.d[i] = str[a.len - i -1] -'0';    //逆着赋值    
  19.     }
  20.     return a;
  21. } 
  22. bign multi(bign a ,int b){    //注意是 int 因为 b 是低精度 
  23.     bign c;
  24.     int carry = 0;
  25.     for(int i = 0; i<a.len; i++){
  26.         int temp = a.d[i]*b + carry;
  27.         c.d[c.len++] = temp % 10;
  28.         carry = temp / 10 ; 
  29.     }
  30.     while(carry!=0){    //和加法不一样，乘法的进位可能不止一位，因此用while 
  31.         c.d[c.len++] = carry%10;
  32.         carry /= 10 ;
  33.     }
  34.     return c; //注意返回 
  35. } 
  36. int main()
  37. {
  38.     char s1[1001];
  39.     cin>>s1;
  40.     bign a=change(s1);
  41.     int b;
  42.     cin>>b;
  43.     bign c=multi(a,b);
  44.     for(int i = c.len-1 ;i >= 0 ;i--){
  45.         cout<<c.d[i];
  46.     }    
  47. }

高精度与低精度的除法

  1. /* 高精度乘法*/ 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. struct bign{
  5.     int d[1000];
  6.     int len;
  7.     bign()  //每次定义结构体变量时，都会自动对该变量进行初始化 
  8.     {
  9.         memset(d,0,sizeof(d));
  10.         len = 0;
  11.     }
  12. };
  13. bign change(char str[]){    //将整数转换为 bign 
  14.     bign a;
  15.     a.len = strlen(str);
  16.     //整数的高位变成数组的低位 
  17.     for(int i=0 ; i<a.len ; i++){
  18.         a.d[i] = str[a.len - i -1] -'0';    //逆着赋值    
  19.     }
  20.     return a;
  21. } 
  22. bign divide(bign a ,int b){    //注意是 int 因为 b 是低精度 
  23.     bign c;
  24.     int r = 0;
  25. //被除数的每一位和商的每一位是一一对应的，因此先令长度相等
  26.     c.len = a.len ; 
  27.     for(int i=a.len-1 ; i>=0 ; i--){
  28.         r=r*10+a.d[i] ;    //和上一位遗留的余数组合 
  29.         if(r < b) c.d[i] = 0;    //不移除，该位为 0  
  30.         else{
  31.             c.d[i] = r / b;    //商 
  32.             r=r % b;            //新余数 
  33.         }
  34.     }
  35.     //去除高位 0
  36.     while(c.len - 1 >= 1 && c.d[c.len-1] == 0){
  37.         c.len--;
  38.     } 
  39.     return c; //注意返回 
  40. } 
  41. int main()
  42. {
  43.     char s1[1001];
  44.     cin>>s1;
  45.     bign a=change(s1);
  46.     int b;
  47.     cin>>b;
  48.     bign c=divide(a,b);
  49.     for(int i = c.len-1 ;i >= 0;i--){
  50.         cout<<c.d[i];
  51.     }    
  52. }

组合数的计算

  1. 关于n!的一个问题 :求 n！中有多少个质因子 p 

  1. int cal(int n,int p)
  2. {
  3.     int ans=0;
  4.     for(int i=2 ;i<=n;i++){
  5.         int temp = i;
  6.         while(temp % p == 0){    //只要temp 还是 p 的倍数
  7.             ans++;    
  8.             temp /= p;
  9.         }
  10.     }
  11.     return ans;
  12. }

但如果 n 很大的时候 ，会严重超时的 ，所以需要寻求速度更快的方法。

  1. int cal(int n,int p)
  2. {
  3.     int ans = 0;
  4.     while(n){
  5.         ans += n / p ;
  6.         n /= p;
  7.     }
  8.     return ans;
  9. }

新加：求n的阶乘末尾零的个数：

  1. 组合数的计算

  1. long long C(long long n,long long m)
  2. {
  3.     long long ans = 1;
  4.     for(long long i = 1 ; i <= n ; i++){
  5.         ans*=i;
  6.     }
  7.     for(long long i = 1 ; i <= m ; i++){
  8.         ans /= i;
  9.     }
  10.     for(long long i = 1 ; i <= n-m ; i++){
  11.         ans /= i;
  12.     }
  13.     return ans;
  14. }
  1. long long C(long long n,long long m)
  2. {
  3.     if(m==0 || m==n ) return 1;
  4.     return C(n-1 , m) +C(n - 1 , m - 1);
  5. }
  1. long long vis[100][100] = {0};
  2. long long C(long long n,long long m)
  3. {
  4.     if(m==0 || m==n ) return 1;
  5.     if(res[n][m] != 0) return res[n][m];
  6.     return res[n][m] = C(n-1 , m) +C(n - 1 , m - 1);
  7. }

C++标准模板库（STL）介绍

一 . vector

1.push_back()

  1. int main(){
  2.     vector<int > vi;
  3.     for(int i=0 ; i<=5 ;i++){
  4.         vi.push_back(i);
  5.     } 
  6.     for(int i=0 ;i<vi.size() ;i++){
  7.         cout<<vi[i]<<" ";
  8.     }
  9. }
  10. //输出 1 2 3

2.pop_back()

  1. int main(){
  2.     vector<int > vi;
  3.     for(int i=1 ; i<=3 ;i++){
  4.         vi.push_back(i);
  5.     } 
  6.     vi.pop_back();  //删除尾部元素 
  7.     for(int i=0 ;i<vi.size() ;i++){
  8.         cout<<vi[i]<<" ";
  9.     }
  10. }
  11. //输出 1 2

3.size()

4.clear() //清空所有元素

5.insert()

  1. int main(){
  2.     vector<int > vi;
  3.     for(int i=1 ; i<=3 ;i++){
  4.         vi.push_back(i);
  5.     } 
  6.     vi.insert(vi.begin() + 2 , -1);  //将 -1 插入vi[2]的位置 
  7.     for(int i=0 ;i<vi.size() ;i++){
  8.         cout<<vi[i]<<" ";
  9.     }
  10. }
  11. //输出1 2 -1 3

6. erase()

用法一：删除单个元素 erase( it ) 即删除迭代器为 it 处的元素

  1. int main(){
  2.     vector<int > vi;
  3.     for(int i=1 ; i<=3 ;i++){
  4.         vi.push_back(i);
  5.     } 
  6.     vi.erase(vi.begin() + 1);  //删除vi[1]的位置的元素 
  7.     for(int i=0 ;i<vi.size() ;i++){
  8.         cout<<vi[i]<<" ";
  9.     }
  10. }
  11. //输出 1 3

用法二：删除一个区间内的所有元素

erase( first , last )即删除 [ first , last )内的所有元素

  1. int main(){
  2.     vector<int > vi;
  3.     for(int i=1 ; i<=5 ;i++){
  4.         vi.push_back(i);
  5.     } 
  6.     vi.erase(vi.begin() + 1,vi.begin() + 3);  //删除vi[1],vi[2]的位置的元素 
  7.     for(int i=0 ;i<vi.size() ;i++){
  8.         cout<<vi[i]<<" ";
  9.     }
  10. }
  11. // 输出 ： 1 4 5

7. vi . begin( ) vi.end( )

  1. int main(){
  2.     vector<int > vi;
  3.     for(int i=1 ; i<=5 ;i++){
  4.         vi.push_back(i);
  5.     } 
  6.     //用迭代器 循环条件只能用 it != vi.end() 
  7.     for(vector<int>::iterator it = vi.begin() ; it != vi.end() ; it++ ){
  8.         cout<<*it<<" ";    //注意输出格式 
  9.     }
  10. }

二 . set 常见用法详解：一个内部自动有序且不重复元素的容器

1. set的定义

  1. set<int> name ;
  2. set<double> name ;
  3. set<char> name ;
  4. set<node> name ; // node是结构体的类型

2. insert( )

  1. int main(){
  2.     set<int > st;
  3.     st.insert(1);
  4.     st.insert(1);
  5.     st.insert(5);
  6.     st.insert(3);
  7.     //注意：不支持 it < st.end() 的写法 
  8.     for(set<int>::iterator it = st.begin() ; it != st.end() ; it++ ){
  9.         cout<<*it<<" ";    //注意输出格式 
  10.     }
  11. }
  12. //输出 1 3 5
  13. //set内的元素自动递增排序 ，且自动删除了重复元素

3.find( )

  1. int main(){
  2.     set<int > st;
  3.     for(int i=1 ; i<=5 ;i++){
  4.         st.insert(i);
  5.     } 
  6.     set<int>::iterator it = st.find(2);  //返回迭代器 
  7.     cout<<*it;
  8. }
  9. //输出 2

4.erase()

  1. int main(){
  2.     set<int > st;
  3.     for(int i=1 ; i<=5 ;i++){
  4.         st.insert(i);
  5.     } 
  6.     st.erase(st.find(2));    //利用find() 函数找到 2,然后再删除它 
  7.     for(set<int>::iterator it = st.begin() ; it != st.end() ; it++ ){
  8.         cout<<*it<<" ";    
  9.     }
  10. }
  11. //输出 1 3 4 5
  1. int main(){
  2.     set<int > st;
  3.     st.insert(20);
  4.     st.insert(10);
  5.     st.insert(40);
  6.     st.insert(30);
  7.     set<int>::iterator it = st.find(20);
  8.     st.erase(it,st.end());    //删除元素 20 至set末尾之间的元素 
  9.     for(it = st.begin() ; it != st.end() ; it++ ){
  10.         cout<<*it<<" ";    
  11.     }
  12. }
  13. //输出 10
5.size( )
6.clear( )
7.set容器内元素访问

string 的常见用法详解

拼接函数：

  1. int main(){
  2.     string s1 = "abc",s2 = "xyz";
  3.     string s3 = s1 + s2;
  4.     cout<<s3;  
  5. }
  6. //输出 abcxyz
比大小：
  1. int main(){
  2.     string s1 = "aa" , s2 = "aaa";
  3.     string s3 = "abc" , s4 = "xyz";
  4.     if(s1<s2) cout<<"1"<<endl;
  5.     if(s2<s3) cout<<"2"<<endl;  
  6. }
insert ( )
erase( )
  1. 删除单个元素

s.erase( it ) 删除单个元素 , it 为迭代器

  1. int main(){
  2.     string s1 = "abcdef" ;
  3.     s1.erase(s1.begin()+2);    //删除 2 号位
  4.     cout<<s1; 
  5. }
  6. //输出 abdef
  1. 删除一个区间内的所有元素
  1. int main(){
  2.     string s1 = "abcdef" ;
  3.     s1.erase(s1.begin()+2 ,s1.begin()+4);    //删除 [2,4)
  4.     cout<<s1; 
  5. }
  6. //输出abef
  1. int main(){
  2.     string s1 = "abcdef" ;
  3.     s1.erase(3,2);    //删除从 3 号位开始的 2 个字符
  4.     cout<<s1; 
  5. }
  6. //输出abcf
clear( )
substr( )
  1. int main(){
  2.     string str = "Thank you for your smile" ; 
  3.     cout<<str.substr(0,5)<<endl; 
  4.     cout<<str.substr(14,4)<<endl;
  5.     cout<<str.substr(19,5)<<endl;
  6. }
  7. //Thank
  8.   your
  9.   smile
find()
  1. int main(){
  2.     string str = "Thank you for your smile" ; 
  3.     string str2 = "you";
  4.     string str3 = "me";
  5.     if(str.find(str2) != string::npos){
  6.         cout<< str.find(str2) << endl;
  7.     }
  8.     //从第七位开始找 
  9.     if(str.find(str2 , 7) != string::npos){    
  10.         cout<< str.find(str2, 7) << endl;
  11.     }
  12.     if(str.find(str3) != string::npos){    
  13.         cout<< str.find(str3) << endl;
  14.     }else{
  15.         cout<<"没有找到"<< endl; 
  16.     } 
  17. }
  18. // 6 
  19.   14
  20.   没有找到
replace()
  1. int main(){
  2.     string str = "Thank you for your smile" ; 
  3.     string str2 = "me";
  4.        cout << str.replace(6,3,str2);
  5. }
  6. //Thank me for your smile

map的常用用法详解

  1. map的定义

  1. map<string , int > mp ; 
  2. map<char , int > mp;

2.map容器内元素的访问

（ 1 ）通过下标访问

  1. int main(){
  2.     map<char,int> mp;
  3.     mp['c'] = 20;
  4.     cout<<mp['c'];
  5. }

（ 2 ）通过迭代器访问

  1. int main(){
  2.     map<char,int> mp;
  3.     mp['c'] = 20;
  4.     mp['m'] = 30;
  5.     mp['a'] = 40;
  6.     for(map<char,int>::iterator it = mp.begin();it!=mp.end();it++)
  7.     {
  8.         cout<<it->first<<" "<<it->second<<endl;;
  9.     }
  10. }
  11. // a  40
  12.    c  30
  13.    m  20

注意的是：map会以从小到大的顺序自动进行排序。即按a < c < m;

3.map常用函数实例解析

(1).find( )
  1. int main(){
  2.     map<char,int> mp;
  3.     mp['c'] = 20;
  4.     mp['m'] = 30;
  5.     mp['a'] = 40;
  6.     map<char, int>::iterator it = mp.find('a');
  7.     cout<<it->first<<" "<<it->second;
  8. }
(2).erase()
a.删除单个元素
  1. int main(){
  2.     map<char,int> mp;
  3.     mp['c'] = 20;
  4.     mp['m'] = 30;
  5.     mp['a'] = 40;
  6.     map<char, int>::iterator it = mp.find('a');
  7.     mp.erase(it);        //删除 a , 40
  8. //  或者写成： mp.erase('a');
  9.     for(map<char,int>::iterator it=mp.begin() ;it!=mp.end();it++) 
  10.         cout<<it->first<<" "<<it->second<<endl;
  11. }
  12. //
  13. c 20
  14. m 30
b.删除一个区间的元素
  1. int main(){
  2.     map<char,int> mp;
  3.     mp['b'] = 30;
  4.     mp['a'] = 20;
  5.     mp['c'] = 40;
  6.     map<char, int>::iterator it = mp.find('b');
  7.     mp.erase(it,mp.end());    //删除 it 之后的所有映射 
  8.     for(map<char,int>::iterator it=mp.begin() ;it!=mp.end();it++) 
  9.         cout<<it->first<<" "<<it->second<<endl;
  10. }
  11. // a 20

(3)size()

(4)clear()

queue的常见用法详解：队列（先进先出）

1.queue定义

queue<... > name;

2.queue容器内的元素的访问

  1. int main(){
  2.     queue<int> q;
  3.     for(int i=1 ; i<=5 ;i++){
  4.         q.push(i);
  5.     } 
  6.     cout<<q.front()<<" "<<q.back();
  7. }
  8. // 1 5

3.常用函数解析

（1）push( ) : 入队

（2） front( ) , back()

(3) pop( ) : 令队首元素出队
  1. int main(){
  2.     queue<int> q;
  3.     for(int i=1 ; i<=5 ;i++){
  4.         q.push(i);        // 1 2 3 4 5依次入队 
  5.     } 
  6.     for(int i=1 ; i<=3 ;i++){
  7.         q.pop();        //1 2 3依次出队 
  8.     }     
  9.     cout<<q.front();    // 输出 4 
  10. }
（4） empty( )

如果为空返回 true

(5) size( )

priority_queue的常见用法详解

1.定义

2.priority_queue内元素优先级的设置

（1）基本数据类型的优先级设置

如果想让队列总是把最小的元素放在队首：只需如下定义：

  1.  priority_queue< int , vector<int> ,greater<int>> q;
  2.     q.push(3);
  3.     q.push(4);
  4.     q.push(1);
  5.     cout<<q.top();
  6. //输出 1

（2）结构体优先级设置

可以对水果的名称和价格建立一个结构体

  1. struct fruit{
  2.     string name;
  3.     int price;
  4. };
  1. struct fruit{
  2.     string name;
  3.     int price;
  4. }f1,f2,f3;
  5. struct cmp{
  6.     bool operator () (fruit f1,fruit f2){
  7.         return f1.price > f2.price;
  8.     } 
  9. };    //优先队列的这个函数与sort函数中的cmp函数的效果是相反的 
  10. int main(){
  11.     priority_queue<fruit, vector<fruit> , cmp> q;
  12.     f1.name = "桃子";
  13.     f1.price = 3;
  14.     f2.name = "梨子";
  15.     f2.price = 4;
  16.     f3.name = "苹果";
  17.     f3.price = 1;
  18.     q.push(f1);
  19.     q.push(f2);
  20.     q.push(f3);
  21.     cout<<q.top().name<<" "<<q.top().price<<endl; 
  22. }
  23. // 输出 苹果 1

习题：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct cmp{
  4.     bool operator()(pair<int,int>& p1 , pair<int,int>& p2){
  5.             return p1.second > p2.second;
  6.     }
  7. };
  8. int main()
  9. {
  10.     int nums[9] = {1,1,1,2,2,3,3,3,3};
  11.     int k = 2;
  12.     unordered_map<int,int> map;
  13.     for(int i = 0 ; i < 9 ;i++){
  14.         map[nums[i]]++;
  15.     }
  16.     priority_queue< pair<int,int>, vector<pair<int,int>> , cmp> q;
  17.     
  18.     for(auto it = map.begin() ; it!=map.end() ;it++){
  19.         q.push(*it);
  20.         if(q.size()>k){
  21.             q.pop();
  22.         }
  23.     }
  24.     for(int i = 0 ; i< k ;i++){
  25.         cout<<q.top().first;
  26.         q.pop();
  27.     }
  28. }

stack 的常见用法详解

stack 翻译为栈 ，是STL中实现一个后进后出的容器。

  1. stack 的定义

stack< ... > name;

2. stack 容器内元素的访问

  1. int main()
  2. {
  3.     stack<int> st;
  4.     for(int i=1 ;i<=5 ;i++){
  5.         st.push(i);        //push(i)可以把 i 压入栈
  6.     }
  7.     cout<<st.top();    
  8. } 
  9. // 输出 ：5

3.stack常用函数实例解析

（1）push()：入栈

（2）top(): 获得栈顶元素

（3）pop(): 用以弹出栈顶元素。

（4） empty() : 用以检测stack内是否为空

（5） size()

pair 的常见用法详解

  1. pair 的定义

  1. //pair< typeName1 , typeName2 > name；
  2. pair< string , int > p;
  3. pair< string , int > p("haha" ,5 );

2.pair中元素的访问

pair中只有两个元素 ， 分别是first 和 second , 只需要按正常结构体的方式与访问即可 。

  1. int main()
  2. {
  3.     pair<string, int> p;
  4.     p.first = "haha";
  5.     p.second = 5;
  6.     cout<<p.first<<" "<<p.second<<endl;
  7.     p = make_pair("xixi",55);
  8.     cout<<p.first<<" "<<p.second<<endl;
  9.     p = pair<string, int>("heihei",555);
  10.     cout<<p.first<<" "<<p.second<<endl; 
  11. } 
  12. // 输出： haha 5
  13.          xixi 55
  14.          heihei 555

3.pair 的常见用途

a. 用来代替二元结构体及其构造函数

b.作为map 的键值对来进行插入，例如下面的例子

  1. int main()
  2. {
  3.     map<string, int> mp;
  4.     mp.insert(make_pair("hhhh",5));
  5.     mp.insert(pair<string, int>("haha", 10));
  6.     for(map<string, int>::iterator it = mp.begin(); it!=mp.end() ;it++){
  7.         cout<<it->first<<" "<<it->second<<endl;
  8.     }
  9. } 
  10. // hhhh 5
  11.    haha 10

algorithm 头文件下的常用函数

1.max( ) , min( ) ,abs( ) ;

2.swap(x , y) 交换 x 和 y的值

3. reserve（）反转

  1. int main()
  2. {
  3.     int a[10]={10,11,12,13,14,15};
  4.     reverse(a, a + 4);    //将 a[0] ~ a[3]进行反转
  5.     for(int i=0 ;i< 6;i++){
  6.         printf("%d ",a[i]);
  7.     }  
  8. } 
  9. // 输出 ：13 12 11 10 14 15

4. fill ( ) 

  1. int main()
  2. {
  3.     int a[5]={1,2,3,4,5};
  4.     fill(a, a + 5,233);    //将 a[0] ~ a[4]均赋值为 233 
  5.     for(int i=0 ;i< 5;i++){
  6.         printf("%d ",a[i]);
  7.     }  
  8. }

5.memset()

对数组进行初始化

  1. int main(){
  2.     int x[5];
  3.     memset(x, 1, sizeof(x));
  4.     for(int i=0; i<5; i++){
  5.         printf("%d ", x[i]);
  6.     }
  7.     return 0;
  8. }

6. sort( )

（1）对 char 型数组从大到小排序的代码

  1. bool cmp(char a , char b){
  2.     return a > b;
  3. } 
  4. int main()
  5. {
  6.     char c[]={'b','a','d','c'};
  7.     sort(c,c + 4,cmp);
  8.     for(int i=0 ;i< 4;i++){
  9.         printf("%c ",c[i]);
  10.     }  
  11. } 
  12. // 输出 ：d c b a

（2） 结构体数组的排序

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node{
  4.     int x,y;
  5. }a[10];
  6. //按照 x 从大到小排序 
  7. bool cmp(node a,node b){
  8.     return a.x > b.x;
  9. }
  10. int main()
  11. {
  12.     a[0].x = 2; a[0].y = 2;    //    { 2 , 2 }
  13.     a[1].x = 1; a[1].y = 3; //    { 1 , 3 }
  14.     a[2].x = 3; a[2].y = 1; //  { 3 , 1 }
  15.     sort( a ,a+3,cmp);
  16.     for(int i = 0 ;i < 3 ;i++){
  17.         cout<<a[i].x<<" "<<a[i].y<<endl;
  18.     }
  19. } 
  20. // 输出 ：3 1
  21.          2 2
  22.          1 3
  1. //按照 x 从大到小排序 ,如果 x 相等  
  2. //按照 y 的大小从小到大来排序 
  3. bool cmp(node a,node b){
  4.     if(a.x != b.x) return a.x > b.x; 
  5.     else return a.y < b.y;
  6. }

深度优先搜索（DFS）

以走迷宫为例，DFS 会搜遍所有的路径，即遇到不碰死胡同不回头。这样就是说：深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。

1.背包问题

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,v;
  4. int w[10],c[10];
  5. int maxValue = 0;
  6. void dfs(int index,int sumW,int sumC){    //a代表第几个物品，sum代表现在容量总和 
  7.     //先写终止条件
  8.     if(index == n){    //已经完成对 n 件物品的选择(死胡同) 
  9.         if(sumW <= v && sumC > maxValue){
  10.             maxValue = sumC;
  11.         }
  12.         return;
  13.     } 
  14.     //不选该物品
  15.     dfs(index+1 , sumW , sumC); 
  16.     //选择该物品
  17.     dfs(index+1 , sumW+w[index] , sumC+c[index]);
  18. }
  19. int main()
  20. {
  21.     cin>>n;
  22.     cin>>v;        //最大容量 
  23.     for(int i=0;i<n;i++){
  24.         cin>>w[i];    //重量 
  25.     }
  26.     for(int i=0 ;i<n;i++){
  27.         cin>>c[i];    //价值 
  28.     }    
  29.     dfs(0,0,0); 
  30.     cout<<maxValue;
  31. }

优化：

  1. void dfs(int index,int sumW,int sumC){    //a代表第几个物品，sum代表现在容量总和 
  2.     if(index == n){
  3.         return;
  4.     }
  5.     //不选择第 index 件物品 
  6.     dfs(index+1 , sumW ,sumC );
  7.     //只有加入第index件物品后未超过容量 V,才能继续
  8.     if(sumW + w[index] <= v){
  9.         if(sumC + c[index] > maxValue){
  10.             maxValue = sumC + c[index];
  11.         }
  12.         //选第 index 件物品 
  13.         dfs(index+1 ,sumW + w[index] ,sumC + c[index]); 
  14.     } 
  15. }

2.选择数

给定 N 个整数 ( 可能有负数 )，从中选择K个数，使得这K个数之和恰好等于一个给定的整数X；如果有多种情况，选择它们中元素平方和最大的一个。例如 ： 从4个整数{2，3，3，4}中选择 2 个数 ，使它们的和为 6 ，显然有两种方案{ 2 ，4 } 与 {3 ，3} ，其中平方和最大的方案为{ 2 ， 4 }；

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,k,x;
  4. int a[10];
  5. int maxSum = 0;
  6. vector<int> temp,ans; //ans为最优方案的数组 
  7. void dfs(int index ,int sumK,int sum,int powSum){
  8.     if(sumK==k && sum == x){        //找到 k 个数的和为 x 
  9.         if(powSum > maxSum){
  10.             maxSum = powSum;
  11.             ans = temp; 
  12.         }
  13.         return;
  14.     }
  15.     //已经处理完 n 个数，或者超过 k个数 ，或者和超过 x 返回 
  16.     if(index==n || sumK >k || sum>x) return;
  17.     //选择 index 号数
  18.     temp.push_back(a[index]);
  19.     dfs(index+1,sumK+1,sum+a[index],powSum+pow(a[index],2));
  20.     temp.pop_back();
  21.     //不选择 index 号数 
  22.     dfs(index+1,sumK,sum,powSum);
  23. }
  24. int main()
  25. {
  26.     cin>>n;
  27.     cin>>k;    
  28.     cin>>x;
  29.     for(int i = 0 ; i<n ; i++){
  30.         cin>>a[i];
  31.     }
  32.     dfs(0,0,0,0);
  33.     for(int i=0 ;i<k;i++){
  34.         cout<<ans[i]<<" ";
  35.     }    
  36. }

3.烤鸡

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int res = 0; //存方案数 
  5. int arr[20];    //存临时方案 
  6. int mem[59055][20];    //存所有方案
  7.  
  8. //index 表示当前枚举到哪一位
  9. // sum表示当前调料的总质量 
  10. void dfs(int sum,int index){
  11.     if(sum > n ) return;
  12.     if(index > 10){
  13.         if(sum == n){
  14.             res++;
  15.             for(int i=1 ;i<=10 ;i++){
  16.                 mem[res][i] = arr[i]; 
  17.             } 
  18.         }    
  19.         return;
  20.     }
  21.     for(int i=1 ; i<=3 ;i++){
  22.         arr[index] = i;
  23.         dfs(sum+i,index+1);
  24.         arr[index] = 0;
  25.     }
  26. }
  27. int main()
  28. {
  29.     cin>>n;
  30.     dfs(0,1);
  31.     cout<<res<<endl;
  32.     for(int i = 1 ; i <= res; i++){
  33.         for(int j=1 ; j<=10 ;j++){
  34.             cout<<mem[i][j]<<" ";
  35.         }
  36.         cout<<endl;
  37.     }        
  38. } 
  39. // 12345
  40.    12354
  41.    12435
  42.    12453
  43.    12534
  44.    12543

4. P1149 火柴棒等式

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int res = 0;
  4. int n;
  5. int arr[101];
  6. int a[10]={6,2,5,5,4,5,6,3,7,6};
  7. int nums(int num){
  8.     if(num < 10){
  9.         return a[num];
  10.     }else{
  11.         int x=0;
  12. //这是对于比如 A = 11 这种多位数来计算火柴根数
  13.         while(num){
  14.             x+=a[num%10];
  15.             num/=10;        
  16.         }
  17.         return x;
  18.     }
  19. }
  20. //注意两个条件 ：
  21. //        1.  A + B = C
  22. //        2.  指定火柴棒数 
  23.      
  24. void dfs(int index , int sum){
  25.     if(sum> n) return;  //如果当前火柴数已经多了，则剪枝 
  26.     if(index > 3){    //表示都选完了，并对此进行判断 
  27.         //满足两个条件时 
  28.         if(arr[1] + arr[2]==arr[3] && sum == n){
  29.             res++;
  30.         }
  31.         return; 
  32.     } 
  33. //对于题目中说最多有20跟火柴 可以知道极限为1000
  34.     for(int i=0 ;i<=1000;i++){
  35.         arr[index]=i;
  36.         dfs(index+1,sum+nums(i));
  37.         arr[index]=0;
  38.     } 
  39. }
  40. int main()
  41. {
  42.     cin>>n;
  43.     n=n-4;
  44.     dfs(1,0); 
  45.     cout<<res; 
  46. }

对于计算火柴棍数可以进行优化 因为比如当计算199 对应的火柴棍数时，199/10=19 而19的火柴棍数在之前已经被算过了，不用费时间再算了。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int res = 0;
  4. int n;
  5. int arr[101];
  6. int a[1001]={6,2,5,5,4,5,6,3,7,6};
  7. //注意两个条件 ：
  8. //        1.  A + B = C
  9. //        2.  指定火柴棒数 
  10. void dfs(int index , int sum){
  11.     if(sum> n) return;  //如果当前火柴数已经多了，则剪枝 
  12.     if(index > 3){    //表示都选完了，并对此进行判断 
  13.         //满足两个条件时 
  14.         if(arr[1] + arr[2]==arr[3] && sum == n){
  15.             res++;
  16.         }
  17.         return; 
  18.     }     
  19.     for(int i=0 ;i<=1000;i++){
  20.         arr[index]=i;
  21.         dfs(index+1,sum+a[i]);
  22.         arr[index]=0;
  23.     } 
  24. }
  25. int main()
  26. {
  27.     cin>>n;
  28.     n=n-4;
  29.     //递推出 10 ~ 1000 需要用到的火柴棍 
  30.     for(int i = 10 ;i<=1000 ;i++){
  31.         a[i]=a[i%10]+a[i/10];
  32.     } 
  33.     dfs(1,0); 
  34.     cout<<res; 
  35. }

5. P 2036 食材配料

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int minNum = 0x7fffffff;
  4. //0x7fffffff 就表示 是一个十六进制的int的最大值 
  5. int n;
  6. int s[15],b[15];
  7. void dfs(int index ,int suan,int ku)
  8. {
  9.     if(index > n){
  10.         //必须判断清水的情况 
  11.         if(suan==1 && ku==0) return;
  12.         //更新最小值 
  13.         minNum = min(abs(suan-ku),minNum);
  14.         return;
  15.     }
  16.     // 选 
  17.     dfs( index+1 , suan*s[index] , ku+b[index]);
  18.     // 不选 
  19.     dfs(index+1,suan,ku);
  20.     
  21. }
  22. int main()
  23. {
  24.     cin>>n;
  25.     for(int i=1; i<=n ; i++){
  26.         cin>>s[i] >>b[i];
  27.     }
  28.     dfs(1,1,0);
  29.     cout<<minNum;
  30. }

6. P1135 奇怪的电梯

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,a,b;
  4. int res = 0;
  5. int minNum = 0x7fffffff;
  6. int k[202];
  7. bool vis[205];
  8. void dfs(int begin,int num){
  9.     if(num >= minNum) return;
  10.     if(begin == b){
  11. //        if(num < minNum){
  12. //            minNum = num;
  13. //        }
  14. //        每次我都按上面写都不能得出答案
  15.         minNum = min(minNum,num); 
  16.         return;
  17.     }
  18.     vis[begin] = 1;
  19.     //下楼 
  20.     if(begin - k[begin] > 0 && !vis[begin - k[begin]]){
  21.         vis[begin - k[begin]] = 1;
  22.         dfs(begin-k[begin],num+1);
  23.         vis[begin - k[begin]] = 0;    //回溯
  24.     }        
  25.     //上楼
  26.     if(begin + k[begin] <= n && !vis[begin + k[begin]]){
  27.         vis[begin + k[begin]] = 1;
  28.         dfs(begin+k[begin],num+1); 
  29.         vis[begin + k[begin]] = 0;    //回溯
  30.     }    
  31.     
  32. }
  33. int main()
  34. {
  35.     cin>>n>>a>>b;
  36.     for(int i=1 ; i<=n ; i++){
  37.         cin>>k[i];
  38.     }
  39.     dfs(a,0);
  40.     if(minNum == 0x7fffffff ){
  41.         cout<<"-1";
  42.         return 0;
  43.     }
  44.     cout<<minNum;
  45. }

DFS正确入门方式 | DFS + 递归与递推习题课(下) | 一节课教你爆搜!_哔哩哔哩_bilibili

7 . P1683 入门

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,n,h,k;
  4. char ch[22][22];
  5. int res = 1;
  6. bool vis[22][22];
  7. // 用数组来表示上下左右的情况 
  8. int dx[4]={0,1,0,-1};
  9. int dy[4]={1,0,-1,0};
  10. void dfs(int x, int y )
  11. {
  12.     for(int i=0 ;i<4;i++){    //枚举四个坐标 
  13.         int xx = dx[i] + x;
  14.         int yy = dy[i] + y;
  15.         if(ch[xx][yy]=='.'&& vis[xx][yy]!=true ){
  16.             res++;
  17.             vis[xx][yy]=true; //设为已经走过的路 
  18.             dfs(xx,yy);
  19.         }
  20.     }
  21.     return;
  22. }
  23. int main()
  24. {    
  25.     cin>>m>>n;
  26.     for(int i=1 ; i <= n ;i++){
  27.         for(int j=1 ; j <= m ;j++){
  28.             cin>>ch[i][j];
  29.             if(ch[i][j]=='@'){
  30.                  h=i,k=j;
  31.             }
  32.         }
  33.     }
  34.     dfs(h,k);
  35.     cout<<res;
  36. }

8 . P1596 : 洪水填充模型

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char ch[102][102];
  4. bool vis[101][101];
  5. int n,m,res=0;
  6. int dx[8]={-1,-1,-1,0,1,1,1,0};
  7. int dy[8]={-1,0,1,1,1,0,-1,-1};
  8. void dfs(int x , int y)
  9. {
  10.     for(int i = 0 ; i < 8 ; i++){
  11.         int xx = x + dx[i];
  12.         int yy = y + dy[i];
  13.         if(ch[xx][yy]=='W' && !vis[xx][yy]){
  14.             vis[xx][yy] = true;
  15.             dfs(xx,yy);
  16.         }else{
  17.             continue;
  18.         }
  19.     }
  20. }
  21. int main()
  22. {
  23.  
  24.     cin>>n>>m;
  25.     for(int i =0 ; i < n  ; i++){
  26.         for(int j = 0 ; j < m ; j++ ){
  27.             cin>>ch[i][j];
  28.             vis[i][j] = false;
  29.         }
  30.     }
  31.     for(int i = 0 ; i < n  ; i++){
  32.         for(int j = 0 ; j < m ; j++ ){
  33.             if(!vis[i][j] && ch[i][j]=='W'){
  34.                 dfs(i,j);
  35.                 res++;
  36.             }
  37.         }
  38.     }
  39.     cout<<res;
  40. }

9. Acwing 1114.棋盘问题

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,k,cnt = 0,res;
  4. char ch[10][10];
  5. bool vis[10];
  6. //表示搜索每一行 
  7. void dfs(int x , int cnt){
  8.     if(cnt == k){
  9.         res++;
  10.         return ;
  11.     }
  12.     if(x >= n) return;
  13.  
  14.     for(int i=0 ; i<n ;i++){
  15.         if( ch[x][i]=='#' && !vis[i]){
  16.             vis[i] = true;
  17.             dfs(x+1,cnt+1);
  18.             vis[i] = false;
  19.         }
  20.     } 
  21.     dfs( x+1 , cnt );
  22. }
  23. int main()
  24. {
  25.     while(scanf("%d%d",&n,&k)){
  26.         if(n == -1 && k == -1) break;
  27.         for(int i = 0; i < n ; i++)
  28.         {
  29.             for(int j = 0 ; j < n ; j++){
  30.                 cin>>ch[i][j];
  31.             }
  32.         }
  33.         res = 0;
  34.         dfs(0,0);
  35.         cout<<res<<endl;
  36.     }
  37. }

10 . P1025 数的划分

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,k;
  4. int res=0;
  5. int arr[101];
  6. void dfs( int x , int start ,int nowSum)
  7. {
  8.     if(nowSum > n) return;
  9.     if(x > k){
  10.         if(nowSum == n){
  11.             res++;
  12.         }
  13.         return;
  14.     }
  15.     
  16.     for(int i = start ; i<=n ;i++){
  17.         dfs( x+1 , i , nowSum + i);
  18.     }
  19. }
  20. int main()
  21. {
  22.     cin>>n>>k;
  23.     dfs(1,1,0);
  24.     cout<<res;
  25. }

若要打印方案：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,k;
  4. int res=0;
  5. int arr[101];
  6. void dfs( int x , int start ,int nowSum)
  7. {
  8.     if(nowSum > n) return;
  9.     if(x > k){
  10.         if(nowSum == n){
  11.             res++;
  12.             for(int i = 1 ;i <= k ;i++){
  13.                 cout<<arr[i];
  14.             }
  15.             cout<<endl;
  16.         }
  17.         return;
  18.     }
  19.     
  20.     for(int i = start ; i<=n ;i++){
  21.         arr[x] = i ;
  22.         dfs( x+1 , i , nowSum + i);
  23.         arr[x] = 0;    //回溯 
  24.     }
  25. }
  26. int main()
  27. {
  28.     cin>>n>>k;
  29.     dfs(1,1,0);
  30.     cout<<res;
  31. }

10.P1019 单词接龙

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 21;
  8.  
  9. int n;
  10. string word[N];
  11. int g[N][N];//两个单词重合部分最小长度
  12. int used[N];//单词使用次数
  13. int ans;
  14. string d;
  15. void dfs(string dragon, int last) //last表示结尾用的单词
  16. {
  17.     if(dragon.size() > ans){
  18.     ans = dragon.size();
  19.     d=dragon;
  20.     }
  21.  
  22.     used[last] ++ ;
  23.  
  24.     for (int i = 0; i < n; i ++ )
  25.         if (g[last][i] != 0 && used[i] < 2){
  26.             dfs(dragon + word[i].substr(g[last][i]), i);
  27.  
  28.     used[last] -- ; //回溯减一
  29. }
  30.  
  31. int main()
  32. {
  33.     cin >> n;
  34.     for (int i = 0; i < n; i ++ ) cin >> word[i];
  35.     char start;
  36.     cin >> start;
  37.  
  38.     for (int i = 0; i < n; i ++ )
  39.         for (int j = 0; j < n; j ++ )
  40.         {
  41.          string a = word[i], b = word[j];
  42.         //重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度
  43.           for (int k = 1; k < min(a.size(), b.size()); k ++ )
  44.             if (a.substr(a.size() - k, k) == b.substr(0, k))
  45.                 {
  46.                     g[i][j] = k;
  47.                     break;
  48.                 }
  49.         }
  50.  
  51.     for (int i = 0; i < n; i ++ )
  52.         if (word[i][0] == start)
  53.             dfs(word[i], i);
  54.  
  55.     cout << ans << endl;
  56.  
  57.     return 0;
  58. }

11.P1605 迷宫

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dx[4]={0,0,1,-1};
  4. int dy[4]={1,-1,0,0};
  5. int mp[10][10];
  6. int fx,fy,sx,sy,ans=0,n,m,T,l,r;
  7. //int minX = 0x7fffffff;
  8. int vis[10][10]={false};
  9. void dfs(int x,int y){
  10.     if(x==fx && y==fy){
  11.         ans++;
  12.         return;
  13.     }
  14.     for(int i = 0 ; i < 4 ; i++){
  15.         int xx = x + dx[i];
  16.         int yy = y + dy[i];
  17.         if(mp[xx][yy]==1 && !vis[xx][yy]&&xx>=1&&xx<=n&&yy>=1&&yy<=m){
  18.             vis[xx][yy] = true;
  19.             dfs(xx,yy);
  20.             vis[xx][yy] = false;
  21.         }
  22.     }
  23. }
  24. int main()
  25. {
  26.     cin>>n>>m>>T;
  27.     for(int i= 1 ; i<=n;i++){
  28.         for(int j =1 ; j<=m ;j++){
  29.             mp[i][j]=1;
  30.         }
  31.     }
  32.     cin>>sx>>sy;
  33.     cin>>fx>>fy;
  34.     for(int i = 1 ; i<=T ;i++){
  35.         cin>>l>>r;    //障碍坐标 
  36.         mp[l][r] = 0;
  37.     }
  38.     vis[sx][sy]=1;//起点算重复 (一定要写！！！)
  39.     dfs(sx,sy);
  40.     cout<<ans; 
  41. }

12.电话号码字母组合

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. string letterMap[10] = {
  4.         "", // 0
  5.         "", // 1
  6.         "abc", // 2
  7.         "def", // 3
  8.         "ghi", // 4
  9.         "jkl", // 5
  10.         "mno", // 6
  11.         "pqrs", // 7
  12.         "tuv", // 8
  13.         "wxyz"    // 9
  14.     };
  15. string digits;
  16. vector<string> result;
  17. void dfs(int index , string s)
  18. {
  19.     if(index == digits.size()){
  20.         result.push_back(s);
  21.         return;
  22.     }
  23.     
  24.     int digit = digits[index] - '0';
  25.     string letters = letterMap[digit];
  26.     for(int i = 0 ; i < letters.size() ;i++){
  27.         s.push_back(letters[i]);
  28.         dfs(index+1,s);
  29.         s.pop_back();
  30.     }
  31. }
  32. int main()
  33. {
  34.     cin>>digits;
  35.     dfs(0,"");
  36.     for(int i = 0 ; i < result.size() ;i++){
  37.         cout<<result[i]<<" ";
  38.     }
  39. }

13.分割回文串

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<string> path;
  4. vector<vector<string> > result; 
  5. string s;
  6. bool isPalindrome(int start, int end) {
  7.      for (int i = start, j = end; i < j; i++, j--) {
  8.          if (s[i] != s[j]) {
  9.              return false;
  10.          }
  11.      }
  12.      return true;
  13. }
  14. void dfs(int start)
  15. {
  16.     if(start >= s.size()){
  17.         result.push_back(path);
  18.         return;
  19.     }
  20.     for(int i = start ; i < s.size() ;i++){
  21.         if(isPalindrome(start,i)){
  22.             string str = s.substr(start,i-start+1);
  23.             path.push_back(str);
  24.         }else{
  25.             continue;
  26.         }
  27.         dfs(i+1);
  28.         path.pop_back();
  29.     }
  30. }
  31. int main()
  32. {
  33.     cin>>s;
  34.     dfs(0);
  35.     for(int i = 0 ; i < result.size() ;i++){
  36.         vector<string > cmp = result[i];
  37.         for(int j = 0 ; j <cmp.size() ;j++ ){
  38.             cout<<cmp[j]<<" ";
  39.         }
  40.         cout<<endl;
  41.     }    
  42. }

BFS

  1. void BFS( int s )
  2. {
  3.     queue<int> q;
  4.     q.push(s);    //将起点s入队
  5.     while(!q.empty()){
  6.         取出队首元素 top;
  7.         访问队首元素 top;
  8.         将队首元素出队;
  9.         将top的下一层结点中未曾入队的结点全部入队，并设置为已入队;
  10.     }
  11. }

1.洪水填充模型

如果用dfs来写：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,n,res = 0;
  4. int a[10][10];
  5. bool vis[10][10];
  6. int dx[4]={-1,1,0,0};
  7. int dy[4]={0,0,1,-1};
  8. void dfs(int x,int y){
  9.     
  10.     for(int i = 0 ; i < 4 ; i++){
  11.         int xx = x+dx[i];
  12.         int yy = y+dy[i];
  13.         if(a[xx][yy]==1 && !vis[xx][yy]){
  14.             vis[xx][yy]=true;
  15.             dfs(xx,yy);
  16.         }else{
  17.             continue;
  18.         }    
  19.     }
  20. }
  21.  
  22. int main()
  23. {
  24.     cin>>m>>n;
  25.     for(int i=1 ; i <= m ; i++){
  26.         for(int j=1 ; j <= n ; j++){
  27.             cin>>a[i][j];
  28.         }
  29.     }    
  30.     for(int i=1 ; i <= m ; i++ ){
  31.         for(int j = 1 ; j <= n ; j++ ){
  32.             if(a[i][j]==1 && !vis[i][j]){
  33.                 dfs(i,j);
  34.                 res++;
  35.             }        
  36.         }
  37.     }
  38.     cout<<res;    
  39. }

如果用BFS来写：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dx[4]={0,0,1,-1};
  4. int dy[4]={1,-1,0,0};
  5. int a[10][10];
  6. int m,n,ans=0;
  7. bool vis[10][10]={false};
  8. struct node{
  9.     int x;
  10.     int y;
  11. }Node;
  12. void bfs(int x,int y){
  13.     queue<node> Q;
  14.     Node.x = x , Node.y = y;
  15.     Q.push(Node);
  16.     while(!Q.empty()){
  17.         node top = Q.front();//取出队首元素
  18.         Q.pop();    //队首元素再出队
  19.         for(int i = 0 ; i < 4 ;i++){
  20.             int xx = top.x + dx[i];
  21.             int yy = top.y + dy[i];
  22.             if(!vis[xx][yy] && a[xx][yy] == 1){
  23.                 //设置Node新坐标
  24.                 Node.x = xx;
  25.                 Node.y = yy;
  26.                 vis[xx][yy]=true;
  27.                 Q.push(Node);     //将结点Node加入队列
  28.             }
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     cin>>m>>n;
  35.     for(int i=0 ; i<m ;i++){
  36.         for(int j=0 ; j<n ;j++){
  37.             cin>>a[i][j];
  38.         }
  39.     }
  40.     for(int i = 0 ; i < m ; i++){
  41.         for(int j = 0 ; j < n ; j++){
  42.             if(a[i][j]==1 && !vis[i][j]){
  43.                 ans++;
  44.                 bfs(i,j);
  45.             }
  46.         }
  47.     }
  48.     cout<<ans;    
  49. }

2.走迷宫

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 110;
  4. int g[N][N];
  5. int dx[4] = {-1,0,1,0};
  6. int dy[4] = {0,1,0,1};
  7. typedef pair<int,int> PII;
  8. int d[N][N];
  9. int m,n;
  10.  
  11. int bfs(){
  12.     queue<PII> q;
  13.     PII t = {0,0};
  14.     q.push(t);
  15.  
  16.     while(!q.empty()){
  17.         auto pp = q.front();
  18.         q.pop();
  19.         for(int i = 0 ;i < 4 ;i++){
  20.             int x = pp.first + dx[i];
  21.             int y = pp.second + dy[i];
  22.             if(x >= 0 && x < n && y >= 0 && y < m && g[x][y]==0 && d[x][y]==-1 ){
  23.                 d[x][y] = d[pp.first][pp.second]+ 1;
  24.                 q.push({x,y});
  25.             }    
  26.         }
  27.     }
  28.     return d[n-1][m-1];
  29. }
  30. int main()
  31. {
  32.     cin>>n>>m;
  33.     for(int i = 0 ; i < n ;i++){
  34.         for(int j = 0; j < m ; j++){
  35.             cin>>g[i][j];
  36.         }
  37.     }
  38.     memset(d,-1,sizeof(d));
  39.     d[0][0] = 0;
  40.     cout<<bfs()<<endl;
  41. }

dfs:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. int dx[4] = {0,0,1,-1};
  5. int dy[4] = {-1,1,0,0};
  6. int a[102][102];
  7. bool vis[102][102];
  8. int minStep = 0x7fffffff;
  9. void dfs(int x , int y,int step){
  10.     if(x < 0 || x >= n || y < 0 || y >= m) return;
  11.     if(x==n-1 && y==m-1){
  12.         minStep = min(minStep,step);
  13.         return;
  14.     }
  15.     for(int i = 0 ; i < 4 ;i++ ){
  16.         int xx = x + dx[i];
  17.         int yy = y + dy[i];
  18.         if(a[xx][yy]==0 && !vis[xx][yy])
  19.         {
  20.             vis[xx][yy] = true;
  21.             dfs(xx,yy,step+1);
  22.             vis[xx][yy] = false;    //注意写这个
  23.         }
  24.          
  25.     }
  26. }
  27. int main()
  28. {
  29.     cin>>n>>m;
  30.     for(int i = 0 ; i < n ;i++){
  31.         for(int j = 0 ; j < m ;j++){
  32.             cin>>a[i][j];
  33.         }
  34.     }    
  35.     dfs(0,0,0);
  36.     cout<<minStep;
  37. }

3. 1746 离开中山路

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1100;
  4. char g[N][N];
  5. int dx[4] = {-1,0,1,0};
  6. int dy[4] = {0,1,0,-1};
  7. typedef pair<int,int> PII;
  8. int d[N][N];
  9. int n,x1,x2,y3,y2;
  10. queue<PII> q;
  11. int bfs(int x,int y){
  12.     memset(d,-1,sizeof(d));
  13.     q.push({x,y});
  14.     d[x][y] = 0;
  15.     while(!q.empty()){
  16.         auto t = q.front();
  17.         q.pop();
  18.         for(int i = 0 ; i < 4 ; i++){
  19.             int xx = dx[i] + t.first;
  20.             int yy = dy[i] + t.second;
  21.             if(xx < 1 || xx > n || yy < 1 || yy > n) continue;
  22.             if(g[xx][yy]!='0') continue;
  23.             if(d[xx][yy] >= 0) continue;
  24.                 
  25.             q.push({xx,yy});
  26.             d[xx][yy] = d[t.first][t.second] + 1;
  27.             if(d[x2][y2]>0) return d[x2][y2];
  28.         }
  29.     }
  30. }
  31. int main()
  32. {
  33.     cin>>n;
  34.     for(int i = 1 ; i <= n ;i++){
  35.         for(int j = 1; j <= n ; j++){
  36.             cin>>g[i][j];
  37.         }
  38.     }
  39.     scanf("%d %d %d %d",&x1,&y3,&x2,&y2);
  40.     int res = bfs(x1,y3);
  41.     cout<<res;
  42. }

4.马的遍历

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dx[8]={-2,-2,-1,+1,-1,+1,+2,+2};
  4. int dy[8]={-1,1,-2,-2,+2,+2,-1,+1};
  5. const int N = 401;
  6. int n,m,x,y;
  7. int dist[N][N];
  8. typedef pair<int,int> PII;
  9. PII q[N*N];
  10. int head,tail; 
  11.  //数组来模拟队列 
  12. void bfs(int x1,int y1){
  13.     memset(dist,-1,sizeof(dist));
  14.     q[0] = {x1,y1};    //起点入队 
  15.     dist[x1][y1] = 0;
  16.     int head = 0,tail = 0;
  17.     
  18.     while(head<=tail){
  19.         auto t = q[head];    //取出队首的元素 类似 t = q.front() 
  20.         head++;    //出队         //类似之前 q.pop() 
  21.         for(int i = 0 ; i < 8 ; i++){
  22.             for(int j = 0 ; j < 8 ;j++){
  23.                 int xx = t.first + dx[i];
  24.                 int yy = t.second + dy[i];
  25.                 
  26.                 if( xx < 1 || xx > n || yy < 1 || yy > m) continue;
  27.                 if(dist[xx][yy]!=-1) continue;
  28.                 
  29.                 dist[xx][yy] = dist[t.first][t.second] + 1;
  30.                 q[++tail] = {xx,yy};        
  31.             }
  32.         } 
  33.     } 
  34. }
  35. int main()
  36. {
  37.     int x1,y1;    //起点 
  38.     cin>>n>>m>>x1>>y1;
  39.     bfs(x1,y1);
  40.     for(int i = 1 ;i <= n ;i++){
  41.         for(int j = 1 ;j<=m ;j++){
  42.             printf("%-5d",dist[i][j]);
  43.         }
  44.         cout<<endl;
  45.     }
  46. }

5.P1162填涂颜色

6.P2658 汽车拉力赛

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dx[4]={-1,1,0,0};
  4. int dy[4]={0,0,1,-1};
  5. const int N = 520;
  6. typedef pair<int,int> PII;
  7. PII q[N*N];
  8. int dist[N][N];
  9. int a[N][N],flag[N][N];
  10. int m,n,mid;
  11. bool check[N][N];
  12. int stx,sty,tp,ans; 
  13. //bfs用来判断能否到达路标 
  14. bool bfs(int mid){
  15.     q[0] = {stx,sty};
  16.     check[stx][sty] = true;
  17.     int now = 1;    //统计已经到达的路标数
  18.     int head = 0 ,tail = 0; 
  19.     
  20.     while(head<=tail){
  21.         auto t =q[head];
  22.         head++;
  23.         for(int i = 0 ; i < 4 ; i++ ){
  24.             int xx = t.first + dx[i];
  25.             int yy = t.second + dy[i];
  26.             if(check[xx][yy]) continue;
  27.             if(xx < 1 || xx > m || yy < 1 || yy > n) continue;
  28.             if(abs(a[xx][yy]-a[t.first][t.second])>mid) continue;
  29.             q[++tail] = {xx,yy};
  30.             check[xx][yy] = true;
  31.             if(flag[xx][yy] == 1){
  32.                 now++;
  33.                 if(now == tp){
  34.                     return true;
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     return false;
  40. }
  41. int main()
  42. {
  43.     cin>>m>>n;
  44.     for(int i = 1 ; i <= m ;i++){
  45.         for(int j = 1 ; j <= n ;j++){
  46.             cin>>a[i][j];
  47.         }
  48.     }    
  49.     int sign = 1;
  50.     for(int i = 1 ; i <= m ;i++){
  51.         for(int j = 1 ; j <= n ;j++){
  52.             cin>>flag[i][j];
  53.             if(flag[i][j]==1) tp++;    //记录路标数
  54.             if(flag[i][j] && sign){
  55.                 sign = 0;
  56.                 stx = i;
  57.                 sty = j;    //记录第一个坐标点 
  58.             } 
  59.         }
  60.     }
  61.     int l = -1,r = 1e9+10;
  62.     while(l+1<r){
  63.         mid=(l+r)/2;    //先找到一个可能的值 
  64.         memset(q,0,sizeof q);
  65.         memset(check,false,sizeof check);
  66.         if(bfs(mid)){        //判断这个值能不能使汽车从一个路标到达另一个坐标 
  67.             //如果能到达，说明这个值偏大，应该考虑将它变小一点 
  68.             r = mid;
  69.         }else{
  70. //            cout<<"4";
  71.             //如果不能到达，说明这个值偏小，应该考虑将它变大一点 
  72.             l = mid ;
  73.         }
  74.     }
  75.     cout<<r; 
  76. }

7.4554 小明的游戏（双端队列deque）

8.P1379 八数码难题

  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. int dx[]={0,0,1,-1};
  5. int dy[]={1,-1,0,0};
  6. ll n;
  7. int main()
  8. {
  9.     cin>>n;
  10.     queue<ll> q;
  11.     q.push(n);
  12.     map<ll,ll> mp;
  13.     mp[n] = 0;
  14.     while(!q.empty()){
  15.         int c[3][3];
  16.         int x,y; 
  17.         int t = q.front();
  18.         q.pop();
  19.         n = t;
  20.         if(t==123804765) break;
  21.         //数列转矩阵 
  22.         for(int i = 2 ; i >= 0 ; i--){
  23.             for(int j = 2 ; j>=0 ; j--){
  24.                 c[i][j] = n%10;
  25.                 n/=10;
  26.                 if(!c[i][j]) x=i,y=j;
  27.             }
  28.         }
  29.         for(int i=0 ;i<4;i++){
  30.             ll ns = 0;
  31.             int xx = dx[i] + x;
  32.             int yy = dy[i] + y;
  33.             if(xx < 0 ||yy < 0||xx > 2 || yy > 2) continue;
  34.             swap(c[xx][yy],c[x][y]);
  35.             //矩阵转数列 
  36.             for(int i = 0 ; i < 3 ;i++){
  37.                 for(int j = 0 ;j <3 ;j++){
  38.                     ns = ns*10 +c[i][j];
  39.                 }    
  40.             }
  41.     
  42.             //看map里有没有key值为ns的元素，如果有则返回1，否则返回0 
  43.             if(!mp.count(ns)){
  44.                 mp[ns] =  mp[t] + 1;//统计到达这个状态的步数
  45.                 q.push(ns); 
  46.             }
  47.             swap(c[xx][yy],c[x][y]);//状态还原 
  48.         }
  49.     }
  50.     cout<<mp[123804765]<<endl; 
  51. }

反码与补码 || lowbit运算

如何求一个数二进制表示中含 1 的个数

法一：

  1. #include <iostream> 
  2. using namespace std;
  3.  
  4. int f(int x) {
  5.     int n = 0;
  6.     while (x) {
  7.         n++;
  8.         x &= x - 1;
  9.     }
  10.     return n;
  11. }
  12. int main() {
  13.     cout << f(26) << endl;
  14.     return 0;
  15. }

法二：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int n,cnt;
  7.     cin>>n;
  8.     while(n){
  9.         if(n & 1 == 1){
  10.             cnt++;
  11.         }
  12.         n = n >> 1; //向右移一位
  13.     }    
  14.     cout<<cnt;
  15. }

lowbit运算

  1. int lowbit(int x){
  2.     return x & -x;
  3. }

二分法

1.

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 100010;
  5. int n,q;
  6. int arr[N];
  7. bool isBlue1(int num , int x){
  8.     if(num < x) return true;
  9.     else return false;
  10. }
  11. int binary_search1(int arr[],int len,int x)
  12. {
  13.     int l = -1 ,r = len;
  14.     while(l + 1 != r){
  15.         int mid = (l + r) / 2;
  16.         if(isBlue1(arr[mid],x)){
  17.             l = mid;
  18.         }else{
  19.             r = mid;
  20.         }
  21.     }
  22.     if(arr[r]==x){
  23.         return r;
  24.     }else{
  25.         return -1;
  26.     }
  27. }
  28. bool isBlue2(int num , int x){
  29.     if(num <= x) return true;
  30.     else return false;
  31. }
  32. int binary_search2(int arr[],int len,int x)
  33. {
  34.     int l = -1 ,r = len;
  35.     while(l + 1 != r){
  36.         int mid = (l + r) / 2;
  37.         if(isBlue2(arr[mid],x)){
  38.             l = mid;
  39.         }else{
  40.             r = mid;
  41.         }
  42.     }
  43.     if(arr[l]==x){
  44.         return l;
  45.     }else{
  46.         return -1;
  47.     }
  48. }
  49. int main()
  50. {
  51.     cin>>n>>q;
  52.     for(int i = 0 ; i < n ; i++ ){
  53.         cin>>arr[i];
  54.     }
  55.     while(q--){
  56.         int x;
  57.         cin>>x;
  58.         int res1 = binary_search1(arr,n,x);
  59.         int res2 = binary_search2(arr,n,x);
  60.         cout<<res1<<" "<<res2<<endl;
  61.     }    
  62. }

2.浮点数二分

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,r,l;
  4. bool check(double x){
  5.     if(x*x*x <= n){
  6.         return true;
  7.     }else{
  8.         return false;
  9.     }
  10. } 
  11. int main()
  12. {
  13.     cin>>n;
  14.     double l = -100 ,r = 100;
  15.     while(r - l > 1e-8){
  16.         double mid = ( l + r )/2;
  17.         if(check(mid)){
  18.             l = mid;
  19.         }else{
  20.             r = mid;
  21.         }
  22.     }
  23.     cout<<l;
  24. }

3.P2249查找

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. const int N = 1000010;
  5. int a[N];
  6. int mid;
  7. bool IsBlue(int x){
  8.     if(a[mid] < x) return true;
  9.     else return false;
  10. }
  11. int main()
  12. {
  13.     cin>>n>>m;
  14.     for(int i = 1 ; i <= n ;i++){
  15.         cin>>a[i];
  16.     }    
  17.  
  18.     while(m--){
  19.         int l = 0 , r = n + 1; 
  20.         int x;
  21.         cin>>x;
  22.         while(l + 1 < r){
  23.              mid = (l+r)/2 ;//7
  24.             if(IsBlue(x)){
  25.                 l = mid;
  26.             }else{
  27.                 r = mid;
  28.             }
  29.         }
  30.         if(a[r]==x){
  31.             cout<<r<<" ";
  32.         }else{
  33.             cout<<"-1"<<" ";
  34.         }    
  35.     }
  36. }

4. A-B数对

  1. #include<iostream>
  2. #include<cstdio> 
  3. #include<cmath>
  4. #include<map>
  5. #include<algorithm>
  6. using namespace std;
  7. int n,c;
  8. long long ans;
  9. map<int,int> a;
  10. int num[200005];
  11. int main()
  12. {
  13.     scanf("%d%d",&n,&c);
  14.     for(int i=1;i<=n;i++)
  15.     {
  16.         scanf("%d",&num[i]);
  17.         a[num[i]]++;    //当前数的个数++ 
  18.     }
  19.     for(int i=1;i<=n;i++)
  20.     {
  21.         ans+=a[num[i]+c];    //答案+=相差为c的数的个数，即a[num[i]+c]位置的数的个数 
  22.     }
  23.     printf("%lld",ans);
  24.     return 0;
  25. }

A = B + C

枚举 B ，从数组中找 A 的位置

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,c;
  4. const int N = 1e6;
  5. int a[N];
  6. long long mid,cnt;
  7. bool IsBlue1(int x){
  8.     if(a[mid] < x) return true;
  9.     else return false;
  10. }
  11. int search1(int a[],int n ,int x){
  12.     int l = -1 ,r = n;
  13.     while( l + 1 < r){
  14.         mid = (l+r)/2;
  15.         if(IsBlue1(x)){
  16.             l = mid;
  17.         }else{
  18.             r = mid;
  19.         }
  20.     }
  21.     if(a[r]==x) return r;
  22.     else return -1;
  23. }
  24. // 0 1 1 1 2 3 
  25. bool IsBlue2(int x){
  26.     if(a[mid] <= x) return true;
  27.     else return false;
  28. }
  29. int search2(int a[],int n ,int x){
  30.     int l = -1 ,r = n;
  31.     while( l + 1 < r){
  32.         mid = (l+r)/2;
  33.         if(IsBlue2(x)){
  34.             l = mid;
  35.         }else{
  36.             r = mid;
  37.         }
  38.     }
  39.     if(a[l]==x) return l;
  40.     else return -1;
  41. }
  42. int main()
  43. {
  44.     cin>>n>>c;
  45.     for(int i = 0 ; i < n ;i++ ){
  46.         cin>>a[i];
  47.     }
  48.     sort(a,a+n);
  49.     for(int i=0 ; i<n ; i++){
  50.         int A = a[i] + c;
  51.         int res1 = search1(a,n,A);    //找左边界 
  52.         if(res1 == -1) continue;
  53.         else{
  54.             int res2 = search2(a,n,A);    //找右边界 
  55.             cnt += res2 - res1 + 1;  
  56.         }
  57.     }
  58.     cout<<cnt;
  59. }

5.P1873 伐木

首先我们想的会是暴力解法，即从最低端，到最高端进行递增枚举，直到符合要求为止。

其实这样必定会超时的，通过（递增枚举找答案）我们其实是可以想到要用到二分法来做的

找到蓝色最右边那个

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m;
  4. const int N = 1000010;
  5. int a[N];
  6. bool check(int x){
  7.     long long ans = 0;
  8.     for(int i = 1 ; i <= n ;i++){
  9.         ans+=max(0,a[i]-x); 
  10.     }
  11.     if(ans >= m) return true;
  12.     else return false;
  13. }
  14. int main()
  15. {
  16.     cin>>n>>m;
  17.     int highest = 0;
  18.     for(int i = 1 ; i <= n ;i++){
  19.         cin>>a[i];
  20.         highest = max(a[i],highest);
  21.     }
  22.     int l = 0, r = highest;
  23.     while(l + 1 < r){
  24.         int mid = (l + r)/2;
  25.         if(check(mid)){
  26.             l = mid;
  27.         }else{
  28.             r = mid;
  29.         }
  30.     }
  31.     cout<<l;
  32. }

6.P2440 木材加工

  1. #include<bits/stdc++.h>
  2. #define long long int
  3. using namespace std;
  4. int n,k;
  5. const int N = 100010;
  6. int a[N];
  7. bool check(int x)
  8. {
  9.     int ans = 0;
  10.     for(int i = 0 ; i < n ;i++){
  11.         ans +=a[i]/x;
  12.         if(ans >= k) return true;
  13.     } 
  14.     return false;
  15. }
  16. int main()
  17. {
  18.     cin>>n>>k;
  19.     int longest = 0;
  20.     for(int i = 0 ; i < n ;i++){
  21.         cin>>a[i];
  22.         longest = max(a[i],longest);
  23.     }    
  24.     int r = longest;
  25.     int l = -1;
  26.     while(l + 1 < r){
  27.         int mid=(r+l)/2;
  28.         if(check(mid)){
  29.             l = mid;
  30.         }else{
  31.             r = mid;
  32.         }
  33.     }
  34.     if(check(r)) cout<<r;
  35.     else cout<<l;
  36. }

7.3853 路标设置

由上图所示：所以先 r = mid,再 l = mid;

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 100010;
  4. int a[N];
  5. int s[N];    //表示差值 
  6. int n,k,L;
  7. bool check(int x){//42
  8.     int cnt = 0;
  9.     //接下来主要是来计算最少需要几个路标 
  10.     for(int i = 1 ;i <= n + 1 ; i++){
  11.         if(s[i] > x){
  12.             cnt++;
  13.             int num = s[i] - x;     
  14.             while(num > x){
  15.                 cnt++;
  16.                 num-=x;
  17.             }
  18.         }
  19.     }
  20.     if(cnt<=k) return true;
  21.     else return false;
  22. }
  23. int main()
  24. {
  25.     cin>>L>>n>>k;
  26.     int maxLength;
  27.     for(int i = 1 ; i <= n ; i++){
  28.         cin>>a[i];
  29.         s[i] = a[i] - a[i-1];
  30.         maxLength = max(maxLength,a[i]); 
  31.     }
  32.     a[n+1] = L;
  33.     s[n+1] = a[n+1] - a[n];
  34.     int l = 0 , r = maxLength;
  35.     //直接判断这个答案对不对
  36.     //check主要是通过对最少需要的路标数来判断
  37.     while(l + 1 < r){
  38.         int mid = (l + r) / 2;
  39.         if(check(mid)){
  40.             r = mid;
  41.         }else{
  42.             l  =mid;
  43.         }
  44.     }
  45.     if(check(l)) cout<<l;
  46.     else cout<<r;
  47. }

8.P2678 跳石头

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int L,n,m;
  4. const int N = 50010;
  5. int a[N];
  6. int s[N];
  7. int mid;
  8. bool check(int x){
  9.     int cnt = 0,now = 0,i = 0;
  10.     while(i < n + 1 ){
  11.         i++;
  12.         if(a[i] - a[now] < x){
  13.             cnt++;
  14.         }else{
  15.             now = i;
  16.         }
  17.     }
  18.     if(cnt <= m) return true;
  19.     else return false;
  20. } 
  21. int main()
  22. {
  23.     cin>>L>>n>>m;
  24.     a[0] = 0;
  25.     for(int i = 1 ; i <= n ;i++){
  26.         cin>>a[i];
  27.     }    
  28.     a[n+1] = L;
  29.     int l = 0 , r = L + 1;
  30.     while (l + 1 < r){
  31.         mid = ( l + r ) / 2;
  32.         if(check(mid)){
  33.             l = mid;
  34.         }else{
  35.             r = mid;
  36.         }
  37.     }
  38.     if(check(r)) cout<<r;
  39.     else cout<<l;
  40. }

双指针

1.最长连续子列

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 100010;
  4. int a[N];
  5. bool check(int left , int  right)
  6. {
  7.     for(int  i= left ; i <= right ; i++ ){
  8.         for(int j = i ; j <= right ; j++){
  9.             if(i!=j && a[i]==a[j]){
  10.                 return false;
  11.             }
  12.         }
  13.     }
  14.     return true;
  15. }
  16. int main()
  17. {
  18.     cin>>n;
  19.     for(int i = 1 ; i <= n ;i++){
  20.         cin>a[i];
  21.     }
  22.     int res = 0;
  23.     for(int i = 1 ; i <= n ; i++){
  24.         for(int j = i ; j <= n ; j++){
  25.             if(check(i,j)){
  26.                 res = max(res,j - i + 1);
  27.             }
  28.         }
  29.     }
  30.     cout<<res;
  31. }

2.

动态规划

1.跳台阶

法一：dfs暴力

（从上向底）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dfs(int x)
  4. {
  5.     if(x == 1) return 1;
  6.     else if(x == 2) return 2;
  7.     else return dfs(x-1)+dfs(x-2); 
  8. }
  9. int main()
  10. {
  11.     int n;
  12.     cin>>n;
  13.     int res = dfs(n);
  14.     cout<<res; 
  15. }

优化：记忆化，避免重复计算

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int msm[20];
  4. int dfs(int x)
  5. {
  6.     int sum = 0;
  7.     if(x == 1) sum = 1;
  8.     else if(x == 2) sum = 2;
  9.     else sum = dfs(x-1)+dfs(x-2); 
  10.  
  11.     mem[x] = sum;
  12.     return sum;
  13. }
  14. int main()
  15. {
  16.     int n;
  17.     cin>>n;
  18.     int res = dfs(n);
  19.     cout<<res; 
  20. }

法二：（从底向上）

  1. int f[20];
  2. int main()
  3. {
  4.     int n;
  5.     cin>>n;
  6.     f[1]=1,f[2] = 2;
  7.     for(int i = 3 ; i <= n;i++){
  8.         f[i] = f[i-1] + f[i-2];
  9.     }
  10.     cout<<f[n];
  11. }

2.大盗阿福

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int f[20]={0};
  4. int a[20];
  5. int n;
  6. int res = 0;
  7. int maxSum = 0;
  8. //x 表示当前正在考虑那家店 
  9. void dfs(int x)
  10. {
  11.     if(x > n) return 0;
  12.     else return max(dfs(x+1),dfs(x+2)+a[x]);
  13. }
  14. int main()
  15. {
  16.     int t;
  17.     cin>>t;
  18.     while(t--){
  19.         cin>>n;
  20.         for(int i = 1 ; i <= n ;i++){
  21.             cin>>a[i];
  22.         }
  23.         dfs(1);
  24.         cout<<res<<endl;
  25.     }
  26. }

记忆化搜索进行剪枝：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int mem[20];
  4. int a[20];
  5. int n;
  6. //x 表示当前正在考虑那家店 
  7. void dfs(int x)
  8. {
  9.     if(mem[x]) return mem[x];
  10.     
  11.     int sum = 0;
  12.     if(x > n) sum = 0;
  13.     else sum = max(dfs(x+1),dfs(x+2)+a[x]);
  14.     
  15.     mem[x] = sum;
  16.     return sum;
  17. }
  18.  
  19. int main()
  20. {
  21.     int t;
  22.     cin>>t;
  23.     while(t--){
  24.         cin>>n;
  25.         for(int i = 1 ; i <= n ;i++){
  26.             cin>>a[i];
  27.         }
  28.         dfs(1);
  29.         cout<<res<<endl;
  30.     }
  31. }

3.数字三角形

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dfs(int x1,int y1)
  5. {
  6.     if(x1 > n || y1 > n) return 0;
  7.     //求 最优子问题 dfs(x) = max(dfs( x + 1 ),dfs( x + 2))
  8.     //求 子问题的和 dfs(x) = dfs( x + 1 ) + dfs( x + 2 )
  9.     else return max(dfs (x1 + 1,y1),dfs(x1 + 1,y1 + 1)) + g[x1][y1];
  10. }
  11. int main()
  12. { 
  13.     cin>>n;
  14.     for(int i = 1 ; i <= n ;i++){
  15.           for(int j = 1 ; j <= i ;j++){
  16.               cin>>g[i][j];
  17.         }
  18.     }
  19.     int res = dfs(1,1);
  20.     cout<<res;
  21.     return 0; 
  22. }

记忆化搜索 优化：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1010;
  4. int mem[N][N];
  5. int n;
  6. int g[N][N];
  7. int dfs(int x1,int y1)
  8. {
  9.     if(mem[x1][y1]) return mem[x1][y1];
  10.     
  11.     int sum = 0;
  12.     if(x1 > n || y1 > n) sum = 0;
  13.     else sum = max(dfs (x1 + 1,y1),dfs(x1 + 1,y1 + 1)) + g[x1][y1];
  14.     
  15.     mem[x1][y1] = sum;
  16.     return sum;
  17. }
  18. int main()
  19. { 
  20.     cin>>n;
  21.     for(int i = 1 ; i <= n ;i++){
  22.           for(int j = 1 ; j <= i ;j++){
  23.               cin>>g[i][j];
  24.         }
  25.     }
  26.     int res = dfs(1,1);
  27.     cout<<res;
  28.     return 0; 
  29. }

从上往下递归：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. const int N = 1010;
  5. int g[N][N],f[N][N];
  6. int main()
  7. { 
  8.     cin>>n;
  9.     for(int i = 1 ; i <= n ;i++){
  10.           for(int j = 1 ; j <= i ;j++){
  11.               cin>>g[i][j];
  12.         }
  13.     }
  14.     for(int i = 1 ;i <= n ;i++){
  15.         for(int j = 1 ; j <= i ; j++){
  16.             f[i][j] = max(f[i-1][j],f[i-1][j-1]) + g[i][j];
  17.         } 
  18.     }
  19.     int res = 0;
  20.     // 从上往下推，每一个都可能是终点 ，需要遍历找到最大的那个点 
  21.     for(int i = 1 ; i <= n ;i++){
  22.          res = max( res , f[n][i]); 
  23.     }
  24.     cout<<res;
  25. }

蓝桥杯填空题小技巧：

python处理大数据不会溢出，自带高精度

(106条消息) 蓝桥杯真题 购物单 EXCEl解法详细步骤_蓝桥杯excel__scling的博客-CSDN博客

(106条消息) [蓝桥杯]Excel题_蓝桥杯excel_天赐细莲的博客-CSDN博客

(106条消息) 【蓝桥杯小技巧】暴力+ Excel的使用(持续更新)_蓝桥杯可以用excel吗_404name的博客-CSDN博客（那个函数与OR相对用AND）

滑动窗口

  1. //209.长度最小的数组 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int nums[6]={2,3,1,2,4,3};
  5. int s = 7; 
  6. int main()
  7. {
  8.     int result = 0x7fffffff;
  9.     int sum = 0;    //滑动窗口数值之和 
  10.     int i = 0;        //滑动窗口起始位置 
  11.     int subLength = 0;  //滑动窗口的长度
  12.     for(int j = 0 ; j < 6 ; j++){
  13.         sum += nums[j];
  14.         while(sum >= s){
  15.             subLength = j-i+1;
  16.             if(result >= subLength){
  17.                 result = subLength;
  18.             }
  19.             sum -= nums[i++];        //精髓之处 
  20.         }
  21.     }
  22.     if(result == 0x7fffffff){
  23.         cout<<"0";
  24.     }else{
  25.         cout<<result;     
  26.     }
  27. } 
  1. //209.长度最小的数组 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int nums[11]={3,3,3,1,2,1,1,2,3,3,4};
  5. unordered_map<int, int> basket;
  6. int main()
  7. {
  8.     int ans = 0;
  9.     int i = 0;        //滑动窗口起始位置 
  10.     int cnt = 0;
  11.     // 不断后移终止指针
  12.     for(int j = 0 ; j < 11 ; j++){
  13.         // 更新cnt
  14.         if(basket[nums[j]]==0){
  15.             cnt++;
  16.         }
  17.         basket[nums[j]]++;
  18.         // 不满足cnt≤2则保守地后移起始指针，一旦满足条件就停止移动
  19.         while(cnt>2){
  20.             basket[nums[i]]--;
  21.             if(basket[nums[i]]==0) cnt--;
  22.             i++;
  23.         }
  24.         ans=max(ans,j-i+1);
  25.     }
  26.     cout<<ans;
  27. } 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. unordered_map<char,int> need,win;
  4. int main()
  5. {
  6.     string s="ADOBECODEBANC";
  7.     string t="ABC";
  8.     for(int i = 0 ; i < t.size() ; i++)
  9.     {
  10.         need[t[i]]++;
  11.     }
  12.     int left = 0,right = 0,start = 0;
  13.     int cnt = 0;
  14.     int min_len = 0x7fffffff;
  15.     //对窗口进行处理 
  16.     for( right = 0 ; right<s.size() ; right++){
  17.         if(need[s[right]] > 0) cnt++;
  18.         need[s[right]]--;
  19.         while(cnt == t.size())
  20.         {
  21.             if(min_len > right-left+1)
  22.             {
  23.                 min_len = right-left + 1;
  24.                 start = left;    //方便后续提取子串 
  25.             }
  26.             if(need[s[left]]==0) cnt--;
  27.             need[s[left]]++;
  28.             left++;
  29.         }
  30.     }
  31.     cout<<s.substr(start,min_len);
  32. }

哈希表

1.有效的字母异位词（hash）

  1. class Solution {
  2. public:
  3.     bool isAnagram(string s, string t) {
  4.         int record[26] = {0};
  5.         for (int i = 0; i < s.size(); i++) {
  6.             // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
  7.             record[s[i] - 'a']++;
  8.         }
  9.         for (int i = 0; i < t.size(); i++) {
  10.             record[t[i] - 'a']--;
  11.         }
  12.         for (int i = 0; i < 26; i++) {
  13.             if (record[i] != 0) {
  14.                 // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
  15.                 return false;
  16.             }
  17.         }
  18.         // record数组所有元素都为零0，说明字符串s和t是字母异位词
  19.         return true;
  20.     }
  21. };

2.两个数组的交集（set）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     unordered_set<int> result;    // 存放结果，之所以用set是为了给结果集去重
  6.     unordered_set<int> nums_set;
  7.     vector<int> nums1;
  8.     int nums2[5];
  9.     
  10.     int n,m,a;
  11.     cin>>n;
  12.     for(int i = 0 ; i < n ;i++){
  13.         cin>>a;
  14.         nums_set.insert(a);    //set用.insert来进行插入 
  15.     }
  16.     cin>>m;
  17.     for(int i = 0 ; i < m ;i++){
  18.         cin>>nums2[i];
  19.     }
  20.     
  21.     for(int i = 0 ; i < m ; i++)
  22.     {
  23.         // 发现nums2的元素 在nums_set里又出现过
  24.         if(nums_set.find(nums2[i])!=nums_set.end()){
  25.             result.insert(nums2[i]);
  26.         }
  27.     }
  28.     for(auto it = result.begin() ; it != result.end() ; it++){
  29.         cout<<*it<<" ";   //学会输出 
  30.     }
  31. }

3.两个数组的交集II （map）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int nums1[5] = {4,9,5,4,4};
  6.     int nums2[6] = {9,4,9,8,4,6};
  7.     unordered_map<int,int> mp;
  8.     for(int i= 0 ; i < 5 ;i++ ){
  9.         mp[nums1[i]]++;
  10.     }
  11.     int result[6];
  12.     int len = 0;
  13.     for(int i = 0 ; i < 6 ;i++){
  14.         if(mp[nums2[i]]!=0){
  15.             result[len++] = nums2[i];
  16.             mp[nums2[i]]--;
  17.         }
  18.     }
  19.     for(int i = 0 ; i<len ;i++){
  20.         cout<<result[i];
  21.     }
  22. }

4.快乐数（map）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int getSum(int n)
  4. {
  5.     int sum = 0;
  6.     while(n) 
  7.     {
  8.         sum+=(n%10)*(n%10);
  9.         n/=10;    
  10.     }
  11.     return sum;
  12. }
  13. int main()
  14. {
  15.     int n;
  16.     cin>>n;
  17.     unordered_map<int,int> mp;
  18.     while(1)
  19.     {
  20.         int sum = getSum(n);
  21.         mp[sum]++;
  22.         if(sum==1){
  23.             cout<<"true";
  24.             break;
  25.         }
  26.         if(mp[sum]==2){
  27.             cout<<"false";
  28.             break;
  29.         }
  30.         n=sum;
  31.     }
  32. }

5.两数之和

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int target = 26;
  6.     int nums[4]={2,7,11,15};
  7.     unordered_map<int ,int> map;
  8.     vector<int> v;
  9.     for(int i = 0 ; i < 4 ;i++){
  10.         //遍历当前元素，并在 map 寻找是否有匹配的 key 
  11.         auto iter = map.find(target-nums[i]);
  12.         if(iter!=map.end()){
  13.             v.push_back(i);
  14.             v.push_back(iter->second);
  15.         }
  16.         map.insert(pair<int,int>(nums[i],i));
  17.     }
  18.     for(auto it = v.begin() ; it!=v.end() ; it++){
  19.         cout<<*it<<" ";
  20.     }
  21. }

6.四数相加(map<int,int>)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int A[2] = {1,2} , B[2] = {-2,-1} ,C[2] = {-1,2} , D[2] = {1,-2};
  6.     int sum1[4],len1=0;
  7.     for(int i = 0 ; i < 2 ;i++){
  8.         for(int j = 0 ; j<2 ;j++){
  9.             sum1[len1++] = A[i]+B[j];
  10.         }
  11.     }
  12.     int len2 = 0 ,sum2[4];
  13.     for(int i = 0 ; i < 2 ;i++){
  14.         for(int j = 0 ; j<2 ;j++){
  15.             sum2[len2++] = C[i]+D[j];
  16.         }
  17.     }    
  18.     unordered_map<int,int> mp;
  19.     int cnt=0;
  20.     for(int i = 0 ; i < len2 ; i++){
  21.         mp[sum2[i]]++;
  22.     }
  23.     for(int i = 0; i < len1 ; i++){
  24.         if(mp.find(0-sum1[i]) != mp.end()){
  25.             cnt+=mp[-sum1[i]];
  26.         }
  27.     }
  28.     cout<<cnt;    
  29. }

7.赎金信（map<char,int>）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     unordered_map<char,int> map;
  6.     string s1 = "aa";
  7.     string s2 = "ava";
  8.     for(int i = 0 ; i < s2.size() ; i++){
  9.         map[s2[i]]++;
  10.     }    
  11.     for(int i = 0 ; i < s1.size() ; i++){
  12.         map[s1[i]]--;
  13.         if(map[s1[i]] < 0){
  14.             cout<<"false";
  15.             return 0;
  16.         }
  17.     }
  18.     cout<<"true";
  19. }

8.三数之和（三指针）

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     vector<vector<int> > result;
  6.     int nums[6] = {-4,-1,-1,0,1,2};
  7.     for(int i = 0 ; i < 6 ; i++){
  8.         if(nums[i] > 0){
  9.             break;
  10.         }
  11.         if(i > 0 && nums[i] == nums[i-1]){
  12.             continue;
  13.         } 
  14.         int left = i + 1;
  15.         int right = 5;
  16.         while(left < right){
  17.             if(nums[i] + nums[left] + nums[right] > 0) right--;
  18.             else if(nums[i] + nums[left] + nums[right] < 0) left--;
  19.             else{
  20.                 result.push_back(vector<int>{nums[i],nums[left],nums[right]});
  21.                 //去重操作 
  22.                 while(nums[right] == nums[right-1]) right--;
  23.                 while(nums[left] == nums[left+1]) left++;
  24.             }
  25.             left++;
  26.             right--;
  27.         }
  28.     }
  29.     for(int i = 0 ; i < result.size() ;i++){
  30.         vector<int> cmp = result[i];
  31.         for(int j = 0 ; j < cmp.size() ; j++){
  32.             cout<<cmp[j]<<" "; 
  33.         }
  34.         cout<<endl;
  35.     }
  36. }

9.四数之和

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int nums[6] = {1,0,-1,0,-2,2};
  6.     int target;
  7.     cin>>target;
  8.     vector<vector<int> > result;
  9.     sort(nums,nums+6);
  10.     for(int k = 0 ; k < 6 ;k++ ){
  11.         if(nums[k] > target && nums[k] >= 0 ){
  12.             break;
  13.         }
  14.         if(k > 0 && nums[k] == nums[k-1]){
  15.             continue;
  16.         }
  17.         for(int i = k+1 ; i < 6 ; i++){
  18.  
  19.             if(nums[k] + nums[i] > target&&nums[k]+nums[i]>=0 ){
  20.                 break;
  21.             }
  22.             if(i > k+1 && nums[i] == nums[i-1]){
  23.                 continue;
  24.             }
  25.  
  26.             //和三个数之和操作一样
  27.             int left = i+1;
  28.             int right = 5;
  29.             
  30.             while(left < right){
  31.                 if((long)nums[k] + nums[i] + nums[left] + nums[right] > target){
  32.                     right--;
  33.                 }
  34.                 else if((long)nums[k] + nums[i] + nums[left] + nums[right] < target){
  35.                     left++;
  36.                 }
  37.                 else{
  38.                 
  39.                  result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
  40.                     
  41.                     while(nums[right] == nums[right-1] && left < right) right--;
  42.                     while(nums[left] == nums[left+1] && left < right) left++;
  43.                 
  44.                     right--;
  45.                     left++;
  46.                 
  47.                 }
  48.             } 
  49.         }
  50.     }
  51.     for(int i = 0 ; i < result.size() ;i++){
  52.         vector<int> cmp = result[i];
  53.         for(int j = 0 ; j < cmp.size() ; j++){
  54.             cout<<cmp[j]<<" "; 
  55.         }
  56.         cout<<endl;
  57.     }
  58. }

10.翻转单词

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     unordered_map<int , string> record;
  6.     int maxmum = INT_MAX;
  7.     string st;
  8.     string s;
  9.     getline(cin,s); //输入带空格字符串
  10.     for(int i = 0 ; i < s.size() ;i++){
  11.         if(s[i]!=' '){
  12.             st+=s[i];
  13.         }
  14.         if(s[i]!=' ' && s[i+1]==' ' && i < s.size() - 1)
  15.         {
  16.             st+=' ';
  17.             record.insert(pair<int,string>(maxmum - i ,st));
  18.             st.clear();
  19.         }
  20.         if(s[i]!=' '&&i==s.size()-1){
  21.             st+=' ';
  22.             record.insert(pair<int,string>(maxmum - i ,st));
  23.             st.clear();
  24.         }
  25.     }
  26.     string res;
  27.     for(auto it = record.begin() ; it!=record.end() ; it++){
  28.         res+=it->second;
  29.     } 
  30.     res.erase(res.end()-1);    //删除最后的空格
  31.     cout<<res; 
  32. }

字符串

注意反转的方法以及循环 i += 2*k

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     string s = "abcdefg";
  6.     int k = 2;
  7.     for(int i = 0 ; i < s.size() ;i+=2*k ){
  8.         // 1. 每隔 2k 个字符的前 k 个字符进行反转
  9.         // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符 
  10.         if(i + k <= s.size()){
  11.             reverse(s.begin() + i , s.begin() + i + k);
  12.         }else{
  13.             // 3. 剩余字符少于 k 个，则将剩余字符全部反转
  14.             reverse(s.begin() + i , s.end());
  15.         }
  16.     }
  17.     cout<<s; 
  18. }

队列和堆

1.旋转字符串

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     queue<char> q;
  6.     string s;
  7.     cin>>s;
  8.     for(int i = 0 ; i < s.size() ; i++){
  9.         q.push(s[i]);
  10.     }
  11.     int n;
  12.     cin>>n;
  13.     while(n--){
  14.         char a;
  15.         a = q.front();
  16.         q.push(a);
  17.         q.pop();
  18.     }
  19.     for(int i = 0 ; i<s.size(); i++){
  20.         cout<<q.front();
  21.         q.pop();
  22.     }
  23. }

2.有效的括号

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     string s;
  6.     cin>>s;
  7.     stack<int> st;
  8.     for(int i = 0 ; i < s.size() ;i++){
  9.         if(s[i]=='('){
  10.             st.push(')');
  11.         }
  12.         else if(s[i]=='{'){
  13.             st.push('}');
  14.         }
  15.         else if(s[i]=='['){
  16.             st.push(']');
  17.         }
  18.         else if(st.empty() || st.top() != s[i]){
  19.             cout<<"false";
  20.             break;
  21.         }else if(st.top()==s[i]){
  22.             st.pop();
  23.         }
  24.     }
  25.     cout<<"true";
  26. }

3.删除字符串中的所有相邻重复项

  1. //????????????????????????????????????????????????????
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int main()
  5. {
  6.     stack<char> st; 
  7.     string s;
  8.     cin>>s;
  9.     for(int i = 0 ; i < s.size() ; i++){
  10.         if(s[i]!=st.top() || st.empty()){
  11.             st.push(s[i]);    
  12.         }else{
  13.             st.pop();    
  14.         }
  15.     }
  16.     while(!st.empty())
  17.     {
  18.         cout<<st.top();
  19.         st.pop();
  20.     }
  21. }

前缀和

  1.     cin>>n;
  2.     for(int i = 0 ; i < n ;i++){
  3.         cin>>nums[i];
  4.     }     
  5.     preSum[0] = 0;
  6.     for(int i = 1 ; i <= n  ; i++){
  7.         preNum[i] = preNum[i-1] + nums[i-1];    
  8.     }
  1. void sum(int left , int right){
  2.     return preNum[right+1] - preNum[left];
  3. }

二维前缀：

  1.     int a[10][10];
  2.     for(int i = 1 ; i <= n ;i++){
  3.         for(int j = 1 ; j <= m ;j++){
  4.             // 计算每个矩阵 [ 0 , 0 , i ,j ] 的元素和 
  5.             preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + a[i-1][j-1] - preSum[i-1][j-1]; 
  6.         }
  7.     }
  1. int sum(int x1 , int y1 ,int x2,int y2){
  2.     return preSum[x2+1][y2+1] - preSum[x2][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
  3. } 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int num[105] , diff[105],n,m;
  6.     cin>>n>>m;
  7.     for(int i = 1 ; i <= n ;i++){
  8.         cin>>num[i];
  9.     }
  10.     for(int i = 1 ; i <=n ;i++){
  11.         diff[i] = num[i] - num[i-1];
  12.     }
  13.     //区间修改操作 
  14.     for(int i = 0 ; i < m ;i++){
  15.         int a,b,c;        // 起始位, 结束位 , 改变的值 
  16.         cin>>a>>b>>c;
  17.         diff[a] += c;
  18.         diff[b+1] -= c;
  19.     }
  20.     for(int i = 1; i <= n ;i++){
  21.         num[i] = num[i-1] + diff[i];    
  22.     }
  23.     
  24.     for(int i = 1 ; i<=n ;i++){
  25.         cout<<num[i]<<" ";
  26.     }
  27.     cout<<endl;
  28. }

二维差分

  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N=1010;
  5. int a[N][N],b[N][N];//a[N][N]为原序列  b[N][N]为a[N][N]的差分
  6. int main()
  7. {
  8.     int n,m;
  9.     cin>>n>>m;
  10.                
  11.     //对差分序列进行处理，也就是一维差分中的构建差分数组
  12.     while(m--)
  13.     {
  14.         int x1,y1,x2,y2,c = 1;
  15.         cin>>x1>>y1>>x2>>y2;
  16.         b[x1][y1]+=c;
  17.         b[x2+1][y1]-=c;
  18.         b[x1][y2+1]-=c;
  19.         b[x2+1][y2+1]+=c;
  20.     }
  21.     
  22.     //对差分求前缀和,输出结果 
  23.      for(int i=1;i<=n;i++)
  24.      {
  25.         for(int j=1;j<=n;j++)
  26.         {
  27.             b[i][j]+=b[i][j-1]+b[i-1][j]-b[i-1][j-1];
  28.             cout<<b[i][j]<<" ";
  29.         }
  30.         cout<<endl;
  31.      }
  32.     return 0;
  33. }

、

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/867371
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号