SMOI Round 1 题解

larsr · 2024-04-29 18:59:35 · 题解

A:Queue

（稍微打下表就可以得到答案的规律题）

结论：当 n\bmod 4=1 时答案为 n。

当 n\bmod 4=2 时答案为 n-2。

当 n\bmod 4=3 时答案为 3。

当 n\bmod 4=0 时答案为 0。

我们可以通过暴力求出答案序列为 1,0,3,0,5,4,3,0,\ldots,x,x-2,3,0，很容易找到规律，下面讲一下为什么会出现这种情况。

我们发现第 4r 个人的值都是 0，那有没有可能不为 0 呢？假设我们已经求得第 4r 个人的值为 0，则第 4r+1 个人的值也就为 4r+1，而第 4r+2 的第二位以后的值与 4r+1 一致，所以只会把前两位清零，所以值为 4r，第 4r+3 个人的第二位以后的值也是一致的，异或后第二位以后的值变成 0，而第 4r+2 个人的数前两位的值是 0，所以异或后值为 3，第 4r+4 个人前两位是 0,所以 4r 的值一定为 0，相应的 4r+1,4r+2,4r+3 的值也如上文所说。

例子：第 4 到第 8 个人数的变化：0_{(2)}\to101_{(2)}\to100_{(2)}\to11_{(2)}\to0_{(2)}。

B:Company

Part 1

对于 subtask 1。

因为只有两所公司，枚举最后的老板是哪所公司的，再枚举这个公司的哪个人成为另一所公司的上司。时间复杂度 O(n)。

Part 2

为方便叙述，下文中大公司是最后合并后的公司，公司是初始时的公司。

通过贪心，我们可以想到最优的大公司如果用公司之间的关系表示，是呈现链的形态的，并且链的两头分别是 myz 和 ljs 所在的公司。

Part 3

对于大公司的老板所在的公司，我们可以称之为组公司。

我们很容易想到，当链的形态固定时，组公司想让对答案的贡献最大，需要让他相连的两个公司，通过它的两个距离最远的叶节点连接。

不过当组公司是 myz 和 ljs 所在的树时就不一样了，它只需要连接一个公司，想要贡献最大，用距离 myz（或 ljs）最远的叶结点连接。

Part 4

处理完组公司之后，就剩不是组公司的了。

如果这个公司是 myz（或 ljs）所在的树，对答案的贡献是 myz（或 ljs）到根的距离。

否则对答案的贡献是树的深度。

Part 5

设 a_i 是第 i 所公司是组公司时对答案的最大贡献，b_i 是第 i 所公司不是是组公司时对答案的最大贡献。

答案为，

如果直接算，复杂度是 O(n^2)。但是我们可以转化为，

即，

时间复杂度 O(n)。

#include<cstdio>
#include<algorithm>
#include<vector>
#define N 1000010
using namespace std;
int n, x, y, m[N], tot = 0, root[N];
int a[N], b[N];
int dea[N], lea[N], ds[N];
int ok = 0;
vector<int>e[N];
int dfs_d(int now, int fa, int d)
{
    int maxn = d;
    dea[now] = ds[now] = d;
    for(int i = 0; i < e[now].size(); i++)
    if(e[now][i] != fa)
    {
        if(ok)
        lea[now] = 1;
        maxn = max(maxn, dfs_d(e[now][i], now, d + 1));
        dea[now] = max(dea[now], dea[e[now][i]]);
    }
    return maxn;
}
int dfs_zh(int now, int fa, int d)
{
    int maxn = 0, max1 = 0, max2 = 0;
    for(int i = 0; i < e[now].size(); i++)
    if(e[now][i] != fa)
    {
        int to = e[now][i];
        maxn = max(maxn, dfs_zh(to, now, d + 1));
        if(dea[to] - d >= max1)max2 = max1, max1 = dea[to] - d;
        else if(dea[to] - d > max2)max2 = dea[to] - d;
    }
    if(max1 && max2) maxn = max(maxn, max1 + max2);
    return maxn;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", m + i);
        root[i] = tot + 1;
        for(int j = 2; j <= m[i]; j++)
        {
            int f;
            scanf("%d", &f);
            e[f + tot].push_back(j + tot);
            e[j + tot].push_back(f + tot);
        }
        tot += m[i];
    }
    scanf("%d%d", &x, &y);
    ok = 1;
    dfs_d(root[1], 0, 0);
    ok = 0;
    a[1] = ds[x] - ds[1];
    dfs_d(x, 0, 0);
    for(int i = 1; i <= m[1]; i++)
        if(!lea[i])
            b[1] = max(b[1], ds[i]);
    y += m[1];
    ok = 1;
    dfs_d(root[2], 0, 0);
    ok = 0;
    a[2] = ds[y] - ds[root[2]];
    dfs_d(y, 0, 0);
    for(int i = m[1] + 1; i <= m[1] + m[2]; i++)
        if(!lea[i])
            b[2] = max(b[2], ds[i]);
    for(int i = 3; i <= n; i++)
    {
        a[i] = dfs_d(root[i], 0, 0);
        b[i] = dfs_zh(root[i], 0, 0);
    }
    int ans = 0, maxn = -1e9;
    for(int i = 1; i <= n; i++) ans += a[i], maxn = max(maxn, b[i] - a[i]);
    printf("%d\n", ans + maxn + n - 1);
    return 0;
}

