Visits: 354

JOI Open 2019

三级跳

考虑 $a,b$，注意到如果存在 $a < i < b$ 且 $A_i \ge A_a$，$A_i \ge A_b$，则选择 $a,i$ 或者 $i,b$ 一定比 $a,b$ 不劣。

因此理论上可能成为答案的 $a,b$ 只有 $\mathcal O(n)$ 组，具体而言就是每个 $i$ 的左右第一个 $\ge A_i$ 的位置，用单调栈就可以求出来。

把询问离线下来按照 $l$ 从大到小排序，用一个指针从右向左扫。

当扫到 $i$ 时，把所有 $a = i$ 的 $A_a + A_b$ 加到 $\ge 2b – a$ 的位置，然后对于所有 $l = i$ 的询问，查询 $[l,r]$ 的最大值。

用线段树维护即可，对于一个区间要维护最大的 $a$ 以及最大的加权。

时间复杂度 $\mathcal O(n \log n)$。

const int N = 5e5 + 7;
int n, m;
ui a[N], ans[N];
vector<pi> q[N];

struct SGT {
    struct T {
        int l, r;
        ui x, y, z;
    } t[N<<2|1];

    inline void update(int p) {
        t[p].z = max(t[ls].z, t[rs].z);
    }

    inline void work(int p, ui x) {
        t[p].z = max(t[p].z, t[p].x + (t[p].y = max(t[p].y, x)));
    }

    inline void spread(int p) {
        if (t[p].y) work(ls, t[p].y), work(rs, t[p].y), t[p].y = 0;
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) return t[p].x = a[l], void();
        build(ls, l, md), build(rs, md + 1, r);
        t[p].x = max(t[ls].x, t[rs].x);
    }

    void add(int p, int l, int r, ui x) {
        if (t[p].l >= l && t[p].r <= r) return work(p, x);
        spread(p);
        if (l <= md) add(ls, l, r, x);
        if (r > md) add(rs, l, r, x);
        update(p);
    }

    ui ask(int p, int l, int r) {
        if (t[p].l >= l && t[p].r <= r) return t[p].z;
        spread(p);
        ui ret = 0;
        if (l <= md) ret = max(ret, ask(ls, l, r));
        if (r > md) ret = max(ret, ask(rs, l, r));
        return ret;
    }
} sgt;

int s[N], t;
vi p[N];

int main() {
    rd(n), rda(a, n), sgt.build(1, 1, n), rd(m);
    for (int i = 1; i <= n; i++) {
        while (t && a[s[t]] < a[i]) p[s[t--]].pb(i);
        if (s[t]) p[s[t]].pb(i);
        s[++t] = i;
    }
    for (int i = 1, l, r; i <= m; i++)
        rd(l, r), q[l].pb(mp(r, i));
    for (int i = n; i; i--) {
        for (int j : p[i])
            if (2 * j - i <= n)
                sgt.add(1, 2 * j - i, n, a[i] + a[j]);
        for (pi o : q[i])
            ans[o.se] = sgt.ask(1, i, o.fi);
    }
    for (int i = 1; i <= m; i++) print(ans[i]);
    return 0;
}

汇款

暴力，不停地贪心地给钱。

由于每轮能给的钱数都会折半，因此最多只有 $\mathcal O(\log w)$ 轮。

最后判一下特殊情况即可。

const int N = 1e6 + 7;
int n, a[N], b[N]; 

int main() {
    rd(n);
    for (int i = 0; i < n; i++) rd(a[i], b[i]);
    while (1) {
        bool ok = 0;
        for (int i = 0, j = 1; i < n; i++, j = ++j == n ? 0 : j) {
            int c = (a[i] - b[i]) >> 1;
            if (a[i] - b[i] > 1) a[j] += c, a[i] -= c << 1, ok = 1; 
        }
        if (!ok) break;
    }
    bool ok1 = 1, ok2 = 1, ok3 = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) ok1 = 0;
        if (a[i] != b[i] + 1) ok2 = 0;
        if (a[i] >= 2) ok3 = 1;
    }
    prints((ok1 || (ok2 && ok3)) ? "Yes" : "No");
    return 0;
}

病毒实验

先预处理 $2^4$ 种状态在字符串环上的最长连续段。

