专栏文章

MX Day 20

OOIer_ACMer
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minalzxu
此快照首次捕获于
2025/12/01 23:17
3 个月前
此快照最后确认于
2025/12/01 23:17
3 个月前
查看原文

T1：

1762771019065.png

做题思路：

由于是场切，所以就不详细说。大致思路就是我们要求最大值和最小值这几个数之间的数要包括所有的种类，那么我们可以双指针来移动，唯有找到所有种类都包含的块才能计算答案。
总结一句话：当我们要求最大与最小，包括所有种类，那么很好办，映射数轴+双指针。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int cnt;
int vis[3000009];
struct node
{
    int val, id;
} a[3000009];
int l = 0;
bool cmp(node a, node b)
{
    return a.val > b.val;
}
signed main()
{
    freopen("cake.in", "r", stdin);
    freopen("cake.out", "w", stdout);
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        int T = read();
        while (T--)
        {
            int x = read();
            a[++l] = {x, i};
        }
    }
    sort(a + 1, a + l + 1, cmp);
    int r = 1, ans = INT_MAX;
    // for (int i = 1; i <= l; i++)
    // {
    //     cout << a[i].val << ' ' << a[i].id << endl;
    // }
    // cout << endl;
    // for (int i = 1; i <= l; i++)
    // {
    //     cout << a[i].val << ' ' << a[i].id << endl;
    // }
    // cout << endl;
    vis[a[1].id] = 1;
    cnt = 1;
    for (int i = 1; i <= l; i++)
    {
        // cout << "sta i=" << i << " cnt=" << cnt << endl;
        if (cnt < n && r < l)
        {
            while (1)
            {
                r++;
                // cout << "in r=" << r << " id=" << a[r].id << " vis=" << vis[a[r].id] << endl;
                if (vis[a[r].id] == 0)
                {
                    cnt++;
                }
                vis[a[r].id]++;
                if (r == l)
                {
                    break;
                }
                if (cnt == n)
                {
                    break;
                }
                // r++;
            }
        }
        // cout << "??? i=" << i << ' ' << "r=" << r << " cnt=" << cnt << endl;
        // for (int j = i; j <= r; j++)
        // {
        //     cout << a[j].val << ' ' << a[j].id << endl;
        // }
        if (cnt == n && i != r)
        {
            ans = min(ans, a[i].val - a[r].val);
        }
        vis[a[i].id]--;
        // cout << "shan noww a[" << i << "].id=" << a[i].id << endl;
        // cout << "vis=" << vis[a[i].id] << endl;
        if (vis[a[i].id] == 0)
        {
            cnt--;
        }
        // cout << endl;
    }
    cout << ans << endl;
    return 0;
}

T2：

1762771644136.png

做题思路：

这道题非常水。
因为我们发现最多只有log2(2e6)种不同的矿，也就是只有21种，那么我们可以从搜索上考虑。
首先，我们的矿之间存在倍数关系，那么就给了我们合并他们的机会。我们现将我们每一种体积的矿按照价值大小从大到小排个序，同时我们的最终的答案是由不同体积的矿组成的，那么我们从大往小考虑，将体积先搜索下去，然后进行每阶段阶段的合并，将装不下的合并成新的矿给上一层体积更大的再去合并。
什么，你问我这是否会出现只考虑到了几个矿多的情况，却没考虑到别的价值更大但体积更小或大的情况，OK，请看JPG：
1762772396056.png
总之，未来的小胖只用知道，每次dfs的区域都是上一次剩的，对前面不会有丝毫影响，因为剩下的体积连一块当前层的矿都塞不下。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m;
struct node
{
    int val, wei;
} a[1000009];
vector<int> g;
vector<int> wp[1000009], p;
int len;
int dfs(int now, int shengyu)
{
    if (now == -1)
    {
        return 0;
    }
    int shang = shengyu / g[now];
    int yushu = shengyu % g[now];
    cout << "now=" << now  << " shengyu=" << shengyu << " shang=" << shang << " yushu=" << yushu << endl;
    int res = dfs(now - 1, yushu);
    sort(wp[now].begin(), wp[now].end(), greater<int>());
    p.clear();
    for (int i = 0; i < wp[now].size(); i++)
    {
        if (i < shang)
        {
            res += wp[now][i];
        }
        else
        {
            p.push_back(wp[now][i]);
        }
    }
    if (now != len - 1)
    {
        int bl = g[now + 1] / g[now];
        int sum = 0;
        for (int i = 0; i < p.size(); i++)
        {
            sum += p[i];
            if ((i + 1) % bl == 0 || i == p.size() - 1)
            {
                wp[now + 1].push_back(sum);
                sum = 0;
            }
        }
    }
    return res;
}
signed main()
{
    // freopen("mining.in", "r", stdin);
    // freopen("mining.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
    {
        a[i].val = read();
        a[i].wei = read();
        g.push_back(a[i].wei);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()), g.end());
    len = g.size();
    for (int i = 1; i <= n; i++)
    {
        int x = lower_bound(g.begin(), g.end(), a[i].wei) - g.begin();
        wp[x].push_back(a[i].val); 
    }
    cout << dfs(len - 1, m);
    return 0;
}
/*
6 7
1 2
1 2
1 2
4 2
100000 1
100000 1

6 5
5 1
5 1
4 1
4 1
3 1
100 2
*/

