题目链接戳这里
整理3道小题立刻睡了。
1-偏差排列
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
如果一个1~N的排列P=[P1, P2, ... PN]中的任意元素Pi都满足|Pi-i| ≤ 1，我们就称P是1-偏差排列。
给定一个N，请你计算一共有少个不同的排列是1-偏差排列。
例如对于N=3，有3个1-偏差排列：[1, 2, 3], [1, 3, 2], [2, 1, 3]。
输入
一个整数N。
对于50%的数据，1 ≤ N ≤ 15
对于100%的数据，1 ≤ N ≤ 50
输出
一个整数表示答案
样例输入 3 样例输出 3
分析：由于要满足|pi-i|<=1，考虑已有一个长度为n-1的“1-偏差排列”，插入第n个数字时，我们可以发现只有第n和第n-1个位置是符合条件的。记n个数的1-偏差排列数量为f(n)，放第n个位置，排列有f(n-1)种，放第n-1个位置，排列有f(n-2)种(第n-1个数被固定死在第n个位置)，所以是斐波那契数列，用数组递推/矩阵方法都行。小心最后int越界。
递增N元组
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定N个数组，每个数组都包含M个整数。
现在你被要求从每个数组中选出一个数，总共N个数。
在MN种选法中，有多少种选法满足选出的N个数恰好是严格递增的？
样例中有5种选法：{1, 3, 4}, {1, 3, 9}, {1, 5, 9}, {1, 7, 9}, {6, 7, 9}
输入
第一行包含两个整数N和M。
以下N行，每行包含M个整数。
对于50%的数据，1 ≤ N, M ≤ 100
对于100%的数据，1 ≤ N ≤ 100 M ≤ 10000 0 ≤ 每个整数 ≤ 100000
输出
由于答案可能非常大，你只需要输出答案模1000000007的余数。
样例输入
3 3
8 1 6
3 5 7
4 9 2
样例输出 5
分析：
动手画一下“树状图”，可知是DFA求叶子节点值之和，考虑用dp递推。i和j都从1开始计数，令dp[i][j]是：到第i号数组，取第j个元素时的取法数。那么答案将是∑dp[N][j]，其中j∈[1,M]。
元素elements，i号数组j元素我放在e[i][j]中，那么dp[i][j] = ∑dp[i-1][k]，其中k是e[i-1]数组中，严格小于e[i][j]的元素个数。简单来分析就是：要取到第i个数组的j元素，那么到这儿的取法总数就是到上一个数组时，比j严格小的元素的取法的和。但是到第i个数组，每个j元素都去查询有多少个比自己小的(设为k个)，然后从第1项开始求这k项和会超时！我们先给元素都排个序。假设e[i-1]数组中比e[i][j-1]小的有k"个，比e[i][j]小的有k个，那么e[i-1]中前k"项当然也小于e[i][j]，这部分的和无需重复求，dp[i][j] = dp[i][j-1]，dp[i][j]再加上k"项后仍需的那k-k"项即可。
另外有个小tips：平时喜欢数组从0开始数，但在dp时，用1开始往往能更顺心地去“一般化边界情况”，建议从1开始，留下点空间来初始化。最终代码：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const int maxN = 1e2 + 5, maxM = 1e4 + 5;
const int mod = 1e9 + 7;
int N, M, T;
int e[maxN][maxM];
int dp[maxN][maxM];
int main() {
scanf("%d%d", &N, &M);
dp[0][1] = 1;
rep(i, 1, N + 1) {
rep(j, 1, M + 1) {
scanf("%d", &e[i][j]);
}
sort(e[i] + 1, e[i] + M + 1);
int k = 0;
rep(j, 1, M + 1) {
dp[i][j] = dp[i][j - 1];
while (k <= M && e[i - 1][k] < e[i][j]) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
++k;
}
}
}
int ans = 0;
rep(j, 1, M + 1)
ans = (ans + dp[N][j]) % mod;
printf("%d", ans);
return 0;
}
逃离迷宫5
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi被坏女巫抓进里一间有N × N个格子组成的矩阵迷宫。
有些格子是小Hi可以经过的，我们用'.'表示；有些格子上有障碍物小Hi不能经过，我们用'#'表示。小Hi的起始位置在左上角，他需要到达右下角的格子才能逃离迷宫。小Hi每一步可以移动到上下左右四个方向相邻的格子上，前提是目标格式必须是没有障碍的。
现在小Hi可以用魔法移除一个格子上的障碍，也就是'#'变成'.'，使其可以经过。
请你计算在只能移除一处障碍的情况下，小Hi最少移动多少步可以逃离迷宫。
输入
第一行包含一个整数N。
以下N行包含一个N × N的矩阵。
矩阵保证左上角和右下角是'.'。
对于70%的数据，1 ≤ N ≤ 100
对于100%的数据，1 ≤ N ≤ 1000
输出
一个整数表示答案。如果小Hi不能逃离迷宫，输出-1。
样例输入
4
.#..
#.#.
.##.
.#..
样例输出
6
这道题...有细节容易忽略。方法是：首先bfs还是比较容易确定的，然后遇到墙的时候，如果本就可以走，那便走，不可走，考虑用魔法，用了的话，自己包括以后自己扩展的节点都要留下记录，防止再用。
注意2个地方：
一个是若是可直接走，验证的是vis[nx][ny][cur.q]，即根据cur节点来判断是要修改“用了魔法的状态”或者“没用的”，这里很容易忽略，以为是平地，应该判断vis[nx][ny][0]的情况，其实也有可能是用了魔法之后到平地的呀！
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const int inf = 0x3f3f3f3f, maxN = 1e4 + 5;
int N, M, T;
char G[maxN][maxN];
// vis数组vis[i][j][k],k0是未用魔法的 1是用了的
bool vis[maxN][maxN][2];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// x和y坐标，q:1/0表示是/否破过墙,cnt是步数
struct Node {
int x, y, q, cnt;
Node(int a, int b, int c, int d)
: x(a), y(b), q(c), cnt(d) {}
};
void bfs() {
mst(vis, 0);
queue<Node> Q;
Q.push(Node(0, 0, 0, 0));
vis[0][0][0] = vis[0][0][1] = 1;
int ans = -1;
while (!Q.empty()) {
Node cur = Q.front(); Q.pop();
if (cur.x == N - 1 && cur.y == N - 1) {
ans = cur.cnt;
break;
}
rep(d, 0, 4) {
int nx = cur.x + dx[d], ny = cur.y + dy[d];
if (0 <= nx && nx < N && 0 <= ny && ny < N) {
bool *vi = vis[nx][ny];
if (!vi[cur.q] && G[nx][ny] == '.') {
vi[cur.q] = 1;
Q.push(Node(nx, ny, cur.q, cur.cnt + 1));
} else if (!vi[1] && G[nx][ny] == '#' && cur.q == 0) {
vi[1] = 1;
Q.push(Node(nx, ny, 1, cur.cnt + 1));
}
}
}
}
printf("%d\n", ans);
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d", &N);
rep(i, 0, N)
scanf("%s", G[i]);
bfs();
return 0;
}
网友评论