C:Game

简要题意：

给一个 \{1,2,3,\ldots,b_1,1,2,3,\ldots,b_2,\ldots,1,2,3,\ldots,b_n\}的序列，问每一个子区间的最大值的和是多少。

Subtask3

我们沿用 \text{Subtask 2} 的思路，但是因为 b_i 最大可能到 10^{18}，所以不能再处理出这个序列了，我们考虑分段，将 {1,2,\ldots，b_i} 分为一段，然后我们一段一段地考虑。

先计算出在左右端点都在第 i 段内的区间的贡献，因为这是一个递增的序列，所以最大值就是右端点，我们枚举右端点，当 i 作为右端点时，显然前 i 个数都能成为左端点，所以贡献是 i^2 ，所以第 i 段的贡献是 {\sum_{j = 1}^{b_i}}{j^2} 可以用公式快速计算。

然后我们再考虑右端点在第 i 段，左端点在 1-(i-1) 段的区间的贡献，很显然，以 1-b_{i-1} 为右端点的数的区间的贡献都是 b_{i-1} 所以总贡献是 {b_{i-1}}^2 ，而以 b_{i-1}+1-b_i 为右端点的区间的贡献都是右端点的值，所以总贡献是 \sum_{j=b_{i-1}+1}^{b_i}j^2 同样可以通过公式快速计算。

时间复杂度：O(n)。

Subtask 4

我们继续沿用 \text{Subtask 3} 的思路，对于段内的贡献计算还是一样的。

我们考虑如何计算右端点在第 i 段，左端点在 1-(i-1) 段的区间的贡献，我们用 f_i 来表示以 b_i 为右端点的所有区间的总贡献。

我们受到 \text{Subtask 3} 的启发，发现 1-b_{i-1} 的数的贡献就是以 b_{i-1} 为右端点的区间的贡献，那么怎么算以 b_{i-1}-b_i 为右端点的贡献呢，我们找到最后一个比 b_{i-1} 大的数 t ，那么我们可以很容易的求出 b_{i-1}+1-b_t 的数的贡献，一直求下去就能求出最终答案，用单调队列维护就好了。

由于有点难理解放一下代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5, mod = 998244353, inv6 = 166374059, inv2 = 499122177;
stack<int> q;
int n, b[maxn], sum[maxn], f[maxn];
int ans = 0;
signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", b + i);
    }
    for (int i = 1; i <= n; i++) {
        int l = 0;
        ans += (b[i]) * (b[i] + 1) % mod * (2 * b[i] + 1) % mod * inv6 % mod;
        ans %= mod;
        while (!q.empty() && b[i] >= b[q.top()]) {
            int t = q.top();
            q.pop();
            ans += (b[t] - l) * f[t];
            ans %= mod;
            ans +=
                (sum[i - 1] - sum[t]) % mod * (b[t] - l) % mod * (b[t] + l + 1) % mod * inv2 % mod;
            ans %= mod;
            l = b[t];
        }
        sum[i] = sum[i - 1] + b[i];
        sum[i] %= mod;
        int t;
        if (!q.empty()) t = q.top();
        else t = 0;
        ans += (b[i] - l) * f[t];
        ans %= mod;
        ans += (sum[i - 1] - sum[t]) % mod * (b[i] - l) % mod * (b[i] + l + 1) % mod * inv2 % mod;
        ans %= mod;
        f[i] = f[t] + (sum[i] - sum[t]) * b[i] % mod;
        f[i] %= mod;
        q.push(i);
    }
    ans = (ans % mod + mod) % mod;
    cout << ans;
    return 0;
}

