个人题解| ACGO排位赛#14

xueman

2024-11-11 13:54:27

发布于：山东

95阅读

0回复

0点赞

A. 混淆字符串

按照题意模拟即可，将两个字符串中的混淆字符都改成相同字符，最后判断两个字符串是否相等。

时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    for (auto &c : s)
    {
        if (c == '1')
            c = 'l';
        else if (c == '0')
            c = 'O';
        else if (c == '5')
            c = 'S';
    }
    for (auto &c : t)
    {
        if (c == '1')
            c = 'l';
        else if (c == '0')
            c = 'O';
        else if (c == '5')
            c = 'S';
    }
    if (s == t)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B. 循环小数

按照题意模拟，找到循环节，输出循环节即可。

当余数 $x$ 为 0 的时候的时候证明能够除尽，输出0即可，否则当等到 $x$ 上一次出现过的时候输出证明找到了循环节，输出循环节即可。

细节见代码，时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x, y;
    cin >> x >> y;
    x %= y;
    map<int, int> mp;
    int cnt = 0;
    mp[x] = cnt++;
    vector<int> v;
    while (1)
    {
        if (x == 0)
        {
            cout << 0 << endl;
            return 0;
        }
        x *= 10;
        v.push_back(x / y);
        x %= y;
        if (x && mp.count(x))
        {
            for (int i = mp[x]; i < v.size(); i++)
                cout << v[i];
            cout << endl;
            return 0;
        }
    }
    return 0;
}

C. 特殊的染料

注意到 $n$ 很小，因此考虑直接暴力。

贪心的考虑，因为最后要把所有桶按顺序排好，所以一个桶一定会通过交换换到他应该在的地方，如果先把最大的桶放好，那么这个桶在之后一定不会与其他的桶发生交换，这样显然更优。

因此我们能够得到一个策略，从大到小把对应的桶给直接放好即可。而每次选择交换的容器的时候，可以 $O(n)$ 暴力求出花费最小的交换容器。

整体时间复杂度 $O(n^3)$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;

int a[maxn], b[maxn];
int vis[maxn];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], vis[a[i]] = i;
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    int ans = 0;
    for (int i = n; i >= 1; i--)
    {
        if (vis[i] == i)
            continue;
        int pos = vis[i];
        while (pos != i)
        {
            int mi = inf;
            for (int j = 1; j <= n; j++)
            {
                if (j != a[pos] && j != a[pos + 1] && (j + a[pos] <= n || j + a[pos + 1] <= n))
                    mi = min(mi, b[j]);
            }
            swap(vis[a[pos]], vis[a[pos + 1]]);
            swap(a[pos], a[pos + 1]);
            pos++;
            ans += mi;
        }
    }
    cout << ans << endl;
    return 0;
}

D. 君往何处

搜索。

注意剪枝优化，不然会 TLE。

细节见代码，注意每次应该让最前面的手指匹配音符，这个过程可以拿一个堆来维护。

实测跑的挺快，最慢的点也只跑了 $50ms$ ，时间复杂度为目测估计为 $O(n)$ ，常数略大。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;

int a[maxn];
int n, ans;

