1、a ^ b

题目描述

求 $a$ 的 $b$ 次方对 $p$ 取模的值。

输入格式

三个整数 $a,b,p$ ,在同一行用空格隔开。

输出格式

输出一个整数,表示 $a^b%p$的值。

数据范围

$0\le a,b,p\le10^9$
数据保证 $p\ne0$

输入样例:
3 2 7
输出样例:
2

思路及题解

快速幂模板

代码

#include<iostream>
using namespace std;
typedef long long LL;
LL a, b, p;
int main() {
    cin >> a >> b >> p;
    LL res = 1 % p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    cout << res << endl;
    return 0;
}

原题链接:https://ac.nowcoder.com/acm/problem/50906


2、64位整数乘法

题目描述

求 $a$ 乘 $b$ 对 $p$ 取模的值。

输入格式

第一行输入整数 $a$,第二行输入整数 $b$,第三行输入整数 $p$。

输出格式

输出一个整数,表示 $a*b%p$的值。

数据范围

$1\le a,b,p\le10^{18}$

输入样例:
3
4
5
输出样例:
2

思路及题解

快速幂模板

代码

#include<iostream>
using namespace std;

typedef unsigned long long ULL;

ULL a, b, p;

int main() {
    cin >> a >> b >> p;
    ULL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    cout << res << endl;
    return 0;
}

原题链接:https://ac.nowcoder.com/acm/problem/50908


3、最短Hamilton路径

题目描述

给定一张 $n$ 个点的带权无向图,点从 $0 \sim n-1$ 标号,求起点 $0$ 到终点 $n-1$ 的最短 $Hamilton$ 路径。 $Hamilton$ 路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$。

接下来 $n$ 行每行 $n$ 个整数,其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离(记为 $a[i, j]$)。

对于任意的 $x,y,z$,数据保证 $a[x,x]=0$,$a[x,x]=0$,$a[x,y]=a[y,x]$,并且$a[x,y] + a[y,z] \ge a[x,z]$。

输出格式

输出一个整数,表示最短 $Hamilton$ 路径的长度。

数据范围

$1 \le n\le 20$
$0 \le a[i,j] \le 10^7$

输入样例:
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例:
18

思路及题解

先看看暴力要怎么做,假设现在我们有$5$个点,分别是0,1,2,3,4
那在暴搜的情况下,会有以下几种路径:

  • $case 1:0 \to 1 \to 2 \to 3 \to 4$
  • $case 2:0 \to 1 \to 3 \to 2 \to 4$
  • $case 3:0 \to 2 \to 1 \to 3 \to 4$
  • $case 4:0 \to 2 \to 3 \to 1 \to 4$
  • $case 5:0 \to 3 \to 1 \to 2 \to 4$
  • $case 6:0 \to 3 \to 2 \to 1 \to 4$

我们观察 $case1$ 和 $case3$ ,可以发现在计算点 $0$ 到点 $3$ 时,其实我们并不关心这两中路径经过的点的顺序,而是只需要这两种路径中的较小值,因为只有较小值才有可能对答案有贡献。
所以,我们在枚举路径的时候,只需要记录两个属性:当前经过了哪些点当前到了哪个点
而我们当前经过的点并不是一个数,是个集合,由于输入数据 $n$ 不会超过 $20$ ,所以我们用一个二进制的 $0/1$ 序列来表示当前经过了哪些点,第 $i$ 位 为 $0$ 表示未经过,为 $1$ 表示已经过。这里用到了状态压缩DP思想。

考虑状态表示,这里用 $f[state][j]$ 表示:当前已经走过了的点的集合state,且当前停留在 $j$ 点上的所有路径的最小值。

然后考虑状态转移方程:假设当前要从 $k$ 点走到 $j$ 点,根据 $Hamilton$ 路径的定义,每个点只能走一次,所以当前已经走过的点不能包含 $j$ 点,即所有走到 $k$ 点的路径中不能包含 $j$ 点。所以状态方程可以写成
$$
f[state][j] = min(f[state][j], f[state - (1 \ll j)][k] + weight[k][j])
$$

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 20, M = 1 << 20;

int n;
int f[M][N], weight[N][N];

int main() {
    
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> weight[i][j];
        }
    }
    
    memset(f, 0x3f, sizeof f);
    
    f[1][0] = 0;
    
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (i >> j & 1) {
                for (int k = 0; k < n; ++k) {
                    if (i - (1 << j) >> k & 1) {
			// 若当前经过的点的集合去掉j点后,还包含k点才能进行转移。
			// 也可以不加,因为如果不包含k点,那f[state - (1 << j)][k]是正无穷,不会更新当前值
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);
                    }
                }
            }
        }
    }
    
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

原题链接:https://ac.nowcoder.com/acm/problem/50909


4、递归实现指数型枚举

