[SCOI2005]扫雷

分手后的思念是犯贱 2021-12-21 21:21 247阅读 0赞

这道题一开始尝试用数学方程来解，后来觉得太复杂，事实上解的个数很少，所以就考虑搜索了，不确定的格子枚举，确定的格子填上，如果发现错误就退出。

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <algorithm>
     5 
     6 using namespace std;
     7 
     8 #define re register
     9 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
    10 #define repd(i, a, b) for (re int i = a; i >= b; --i)
    11 #define maxx(a, b) a = max(a, b);
    12 #define minn(a, b) a = min(a, b);
    13 #define LL long long
    14 #define inf (1 << 30)
    15 
    16 inline int read() {
    17     int w = 0, f = 1; char c = getchar();
    18     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
    19     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
    20     return w * f;
    21 }
    22 
    23 const int maxn = 1e4 + 5;
    24 
    25 int n, a[maxn], b[maxn], ans = 0;
    26 
    27 void dfs(int x) {
    28     if (x == n+1 && a[x-1] == b[x-2] + b[x-1]) {
    29         ans++;
    30         return;
    31     }
    32     if (x > 1) {
    33         if (a[x-1] == b[x-1] + b[x-2]) {
    34             b[x] = 0;
    35             dfs(x+1);
    36         }
    37         else if (a[x-1] == b[x-1] + b[x-2] + 1) {
    38             b[x] = 1;
    39             dfs(x+1);
    40         }
    41         else return;
    42     } else {
    43         b[x] = 0;
    44         dfs(x+1);
    45         b[x] = 1;
    46         dfs(x+1);
    47     }
    48 }
    49 
    50 int main() {
    51     n = read();
    52 
    53     rep(i, 1, n) a[i] = read();
    54 
    55     dfs(1);
    56 
    57     printf("%d", ans);
    58 
    59     return 0;
    60 }

转载于:https://www.cnblogs.com/ac-evil/p/10316374.html

发表评论取消回复

表情：

评论列表（有 0 条评论，247人围观）

还没有评论，来说两句吧...

相关阅读

相关 BZOJ 1087- [SCOI2005]互不侵犯【状压DP】

题目描述在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。输入

快来打我*/ 2023年10月11日 11:57/ 0 赞/ 59 阅读

相关 P2330 [SCOI2005]繁忙的都市

题目描述城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相

╰半夏微凉°/ 2023年07月12日 01:29/ 0 赞/ 26 阅读

相关 P2330-[SCOI2005]繁忙的都市

1 include <bits/stdc++.h> 2 using namespace std; 3 define pb push_back

墨蓝/ 2023年06月01日 08:55/ 0 赞/ 20 阅读

相关 P2327-[SCOI2005]扫雷

1 include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll;

小鱼儿/ 2023年06月01日 08:54/ 0 赞/ 6 阅读

相关扫雷

扫雷游戏是晨晨和小璐特别喜欢的智力游戏，她俩最近沉迷其中无法自拔。该游戏的界面是一个矩阵，矩阵中有些格子中有一个地雷，其余格子中没有地雷。游戏中，格子可能处于己知和未

深藏阁楼爱情的钟/ 2022年06月08日 23:48/ 0 赞/ 198 阅读

相关 P2327 [SCOI2005]扫雷

[https://www.luogu.org/problem/show?pid=2327][https_www.luogu.org_problem_show_pid_2327]

浅浅的花香味﹌/ 2022年06月07日 14:08/ 0 赞/ 170 阅读

相关扫雷外挂（扫雷辅助程序）

1. 程序演示 ![在这里插入图片描述][20190624222439696.gif] 2. 程序实现思路主要分为以下三部分【定位窗口】【将扫雷界面转化为矩阵存

我会带着你远行/ 2022年01月06日 12:41/ 0 赞/ 895 阅读

相关 [SCOI2005]扫雷

这道题一开始尝试用数学方程来解，后来觉得太复杂，事实上解的个数很少，所以就考虑搜索了，不确定的格子枚举，确定的格子填上，如果发现错误就退出。 1 include <i

分手后的思念是犯贱/ 2021年12月21日 21:21/ 0 赞/ 248 阅读

相关 SCOI2009迷路

当初学矩阵幂的时候弃掉了，那时候只会用矩阵优化递推，碰到这种图论的瞬间躺地。昨天听学长的课，有一道例题，在边权为一的图上求从某点到某点的路径方案数，只要对邻接矩阵跑qpow

梦里梦外;/ 2021年12月03日 11:13/ 0 赞/ 280 阅读

相关 P2324 [SCOI2005]骑士精神

[传送门][Link 1] 直接 $dfs$ 会 $T$ 飞，$BFS$ 又会爆空间考虑迭代加深搜索，枚举走的最大步数， $dfs$ 时如果步数大于枚举的步数就返回然

朱雀/ 2021年10月29日 09:30/ 0 赞/ 332 阅读