D:Apple

题目简述：

给你 2^n 个集合和每个集合的初始值 v_s，有 q 次操作。

• 操作一：求某个集合的子集和。

• 操作二：改变某个集合的值。

Subtask 1

直接暴力遍历子集求子集和。

时间复杂度 O(2^nq)。

Subtask 2

稍微优化一下就可以过了。

比如说当要改变的值的 1 的个数大于一个值时就遍历超集，给每个超集都更新一遍，到求答案时只要遍历当前集合中 1 的个数小于等于那个值的子集并累加进答案就可以了。

可能还有别的优化。

Subtask 3

特殊性质：只有操作 1。（说实话这个点就是子集 dp 的模板，感兴趣的可以去了解一下，以下为简略概括）。

所以我们只要预处理出每个集合的子集和就可以了。

设 S(s,i)=\{v_x|x\sube s,s\oplus x \le 2^i\}，表示只有第 i 位以及更低位与 s 不同的 x 的子集的值的和（包括集合 s）。

有

只要递推出 S(s,n) 就求出 s 的子集和了。

显然，时间复杂度为 O(2^nn)。

code

n = read();
q = read();
alls = (1 << n);
for(ll i = 0; i < alls; i++)
{
    ll v = read();
    p[i] = v;
}
for(ll j = 1; j < alls; j <<= 1)
    for(ll k = 0; k < alls; k++)
        if(k & j)
            p[k] = p[k] + p[k - j];
while(q--)
{
    ll opt, s;
    opt = read(), s = read();
    printf("%lld\n", p[s]);
}

Subtask 4

把询问分块，每个块内询问一次就遍历一次块内的修改操作，一个块结束后再子集 dp 一次。

把块长设为 \sqrt{2^nn} 的时间复杂度为 O(q\sqrt{2^nn})。

Subtask 5

我们发现可以暴力更新出所有的 S(s,\lfloor\frac{n}{2}\rfloor)，设要询问 s 的子集和，则答案为所有的只有第 \lfloor\frac{n}{2}\rfloor+1 位以及更高位与 s 不同的 s 的子集的 S(x,\lfloor\frac{n}{2}\rfloor) 之和。

时间复杂度为 O(q2^{\lceil\frac{n}{2}\rceil}+2^{n+\lfloor\frac{n}{2}\rfloor})。

发现还是有点大，可以用上文的子集 dp 优化（当然不用也可以卡过），同样的，只处理到 S(x,\lfloor\frac{n}{2}\rfloor) 就可以了。

时间复杂度为 O(q2^{\lceil\frac{n}{2}\rceil}+2^n\lfloor\frac{n}{2}\rfloor)。

code（这里的 \lfloor\frac{n}{2}\rfloor 固定为 10）:

#include<cstdio>
#include<ctime>
#define ll long long
#define N 2100010
using namespace std;
ll n, q, alls;
const ll A = (1 << 10) - 1, B = A << 10;
ll p[N], val[N];
ll read()
{
    ll x = 0;
    char c = getchar();
    while(c < '0' || c > '9')c = getchar();
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return x;
}
int main()
{
    n = read();
    q = read();
    alls = (1 << n);
    for(ll i = 0; i < alls; i++)
    {
        ll v = read();
        p[i] = v;
        val[i] = v;
    }
    for(ll j = 1; j < A; j <<= 1)
        for(ll k = 0; k < alls; k++)
            if(k & j)
                p[k] = p[k] + p[k - j];
    while(q--)
    {
        ll opt;
        ll s, a;
        opt = read();
        if(opt == 1)
        {
            s = read();
            ll enb = s & B, ans = 0, ena = s & A;
            for(ll i = enb; i; i = (i - 1) & enb)
                ans += p[i | ena];
            ans += p[s & A];
            printf("%lld\n", ans);
        }
        else
        {
            s = read();a = read();
            ll m = a - val[s];
            ll ena = (s & A) ^ A;
            for(ll i = ena; i; i = (i - 1) & ena)
                p[i | s] += m;
            p[s] += m;
            val[s] = a;
        }
    }
    return 0;
}