題目鏈接戳這里
整理3道小題立刻睡了兑宇。

1-偏差排列

時間限制:10000ms
單點(diǎn)時限:1000ms
內(nèi)存限制: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]萄凤。
輸入
一個整數(shù)N。
對于50%的數(shù)據(jù)妒穴，1 ≤ N ≤ 15
對于100%的數(shù)據(jù)宋税，1 ≤ N ≤ 50
輸出
一個整數(shù)表示答案
樣例輸入 3 樣例輸出 3

分析：由于要滿足|pi-i|<=1，考慮已有一個長度為n-1的“1-偏差排列”讼油，插入第n個數(shù)字時杰赛，我們可以發(fā)現(xiàn)只有第n和第n-1個位置是符合條件的。記n個數(shù)的1-偏差排列數(shù)量為f(n)矮台，放第n個位置乏屯，排列有f(n-1)種，放第n-1個位置瘦赫，排列有f(n-2)種(第n-1個數(shù)被固定死在第n個位置)辰晕，所以是斐波那契數(shù)列，用數(shù)組遞推/矩陣方法都行确虱。小心最后int越界含友。

遞增N元組

時間限制:10000ms
單點(diǎn)時限:1000ms
內(nèi)存限制:256MB
描述
給定N個數(shù)組，每個數(shù)組都包含M個整數(shù)校辩。
現(xiàn)在你被要求從每個數(shù)組中選出一個數(shù)窘问，總共N個數(shù)。
在MN種選法中宜咒，有多少種選法滿足選出的N個數(shù)恰好是嚴(yán)格遞增的惠赫？
樣例中有5種選法：{1, 3, 4}, {1, 3, 9}, {1, 5, 9}, {1, 7, 9}, {6, 7, 9}
輸入

第一行包含兩個整數(shù)N和M。
以下N行荧呐，每行包含M個整數(shù)汉形。
對于50%的數(shù)據(jù)，1 ≤ N, M ≤ 100
對于100%的數(shù)據(jù)倍阐，1 ≤ N ≤ 100 M ≤ 10000 0 ≤ 每個整數(shù) ≤ 100000
輸出
由于答案可能非常大概疆，你只需要輸出答案模1000000007的余數(shù)。
樣例輸入
3 3
8 1 6
3 5 7
4 9 2
樣例輸出 5

分析：
動手畫一下“樹狀圖”峰搪，可知是DFA求葉子節(jié)點(diǎn)值之和岔冀，考慮用dp遞推。i和j都從1開始計數(shù)概耻，令dp[i][j]是：到第i號數(shù)組使套，取第j個元素時的取法數(shù)罐呼。那么答案將是∑dp[N][j]，其中j∈[1,M]侦高。
元素elements嫉柴，i號數(shù)組j元素我放在e[i][j]中，那么dp[i][j] = ∑dp[i-1][k]奉呛，其中k是e[i-1]數(shù)組中计螺，嚴(yán)格小于e[i][j]的元素個數(shù)。簡單來分析就是：要取到第i個數(shù)組的j元素瞧壮，那么到這兒的取法總數(shù)就是到上一個數(shù)組時登馒，比j嚴(yán)格小的元素的取法的和。但是到第i個數(shù)組咆槽，每個j元素都去查詢有多少個比自己小的(設(shè)為k個)陈轿，然后從第1項開始求這k項和會超時！我們先給元素都排個序秦忿。假設(shè)e[i-1]數(shù)組中比e[i][j-1]小的有k"個麦射，比e[i][j]小的有k個，那么e[i-1]中前k"項當(dāng)然也小于e[i][j]小渊，這部分的和無需重復(fù)求法褥，dp[i][j] = dp[i][j-1]，dp[i][j]再加上k"項后仍需的那k-k"項即可酬屉。

另外有個小tips：平時喜歡數(shù)組從0開始數(shù)半等，但在dp時，用1開始往往能更順心地去“一般化邊界情況”呐萨，建議從1開始杀饵，留下點(diǎn)空間來初始化。最終代碼：

#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
單點(diǎn)時限:1000ms
內(nèi)存限制:256MB
描述
小Hi被壞女巫抓進(jìn)里一間有N × N個格子組成的矩陣迷宮谬擦。
有些格子是小Hi可以經(jīng)過的切距，我們用'.'表示；有些格子上有障礙物小Hi不能經(jīng)過惨远，我們用'#'表示谜悟。小Hi的起始位置在左上角，他需要到達(dá)右下角的格子才能逃離迷宮北秽。小Hi每一步可以移動到上下左右四個方向相鄰的格子上葡幸，前提是目標(biāo)格式必須是沒有障礙的。
現(xiàn)在小Hi可以用魔法移除一個格子上的障礙贺氓，也就是'#'變成'.'蔚叨，使其可以經(jīng)過。
請你計算在只能移除一處障礙的情況下，小Hi最少移動多少步可以逃離迷宮蔑水。
輸入
第一行包含一個整數(shù)N邢锯。
以下N行包含一個N × N的矩陣。
矩陣保證左上角和右下角是'.'搀别。
對于70%的數(shù)據(jù)丹擎，1 ≤ N ≤ 100
對于100%的數(shù)據(jù)，1 ≤ N ≤ 1000
輸出
一個整數(shù)表示答案领曼。如果小Hi不能逃離迷宮鸥鹉，輸出-1蛮穿。
樣例輸入
4
.#..
#.#.
.##.
.#..
樣例輸出
6

這道題...有細(xì)節(jié)容易忽略庶骄。方法是：首先bfs還是比較容易確定的，然后遇到墻的時候践磅，如果本就可以走单刁，那便走，不可走府适，考慮用魔法羔飞，用了的話，自己包括以后自己擴(kuò)展的節(jié)點(diǎn)都要留下記錄檐春，防止再用逻淌。
注意2個地方：
一個是若是可直接走，驗(yàn)證的是vis[nx][ny][cur.q]疟暖，即根據(jù)cur節(jié)點(diǎn)來判斷是要修改“用了魔法的狀態(tài)”或者“沒用的”卡儒，這里很容易忽略，以為是平地俐巴，應(yīng)該判斷vis[nx][ny][0]的情況骨望，其實(shí)也有可能是用了魔法之后到平地的呀！

#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數(shù)組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坐標(biāo)欣舵，q:1/0表示是/否破過墻,cnt是步數(shù)
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;
}