100 + 20 + 25 + 0, rk 90.

评价是昨天上的分今天全吐出去了。

虽然但是，思维好场！

A

一个偏难的签到题。

我们考虑，先把这个图建出来，那么我们分类考虑一下：

对于直接走来说，我们只需要判断周围六格有没有空格即可，实现较为容易。

对于跳来说，我们考虑先根据每个有棋子的店把边建出来，那么我们每次需要查询的就是周围可达的联通块大小总和。这部分可以用并查集实现。并且注意去重，即我们不能访问到任意一个已经访问过的联通块。所以代码实现的时候注意一下细节即可。

时间复杂度理论上是 \mathcal{O}(6n\log n) 但是我实现的不好 97 了。开摆。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cassert>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define int long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    int v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

const ll mod = 998244353;
const double eps = 1e-10;
const int N = 1e6 + 10;

vector <int> G[N],G2[N];
vector <pii> poi;
map <pii,int> pos;
int n,vis[N],tot,ans[N][10],chk[N],siz[N];
pii rev[N];

void addedge(int x,int y) {
    if (!pos.count(mp(x,y))) pos[mp(x,y)] = ++tot,rev[tot] = mp(x,y);

    if (!pos.count(mp(x-1,y-1))) pos[mp(x-1,y-1)] = ++tot,rev[tot] = mp(x-1,y-1);

    if (!pos.count(mp(x-1,y))) pos[mp(x-1,y)] = ++tot,rev[tot] = mp(x-1,y);

    if (!pos.count(mp(x,y-1))) pos[mp(x,y-1)] = ++tot,rev[tot] = mp(x,y-1);

    if (!pos.count(mp(x+1,y+1))) pos[mp(x+1,y+1)] = ++tot,rev[tot] = mp(x+1,y+1);

    if (!pos.count(mp(x+1,y))) pos[mp(x+1,y)] = ++tot,rev[tot] = mp(x+1,y);

    if (!pos.count(mp(x,y+1))) pos[mp(x,y+1)] = ++tot,rev[tot] = mp(x,y+1);

    G[pos[mp(x-1,y-1)]].push_back(pos[mp(x+1,y+1)]);
    G[pos[mp(x+1,y+1)]].push_back(pos[mp(x-1,y-1)]);

    G[pos[mp(x,y-1)]].push_back(pos[mp(x,y+1)]);
    G[pos[mp(x,y+1)]].push_back(pos[mp(x,y-1)]);

    G[pos[mp(x+1,y)]].push_back(pos[mp(x-1,y)]);
    G[pos[mp(x-1,y)]].push_back(pos[mp(x+1,y)]);
}

int check(pii p) {
    int tmp =0;
    int x = p.first,y = p.second;
    if (!chk[pos[mp(x-1,y-1)]]) ++tmp;
    if (!chk[pos[mp(x-1,y)]]) ++tmp;
    if (!chk[pos[mp(x,y-1)]]) ++tmp;
    if (!chk[pos[mp(x+1,y+1)]]) ++tmp;
    if (!chk[pos[mp(x+1,y)]]) ++tmp;
    if (!chk[pos[mp(x,y+1)]]) ++tmp;
    return tmp;
}

int f[N];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void merge(int x,int y) {
    int fx = find(x),fy = find(y);
    if (fx == fy) return ;
    if (siz[fy] > siz[fx]) swap(fx,fy);
    f[fy] = fx;siz[fx] += siz[fy];
}

signed main() {
    //FO(ex_checkers2)
    read(n);
    for (int i = 1;i <= n;++i) {
        int x,y;read(x,y);
        addedge(x,y);
        poi.push_back(mp(x,y));chk[pos[mp(x,y)]] = 1;
    }
    for (int i = 1;i <= tot;++i) f[i] = i,siz[i] = 1;
    for (int i = 1;i <= tot;++i) {
        if (!chk[i]) {
            for (auto y : G[i]) {
                if (!chk[y])merge(y,i);
            }
        }
    }
    //for (int i = 1;i <= tot;++i) printf("%d %d\n",siz[i],find(i));

    //printf("%d\n",pos.size());
    for (auto x : poi) {
        int num = pos[x],tmp = 0;
        vector <int> used;
        tmp += check(x);
        for (auto y : G[num]) {
            if (!chk[y]) {
                int nxt = find(y);
                if (vis[nxt]) continue;
                vis[nxt] = 1;used.push_back(nxt);
                tmp += siz[nxt];
            }
        }
        printf("%d\n",tmp);
        for (auto x : used) vis[x] = 0;
    }
    return 0;
}

