某岛

… : "…アッカリ～ン . .. . " .. .
April 26, 2023

AtCoder Regular Contest 159

Problem B. GCD Subtraction

和前一天 Beginner Contest 297 的 D 题很像！但是需要更多的智力。

不失一般性，考虑 a <= b，首先我们构造一个数据让暴力挂掉，比如 a=n, b=n+1，因为每次 d = gcd(a,b) 都是 1。
对于 d 不是 1 的情况，后面的 d 也都是 d 的倍数，因此可以直接 a/=d, b/=d 然后归成 d=1 的情况处理。

现在就是考虑 d = 1 的情况具体会持续多久，也就是我们要找到一个最小的 t，使得新的 d > 1，
如果我们能 O(1) 的算出这个值，那么每次至少 /= 2，我们就能得到一个 O(logn) 的做法。

由于减法操作不改变 a、b 之差，所以我们有：
1. d | b-a
2. a = b (mod d)

只要检查的 d 的因子即可，每次的 t 取 a % d，从中找到最小值即可，复杂度为 O(log(n)sqrt(n))。

#include <lastweapon/io>
using namespace lastweapon;

int main() {

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif

    LL a, b; RD(a, b); if (a > b) swap(a, b); LL z = 0;
    while (a) {
        LL d = __gcd(a, b); a /= d; b /= d;
        LL m = b-a, t = a;
        if (m > 1) {
            checkMin(t, a % m);
            for (d=2;d*d<=m;++d) if (m%d == 0) {
                checkMin(t, a % d);
                checkMin(t, a % (m/d));
            }
        }
        a -= t; b -= t; z += t;
    }
    cout << z << endl;
}

进一步 b-a 中间只会除以 d，又因为 d 一定是素因子的情况下 t 更优，所以可以进一步用预处理优化复杂度到 O(sqrt(n))。

Problem F. Good Division

虽然是 F 题，做法却意外的简单。

不难证明，一个序列是好的，当且仅当不存在 majority。
（这个概念是不是没中文对应？= =）
总之我们立刻得到一个 O(n2) 的动态规划。

#include <lastweapon/io>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(1e6) + 9;
Int f[N]; int a[N], c[N];
int n, maj;

void add(int x) {
    ++c[x]; if (c[x] > c[maj]) maj = x;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    MOD = 998244353;
    RD(n); REP(i, 2*n) RD(a[i]);

    f[0] = 1;

    REP_1(i, n) {
        maj = 0;
        DWN(j, i, 0) {
            add(a[j*2]); add(a[j*2+1]);
            if (!(c[maj] > i-j)) f[i] += f[j];
        }
        DWN(j, i, 0) c[a[j*2]] = c[a[j*2+1]] = 0;
    }
    cout << f[n] << endl;
}

然后怎么办？cdq 分治啊！
可具体怎么分治呢，好像不太容易拿数据结构维护的样子。。。

如果输入的元素互不相同的话，那么 dag 的边很容易是 O(n2) 级别的，
但是如果我们考虑补图，却会发现转移要稀疏很多，于是考虑进行容斥 … 先把和算了再把不合法的减掉。。

进一步思考 cdq 分治，分治之后，我们枚举每一个可能的 maj，从左侧影响右侧的转移现在可以用类似摩尔投票法的方法用前缀和维护成线性，虽然可能有很多 maj，但是每次要考察的范围和 maj 出现的次数相关，合起来还是线性，于是我们得到了一个 O(nlogn) 的做法，最后只要处理好细节就好了。

具体说来，对于每个潜在的 maj，我们先根据其出现次数，得到左右可能影响到的最远边界，然后从中间开始左右两边分别预处理摩尔示数，
就是摩尔投票法中间维护的那个 maj 的出现次数，maj 存在等价于示数大于 0，我们只要找到这些区间即可，而这只需要枚举右区间，对左区间预处理出所有示数 >= x 的位置的 dp 和即可。

#include <lastweapon/io>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(1e6) + 9;
Int f[N]; int a[N], c[N]; VI b;
Int fs[N*2]; int ps[N];
int n;

void add(int i) {
    REP(o, 2) {
        int x = a[i*2 + o];
        if (!c[x]++) b.PB(x);
    }
}

int get_p(int i, int x) {
    return (a[i*2] == x ? 1 : -1) + (a[i*2+1] == x ? 1 : -1);
}

void gao(int l, int m, int r, int x) {
    ps[m-1] = 0; FOR(i, m, r) ps[i] = ps[i-1] + get_p(i-1, x);
    DWN(i, m-1, l) ps[i] = ps[i+1] + get_p(i, x);

    int ll = INF, rr = -INF;
    FOR(i, l, m) {
        checkMin(ll, ps[i]); checkMax(rr, ps[i]+1);
        fs[N+ps[i]] += f[i];
    }

    ll += N; rr += N; DWN(i, rr, ll) fs[i] += fs[i+1];
    FOR(i, m, r) f[i] -= fs[max(N+1-ps[i], ll)];
    FOR(i, ll, rr) fs[i] = 0;
}

void cdq(int l, int r) {
    if (l + 1 == r) return;
    int m = (l+r+1)>>1;
	cdq(l, m);
	Int s = 0; FOR(i, l, m) s += f[i]; FOR(i, m, r) f[i] += s; FOR(i, l, r-1) add(i);
	for (auto x: b) gao(max(l, m-c[x]), m, min(r, m+c[x]), x);
	for (auto x: b) c[x] = 0; b.clear();
	cdq(m, r);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    MOD = 998244353;
    RD(n); REP(i, 2*n) RD(a[i]);

    f[0] = 1; cdq(0, n+1);
    cout << f[n] << endl;
}

btw, 题解 语法好怪。。完全看不懂。
但是看 jly 的代码 哇，好像确实可以直接线性做。。。
核心是考察区间更局部的性质。。

这让我想起来 Deltix Round, Autumn 2021 的 F 题，比赛时也是一大堆 cdq 分治。。。但是其实有更好的单调栈的做法。。。反正我觉得能用单调栈的都应该尽可能用单调栈，比如前一天的 G 题。。

Posted by xiaodao
Category: 日常

« | »

  • Archives

    open all | close all