A 演讲

给定矩阵 \(g\)，如果 i 被 j D，那么 i 就会去 D \(g_{i,j}\)，一直循环下去，求第 d 个人。

\(n\le 600,d\le 10^{18}\)。

规律题。

可以发现状态 \((i,j)\) 只能转移到确定的一处，手模一下可以发现，这样下去会产生一个 ρ 型环。

只要预处理 \(n^2\) 个状态就能找到环。

const int N = 609;

int n, tot, cur;
LL d;
int g[N][N];
pair <int, int> mem[N*N];
map <pair <int, int>, int> mp;

inline void main() {
    read(n), read(d);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            read(g[i][j]);
    int i = 2, j = 1;
    mem[tot = 1] = make_pair(1, 0);
    for (int id = 2; ; ++id) {
        pair <int, int> t(i, j);
        if (mp.count(t)) {
            cur = mp[t];
            break;
        }
        mp[t] = id;
        mem[++tot] = t;
        int k = g[i][j];
        j = i, i = k;
    }
    if (d <= tot)
        printf("%d\\n", mem[d].first);
    else {
        d -= cur - 1;
        d = (d - 1) % (tot - cur + 1) + cur;
        printf("%d\\n", mem[d].first);
    }
}

B 卡车调度

题目

给出一个 n 点 m 边带权无向图，q 次询问：每次需要选的 x 和 y之间的路径和另外一条边（该边一端点是选定路径上的点），最小化这些边的最大值。

\(n,q\le 3\times 10^5,m\le10^6\)。

最小生成树 + 树链剖分。

易证该路径一定在最小生成树上，树链剖分或倍增维护。

问题在于如何处理多出来的这条边。

对于路径上的每个点（不包括两端），已经被两条边经过，第三条边一定不大于该点第三小的出边，直接维护每个点第三小的出边边值，端点单独处理。（这里的边是原图的边。）

为什么？如果已经经过的两条边为最小的两条出边，那么该边就是第三小的最优；如果不是，该边为最小或第二小，其权值会经过的那两条边覆盖。

最后只要对路径边权最大值和路径点第三小边权两者取最大值。

有些地方用了奇怪的 trick，莫名其妙被别人慢很多。好像还是最长的？？？

const int N = 3e5 + 9;
const int M = 1e6 + 9;
const int INF = 0x3f3f3f3f;

struct Graph {
    int cnt;
    int head[N], nxt[N<<1], to[N<<1], val[N<<1];
    inline void add(int u, int v, int w) {
        nxt[++cnt] = head[u], to[cnt] = v, val[cnt] = w, head[u] = cnt;
        nxt[++cnt] = head[v], to[cnt] = u, val[cnt] = w, head[v] = cnt;
    }
} G;
struct Edge {
    int x, y, val;
    bool operator <(const Edge &t) const {
        return val < t.val;
    }
};
struct FindSet {
    int fa[N];
    inline void init(int n) {
        for (int i = 1; i <= n; ++i) fa[i] = i;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
} F; 

int n, m, Q, tot;
int a1[N], a2[N], fa[N], deep[N], son[N], size[N], top[N], id[N];
Edge ed[M];
vector <int> out[N];

void dfs1(int u, int pre) {
    deep[u] = deep[pre] + 1;
    fa[u] = pre;
    size[u] = 1;
    for (int i = G.head[u], v; i; i = G.nxt[i]) {
        v = G.to[i];
        if (v == pre) continue;
        dfs1(v, u);
        size[u] += size[v];
        if (!son[u] || size[v] > size[son[u]]) son[u] = v;
    }
}

struct SegTree {
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
    int ma[N<<2];
    SegTree() {
        for (int i = 0; i < (N<<2); ++i) ma[i] = -INF;
    }
    inline void push_up(int suc) {
        ma[suc] = max(ma[ls(suc)], ma[rs(suc)]);
    }
    void build(int suc, int l, int r, int *a) {
        if (l == r) {
            ma[suc] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(suc), l, mid, a), build(rs(suc), mid+1, r, a);
        push_up(suc);
    }
    void update(int suc, int l, int r, int p, int k) {
        if (l == r) {
            ma[suc] = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(ls(suc), l, mid, p, k);
        else update(rs(suc), mid+1, r, p, k);
        push_up(suc);
    }
    int query(int suc, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return ma[suc];
        int mid = (l + r) >> 1, res = -INF;
        if (ql <= mid) res = max(res, query(ls(suc), l, mid, ql, qr));
        if (qr > mid) res = max(res, query(rs(suc), mid+1, r, ql, qr));
        return res;
    }
} tr1, tr2;

void dfs2(int u, int tp, int eval) {
    id[u] = ++tot;
    top[u] = tp;
    a1[id[u]] = eval;
    if (!son[u]) return;
    for (int i = G.head[u], v; i; i = G.nxt[i]) {
        v = G.to[i];
        if (v == son[u]) {
            dfs2(v, tp, G.val[i]);
            break;
        }
    }
    for (int i = G.head[u], v; i; i = G.nxt[i]) {
        v = G.to[i];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v, G.val[i]);
    }
}

inline int query1(int x, int y) {
    int res = -INF;
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x, y);
        res = max(res, tr1.query(1, 1, n, id[top[x]], id[x]));
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) swap(x, y);
    if (x != y) res = max(res, tr1.query(1, 1, n, id[x]+1, id[y]));
    return res;
}

