专栏文章

MX Day 16

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

文章操作

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

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

T1:

1762583242096.png

考试思路：

由于是场切，所以就简单说说，我们只用知道这玩意从前往后和从后往前枚举都能得到一份答案，但是可能不会满足字典序要求，所以我们首先将枚举顺序确定为从后往前，然后有发现只要删掉一个数它后面所有没删成功（也就是奇偶不一样的那几对）的数都会被删掉，这时我们删掉的顺序也和我们遍历时的一样，从后往前，当然你一边枚举一边记录失败的数更方便。

Code:

CPP
#include <bits/stdc++.h>
using namespace std;
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;
}
int n, a[1000009];
int sy[1000009], l = 0;
vector<int> ans;
int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    // if (a[1] % 2 == 0)
    // {
    //     cout << n - 1 << endl;
    // }
    // else
    // {
    //     cout << n << endl;
    // }
    for (int i = n; i >= 1; i--)
    {
        if (a[i] % 2 == i % 2)
        {
            ans.push_back(a[i]);
            for (int i = 1; i <= l; i++)
            {
                ans.push_back(sy[i]);
            }
            l = 0;
        }
        else
        {
            sy[++l]=(a[i]);
        }
    }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << " ";
    }
    return 0;
}

T2:

1762585578216.png

思路：

首先，啊~~我们要知道一个结论，就是我们从中挑一个最小面额的当除数，然后枚举它所有可能的余数，然后找每一个余数对应的最小可以被凑出的面额，将这个面额减去除数（也就是最小值），得到的就是最大无法凑出的面额，这个玩意叫Frobenius扩展定理，原定理是只有两种面额，这里的话证明如下：
之后的话，我们就可以以每一个余数为一个点，跑同余最短路，得到的就是每个余数对应的最小被除数，将这个玩意减去除数，得到的就是答案。

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 (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 work(vector<int> &now)
{
    int n = now.size();
    int gcd_all = now[0];
    for (int i = 1; i < n; i++)
    {
        gcd_all = __gcd(gcd_all, now[i]);
    }
    if (gcd_all > 1)
    {
        return -1;
    }
    int m = *min_element(now.begin(), now.end());
    vector<int> a(m, LLONG_MAX);
    a[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});
    while (!pq.empty())
    {
        auto [val, r] = pq.top();
        pq.pop();
        if (val > a[r])
        {
            continue;
        }
        for (int d : now)
        {
            int nwv = val + d;
            int s = nwv % m;
            if (nwv < a[s])
            {
                a[s] = nwv;
                pq.push({nwv, s});
            }
        }
    }
    int res = 0;
    for (int r = 0; r < m; r++)
    {
        res = max(res, a[r] - m);
    }
    return res < 0 ? 0 : res;
}
vector<int> a;
signed main()
{
    freopen("reform.in", "r", stdin);
    freopen("reform.out", "w", stdout);
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        int x = read();
        a.push_back(x);
        int ans = work(a);
        if (ans == 0)
        {
            cout << -1 << endl;
        }
        else if (ans == -1)
        {
            cout << "INF" << endl;
        }
        else
        {
            cout << ans << endl;
        }
    }
    return 0;
}

T3:

1762590527063.png

大致思路：

