grant's Blog

记录生活中的点点滴滴

蓝桥杯学习总结（三）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 5.7k 阅读时长 ≈ 5 分钟

续蓝桥杯学习总结（二）。

3.递推

关于递归与递推的区别：

递推：从初值出发反复进行某一运算得到所需结果。——-从已知到未知，从小到达（比如每年长高9cm，20年180，30后270）

递归：从所需结果出发不断回溯前一运算直到回到初值再递推得到所需结果——从未知到已知，从大到小，再从小到大(你想进bat，那么编程就得牛逼，就得卸载玩者农药，努力学习）。递归(Recursion)是从归纳法(Induction)衍生出来的。

3.1 acwing.717.简单斐波那契（语法课）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
以下数列0 1 1 2 3 5 8 13 21 …被称为斐波纳契数列。

这个数列从第3项开始，每一项都等于前两项之和。

输入一个整数N，请你输出这个序列的前N项。

输入格式
一个整数N。

输出格式
在一行中输出斐波那契数列的前N项，数字之间用空格隔开。

数据范围
0<N<46
输入样例：
5
输出样例：
0 1 1 2 3
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
34
// y总题解
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int fabo[48];
    fabo[1] = 0;
    fabo[2] = 1;
    for (int i = 3;i <= n;i ++) fabo[i] = fabo[i-1]+fabo[i-2];
    for (int i = 1;i <= n;i ++) cout << fabo[i] << ' ';
	return 0;
}

// 优化版本，节省空间，和语法课相同
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a = 0,b =1;
	for (int i = 1;i <= n;i ++)
    {
        cout << a << ' ';
        int fn = a + b;
	a = b,b = fn;
    }
	return 0;
}

3.2 acwing.95.费解的开关（算法竞赛进阶指南，难）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
你玩过“拉灯”游戏吗？
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。
数据范围
0<n≤500
输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：
3
2
-1
思路：

先枚举第一行的灯，每个灯有按或不按两种选择，可以用到指数型枚举。

第二行的灯受第一行影响，如果第一行灯是灭的，它下方第二行灯必须按，因为只有第二行这个灯能影响它的状态；同理，第一行灯是亮的，它下方第二行灯必须不能按。

由此我们知道，每一行灯按或不按由前一行状态唯一确定。

image-20210314090051648

image-20210314092102637

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 6;
int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};// 按一次开关改变5个灯的状态
char g[N][N], backup[N][N];

// 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色
void turn (int x, int y)// 通过坐标偏移量实现
{
    for (int i = 0; i < 5; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        //如果在边界外边，直接忽略即可
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        g[a][b] ^= 1;   //异或，值不同时结果为1，相同为0
        // '0'是48 所以 ^1就是49 =='1'
        // '0'对应十进制48,110000（2），110000 ^ 000001 = 110001(对应十进制49，'1')
       // '0'^1 = '1','1'^1='0'
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n -- )
    {
        // 按行输入，把每一行当成一个字符串
        for (int i = 0; i < 5; i ++ ) cin >> g[i];
        int res = 10; // 因为后面要取min，所以res赋一个非法且较大的数
        // 这里我们枚举了第一行的32种按法，不用管是亮是灭，把第一行所有情况都按一遍
        // 按每种情况的第一行，去遍历接下来的行
        for (int op = 0; op < 32; op ++ )
        {
            // 我在对这种情况操作的时候，得先备用一下
            // 把原始数组备份一下，然后操作g，操作完了还原，然后再操作
            memcpy(backup, g, sizeof g);
            int step = 0;
            // 第一行的按法(在这里 1 表示按了, 0 表示不按)，这里只是为了输出第一行按完之后的状态
            for (int i = 0; i < 5; i ++ )
                if (op >> i & 1)  // 取op对应二进制数的第i位数字
                                  // 00010 >> 1 & 1  是1 所以turn(0, 1) 就是第一行第二个位置
                {                 // 数字3 对应了00011 表示第1 和第2个位置的按一下
                    step ++ ;
                    turn (0, i);
                }
            // 然后通过第一行按完之后的状态，按234行
            for (int i =0; i < 4; i ++ )// 枚举行数
                for (int j = 0; j < 5;j ++ )// 枚举每行的灯
                    if (g[i][j] == '0')
                    {
                        step ++;
                        turn (i + 1, j);  // 如果这个位置是灭的，就按下一行对应的位置
                    }
            bool dark = false;
            for (int j = 0; j < 5; j ++ )
                if (g[4][j] == '0')// 判断最后一行的灯，如果至少有一个暗就无解
                {
                    dark = true;
                    break;
                }

            // 对于32种情况的这一种，如果所有的全亮就记录下步数(事实上只记录了最后一行是否dark)
            if (!dark) res = min(res, step);
            memcpy (g, backup, sizeof g);
        }
        if(res > 6) res = -1;
        cout << res << endl;
    }
    return 0;
}
Note:
  • 细节很多，一定要自己多动手写写，最好打一下挑战模式
  • 枚举第一行时：1表示按一下，0表示不按(当然反过来也可以啦~看你)
  • 在遍历整个矩阵时：1是灯亮，0是灯灭
  • memcpy 可以用来复制数组，这里是先把原数组备份一下，然后对本数组操作，本次操作结束后，要再把备份数组还原回来，再进行下一次操作啦~
  • 从第一行开始递推，若达到第n行不全为0，说明这种点击方式不合法。
    在所有合法的点击方式中取点击次数最少的就是答案。
    对第一行的32次枚举涵盖了该问题的整个状态空间，因此该做法是正确的
  • 时间复杂度：32*25*5*500
    对第一行操作有32种可能 共有25个灯 每一次操作改变5个灯的状态 * 最多读入的时候可能有500次light矩阵
  • 如果是一个偶数^1,那么答案是偶数+1.如果是一个奇数^1,那么答案是奇数-1。