inline int query2(int x, int y) {
    int res = -INF;
    int tx = x, ty = y;
    tr2.update(1, 1, n, id[tx], -INF), tr2.update(1, 1, n, id[ty], -INF);
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) swap(x, y);
        res = max(res, tr2.query(1, 1, n, id[top[x]], id[x]));
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) swap(x, y);
//	printf("> %d %d\\n", id[x], id[y]);
    res = max(res, tr2.query(1, 1, n, id[x], id[y]));
    tr2.update(1, 1, n, id[tx], a2[id[tx]]), tr2.update(1, 1, n, id[ty], a2[id[ty]]);
    return -res;
}

inline void main() {
    read(n), read(m), read(Q);
    for (int i = 1; i <= m; ++i) {
        read(ed[i].x), read(ed[i].y), read(ed[i].val);
    }
    F.init(n);
    sort(ed+1, ed+m+1);
    for (int i = 1; i <= m; ++i) {
        int x = F.find(ed[i].x), y = F.find(ed[i].y);
        if (x == y) continue;
        F.fa[x] = y;
        G.add(ed[i].x, ed[i].y, ed[i].val);
    }
    dfs1(1, 0), dfs2(1, 1, -INF), tr1.build(1, 1, n, a1);
    for (int i = 1; i <= m; ++i) {
        out[ed[i].x].push_back(ed[i].val);
        out[ed[i].y].push_back(ed[i].val);
    }
    for (int i = 1; i <= n; ++i) {
        sort(out[i].begin(), out[i].end());
        if (out[i].size() >= 3) a2[id[i]] = -out[i][2];
        else a2[id[i]] = -INF;
    }
    tr2.build(1, 1, n, a2);
    //for (int i = 1; i <= n; ++i) printf("%d ", id[i]); puts("");
    //printf(">> %d\\n", tr2.query(1, 1, n, 1, 3));
    int x, y;
    while (Q--) {
        read(x), read(y);
        int q1 = query1(x, y); //puts("(* _ *)");
        int q2 = query2(x, y);
        if (q2 == INF && out[x].size() == 1 && out[y].size() == 1) {
            printf("-1\\n");
            continue;
        }
        if (out[x].size() >= 2) q2 = min(q2, out[x][1]);
        if (out[y].size() >= 2) q2 = min(q2, out[y][1]);
        printf("%d\\n", max(q1, q2));
    }
}

C 篝火舞蹈

题目

给出 \([0,3^n]\) 的序列 \(a\)，有两个操作：1 操作将序列分成三部分，交换第二个和第三个部分，然后各部分递归重复该操作；2 操作将序列整体右移，即 \(a_i=a_{i-1},a_1=a_n\)。

\(n\le 12,Q\le 2\times 10^5\)。

trie 树。

真是难想又巧妙的思路。

将下标转化到 3 进制，可以发现 1 操作就是对于每一位将值为 1 的和值为 2 的交换。

那么可以放到 trie 树上，通过 lazy tag 优化（两次 1 操作会抵消）单次 \(\mathcal O(1)\)。

2 操作难以直接转化到 trie 树上，那么换一个编号方式：

~~这怎么想的到啊。~~因为 1 操作的性质，正反插 trie 都是一样的。

2 操作其实是让所有编号的位置加一，最低位是 0 和 1 的只改变 1 位，是 2 的会进位，所以从低位到高位插 trie 的话，每一层只要交换三个子树，然后往一个子树内递归即可，单次复杂度降至 \(\mathcal{O}(\log_2n)\)。

const int N = 1e6 + 9;

