Visits: 375

【LGR-069】洛谷 2 月月赛 II & EE Round 2 Div. 2

出言不逊

贪心，找到出现次数最多的字符一直加就行了，注意数据范围很大，最好开 __int128。

const int N = 1e6 + 7;
int n, ans, k;
char s[N];
__int128 l, m, x;

int main() {
    rds(s, n), rd(l), m = n;
    map<char, int> c;
    for (int i = 1; i <= n; i++) ++c[s[i]];
    for (auto o : c) k = max(k, o.se);
    x = k;
    while (m < l) m += x, x *= 2, ++ans;
    print(ans); 
    return 0;
}

谔运算

每一位是独立的，按位考虑即可，取模直接自然溢出。

const ui N = 5e5 + 7, M = 32;
ui n, a[N], ans;

int main() {
    rd(n);
    for (ui i = 1; i <= n; i++) rd(a[i]);
    for (ui i = 0; i < M; i++) {
        ui c = 0;
        for (ui j = 1; j <= n; j++) c += (a[j] >> i) & 1;
        ans += ((n * n - (n - c) * (n - c)) * (n * n - c * c) + (n - c) * (n - c) * c * c) * (1u << i);
    }
    print(ans);
    return 0;
}

直接自然溢出啥事没有

考虑递推，设 $f_i$ 表示长度为 $i$ 的「程序片段」，有 $f_0 = 1$。

注意到，「程序片段」只能是「程序片段」$+$「语句」，若设 $c_i$ 表示长度为 $i$ 的「语句」个数，则有 $f_{i} = \sum_{j=0}^{i-1} f_jc_{i-j}$，则可以 $\mathcal O(n^2)$ 递推。

考虑什么东西能当「语句」。

首先，; 为一个「语句」，因此有 $f_i \leftarrow f_{i-1}$。

除此之外，「语句」都必须由另外一个「程序片段」生成。

我们枚举这个「程序片段」的长度 $j$，设其为 A，则 A 的个数为 $f_j$。

它会生成 {A}「语句块」和 {A}「语句」，此时出现了「语句」，则有 $f_i \leftarrow f_{i-j-2} \times f_{j}$。

如果此时我们还想生成「语句」，那么只能走这样一条路：「语句」$\to$「函数」$\to$「值」$\to$「语句」 。

然后就无法再生成更多的「语句」了。

「语句」$\to$「函数」的过程实际上就是长度 $+2$ 或 $+4$。

「值」$\to$「语句」的过程实际上就是长度 $+1$。

我们只需要考虑「函数」$\to$「值」的过程，这也是最复杂的一个过程。

对于一个长度为 $l$ 的「函数」A，它会变成：

• 一个长度为 $l$ 的值 A；
• 两个长度为 $l+2$ 的值 (A),A()；
• 三个长度为 $l+4$ 的值 ((A)),(A()),(A)()；
• 四个长度为 $l+6$ 的值 (((A))),((A())),((A)()),((A))()；
• $\cdots$
• $n$ 个长度为 $l+(n-1)\times 2$ 的值。

考虑到「语句」$\to$「函数」的过程长度 $+2$ 或 $+4$，「值」$\to$「语句」的过程长度 $+1$。

将这些信息整合起来可以得到 $f_i \leftarrow f_j \sum_{k=1}^{i-j-4} [k \bmod 2 = 1]k \cdot f_{i-j-4}$。

于是我们可以写出下面这个 $\mathcal O(n^3)$ 的程序：

const int N = 1e4 + 7;
int n;
ul f[N];

int main() {
    rd(n), f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i-1];
        for (int j = 0; i - j - 2 >= 0; j++) {
            ul o = f[i-j-2];
            for (int k = 1; i - j - k - 4 >= 0; k += 2)
                o += f[i-j-k-4] * k;
            f[i] += o * f[j];
        }
    }
    print(f[n]);
    return 0;
}