考虑一开始每个点都是一个集合，每个集合中有一个特殊点，表示在这个集合中的所有点都可以感染到这个特殊点。

每次枚举一个集合 A，从 A 的特殊点开始 BFS，如果能 BFS 到 B 集合，则将 AB 集合合并，以 B 集合的特殊点作为合并后集合的特殊点。

如果 A 不能走到其他集合，则用它更新答案，A 的特殊点能感染到的点数就是这个集合的最小答案，同时也是方案数。

这么做时间复杂度为 $\mathcal O((nm)^2)$，考虑优化。

有一个求 MST 的算法叫 Boruvka 算法：

每次暴力地给每一个连通块找一条最小的出边，然后合并起来。
直到最后只剩下一个连通块。
每次连通块数都会减半，整个过程最多进行 $\mathcal O(\log n)$ 次。
时间复杂度为 $\mathcal O(n \log n)$。

用在这道题上就可以了，注意在 A 合并到 B 上之后，不能再用 B 向外找出边，否则会重复访问 A。

时间复杂度 $\mathcal O(nm \log (nm))$。

const int K = 2e5 + 7;
char s[K];
const char dc[] = {'N', 'S', 'W', 'E'};
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

const int N = 807;
int n, m, k, a[N][N], p[17], f[N*N], ans, cnt;
bool v[N][N], w[N*N];

int get(int x) {
    return x == f[x] ? x : (f[x] = get(f[x]));
}

inline int F(int x, int y) {
    return x * m + y;
}

inline void F(int z, int &x, int &y) {
    x = z / m, y = z - x * m;
}

inline bool pd(int x, int y) {
    if (!a[x][y]) return 0;
    int t = 0;
    for (int o = 0; o < 4; o++) {
        int X = x + dx[o], Y = y + dy[o];
        if (X < 0 || X >= n || Y < 0 || Y >= m) continue;
        if (v[X][Y]) t |= 1 << (o ^ 1);
    }
    return p[t] == k || p[t] >= a[x][y];
}

inline int work(int i) {
    int sx, sy, t = -1;
    F(i, sx, sy);
    queue<int> qx, qy;
    vi vx, vy;
    qx.push(sx), qy.push(sy), vx.pb(sx), vy.pb(sy), v[sx][sy] = 1;
    while (qx.size()) {
        int x = qx.front(), y = qy.front();
        qx.pop(), qy.pop();
        for (int o = 0; o < 4; o++) {
            int X = x + dx[o], Y = y + dy[o];
            if (X < 0 || X >= n || Y < 0 || Y >= m || v[X][Y]) continue;
            if (pd(X, Y)) {
                if (get(F(X, Y)) == i)
                    qx.push(X), qy.push(Y), vx.pb(X), vy.pb(Y), v[X][Y] = 1;
                else {
                    t = get(F(X, Y));
                    break;
                }
            }
        }
        if (~t) break;
    }
    for (ui i = 0; i < vx.size(); i++) v[vx[i]][vy[i]] = 0;
    if (~t) return f[i] = t, w[t] = 1, 0;
    return vx.size();
}

int main() {
    rd(k, n, m), rds(s, k);
    for (int i = 1; i <= k; i++) s[i+k] = s[i];
    k <<= 1;
    for (int s = 1; s < 16; s++) {
        map<char, bool> v;
        for (int i = 0; i < 4; i++)
            v[dc[i]] = s >> i & 1;
        for (int i = 1, t = 0; i <= k; i++)
            if (v[::s[i]]) p[s] = max(p[s], ++t);
            else t = 0;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            rd(a[i][j]);
    for (int i = 0; i < n * m; i++) f[i] = i;
    while (1) {
        for (int i = 0; i < n * m; i++) w[i] = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (!a[i][j]) w[F(i,j)] = 1;
        ans = 0, cnt = 0;
        bool ok = 0;
        for (int i = 0; i < n * m; i++)
            if (!w[i] && i == get(i)) {
                int ret = work(i);
                if (ret) {
                    if (!ans || ret < ans) ans = cnt = ret;
                    else if (ans == ret) cnt += ret;
                } else ok = 1;
            }
        if (!ok) break;
    }
    print(ans), print(cnt);
    return 0;
}