A – 等差子序列

因为是个排列，读入时我们可以把已有的数值放在数轴上，发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组，维护串和反串的哈希然后判断即可。

// FOJ1913.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 10100, bitnum = 133;
typedef unsigned long long ull;

int T, n, ai[MAX_N];
ull nodes[2][MAX_N], pw[MAX_N];

inline char nc()
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
        ch = nc();
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

inline int lowbit(int x) { return x & (-x); }

void update(ull *arr, int x)
{
    for (int i = x; i <= n; i += lowbit(i))
        arr[i] += pw[i - x];
}

ull query(ull *arr, int x, ull ret = 0)
{
    for (int i = x; i; i -= lowbit(i))
        ret += arr[i] * pw[x - i];
    return ret;
}

ull query(ull *arr, int l, int r) { return query(arr, r) - query(arr, l - 1) * pw[r - l + 1]; }

int main()
{
    T = read();
    for (int i = pw[0] = 1; i < MAX_N; i++)
        pw[i] = pw[i - 1] * bitnum;
    while (T--)
    {
        memset(nodes, 0, sizeof(nodes));
        n = read();
        bool flag = false;
        for (int i = 1; i <= n; i++)
        {
            ai[i] = read();
            int len = min(ai[i] - 1, n - ai[i]);
            if (len && query(nodes[0], ai[i] - len, ai[i]) != query(nodes[1], n - ai[i] - len + 1, n - ai[i] + 1))
                flag = true;
            update(nodes[0], ai[i]), update(nodes[1], n - ai[i] + 1);
        }
        puts(flag ? "Y" : "N");
    }
    return 0;
}

B – 最短路

我们考虑一个常见套路：也就是把环缩起来变成一棵树，然后用树上差分的套路来做。当然，我们不能直接硬算，因为假设 \(LCA\) 为一个环点，那么统计环上的一段弧长就比较麻烦。我们考虑先求出从\(1\)号点的单源最段路，然后再统计每个环点的环长，可知环上两点\(A, B\)的距离为：\(\min \{ |pre[A] – pre[B]|, loop – |pre[A] – pre[B]| \} \)。其中，\(pre\)是新树上的距离，新树为原图暴力破环（且随机）后的图。

// FOJ1914.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;
typedef pair<int, int> pii;
typedef long long ll;

int head[MAX_N], current, n, m, q, dfn[MAX_N], low[MAX_N], stk[MAX_N], tail, ptot;
int ncnt, aff[MAX_N], up[15][MAX_N], dep[MAX_N];
ll dist[MAX_N], loops[MAX_N], prefix[MAX_N];
bool inst[MAX_N], vis[MAX_N];

vector<int> G[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 1];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

void shortest_path(int src)
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pii> pq;
    pq.push(make_pair(0, src)), dist[src] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].weight)
                dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
    memset(vis, false, sizeof(vis));
}

void tarjan(int u, int fa)
{
    dfn[u] = ++ptot;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            if (dfn[edges[i].to] == 0)
                up[0][edges[i].to] = u, prefix[edges[i].to] = prefix[u] + edges[i].weight, tarjan(edges[i].to, u);
            else if (dfn[edges[i].to] < dfn[u])
            {
                loops[++ncnt] = 0LL + prefix[u] - prefix[edges[i].to] + edges[i].weight;
                for (int pt = u, pre; pt != edges[i].to;)
                    G[edges[i].to].push_back(pt), aff[pt] = ncnt, pre = up[0][pt], up[0][pt] = edges[i].to, pt = pre;
            }
        }
    if (up[0][u] == fa)
        G[fa].push_back(u);
}

void dfs_collect(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    for (int i = 0, siz = G[u].size(); i < siz; i++)
        if (G[u][i] != fa)
            dfs_collect(G[u][i], u);
}

ll query(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    int u = x, v = y;
    for (int i = 14; i >= 0; i--)
        if (dep[up[i][x]] >= dep[y])
            x = up[i][x];
    if (x == y)
        return dist[u] - dist[v];
    for (int i = 14; i >= 0; i--)
        if (up[i][x] != up[i][y])
            x = up[i][x], y = up[i][y];
    if (aff[x] && aff[x] == aff[y])
        return dist[u] - dist[x] + dist[v] - dist[y] + min(llabs(prefix[x] - prefix[y]), loops[aff[x]] - llabs(prefix[x] - prefix[y]));
    return dist[u] + dist[v] - (dist[up[0][x]] << 1);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1, u, v, w; i <= m; i++)
        scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w);
    shortest_path(1), tarjan(1, 0);
    dfs_collect(1, 0);
    for (int i = 1; i <= 14; i++)
        for (int j = 1; j <= ptot; j++)
            up[i][j] = up[i - 1][up[i - 1][j]];
    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%lld\n", query(x, y));
    }
    return 0;
}

C – 排斥反应

首先这个问题可以转换成在一个表格上做互不侵犯。具体转换的方式：左上角为起点，向左走视为\(+p\)，向右走视为\(+q\)，因为\(\gcd(p, q) = 1\)，所以表格上的数字各不相同。转换为这个问题之后，我们就可以设计一个状压 DP 的方程。发现状态必须满足两个一不相邻且前端、末端的\(1\)不相邻，所以当\(p = 10\)时，状态变少为\(123\)种。可以考虑矩阵快速幂。

// FOJ1915.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 150, mod = 19921107;

int p, q, stats[MAX_N], stat_tot;

struct matrix
{
    int mat[MAX_N][MAX_N];

    void clear() { memset(mat, 0, sizeof(mat)); }

    int *operator[](const int &rhs) { return mat[rhs]; }

    matrix operator*(const matrix &rhs)
    {
        matrix ret;
        ret.clear();
        for (int i = 1; i <= stat_tot; i++)
            for (int j = 1; j <= stat_tot; j++)
                for (int k = 1; k <= stat_tot; k++)
                    ret[i][j] = (1LL * ret[i][j] + 1LL * mat[i][k] * rhs.mat[k][j] % mod) % mod;
        return ret;
    }

    matrix operator^(const int &rhs)
    {
        int tim = rhs;
        matrix ret, bas = *this;
        ret.clear();
        for (int i = 1; i <= stat_tot; i++)
            ret[i][i] = 1;
        while (tim)
        {
            if (tim & 1)
                ret = ret * bas;
            bas = bas * bas;
            tim >>= 1;
        }
        return ret;
    }
} A, trans;

int main()
{
    scanf("%d%d", &p, &q);
    // process the stats;
    for (int i = 0; i < (1 << p); i++)
    {
        bool flag = true;
        for (int j = 1; j < p; j++)
            if ((i & (1 << (j - 1))) && (i & (1 << j)))
            {
                flag = false;
                break;
            }
        if (p != 1)
            flag &= (!((i & 1) && (i & (1 << (p - 1)))));
        if (flag)
            stats[++stat_tot] = i;
    }
    if (q == 1)
        printf("%d\n", stat_tot), exit(0);
    int ans = 0;
    trans.clear();
    for (int i = 1; i <= stat_tot; i++)
    {
        A[i][i] = 1;
        for (int j = 1; j <= stat_tot; j++)
            if (!(stats[i] & stats[j]))
                trans[i][j] = 1;
    }
    A = A * (trans ^ (q - 1));
    for (int i = 1; i <= stat_tot; i++)
        for (int j = 1; j <= stat_tot; j++)
            if (!(stats[i] & stats[j]))
                ans = (1LL * ans + A[i][j]) % mod;
    printf("%d\n", ans);
    return 0;
}