void dfs(int i, priority_queue<int, vector<int>, greater<int>> q, int sz)
{

    if (sz > 4)
        return;
    if (sz >= ans)
        return;
    if (i > n)
    {
        ans = min(ans, sz);
        return;
    }
    int x = q.top();
    if (a[i] + 30 - x >= 100)
    {
        auto t = q;
        t.pop();
        if (100 + x <= a[i] - 30)
        {
            t.push(max(100 + x, a[i] - 30));
            dfs(i + 1, t, sz);
        }
        else
        {
            t.push(max(100 + x, a[i] - 30));
            dfs(i + 1, t, sz);
            auto s = q;
            s.push(max(0, a[i] - 30));
            dfs(i + 1, s, sz + 1);
        }
    }
    else
    {
        auto s = q;
        s.push(max(0, a[i] - 30));
        dfs(i + 1, s, sz + 1);
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        ans = inf;
        priority_queue<int, vector<int>, greater<int>> q;
        q.push(-100);
        dfs(1, q, 1);
        if (ans == inf)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

E. 万圣糖果

毒瘤 dp 题，写了好久，估计想复杂了。

注意到只有两种形式的修改

第一种就是找两个不相交的区间，然后每个区间施法一次
第二种就是两个区间相交，重叠部分的点会施法两次，其余点施法一次，这种情况可以转换为一个大区间施法一次，在这个大区间的一个小区间里面会施法两次

以这两种状态设计转移方程做 dp 即可

细节特别多，具体细节见代码，时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;

ll a[maxn], b[maxn], c[maxn];
ll dp[maxn][5];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    ll ans = 0;
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) // 第二种操作的dp转移方程
    {
        dp[i][0] = max({dp[i - 1][0] + a[i], 0ll});
        dp[i][1] = max({dp[i][0] - a[i] + b[i], dp[i - 1][1] + b[i], dp[i - 1][0] + b[i], 0ll});
        dp[i][2] = max({dp[i][1] - b[i] + c[i], dp[i - 1][2] + c[i], dp[i - 1][1] + c[i], dp[i - 1][0] + c[i], 0ll});
        dp[i][3] = max({dp[i - 1][3] + b[i], dp[i - 1][2] + b[i], dp[i - 1][1] + b[i], dp[i - 1][0] + b[i], 0ll});
        dp[i][4] = max({dp[i - 1][4] + a[i], dp[i - 1][3] + a[i], dp[i - 1][2] + a[i], dp[i - 1][1] + a[i], dp[i - 1][0] + a[i], 0ll});
        ans = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4], ans});
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) // 第一种操作的dp转移方程
    {
        dp[i][0] = max({dp[i - 1][0] + a[i], 0ll});
        dp[i][1] = max({dp[i][0] - a[i] + b[i], dp[i - 1][1] + b[i], 0ll});
        dp[i][2] = max({dp[i - 1][2] + a[i], dp[i - 1][1] + a[i], dp[i - 1][0] + a[i], 0ll});
        dp[i][3] = max({dp[i][2] - a[i] + b[i], dp[i - 1][3] + b[i], dp[i - 1][2] + b[i], dp[i - 1][1] + b[i], 0ll});
        dp[i][4] = max({dp[i - 1][4] + a[i], dp[i - 1][3] + a[i], dp[i - 1][2] + a[i], dp[i - 1][1] + a[i], dp[i - 1][0] + a[i], 0ll});
        ans = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4], ans});
    }
    cout << ans << endl;
    return 0;
}

F. 可变数组

考察线段树。

如果你不知道线段树是什么，可以点这里：线段树 - OI Wik。

第一种操作和第二种操作都是线段树的单点修改，第三种操作是线段树的区间查询，第四种操作是线段树区间二分查询。

注意操作四不可以二分右边界再使用线段树查询，来找到第一个大于等于 $x$ 的元素，这样的时间复杂度会是 $n\log(n)\log(n)$ 的，在本题会TLE，只有 90 pts 。

操作四可以优化成 $n\log(n)$ 的原因是线段树的查询实际上二分区间内的过程，如果左区间内的元素查询满足了要求则不用再去遍历右区间，直接返回即可。

代码实现使用了快读，因为之前拿 $n\log(n)\log(n)$ 的做法做的，想着能不能卡常过，事实上是不行。

时间复杂度 $O(n\log(n))$

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;