因为题目较难，现将自己的思路说一下。
首先，我们发现一个性质，就是我们在枚举的时候每次取得字符肯定是从字典序小的往字典序大的取，这样的话，最关键的就是此时取出的字符种类最后一个位子是什么，如果确定的话，我们就可以在这个位子之后再去枚举我们要选的字符；
当然，如果最后一个字符之后的字符总数加上已经选上了的还是比K小，那么很好搞，就在之前各个区间递归之前的操作。

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 (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
const int jz = 13131;
const int mod = 998244353;
char s[1000009];
int n, hx[1000009];
inline int add(int x, int y)
{
    return x + y >= mod ? x + y - mod : x + y;
}
inline int mul(int x, int y)
{
    return x * y % mod;
}
inline int sub(int x, int y)
{
    return x - y < 0 ? x - y + mod : x - y;
}
int cf[1000009];
void init()
{
    cf[0] = 1;
    for (int i = 1; i <= n + n; i++)
    {
        cf[i] = mul(cf[i - 1], jz);
    }
    for (int i = 1; i <= n; i++)
    {
        hx[i] = add(mul(hx[i - 1], jz), (s[i]));
    }
}
int query(int l, int r)
{
    return sub(hx[r], mul(hx[l - 1], cf[r - l + 1]));
}
int lcp(int l1, int l2)
{
    if (s[l1] != s[l2])
    {
        return 0;
    }
    int l = 1, r = n - max(l1, l2) + 1;
    int ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (query(l1, l1 + mid - 1) == query(l2, l2 + mid - 1))
        {
            ans = mid, l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return ans;
}
struct node
{
    int len[27];
    int l, r;
    node()
    {
        memset(len, 0, sizeof(len));
        l = r = 0;
    }
};
vector<int> ch[1009];
node getans(int l, int r, int k)
{
    node res;
    res.r = r, res.l = r + 1;
    for (int i = 0; i < 26; i++)
    {
        if (k == 0)
        {
            return res;
        }
        int p = lower_bound(ch[i].begin(), ch[i].end(), l) - ch[i].begin();
        int q = upper_bound(ch[i].begin(), ch[i].end(), r) - ch[i].begin() - 1;
        res.len[i] = min(q - p + 1, k);
        k -= res.len[i];
        int L = p, R = p + res.len[i] - 1, ans = -1;
        while (L <= R)
        {
            int mid = (L + R) / 2;
            if (k > r - ch[i][mid] - (q - mid))
            {
                ans = mid, R = mid - 1;
            }
            else
            {
                L = mid + 1;
            }
        }
        if (ans != -1)
        {
            k -= r - ch[i][ans] - (q - ans);
            res.l = ch[i][ans];
            r = ch[i][ans] - 1;
            // r = ch[i][ans] - 1;
            res.len[i] -= (q - ans + 1);
            if (ans - 1 >= p)
            {
                l = ch[i][ans - 1] + 1;
            }
        }
        else if (res.len[i] >= 1)
        {
            l = ch[i][q] + 1;
        }
    }
    return res;
}
signed main()
{
    freopen("airport.in", "r", stdin);
    freopen("airport.out", "w", stdout);
    scanf("%s", s + 1);
    n = strlen(s + 1);
    init();
    for (int i = 1; i <= n; i++)
    {
        ch[s[i] - 'A'].push_back(i);
    }
    int T;
    cin >> T;
    while (T--)
    {
        int l1 = read(), r1 = read(), k1 = read(), l2 = read(), r2 = read(), k2 = read();
        node ans1 = getans(l1, r1, k1);
        node ans2 = getans(l2, r2, k2);
        char ans = '?';
        for (int i = 0; i < 26; i++)
        {
            if (ans1.len[i] != ans2.len[i])
            {
                int g = min(ans1.len[i], ans2.len[i]);
                ans1.len[i] -= g, ans2.len[i] -= g;
                char n1 = 0, n2 = 0;
                for (int j = i; j < 26; j++)
                {
                    if (!n1 && ans1.len[j] > 0)
                        n1 = j + 'A';
                    if (!n2 && ans2.len[j] > 0)
                        n2 = j + 'A';
                }
                if (!n1 && ans1.r >= ans1.l)
                    n1 = s[ans1.l];
                if (!n2 && ans2.r >= ans2.l)
                    n2 = s[ans2.l];
                // printf("hit %c, get %c %c\n",i+'A',n1,n2);
                assert(n1 != n2);
                ans = "<>"[n1 > n2];
                break;
            }
            // if (ans1.len[i] < ans2.len[i])
            // {
            //     ans = '<';
            //     break;
            // }
            // if (ans1.len[i] > ans2.len[i])
            // {
            //     ans = '>';
            //     break;
            // }
        }
        if (ans == '?')
        {
            int L = lcp(ans1.l, ans2.l);
            if (L >= max(ans1.r - ans1.l + 1, ans2.r - ans2.l + 1))
            {
                if (k1 == k2)
                {
                    ans = '=';
                }
                else
                {
                    ans = "<>"[k1 > k2];
                }
            }
            else
            {
                char n1 = (ans1.l + L) <= ans1.r ? s[ans1.l + L] : 0;
                char n2 = (ans2.l + L) <= ans2.r ? s[ans2.l + L] : 0;
                ans = "<>"[n1 > n2];
            }
            cout << ans << endl;
        }
        else
        {
            cout << ans << endl;
        }
    }
    return 0;
}

评论

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

正在加载评论...