B

字符串嘿嘿我的字符串嘿嘿

首先我们先观察一下这个题的本质，发现直接处理 \theta 操作是相对困难的。我们考虑如何转化一下这个操作。原串以下记为 a。

考虑构造一个 b 串，有 b_i = \theta(a_{n - i + 1})。发现我们如果对于 a_{[l,r]}，执行 \theta 操作等价于令 a_{[l,r]} = b_{[n - r +1,n-l+1]}。那么我们需要考虑的是，如果我们确定了一个左端点 x，我们需要考虑的就是确定一个右端点 y 可以让答案串 ans = a_{[1,x-1]} + b_{[n - y +1,n-x+1]} + a_{[y+1,n]} 字典序最小。

接下来我们考虑对于形如答案串的两个字符串，如何比较他们的的字典序大小？这实际上是一个可以用 二分 + Hash 在单次 \mathcal{O}(\log n) 时间内实现的经典 trick。我们考虑我们可以利用二分在 \mathcal{O}(\log n) 的时间内求出两个串的 LCP.接下来我们考虑对于两组决策 (x,y_1),(x,y_2) 进行讨论：

• 如果 len_{lcp} < \min\{len_1,len_2\} 那么我们可以直接比较 b_{len_{lcp} + 1} 这一位来判断。
• 如果 len_{lcp} = \min\{len_1,len_2\} 那么我们需要接着比较剩下在 a 中的那段，这个实现相对复杂。

可以参考代码：

int hsh1(int l, int r) {
    return (h1[r] + (M1 - h1[l - 1]) * 1ll * pw1[r - l + 1]) % M1;
}
int hsh2(int l, int r) {
    return (h2[r] + (M2 - h2[l - 1]) * 1ll * pw2[r - l + 1]) % M2;
}
int lcp(int x, int y) {
    int l = 0, r = min(n * 2 - x + 1, n * 2 - y + 1), md;
    for (; l < r;) {
        md = (l + r >> 1) + 1;
        if (hsh1(x, x + md - 1) == hsh1(y, y + md - 1) && hsh2(x, x + md - 1) == hsh2(y, y + md - 1))
            l = md;
        else
            r = md - 1;
    }

    return l;
}
bool cmp(int bg, int x, int y) {
    int l = lcp(n * 2 - x + 1, n * 2 - y + 1);

    if (y - l >= bg)
        return s[x - l] > s[y - l];

    x -= y - bg + 1;
    l = lcp(n * 2 - x + 1, y + 1);
    return l <= x - bg && 5 - s[x - l] < s[y + l + 1];
}

如此，我们对于每个左端点做一遍，时间复杂度达到了 \mathcal{O}(n ^ 2\log n)，和暴力老哥一个分。

接下来则是最重要的观察：左端点一定是翻转后能变小的第一个字符。

这实际是一个基于贪心的考虑，我们考虑如果最开始的那个字符可以变小，那么我们如果更改接下来的字符实际上在字典序方面是不会更优的。

如果翻转后都不能变小，那么就翻转最后一个。如果翻转后左端点相等，那么把区间左右往里各缩一步，是没有区别的。 翻转后能变小，要么是本身就是 G 或 T, 要么本身是 C 并且后面有 T.

这样我们就把我们需要考虑的点缩小到了仅剩一个，那么时间复杂度就变成了 \mathcal{O}(n\log n)，代码实现是贺的学弟（

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair <int, int> pi;
#define mp make_pair
#define fi first
#define se second
const int N = 1e5 + 5, mod = 1e9 + 7;

