Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

蓝桥杯突击训练

2020/09/17 ACM C++
Word count: 1,711 | Reading time: 8min

ACM 3-20笔记

3部排序

  • 左指针，右指针， 探路指针–>链表的pq

马虎的算式

  • 枚举（五重循环，注意条件）
  • 内存1000ms大约运行10^8的指令

大数除法

  • 减法
  • 除法

39级阶梯

  • 斐波那契
  • 简化模型后再加上考虑条件

错误票据

  • 获得一行内容：getline()前要用getchar()吃掉换行符

  • 分割一行以空格分隔的元素

    • 1
      2
      3
      4
      5
      string s;
      getline(cin,s);
      stringstream ss(s);
      string tmp;
      while( getline(ss,tmp," ") )

▲翻硬币

最问题

ACM 3-21笔记 （2014年）

奇怪的分式

  • gcd辗转相除法
  • 枚举

蚂蚁感冒

  • 日本白书的蚂蚁模型：穿过身体

▲地宫取宝

  • 深搜
  • 递归
  • 取模

面对&41004^{100}优化思考方向：

  • 贪心 ： 知道有一条最好的路 —X---> 这题要求每种情况都遍历
  • 重复子问题 ： 记忆化搜索
    • dfs(int x, int y , int max,int cnt)，虽然x,y都是不同的，但max,cnt可能会有相同的值，这些情况是重复的
  • 动态规划 （递推方式）：

ACM 3-22笔记 (2015)

T5-全排列

  • DFS框架
    • 递归
    • 回溯

T7-牌型种数

  • 排列组合
    • 一般都是用递归解决
    • 回溯（恢复初始状态）：袋子理论 --> 每次都得把自己的袋子清空再返回
  • 两种思路：
    • 13次选牌(O(1313)O(13^{13}))
    • 每张牌选几次（更简单O(513)O(5^{13}))

T9-垒骰子

  • 递归
    • 分治法
    • 逐步生成

ACM 3-23 (2016)

  • 凑数字
    • 多个不同的数字---->全排列问题

附录：通用的代码工具

void i2s(string &s, int &num)

1
2
3
4
5
void i2s(string &s, int &num){
    stringstream ss;
    ss << num;
    ss > s;
}

string去前置0

1
2
3
void removePre0(string &s){
 	s = s.substr(s.find_first_not_of("0"))
}

string回溯去最后一个元素

1
2
3
path += pai[i];
f(k-1,path);
path.erase(path.end()-1)

求最大公因数(辗转相除法)：

1
2
3
4
5
6
int gcd(int a,int b){
    if( a%b == 0) return b;
    //极端情况最大的公约数为两个中最小的一个
    return gcd(b,a%b);	
    // 被除数为其中小的那个
}

漫画图解

全排列

next_premutation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)&&n){
        int a[1000];
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);//可以自行测试一下删除后的结果
        do{
            for(int i=0;i<n;i++)
                printf("%d ",a[i]);
            printf("\n");
        }while(next_permutation(a,a+n));
    }
    return 0;
}

如果有sort()，输出为

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

若无，则输出为

1 0 2
1 2 0
2 0 1
2 1 0

可以发现少了许多种组合方法。

不过，仔细比较各种组合方法和有无sort()的输出，可以发现函数next_permutation()是按照字典序产生排列的，并且是从数组中当前的字典序开始依次增大直至到最大字典序。

△.sort()默认排序从小到大

DFS+回溯法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <sstream>
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100+5;
#define NUM 5
int arr[] = {1,2,3,4,5};


void f(int k){
    if( k == NUM){
        for(int i = 0 ; i< NUM; i++) cout << arr[i];
        cout <<endl;
        return ;
    }
    for(int i=k ; i <NUM ; i++){
        {
            int t = arr[i];
            arr[i] = arr[k];
            arr[k] = t;
        }
        f(k+1);
        // 回溯复原
        {
            int t = arr[i];
            arr[i] = arr[k];
            arr[k] = t;
        }
    }
}

C++输入输出流设置

1
2
3
4
5
6
7
#include <bits/stdc++.h>	//万能头文件
using namespace std;		//命名空间
int main() {
    ios::sync_with_stdio(false);	//取消输入输出流等待同步
    ...
    if (i != n) cout << endl;		//每个输出样例间有换行,(可理解每个CASE后加个换行,最后一行没有)
}

C语言里的输入输出问题

1
2
3
4
int d,
float f,
char str[20],
scanf("%d%f%s",d,f,str);
scanf:

使用 scanf 输入 42

  • scanf()中使用%c说明符，该函数将只读取字符4 并将其存储在一个char类型的变量中
  • 如果使用%s说明符，该函数会读取两个字符，即字符4和字符2，并将它们存储在一个字符串中。
  • 如果使用%d说明符，则scanf 读取同样的两个字符，但是随后它会继续计算与它们的相应的整数值为4*10+2 得到 42；然后将该整数的二进制表示保存在一个int变量中，
  • 如果使用%f说明符 则scanf（）读取这两个字符 计算它们对应的数值 42，然后以内部的浮点表述该值，并将结果保存在一个float变量中
1
2
3
4
5
6
7
8
9
10
11
12
/**
0234500067
1034560500
2045600671
0000000089
通过控制读入的位数,读入矩阵
*/
for(c=1;c<=m;c++){   
    //循环变量稍微有点奇怪   
    for(d=1;d<=n;d++)   
        scanf("%1d",&mapp[c][d]);   
}
getchar():

getchar()只能输入字符型,输入时遇到回车键才从缓冲区依次提取字符.

说明：当程序调用getchar()函数时，程序就等着用户按键，用户输入的字符被存放在键盘缓冲区中，直到用户按回车为止（回车字符也放在缓冲区中）。当用户键入回车之后，getchar()函数才开始从键盘缓冲区中每次读入一个字符。也就是说，后续的getchar()函数调用不会等待用户按键，而直接读取缓冲区中的字符，直到缓冲区中的字符读完后，才重新等待用户按键。

分割输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 
迷宫题目
010010
001000
000101
110000
*/
for(int i=1 ;  i <= row ; i++){
    for(int j= 1; j <= col ; j++)
        scanf("%c",&maze[i][j]);
        getchar();
}

// ---错误票据--
int n ;
cin >> n ;
getchar();
vector<int> v;
while(n--){
    string s;
    getline(cin,s);
    stringstream ss(s);
    string tmp;
    while( getline(ss,tmp,' ') ){
        v.push_back( s2i(tmp) );
    }
}

// ****C++输入流不同步设置****
int main(){
    ios::sync_with_stdio(false);
    ...
}

循环移位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
* 递推得到幂运算
* @param base基底，n幂次
*/
int selfpow(int base,int n){
    int res = 1;
    while( n-- ){
        res *= base;
    }
    return res;
}

/**
* 自己实现x位二进制循环左移
* e.g. 8=1000 ， 左移=> 0001
* @param n为len位中只有一位为1的十进制数
*/
int ROL(int n,int len,int dir = 1){
    if ( dir == 1) {
        n <<= 1;
        if ( n % selfpow(2,len) == 0 ) n = 1;
    }else{
        n >>= 1;
        if( n == 0 ) n = selfpow(2,len-1);
    }
    return n;
}

宏定义循环

1
2
3
4
5
6
7
8
9
10
11
12
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Forneq(i,s,n) for (int i = (s); i < (n); ++i)
#define Foreq(i,s,n) for (int i = (s); i <= (n); ++i)
int main(){
    rep(i,3){
        cout << 1 << endl;
    }
    For(i,1,2){
        cout << 2 << endl;
    }
    return 0;
}

Author: Mrli

Link: https://nymrli.top/2019/03/28/蓝桥杯突击训练/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
学会Pull requestNextPost >
C++机器学习库MLPack
CATALOG
  1. 1. ACM 3-20笔记
    1. 1.1. 3部排序
    2. 1.2. 马虎的算式
    3. 1.3. 大数除法
    4. 1.4. 39级阶梯
    5. 1.5. 错误票据
    6. 1.6. ▲翻硬币
  2. 2. ACM 3-21笔记 （2014年）
    1. 2.1. 奇怪的分式
    2. 2.2. 蚂蚁感冒
    3. 2.3. ▲地宫取宝
  3. 3. ACM 3-22笔记 (2015)
    1. 3.1. T5-全排列
    2. 3.2. T7-牌型种数
    3. 3.3. T9-垒骰子
    4. 3.4. ACM 3-23 (2016)
  4. 4. 附录：通用的代码工具
    1. 4.0.1. void i2s(string &s, int &num)
    2. 4.0.2. string去前置0
    3. 4.0.3. string回溯去最后一个元素
    4. 4.0.4. 求最大公因数(辗转相除法)：
    5. 4.0.5. 全排列
      1. 4.0.5.1. next_premutation
      2. 4.0.5.2. DFS+回溯法
    6. 4.0.6. C++输入输出流设置
      1. 4.0.6.1. scanf:
      2. 4.0.6.2. getchar():
    7. 4.0.7. 分割输入
    8. 4.0.8. 循环移位运算
    9. 4.0.9. 宏定义循环