CF1654CDE 题解

CF1654C

有一块大小为任意正整数蛋糕，可进行以下操作任意次（可以是 $0$ 次）得到一个无序蛋糕的集合：

• 选择一块蛋糕，它的大小为 $w$，则切为 $\lfloor\dfrac{w}{2}\rfloor$ 和 $\lceil\dfrac{w}{2}\rceil$ 两块放回；

现在给一个有 $n$ 个蛋糕的集合 $a$，问是否合法，即能否通过若干次操作得到这样一个蛋糕集合。

$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。

sb 题，没有想到怎么水的题我做了一个小时。考虑倒着做，计算出 $\sum{a_i}$ 放入一个队列，每次取出队头，如果 $a$ 中有这个数就把这个数删去，没有就把队头裂开放到队尾。

比赛时的实现很糟糕，还用了排序和大根堆。

CODE

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

inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}

#define N 200010

int n, a[N], sum;

signed main() {
    for (int T = read(); T --;) {
        n = read(), sum = 0;
        for (int i = 1; i <= n; i ++) {
            a[i] = read();
            sum += a[i];
        }
        sort(a + 1, a + n + 1);

        int id = n;
        priority_queue<int> q; q.push(sum);
        while (!q.empty() && id >= 1) {
            int x = q.top(); q.pop();
            if (x < a[id]) break;
            if (x == a[id]) id --;
            else q.push(x - x / 2), q.push(x / 2);
        }
        (id < 1) ? puts("YES") : puts("NO");
    }
    return 0;
}

CF1654D

给定一棵树，有边权有点权，点权都是正整数。一条边 $(u,v)$ 的边权 $(x,y)$ 表示 $a_u:a_v=x:y$。求出一组和最小的点权，满足这 $n - 1$ 条边权，输出这个和，答案对 $998244353$ 取模。

$2 \le n \le2 \times10^5$，$1 \le x,y \le n$。

比赛的时候方向是对的。。。就是没利用 $x,y$ 的范围，然后就GG了。

钦定 1 号点的点权为 1，我们就可以用 $\tt{dfs}$ 所有点权的分数表达形式，即 $a_1:a_i=x_i:y_i$ 中的 $x_i$ 和 $y_i$，这里 $x_i$ 和 $y_i$ 是互质的。因为 $a_i=\dfrac{a_1y_i}{x_i}$ 所以 $a_1$ 是 $x_i$ 的倍数，因此 $a_1$ 的最小值就是 $lcm(x_i)$，$2\le i\le n$。这样就可以求出每个点权了，整理一下就是 $a_1(\sum_{2\le i\le n}\dfrac{y_i}{x_i}\ \ +1)$。

这时候有个很严重的问题：$x_i$ 和 $y_i$ 可能很大，会爆炸。然后我们发现 $x,y$ 只有 2e5，因此我们可以把 $x_i$ 和 $y_i$ 用分解质因数的方式来表示。求最大公倍数的话只要对于所有质因数取指数的最大值即可。具体实现看代码吧。

不算预处理的话复杂度 $O(n\log n)$。

CODE

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

inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}

#define N 200010
#define P 998244353
#define PII pair<int, int>
#define PIII pair<int, pair<int, int> >
#define fi first
#define se second
#define mp make_pair

int n, X[N], Y[N], lcm[N], vis[N], res = 0;
vector<int> pr;
vector<PII > dv[N];
vector<PIII > e[N];

void Mem() {
    for (int i = 2; i < N; i ++) {
        if (!vis[i]) pr.push_back(i);
        for (int j = 0; j < pr.size() && i * pr[j] < N; j ++) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) continue;
        }
    }
    dv[1].emplace_back(1, 1);
    for (int i = 2, x = 2; i < N; x = ++ i) {
        for (int j = 0, s; pr[j] * pr[j] <= i; j ++) {
            for (s = 0; x % pr[j] == 0;) s ++, x /= pr[j];
            if (s != 0) dv[i].emplace_back(pr[j], s);
        }
        if (x != 1) dv[i].emplace_back(x, 1);
    }
}

int gcd(int x, int y) {
    return !y ? x : gcd(y, x % y);
}