代码 by y总

注释 by 小张同学 & grant

链接

补充说明：

首先，这题根本就没有什么所谓的状压dp，而且只有一个地方用到了状态压缩，即第一行按开关的方式

本题主要的考察内容其实就是位运算，暴力以及一些递推思想

1.高票题解代码中的 if (k >> j & 1) 究竟什么意思？

其中，k保存的根本就不是第一行的灯所有可能的状态，不然它第j位都为1了还按它干嘛？ k单纯只是保存了第一行按开关的32种方式，与输入数据无关。

且大多数题解代码中都规定了k在二进制下某位为1就代表我们选择按下这一位所在编号的开关，你也可以自己规定k在二进制下某位为0才代表我们选择按下这一位所在编号的开关，这都无所谓。

比如k在二进制下表示为10001，就代表我们选择按第一行编号为0和编号为4的开关，然后对输入数据中第一行这两位执行turn操作。

2.递推思想

当前行若某一位(i,j)为0，那就用其所在列的下一行(i+1,j)去执行turn操作，以使(i,j)变为1，即变亮。

如果对(i,j)执行turn操作，使(i,j)变为1，就会破坏上一行的灯的状态。

所以只能从下一行去改变上一行的灯的状态。

作者：月入星河晚
链接：https://www.acwing.com/solution/content/22367/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// 2021.12.16 新写法，易于理解
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int g[6][6],backup[6][6];
int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};

void change(int x,int y){
    g[x][y] = !g[x][y];
    for (int i = 0;i < 4;i ++){
        int l = x + dx[i],r = y + dy[i];
        if (l >= 1 && l <= 5 && r >= 1 && r <= 5){
            g[l][r] = !g[l][r];
        }
    }
}

int cal(){
    int ans = 10;
    
    for (int op = 0;op < 32;op ++){
        int res = 0;
        memcpy(backup,g,sizeof g); // 保存现场
        for (int i = 0;i < 5;i ++){
            if (op >> i & 1){
                change(1,i+1);
                res ++;
            }
        }
        
        for (int i = 1;i <= 4;i ++){
            for (int j = 1;j <= 5;j ++){
                if (!g[i][j]){
                    change(i+1,j);
                    res++;
                }
            }
        }
        
        bool flag = true;
        for (int i = 1;i <= 5;i ++){
            if (!g[5][i]){
                flag = false;break;
            }
        }
        
        if (flag) ans = min(res,ans);
        memcpy(g,backup,sizeof g); // 恢复现场
    }
    if (ans > 6) return -1;
    else return ans;
}

int main(){
    int n;
    cin >> n;
    
    while (n--){
        char str[5];
        for (int i = 1;i <= 5;i ++){
            cin >> str;
            for (int j = 1;j <= 5;j ++){
                g[i][j] = str[j-1] - '0';
            }
        }
        cout << cal() << '\n';
    }
    
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！