SWOJ: /blog/24/6353c8438302fe4be9d03ce8

T1 蘑菇

只需特判 $a=14,b=15$（下一个为 $14$）和 $a=1,b=0$（下一个为 $1$）即可。若 $a<b$ ，则下一个数为 $b+1$ ；若 $a>b$ ，则下一个数为 $b-1$.

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int a, b;

int main() {
    cin >> a >> b;
    if (a < b) cout << ((b == 15) ? 14 : b+1) << endl;
    else cout << ((b == 0) ? 1 : b-1) << endl;
    return 0;
}

T2 序列

先来判断什么时候有解。显然，当且仅当序列 $a$ 为严格升序或严格降序时，$a$ 可被修改为一个等差数列。

设原序列为 $a_1,a_2,a_3,\cdots,a_n$，而 $a_1,a_n$ 一定，$d$ 越大则需要插入的数越少，而新数组的公差 $d$ 最大即为 $\gcd(a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1})$.

由等差数列项数公式，可得 $a_i\sim a_{i+1}$ 之间要插入 $\left(\dfrac{a_{i+1}-a_{i}}{d}-1\right)$ 个数，则 $\displaystyle\sum_{i=1}^{n-1} \left(\dfrac{a_{i+1}-a_{i}}{d}-1\right)$ 即为答案。

由于本题输入量较大，可以使用快读。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e6+10;

int t;
int n, d, ans, a[N];

int read() {
    int f = 1, x = 0;
    char c = _getchar_nolock();
    while (!isdigit(c)) {
        c = _getchar_nolock();
        if (c == '-') f *= -1;
    }
    while (isdigit(c)) {
        x = x * 10 + c - '0';
        c = _getchar_nolock();
    }
    return f * x;

}

int main() {
    t = read();
    while (t -- ) {
        ans = 0;
        n = read();
        for (int i = 1; i <= n; ++i) a[i] = read();

        d = a[2] - a[1];
        for (int i = 2; i <= n; ++i) {
            d = a[i] - a[i-1];
            if (d != a[2]-a[1]) break;
        }
        if (d == a[2]-a[1]) {puts("0"); continue;}

        for (int i = 2; i <= n; ++i) {
            if (a[i] - a[i-1] == 0) {d = 0; break;}
            else if ((d > 0 && a[i]-a[i-1] < 0) || (d < 0 && a[i]-a[i-1] > 0)) {d = 0; break;}
            d = __gcd(d, a[i]-a[i-1]);
        }
        if (d == 0) {puts("-1"); continue;}
        for (int i = 2; i <= n; ++i) ans += (a[i] - a[i-1]) / d - 1;
        printf("%d\n", ans);
    }
    return 0;
}

T3 破译

爆搜（理论可以骗到 $10\sim 20$ 分）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, int> piii;

const int mod = 1e9+7;

int n, m, t, ans = 0;
int a[1010];

int dis(int x1, int y1, int x2, int y2) {
    return (int)(abs(x1-x2) + abs(y1-y2));
}

void bfs(int x, int y) { 
    queue<piii> q;
    q.push({{x, y}, 1});
    while (q.size()) {
        auto u = q.front();
        q.pop();

        if (u.second == t) {ans = (ans + 1) % mod; continue;}

        int x = u.first.first, y = u.first.second, d = u.second;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (dis(i, j, x, y) <= a[d])
                    q.push({{x, y}, d+1});
            }
        }
    }
    return ;
}

int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i < t; ++i) scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            bfs(i, j);
    }

    cout << ans << endl;

    return 0;
}

T4 走路

或许可以通过最短路算法骗点分？