题目描述

从 $1\sim n$ 这 $n$ 个整数中随机选取任意多个,输出所有可能的选择方案。

输入格式

输入一个整数 $n$。

输出格式

每行输出一种方案。

同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。

对于没有选任何数的方案,输出空行。

本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围

$1\le n\le 15$

输入样例:
3
输出样例:

3
2
2 3
1
1 3
1 2
1 2 3

思路及题解

运用二进制来表示当前数选或不选,$state | (1 \ll u)$ 表示将第u位置为1,即表示选第u个数。
$state\gg i & 1$ 表示获取第 $i$ 位是否为 $1$

代码

#include<iostream>
using namespace std;

int n;

void dfs(int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; ++i) {
            if (state >> i & 1) cout << i + 1 << ' ';
        }
        cout << endl;
        return;
    }
    
    dfs(u + 1, state | (1 << u));
    dfs(u + 1, state);
}

int main() {
    cin >> n;
    dfs(0, 0);
    return 0;
}

原题链接:https://ac.nowcoder.com/acm/problem/50911


5、递归实现组合型枚举

题目描述

从 $1\sim n$ 这 $n$ 个整数中随机选出 $m$ 个,输出所有可能的选择方案。

输入格式

两个整数 $n,m$ ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案,每行 $1$ 个。

首先,同一行内的数升序排列,相邻两个数用一个空格隔开。

其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如1 3 5 7排在1 3 6 8前面)。

数据范围
  • $n > 0$
  • $0 \le m\le n$
  • $ + {(n-m)}\le{25}$
输入样例:
5 3
输出样例:
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

思路及题解

和上一题差不多,只不过这题多了个限制,只能选 $m$ 个数

代码

#include<iostream>
using namespace std;

int n, m;

void dfs(int u, int cnt, int state) {
    if (n - u + cnt < m) return;
    if (cnt == m) {
        for (int i = 0; i < n; ++i) {
            if (state >> i & 1) cout << i + 1 << ' ';
        }
        cout << endl;
        return;
    }
    
    dfs(u + 1, cnt + 1, state | (1 << u));
    dfs(u + 1, cnt, state);
}

int main() {
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}

原题链接:https://ac.nowcoder.com/acm/problem/50918


6、递归实现排列型枚举

题目描述

把 $1\sim n$ 这 $n$ 个整数排成一行后随机打乱顺序,输出所有可能的次序。

输入格式

一个整数 $n$。

输出格式

按照从小到大的顺序输出所有方案,每行1个。

首先,同一行相邻两个数用一个空格隔开。

其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。

数据范围

$1\le n\le9$

输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路及题解

全排列,使用二进制来标记此数是否使用过

代码

#include<iostream>
#include<vector>
using namespace std;

int n;
vector<int> path;

void dfs(int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; ++i) cout << path[i] << " ";
        cout << endl;
    }
    
    for (int i = 0; i < n; ++i) {
        if (!(state >> i & 1)) {
            path.push_back(i + 1);
            dfs(u + 1, state | (1 << i));
            path.pop_back();
        }
    }
}

int main() {
    cin >> n;
    dfs(0, 0);
    return 0;
}

原题链接:https://ac.nowcoder.com/acm/problem/50919


7、费解的开关

题目描述

你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“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 \le 500$

输入样例:
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例:
3
2
-1

思路及题解

枚举第一行的所有点击操作,共 $1\ll5$ 种 ,完成第一行的操作后,固定第一行,然后从第一行开始递推,若达到第 $n$ 行不全为 $0$

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int INF = 0x3f;
char g[10][10];
int dir[5][2] = { {0, 0}, {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void turn(int x, int y) {
    for (int i = 0; i < 5; ++i) {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) g[nx][ny] ^= 1;
    }
}

int work() {
    int res = INF;
    for (int i = 0; i < (1 << 5); ++i) {
        int cnt = 0;
        char backup[10][10];
        memcpy(backup, g, sizeof g);
        for (int j = 0; j < 5; ++j) {
            if (i >> j & 1) {
                ++cnt;
                turn(0, j);
            }
        }
        
        for (int j = 0; j < 4; ++j) {
            for (int k = 0; k < 5; ++k) {
                if (g[j][k] == '0') {
                    ++cnt;
                    turn(j + 1, k);
                }
            }
        }
        
        bool success = true;
        for (int j = 0; j < 5; ++j) {
            if (g[4][j] == '0') {
                success = false;
                break;
            }
        }
        if (success) res = min(res, cnt);
        memcpy(g, backup, sizeof g);
    }
    
    if (res > 6) return -1;
    return res;
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        for (int i = 0; i < 5; ++i) cin >> g[i];
        
        cout << work() << endl;
    }
    return 0;
}

原题链接:https://ac.nowcoder.com/acm/problem/50920


Q.E.D.