A

令\[C_i=\min_{j>i,s_j=s_i}\{j-i\}\]，则题目中所说的B-Suffix Array等价于\(C_1,C_2,C_3,...，C_n\)。因此，只需要求出\(C\)后，对\(C\)算一下后缀数组即可。

代码如下：

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define mst(a, b) memset((a), (b), sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef, mid, rt << 1
#define rson mid + 1, rig, rt << 1 | 1
const int maxn = 1e5 + 5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int wa[maxn], wb[maxn], wv[maxn], wss[maxn], rak[maxn], height[maxn], cal[maxn], n, sa[maxn << 1];
char s[maxn];
int cmp(int* r, int a, int b, int l)
{
    return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int* r, int* sa, int n, int M)
{
    int i, j, p, *x = wa, *y = wb, *t;
    for (i = 0; i < M; i++)
        wss[i] = 0;
    for (i = 0; i < n; i++)
        wss[x[i] = r[i]]++;
    for (i = 1; i < M; i++)
        wss[i] += wss[i - 1];
    for (i = n - 1; i >= 0; i--)
        sa[--wss[x[i]]] = i;
    for (j = 1, p = 1; p < n; j <<= 1, M = p) {
        for (p = 0, i = n - j; i < n; i++)
            y[p++] = i;
        for (i = 0; i < n; i++)
            if (sa[i] >= j)
                y[p++] = sa[i] - j;
        for (i = 0; i < n; i++)
            wv[i] = x[y[i]];
        for (i = 0; i < M; i++)
            wss[i] = 0;
        for (i = 0; i < n; i++)
            wss[wv[i]]++;
        for (i = 1; i < M; i++)
            wss[i] += wss[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[--wss[wv[i]]] = y[i];
        for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
    return;
}
int main()
{
    //freopen("./A.in", "r", stdin);
    while (scanf("%d", &n) != EOF) {
        fill(cal, cal + maxn, 0);
        scanf("%s", s + 1);
        int pre[2] = { n + 1, n + 1 };
        for (int i = n; i >= 1; i--) {
            if (pre[s[i] - 'a'] == n + 1) {
                cal[i] = n;
            } else {
                cal[i] = pre[s[i] - 'a'] - i;
            }
            pre[s[i] - 'a'] = i;
        }
        cal[n + 1] = n + 1;
        //puts("cal: ");
        //for (int i = 1; i <= n + 1; i++) {
        //  printf("%d ",cal[i]);
        //}
        //puts("");
        //puts("----------------------");

        da(cal + 1, sa, n + 2, n + 2);
        for (int i = n; i >= 1; i--) {
            printf("%d%c", sa[i] + 1, i == 1 ? '\n' : ' ');
        }
    }
    return 0;
}

这道题\(n\)的值一定要是\(n+2\)，\(m\)的值一定也要是\(n+2\)！否则不是RE就是WA！

B

待补

C

待补

D

待补

E

待补

F

假设两个字符串\(a,b\)是同一个字符串的循环节，然后在\(2\times max(len(a),len(b))\)的范围内比较即可。如果发现没有不相等的字符，则说明两个无穷字符串是同一个字符串，也就是相等。否则，如果\(a_i<b_i\)，则\(a<b\)；大于的情况同理。这道题的比较范围比较玄学，是猜出来的，但根据题解，范围只需要到\(len(a)+len(b)-gcd(len(a),len(b))\)即可。但目前没想明白为什么。。。等一波详细题解。

G

待补

H

题意是说，给定一个\(n\)个点\(m\)条边的流网络，有\(q\)次询问，第\(i\)次询问会把图上所有边的容量都设为\(\frac{u_i}{v_i}\)，查询当前情况下，从点1发送一个单位的流到点\(n\)的最小花费是多少。

为了方便处理，将所有边的容量都乘以\(\frac{v_i}{u_i}\)，使其变成1；原本发送一个单位的流，现在变成发送\(\frac{v_i}{u_i}\)个单位的流（实际上就相当于定义了一个新单位，该单位和原单位的进率是\(\frac{v_i}{u_i}\)）。然后在算最大流的时候，再记录下不同流量下的最小花费。

而NaN的情况有两种：

  • \(u=0\)（不考虑这种情况会有除零错误）
  • \(v/u>\)最大流（非整除）

最后，注意一下处理最终答案的方法（代码165行）

代码如下：

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define mst(a, b) memset((a), (b), sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef, mid, rt << 1
#define rson mid + 1, rig, rt << 1 | 1
const int maxn = 100 + 5;
const int maxm = 200 + 5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct edge {
    int to;
    int nxt;
    int cap;
    int flow;
    int cost;
} es[maxm];
int head[maxn];
int tol;
int pre[maxn], dis[maxn];
bool vis[maxn];
ll ansarr[maxm];
int N; // 节点总个数, 节点从0~N-1
int M;
inline void init(int n)
{
    N = n;
    tol = 0;
    mst(head, -1);
}
inline void addedge(int u, int v, int cap, int cost)
{
    es[tol].to = v;
    es[tol].cap = cap;
    es[tol].cost = cost;
    es[tol].flow = 0;
    es[tol].nxt = head[u];
    head[u] = tol++;

    es[tol].to = u;
    es[tol].cap = 0;
    es[tol].cost = -cost;
    es[tol].flow = 0;
    es[tol].nxt = head[v];
    head[v] = tol++;
}
bool spfa(int s, int t)
{
    queue<int> que;
    for (int i = 0; i < N; i++) {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (int i = head[u]; i != -1; i = es[i].nxt) {
            int v = es[i].to;
            if (es[i].cap > es[i].flow && dis[v] > dis[u] + es[i].cost) {
                dis[v] = dis[u] + es[i].cost;
                pre[v] = i;
                if (!vis[v]) {
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
    }
    if (pre[t] == -1)
        return false;
    else
        return true;
}
ll mcmf(int s, int t, ll& cost)
{
    ll flow = 0;
    cost = 0;
    while (spfa(s, t)) {
        ll Min = INF;
        for (int i = pre[t]; i != -1; i = pre[es[i ^ 1].to]) {
            if (Min > es[i].cap - es[i].flow) {
                Min = es[i].cap - es[i].flow;
            }
        }
        for (int i = pre[t]; i != -1; i = pre[es[i ^ 1].to]) {
            es[i].flow += Min;
            es[i ^ 1].flow -= Min;
            cost += es[i].cost * Min;
        }
        flow += Min;
        ansarr[(int)flow] = cost;
    }
    return flow;
}
inline int read()
{
    char ch;
    int x = 0;
    int sign = 1;
    do {
        ch = getchar();
        if (ch == '-')
            sign = -1;
    } while (ch > '9' || ch < '0');
    while ('0' <= ch && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return x * sign;
}
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
//inline void Swap(ll& a,ll& b)
//{
//ll tmp=a;
//a=b;b=tmp;
//}
int main()
{
    while (scanf("%d %d", &N, &M) != EOF) {
        init(N);
        int ai, bi, ci;
        for (int i = 0; i < M; i++) {
            ai = read();
            bi = read();
            ci = read();
            ai--;
            bi--;
            addedge(ai, bi, 1, ci);
        }
        ll miniflow;
        ll maxiflow = mcmf(0, N - 1, miniflow);
        int q;
        q = read();
        int u, v;
        while (q--) {
            u = read();
            v = read();
            //printf("maxiflow = %lld\n",maxiflow);
            if (u == 0 || ((1LL * v) / u == maxiflow && (1LL * v) % u > 0) || (1LL * v) / u > maxiflow) {
                puts("NaN");
                continue;
            }
            int idx = v / u;
            ll up = ansarr[idx] * u + (ansarr[idx + 1] - ansarr[idx]) * (v % u);
            //if(v<up) Swap(v, up)
            ll g = gcd(1LL * v, up);
            printf("%lld/%lld\n", up / g, v / g);
        }
    }
    return 0;
}

I

待补

J

高数签到题。虽然这题是我A的，但是因为高数太菜，所以其实积分结果是在OEIS上找到的hhh。

积分过程如下： \[ \begin{aligned} \because (x-x^2)^n&=\frac{1}{4}-\left( \frac{1}{2}-x\right )^2 \\ \therefore \int_0^1(x-x^2)^ndx&=\int_0^1\left(\frac{1}{4}-\left(\frac{1}{2}-x\right)^2\right)^ndx\\ &=\frac{1}{4^n}\int_0^1\left(1-4\left(\frac{1}{2}-x\right)^2\right)^ndx\\ &=\frac{1}{4^n}\int_0^1\left(1-(2x-1)^2\right)^ndx \end{aligned} \] 令\(\sin t=2x-1\)，则有 \[ \begin{aligned} \int_0^1(x-x^2)^ndx&=\frac{1}{4^n}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(1-\sin^2t)^ndx\\ &=\frac{1}{4^n}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(1-\sin^2t)^n\frac{\cos t}{2}dt\\ &=\frac{1}{4^n}\int_0^{\frac{\pi}{2}}\cos^{2n+1}tdt \end{aligned} \]

由Wallis公式： \[ \int_0^{\frac{\pi}{2}}\cos^nxdx= \begin{cases} \frac{\pi(2k)!!}{2(2k+1)!!}&\text{n=2k}\\ \frac{(2k)!!}{(2k+1)!!}&\text{n=2k+1} \end{cases} \] 其中，\(\frac{(2k)!!}{(2k+1)!!}=\frac{2\times4\times6\times\dots\times(2n-2)\times2n}{1\times3\times5\times\dots\times(2n-1)\times(2n+1)}\)。因此，有 \[ \begin{aligned} \int_0^1(x-x^2)^ndx&=\frac{1}{4^n}\frac{(2n)!!}{(2n+1)!!}\\ &=\frac{1}{4^n}\frac{(2n)!!}{\frac{(2n+1)!}{(2n)!!}}\\ &=\frac{1}{4^n}\frac{(2n!!)^2}{(2n+1)!}\\ &=\frac{1}{4^n}\frac{4^n(n!)^2}{(2n+1)!}\\ &=\frac{(n!)^2}{(2n+1)!} \end{aligned} \] 得到上面的积分结果后，套式子再求个逆元就行了。

代码如下：