int Pow(int x, int k, int r = 1) {
    for (; k; k >>= 1, x = x * x % P) {
        if (k & 1) r = r * x % P;
    }
    return r;
}

int F(int *a, int x, int op) {
    int g = 1;
    for (auto it : dv[x]) {
        if (op == 1) {
            a[it.fi] += it.se;
            if (X[it.fi] > lcm[it.fi]) {
                (lcm[0] *= Pow(it.fi, X[it.fi] - lcm[it.fi])) %= P;
                lcm[it.fi] = X[it.fi];
            }
        } else {
            int v = min(a[it.fi], it.se);
            a[it.fi] -= v;
            (g *= Pow(it.fi, it.se - v)) %= P;
        }
    }
    (a[0] *= (op == 1 ? x : Pow(x / g, P - 2))) %= P;
    return g;
}
void dfs(int u, int fa) {
    for (auto it : e[u]) if (it.fi != fa) {
        int v = it.fi, x = it.se.fi, y = it.se.se;
        y = F(X, y, -1), x = F(Y, x, -1);
        F(X, x, 1), F(Y, y, 1);
        (res += Y[0] * Pow(X[0], P - 2) % P) %= P, dfs(v, u);
        F(X, x, -1), F(Y, y, -1);
        F(X, it.se.se / y, 1), F(Y, it.se.fi / x, 1);
    }
}

signed main() {
    Mem();
    for (int T = read(); T --;) {
        n = read(), X[0] = Y[0] = lcm[0] = 1, res = 0;
        for (int i = 1; i < n; i ++) {
            int u = read(), v = read(), x = read(), y = read(), g = gcd(x, y);
            e[u].push_back(mp(v, mp(x / g, y / g)));
            e[v].push_back(mp(u, mp(y / g, x / g)));
        }
        dfs(1, 0), printf("%lld\n", (res + 1) % P * lcm[0] % P);
        for (int i = 1; i <= n; i ++) {
            e[i].clear(), X[i] = Y[i] = lcm[i] = 0;
        }
    }
    return 0;
}

CF1654E

给定长度 $n$ 的序列 $a$，求最少改变多少个数的值，使这 $n$ 个数形成等差数列。

$1\le n \le 10^5$，$1\le a_i\le 10^5$。

将问题放到二维坐标系上，每个点的坐标为 $(i,a_i)$ 。考虑等差数列的几何意义是一条直线，可以问题转化为求一条直线最多经过多少个点。

根号分治，设坐标的最大值为 $m$：

• 考虑当斜率的绝对值小于等于 $\sqrt m$ 时的情况，知道斜率我们就可以对于每个点求出截距，开个桶记录截距出现的次数，取最大值即可，复杂度 $O(n\sqrt m)$；

• 斜率的绝对值大于 $\sqrt m$ 时，显然直线最远端两点横向距离不超过 $\sqrt m$，否则一乘就超过最大值 $m$ 了。所以类似的，对于一个点，枚举它后面的 $\sqrt m$ 个点，将这两点的斜率加入桶，取最大值即可，同样 $O(n\sqrt m)$。

#include <bits/stdc++.h>
using namespace std;
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
#define N 100010
#define M 30000010
#define B 233
#define K 434
 
int n, a[N], res, vc[M << 1];
 
signed main() {
    n = read();
    for (int i = 1; i <= n; i ++) a[i] = read();
    for (int i = -B; i <= B; i ++) {
        for (int j = 1; j <= n; j ++) res = max(res, ++ vc[a[j] - j * i + M]);
        for (int j = 1; j <= n; j ++) vc[a[j] - j * i + M] = 0;
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = i + 1; j <= min(i + K ,n); j ++) {
            if ((a[j] - a[i]) % (j - i) == 0) {
                res = max(res, ++ vc[(a[j] - a[i]) / (j - i) + M] + 1);
            }
        }
        for (int j = i + 1; j <= min(i + K ,n); j ++) {
            vc[(a[j] - a[i]) / (j - i) + M] = 0;
        }
    }
    printf("%d\n", n - res);
    return 0;
}