const pi base = mp(131, 13331);
int add(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
pi operator + (pi x, pi y) { return mp(add(x.fi, y.fi), add(x.se, y.se)); }
pi operator - (pi x, pi y) { return mp(del(x.fi, y.fi), del(x.se, y.se)); }
pi operator * (pi x, pi y) { return mp(1ll * x.fi * y.fi % mod, 1ll * x.se * y.se % mod); }
pi operator * (pi x, int y) { return mp(1ll * x.fi * y % mod, 1ll * x.se * y % mod); }

int n, c[5]; char s[N];
pi h[2][N], w[N];
const char ch[] = {0, 'A', 'C', 'G', 'T'};

int trans(char x) {
    if (x == 'A') return 1;
    if (x == 'C') return 2;
    if (x == 'G') return 3;
    return 4;
}
pi H(int ty, int l, int r) { return (h[ty][r] - h[ty][l - 1]) * w[n - r]; }
int cmp(int l1, int r1, int r2) {
    if (!r1) return r2;
    int l = 1, r = r1 - l1 + 1, L = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (H(1, n - r1 + 1, n - (r1 - mid + 1) + 1) == H(1, n - r2 + 1, n - (r2 - mid + 1) + 1)) l = mid + 1, L = mid;
        else r = mid - 1;
    }
    if (L <= r1 - l1) return s[r1 - L] > s[r2 - L] ? r1 : r2; 
    l = r + 1, r = r2 - l1 + 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (H(0, r1 + 1, l1 + mid - 1) == H(1, n - (r2 - (r1 - l1 + 1)) + 1, n - (r2 - mid + 1) + 1)) l = mid + 1, L = mid;
        else r = mid - 1;
    }
    if (L <= r2 - l1) return s[l1 + L] < 5 - s[r2 - L] ? r1 : r2;
    return r1; 
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) s[i] = trans(s[i]), c[s[i]]++;
    w[0] = mp(1, 1);
    for (int i = 1; i <= n; i++) w[i] = w[i - 1] * base;
    for (int i = 1; i <= n; i++) h[0][i] = h[0][i - 1] + w[i - 1] * (int)s[i];
    for (int i = n; i >= 1; i--) h[1][n - i + 1] = h[1][n - i] + w[n - i] * (int)(5 - s[i]);
    for (int i = 1; i <= n; i++) {
        int _c = 0;
        for (int j = 4; j > 5 - s[i]; j--) if (c[j]) { _c = j; break; }
        if (_c) {
            int r = 0;
            for (int j = i; j <= n; j++) if (s[j] == _c) r = cmp(i, r, j);
            for (int j = 1; j < i; j++) putchar(ch[s[j]]);
            for (int j = r; j >= i; j--) putchar(ch[5 - s[j]]);
            for (int j = r + 1; j <= n; j++) putchar(ch[s[j]]);
            return 0;
        }
        c[s[i]]--;
    }
    for (int i = 1; i < n; i++) putchar(ch[s[i]]);
    putchar(ch[5 - s[n]]);
    return 0;
}

D

我们考虑从区间角度解决这个问题。

首先我们考虑对于花费为 1 的时候，从 x 出发能到达的最左以及最右是哪里。显然如果没有括号匹配的话分别就是 x-1,x+1，如果有括号匹配的时候改一下即可。

接下来我们考虑对于花费为 k 的时候进行讨论，发现可以倍增来算。这里我们套用树的思想，考虑如果区间 b\in a，此时 a 代表了 x 跳 k 次的覆盖区间，b 表示 x 跳 k-1 次的覆盖区间，那么我们可以把 a 作为 b 的父亲。

那么接下来我们的问题就变成了每次查询 [x,x],[y,y] 两个点向上跳求 LCA，那么答案就是我们跳的次数了。

时间复杂度 \mathcal{O}(n\log n)

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;

int n, q, L[N][20], R[N][20]; char s[N];
int stk[N], tp, to[N];

int main() {
    scanf("%s", s + 1), n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') stk[++tp] = i;
        else to[i] = stk[tp], to[stk[tp--]] = i;
    }       
    for (int i = 1; i <= n; i++) {
        L[i][0] = max(1, min(i - 1, to[i]));
        R[i][0] = min(n, max(i + 1, to[i]));
    }
    for (int j = 1; j <= 19; j++)
        for (int i = 1; i <= n; i++) {
            L[i][j] = min(L[L[i][j - 1]][j - 1], L[R[i][j - 1]][j - 1]);
            R[i][j] = max(R[R[i][j - 1]][j - 1], R[L[i][j - 1]][j - 1]);
        }
    scanf("%d", &q);
    for (int i = 1, x, y; i <= q; i++) {
        scanf("%d %d", &x, &y);
        if (x > y) swap(x, y);
        if (x == y) { 
            puts("0"); continue; 
        }
        int ans = 1, l = x, r = x;
        for (int j = 19; ~j; j--) {
            int tl = min(L[l][j], L[r][j]), tr = max(R[l][j], R[r][j]);
            if (tr < y) l = tl, r = tr, ans += (1 << j);
        }
        x = r, l = r = y;
        for (int j = 19; ~j; j--) {
            int tl = min(L[l][j], L[r][j]), tr = max(R[l][j], R[r][j]);
            if (tl > x) l = tl, r = tr, ans += (1 << j);
        }
        printf("%d\n", ans);
    }
    return 0;
}