然而，数据范围要求我们在 $\mathcal O(n^2)$ 的时间复杂度内解决。

考虑优化，注意到 $\sum_{k=1}^{i-j-4} [k \bmod 2 = 1]k \cdot f_{i-j-4}$ 这玩意儿可以前缀和优化 $\mathcal O(1)$ 得到，于是时间复杂度降为 $\mathcal O(n^2)$。

至于对 $2^{64}$ 取模，题目名已经告诉我们怎么做了。

const int N = 1e4 + 7;
int n;
ul f[N], g[N];

int main() {
    rd(n), f[0] = g[1] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i-1];
        for (int j = 0; i - j - 2 >= 0; j++)
            f[i] += f[i-j-2] * f[j];
        for (int j = 0; i - j - 4 >= 0; j++)
            f[i] += g[i-j-4] * f[j]; 
        for (int j = 1; i + 1 - j >= 0; j += 2)
            g[i+1] += f[i+1-j] * j;
    }
    print(f[n]);
    return 0;
}

相同的数字

最后那个相同的数只可能是 $m = \max_{i=1}^{n} a_i$ 或者 $\ge m$ 的最小质数，每次算两种的答案然后取 $\min$ 即可。

算答案的时候，将每个数加到目标值的过程按照质数划分成若干段，可以差分实现。对于长度为 $k$ 的一段，选择用 $c_1$ 还是 $c_2$ 取决于 $kc_1$ 和 $c_2$ 哪个大，显然这玩意儿是单调的，那么前缀和一下即可。

注意如果目标值是 $m$ 且 $m$ 不为质数，每个数加到 $m$ 的最后一段可能只能使用 $c_1$。

总时间复杂度 $\mathcal O(n + m + q)$。

const int N = 1e5 + 7, M = 1 << 17 | 1, P = 1e7 + 20;
int n, m, q, o, a[N], v[P], f[P], c1, c2;
vi p;
vector<ll> c[2], e[2];
ll g[2], ans;

inline void add(int o, int x, int k) {
    if (!x) return;
    if ((int)c[o].size() < x + 1) c[o].resize(x + 1);
    c[o][x] += k;
}

inline void prework(int o, int m) {
    vi d(p.size());
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        if (v[x] == v[m]) add(o, m - x, 1);
        else {
            add(o, v[x] - x, 1);
            if (m == v[m]) add(o, m - p[f[v[m]]-1], 1);
            else g[o] += m - p[f[v[m]]-1];
            ++d[f[v[x]]];
        }
    }
    for (ui i = 0; p[i+1] < v[m]; i++) {
        if (i) d[i] += d[i-1];
        add(o, p[i+1] - p[i], d[i]);
    }
    e[o].resize(c[o].size());
    for (ui i = 0; i < c[o].size(); i++) {
        e[o][i] = c[o][i] * i;
        if (i) e[o][i] += e[o][i-1], c[o][i] += c[o][i-1];
    }
}

inline ll solve(int o) {
    int k = min((int)1.0 * c2 / c1, (int)c[o].size() - 1);
    return (e[o][k] + g[o]) * c1 + (c[o].back() - c[o][k]) * c2;
}

int main() {
    for (int i = 2; i < P; i++) {
        if (!v[i]) p.pb(v[i] = i), f[i] = p.size() - 1;
        for (ui j = 0; j < p.size() && i * p[j] < P && p[j] <= v[i]; j++)
            v[i*p[j]] = p[j];
    }
    for (int i = P - 1; i; i--) if (v[i] != i) v[i] = v[i+1];
    rd(n), rd(q), rd(o);
    for (int i = 1; i <= n; i++) rd(a[i]), m = max(m, a[i]);
    prework(0, m), prework(1, v[m]);
    for (int i = 1; i <= q; i++) {
        rd(c1), rd(c2), c1 ^= o * ans, c2 ^= o * ans;
        print(ans = min(solve(0), solve(1)));
        ans &= M - 2;
    }
    return 0;
}