int n, lim, Q, tot;
int ch[N][3], id[N], tag[N], pw3[N], ans[N];
char s[N];

void build(int suc, int deep, int k) {
    if (deep == n) {
        id[suc] = k;
        return;
    }
    for (int i = 0; i < 3; ++i) {
        ch[suc][i] = ++tot;
        build(ch[suc][i], deep+1, k + i * pw3[deep]);
    }
}

inline void push_down(int suc) {
    if (!tag[suc]) return;
    swap(ch[suc][1], ch[suc][2]);
    for (int i = 0; i < 3; ++i)
        tag[ch[suc][i]] ^= 1;
    tag[suc] = 0;
}

void circle(int suc, int deep) {
    if (deep == n) return;
    push_down(suc);
    int t = ch[suc][2];
    ch[suc][2] = ch[suc][1], ch[suc][1] = ch[suc][0], ch[suc][0] = t;
    circle(ch[suc][0], deep+1);
}

void clear_tag(int suc, int deep, int k) {
    if (deep == n) {
        ans[id[suc]] = k;
        return;
    }
    push_down(suc);
    for (int i = 0; i < 3; ++i)
        clear_tag(ch[suc][i], deep+1, k + i * pw3[deep]);
}

inline void main() {
    read(n);
    scanf("%s", s+1);
    Q = strlen(s+1);
    pw3[0] = 1;
    for (int i = 1; i <= n; ++i) pw3[i] = pw3[i-1] * 3;
    lim = pow(3, n);
    build(tot = 1, 0, 0);
    for (int i = 1; i <= Q; ++i) {
        if (s[i] == 'S') tag[1] ^= 1;
        else circle(1, 0);
    }
    clear_tag(1, 0, 0);
    for (int i = 0; i < lim; ++i)
        printf("%d ", ans[i]);
    puts("");
}

D 练习曲

简单 DP。

不修改的话 DP 方程： \[ \begin{aligned} f_i&=\min_{i-L\le j<i}\{f_j\}+w(j+1,i)\\ w(j,i)&=\max\{\max_{j\le k<i}\{a_k\},\ a_i-1\} + 1 \end{aligned} \]

修改的话，发现一个点只影响 \(2L\) 个 DP 值，那么预处理正着和倒着分别 DP 一遍，处理影响的一段后拼接得到答案。

可以发现 \(f_i\) 是单调不降的。从 \((x-L,x]\) 中固定一个起点，当 \(x\) 所在段权值一定时，这一段越长越好。

所以每次只要 \(\mathcal O(L)\) 处理即可，复杂度 \(\mathcal O((n+q)L)\)。其实觉得过不了的。

const int N = 6e5 + 9;

int n, L, Q;
LL a[N], f[N], g[N];

inline void main() {
    read(n), read(L), read(Q);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + a[i];
        LL ma = a[i] - 1;
        for (int j = i - 1; j > 0 && i - j + 1 <= L; --j) {
            ma = max(ma, a[j]);
            f[i] = min(f[i], f[j - 1] + ma + 1);
        }
    }
    bool last = false;
    for (int i = n; i >= 1; --i) {
        g[i] = g[i + 1] + a[i];
        LL ma = a[i];
        for (int j = i + 1; j <= n && j - i + 1 <= L; ++j) {
            if (a[j] <= ma) last = true;
            else ma = a[j], last = false;
            g[i] = min(g[i], g[j + 1] + ma + last);
        }
    }
    int x;
    LL val;
    while (Q--) {
        read(x), read(val);
        LL ans = f[x - 1] + g[x + 1] + val;
        int j = x + 1;
        LL ma = val;
        for (int i = x - 1; i >= 0 && x - i <= L; --i) {
            while (j <= n && j - i - 1 <= L && a[j] <= ma) ++j;
            j = min(j, i + L + 1);
            ans = min(ans, f[i] + g[j] + ma + 1);
            ma = max(ma, a[i]);
        }
        j = x - 1, ma = val;
        bool last = false;
        for (int i = x + 1; i <= n + 1 && i - x <= L; ++i) {
            while (j > 0 && i - j - 1 <= L && a[j] < ma) --j;
            j = max(j, i - L - 1);
            ans = min(ans, f[j] + g[i] + ma + last);
            if (a[i] <= ma) last = true;
            else ma = a[i], last = false;
        }
        printf("%lld\n", ans);
    }
}

RenaMoe's Blog

20年11月14日模拟赛

A 演讲

B 卡车调度

C 篝火舞蹈

D 练习曲