专栏文章

MX Day 21

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

文章操作

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

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

T1：

1762776488008.png

做题思路：

首先，我们可以发现，反正我们要考虑的就是那些B比A多k个的序列，那么这种情况我们可以转化为以一个点为固定端点向前或者向后最小值是多少。
我们可以在遍历时就求出这几个值，具体来说，我们每到一个数就要去判断三个数值的最小值，一个是之前的值加上当前的字符（是A还是B），一个是直接以当前的字符为开头，最后一种是什么都不要，直接赋值为0，重新开始。
这样的话，我们就可以快速找出以一个端点固定的情况向前或向后的最小值了，接下来，我们考虑怎么枚举答案最小。
如果我们从前往后，那么当我们遇到不符合要求的序列时，我们考虑是删除前面的还是删除后面的，由于后面的序列与当前无关，那么我们肯定删除前面的好（不过作者没想到怎么精准定位前面在哪，所以用的是从后往前，而且估计还要一个for循环遍历才能得到精准位置）。
至于从后往前遍历，那么也差不多，当我们遇到不符合要求的位子时，就反过来，将当前的贡献加上，毕竟后面的贡献肯定更不优秀。

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;
}
char c[3000009];
int n, m, gx[3000009];
int a[3000009];
const int mod = 1e9 + 7;
signed main()
{
    // freopen("webmaster.in", "r", stdin);
    // freopen("webmaster.out", "w", stdout);
    n = read();
    int k = read();
    gx[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> c[i];
        if (c[i] == 'A')
        {
            a[i] = 1;
        }
        else
        {
            a[i] = -1;
        }
        gx[i] = gx[i - 1] * 2 % mod;
    }
    int ans = 0;
    int now = 0;
    for (int i = n;i >= 1; i--)
    {
        now = min({now + a[i], a[i], 0ll});
        if (now < (-k))
        {
            cout << "i=" << i << endl;
            now += 2;
            ans += gx[i];
            ans %= mod;
        }
    }
    cout << ans;
    return 0;
}

T2：

1762777678708.png

做题思路：

我说这道题比第一题简单好多好吧……
首先，我们发现，我们的式子中出现了商和余数，那很好了，一定是整除分块没跑了。
首先，我们的i肯定是要for求出来的，当然你用什么其它的逆天数据结构焯出来我也不管。
现在我们先来考虑第一个下标，也就是由商控制的那一个，我们的j在不断增大，而根据整除分块的性质，当j在[i/(goal + 1) + 1, i / goal]这个区间内是定值goal，这一维也就快速解决了。
接下来来看余数这一块，因为我们的余数是等于被除数减去商乘上除数，商不变，除数依次加一，那么我们的商在被除数不变的情况下肯定是一串等差数列，而且开头肯定是这一串等差数列最小的那个非负整数，既然连续，那么我们就可以预处理出来。
什么，你问我为什么不会炸空间，因为我们的余数肯定不会大于除数，而且我们是等差数列，调和级数决定了我们的空间是绝对不会炸的。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
const int mod = 1e9 + 7;
vector<int> qzh[1000009];
int n;
int a[1000009];
int b[1000009];
signed main()
{
    freopen("failure.in", "r", stdin);
    freopen("failure.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    for (int i = 0; i < n; i++)
    {
        b[i] = read();
    }
    for (int i = 1; i <= n; i++)
    {
        qzh[i].resize(n / i + 1);
        for (int j = 0; j <= n / i; j++)
        {
            qzh[i][j] = b[j];
            if (j - i >= 0)
            {
                qzh[i][j] += qzh[i][j - i];
                qzh[i][j] %= mod;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int ans = 0;
        for (int l = 1, r = 0; l <= i && r <= i; l = r + 1)
        {
            r = i / (i / l);
            int chushu = i / l;
            int yushu = i - l * chushu;
            ans += qzh[chushu][yushu] * a[chushu];
            ans %= mod;
        }
        cout << ans << endl;
    }
    return 0;
}

T3：

1762778531413.png

做题思路：

首先，我们当然可以直接输出0，12分，我只能说，这个很刺激，但不违反组规。
好了，不玩梗了，考虑正解。
首先，我们可以发现，我们的第三种情况，也就是自由人集合，是可以随便分配的，而且，我们的状态一定是由上一个时刻的状态继承而来，所以我们可以用滚动数组优化掉一维。好，接下来，我们考虑组长和组员的情况。
首先，我们将所有人按照资历w排序，以便我们之后分组。接下来，我们先考虑组员的情况（当然你排序顺序不同直接考虑组长也一样），我们每次定义一个临时的数组g保存我们这个时刻的状态，然后，我们每次都给[新增待匹配数,已匹配数不变]的状态更新只当组员的情况，以及给减少待匹配数，增加匹配数的情况更新当组长的情况。
什么，你问我为什么不会发生组员骑在组长头上，那很简单，因为我们排序时已经确保每一个人的资历肯定是要比后一个人浅的（年轻人不要太气盛）。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    if (2 * m > n)
    {
        return cout << -1 << endl, 0;
    }
    struct A
    {
        int w, s, p;
        A()
        {
            cin >> w >> s >> p;
            if (!--p)
            {
                p = 3;
            }
        }
    };
    vector<A> a(n);
    sort(a.begin(), a.end(), [&](A x, A y)
         { return x.w < y.w || x.w == y.w && x.p < y.p; });
    using ll = long long;
    const ll inf = 1e18;
    vector<vector<ll>> f(m + 1, vector<ll>(m + 1, inf));
    f[0][0] = 0;
    for (int i = 0; i < n; i++)
    {
        vector<vector<ll>> g = f;
        if (a[i].p != 3)
        {
            for (int j = 0; j <= m; j++)
            {
                for (int k = 0; k < m; k++)
                {
                    g[j][k + 1] = min(g[j][k + 1], f[j][k] + a[i].s);
                }
            }
        }
        if (a[i].p != 1)
        {
            for (int j = 0; j < m; j++)
            {
                for (int k = 1; k <= m; k++)
                {
                    g[j + 1][k - 1] = min(g[j + 1][k - 1], f[j][k] + a[i].s);
                }
            }
        }
        f = g;
    }
    if (f[m][0] == inf)
    {
        return cout << -1 << endl, 0;
    }
    else
    {
        return cout << f[m][0] << endl, 0;
    }
    return 0;
}

评论

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

正在加载评论...