T3：

1762772501322.png

做题思路：

首先啊，你直接n^2莽，当然是过不了的，不过50分确实刺激。
接下来说正解。
当k=0时，就是根号分治：
对于小于 n\sqrt{n} 的数按上述方式dp加入。
对于大于等于 n\sqrt{n} 的数，其出现次数必然小于根号，于是将转移改为：加入一个数 n\sqrt{n}，将所有数+1。 最终即可以 O(nn)O(n\sqrt{n}) 的时间复杂度求得分拆数。
当 k≤10k\le 10：考虑容斥原理，每次选择一个不能选的数的集合钦定其选至少一个，答案为： ∑S⊂U(−1)∣S∣Fn−∑x∈Sx\sum_{S\subset U} (-1)^{\lvert S\rvert} F_{n-\sum_{x\in S}x} 其中 UU 是所有不能选的数的集合，FiF_i 为 ii 的分拆数。时间复杂度为 O(nn+n2k)O(n\sqrt{n}+n2^k)。
上述式子的求值还可以优化：将容斥过程改为dp，每次加入一个数时乘上 −1-1 的系数即可。具体的，记 hih_i 表示当前式子中 Fn−iF_{n-i} 的系数，加入一个 UU 中的数 xx 的转移为 hi←hi+(−1)×hi−xh_{i}\leftarrow h_i+ (-1)\times h_{i-x}。

Code：

CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200005;
const ll mod = 1e9 + 7;
inline int rd()
{
    int x = 0;
    bool f = 1;
    char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-')
            f = 0;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + (ch ^ 48);
    return f ? x : -x;
}
inline void inc(ll &x, ll y)
{
    (x += y) %= mod;
}
int a[111];
ll f[N], g[N], h[N];
int n, k;
ll res[N];
int main()
{
    freopen("change.in", "r", stdin);
    freopen("change.out", "w", stdout);
    n = rd(), k = rd();
    for (int i = 1; i <= k; i++)
    {
        a[i] = rd();
    }
    int sq = sqrt(n);
    f[0] = h[0] = 1;
    for (int i = 1; i * sq <= n; i++)
    {
        for (int j = sq; j <= n; j++)
        {
            inc(g[j], f[j - sq]);
        }
        for (int j = i; j <= n; j++)
        {
            inc(g[j], g[j - i]);
        }
        swap(f, g);
        memset(g, 0, sizeof(g));
        for (int i = 1; i <= n; i++)
        {
            inc(h[i], f[i]);
        }
    }
    for (int i = 1; i < sq; i++)
    {
        for (int j = i; j <= n; j++)
        {
            inc(h[j], h[j - i]);
        }
    }
    res[0] = 1;
    for (int i = 1; i <= k; i++)
    {
        for (int j = n; j >= a[i]; j--)
        {
            inc(res[j], mod - res[j - a[i]]);
        }
    }
    ll ans = mod - 1;
    for (int j = 0; j <= n; j++)
    {
        inc(ans, res[j] * h[n - j]);
    }
    cout << ans << endl;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...