namespace QuickRead
{ // 快读
    char buf[1 << 21], *p1 = buf, *p2 = buf;
    inline int getc()
    {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T>
    void Cin(T &a)
    {
        T ans = 0;
        bool f = 0;
        char c = getc();
        for (; c < '0' || c > '9'; c = getc())
        {
            if (c == '-')
                f = 1;
        }
        for (; c >= '0' && c <= '9'; c = getc())
        {
            ans = ans * 10 + c - '0';
        }
        a = f ? -ans : ans;
    }
    template <typename T, typename... Args>
    void Cin(T &a, Args &...args)
    {
        Cin(a), Cin(args...);
    }
    template <typename T>
    void write(T x)
    { 
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace QuickRead

using namespace QuickRead;

struct SegmentTree
{

    struct tree
    {
        int l, r;
        int mx, add;
    } tr[4 * maxn];
    int a[maxn];
    int n;

#define lc (p << 1)
#define rc (p << 1 | 1)

    void calc(int p, int k)
    {
        tr[p].mx = k;
    }

    void pushup(int p)
    {
        tr[p].mx = max(tr[lc].mx, tr[rc].mx);
    }

    void pushdown(int p)
    {
        // return;
        if (tr[p].add)
        {
            calc(lc, tr[p].add);
            calc(rc, tr[p].add);
            tr[p].add = 0;
        }
    }

    void build(int p, int l, int r)
    {
        tr[p].l = l, tr[p].r = r;
        if (l == r)
        {
            tr[p].mx = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        pushup(p);
    }

    void change(int p, int x, int y, int k)
    {
        if (x <= tr[p].l && y >= tr[p].r)
        {
            calc(p, k);
            return;
        }
        int mid = tr[p].l + tr[p].r >> 1;
        // pushdown(p);
        if (x <= mid)
            change(lc, x, y, k);
        if (y > mid)
            change(rc, x, y, k);
        pushup(p);
    }

    int query(int p, int x, int y)
    {
        if (x <= tr[p].l && y >= tr[p].r)
            return tr[p].mx;
        int mid = tr[p].l + tr[p].r >> 1;
        // pushdown(p);
        int mx = 0;
        if (x <= mid)
            mx = max(mx, query(lc, x, y));
        if (y > mid)
            mx = max(mx, query(rc, x, y));
        return mx;
    }

    int query2(int p, int x, int y, int k)
    {
        if (y < tr[p].l || x > tr[p].r)
            return -1;
        if (tr[p].l == tr[p].r)
        {
            if (tr[p].mx >= k)
                return tr[p].l;
            else
                return -1;
        }
        if (x <= tr[p].l && y >= tr[p].r)
        {
            if (tr[p].mx < k)
                return -1;
        }
        int mid = tr[p].l + tr[p].r >> 1;

        int t1 = query2(lc, x, y, k);
        if (t1 != -1)
            return t1;
        return query2(rc, x, y, k);
    }

    void debug(int p = 1)
    {
        // return;
        cout << "[" << tr[p].l << ", " << tr[p].r << "]: ";
        cout << "add = " << tr[p].add << ", ";
        cout << endl;
        if (tr[p].l == tr[p].r)
            return;
        debug(lc), debug(rc);
    }

#undef lc
#undef rc
} t;

signed main()
{
    int n, m;
    Cin(n, m);
    for (int i = 1; i <= n; i++)
    {
        Cin(t.a[i]);
    }
    t.build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int op;
        Cin(op);
        if (op == 1)
        {
            int x, y;
            Cin(x, y);
            t.a[x] = y;
            t.change(1, x, x, y);
        }
        else if (op == 2)
        {
            int l, r;
            Cin(l, r);
            swap(t.a[l], t.a[r]);
            t.change(1, l, l, t.a[l]);
            t.change(1, r, r, t.a[r]);
        }
        else if (op == 3)
        {
            int l, r;
            Cin(l, r);
            if (l > r)
                swap(l, r);
            write(t.query(1, l, r));
            puts("");
        }
        else
        {
            int l, r, x;
            Cin(x, l, r);
            write(t.query2(1, l, r, x));
            puts("");
        }
    }
}

写的比较赶，以后有时间部分题目的解释会改详细一点

有帮助，赞一个

去预览

0/2000

全部评论 3

复仇者_THUNDER
真的是大佬啊！！！

2024-11-04 来自广东
1
- xueman
  回复复仇者_THUNDER
  %%%
  
  2024-11-06 来自山东
  0
‮队团加不）ด้้童帅_者仇复

2024-11-03 来自广东
1
- xueman
  回复‮队团加不）ด้้童帅_者仇复
  %%%
  
  2024-11-03 来自山东
  0
Starsfocxy
其实T6可以用树状数组解决

2024-11-04 来自江苏
0
- xueman
  回复Starsfocxy
  好像确实可以，如果用树状数组常数会小很多，但是我感觉比线段树更难写，不如线段树直观(
  
  2024-11-05 来自山东
  0
- ‮队团加不）ด้้童帅_者仇复
  回复xueman
  树状数组怎么求第一个大于等于X的数？
  
  2024-11-05 来自广东
  0
- xueman
  回复‮队团加不）ด้้童帅_者仇复
  感觉不是怎么好写，你可以问一下层主，不过感觉按照https://blog.csdn.net/qq_41829492/article/details/123984745这篇文章的二分思路应该能写出来
  
  2024-11-06 来自山东
  0