ICPC 2024 成都站

幽灵特工 · 2025-04-06 17:02:08 · 个人记录

CF链接 VP过了5题，其中我做了两题，Cu。

L题 Recover Statistics

签到、简单构造

L题签到题我居然WA了4发。。。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
ll n, m;
int T;
ll gcd(ll a, ll b) {
    return b > 0 ? gcd(b, a % b) : a;
}
int main() {
    ios::sync_with_stdio(0);
    int a, b, c;
    cin >> a >> b >> c;
    cout << 100 << endl;
    for (int i = 1; i <= 50; i++)cout << 1 << " ";
    for (int i = 51; i <= 95; i++)cout << a+1 << " ";
    for (int i = 96; i <= 99; i++)cout << b+1 << " ";
    cout << c + 1;
}

J题 Grand Prix of Ballance

签到、模拟

太简单了，而且是队友做的，代码就不贴了。

A题 Arrow a Row

构造

#include<bits/stdc++.h>
using namespace std;
#define  ll long long
#define IOS cin.tie(0);cout.tie(0);ios::sync_with_stdio(0)
#define  pll pair<long long,long long>
ll t, n,ed;
string s;
int main()
{
    IOS;
    cin >> t;
    while (t--)
    {
        vector<pll>ans;
        cin >> s;
        n = s.length();
        s = " " + s;
        ll cnt = 0;
        for (ll i = n; i >=1; i--)
        {
            if (s[i] == '>')
                cnt++;
            else break;
        }
        ed = 0;
        for (ll i = n - cnt; i >=1; i--)
        {
            if (s[i] == '>')
            {
                ed = i;
                break;
            }
        }
        ll sum = 0;
        if (cnt >= 3 and s[1] == '>' and cnt != n)
        {
            cout << "Yes ";
            ll i = 1, j = n - 2;
            while (i != ed or j != n - cnt + 1)
            {
                sum++;
                ans.push_back({ i,j-i+3 });
                j = max(j - 3, n - cnt + 1);
                while (s[++i] == '-');
                i = min(i, ed);
            }
            ans.push_back({ i,j-i+3 });
            sum++;
            cout << sum << '\n';
            for (auto e : ans)
                cout << e.first << ' ' << e.second << '\n';
        }
        else
        {
            cout << "No\n";
        }
    }
}

B题 Athlete Welcome Ceremony

动态规划、前缀和

题意

给你一个由a,b,c和?构成的串，你要将所有?变成a,b,c之一，使其成为没有相邻字符相同的串。

有Q个询问，每次给你一组 x,y,z，问你最多用 x 个a, y 个b 和 z 个c能构成多少合法串。输入保证合法且有解。

题解

我还不会下次补。。。代码先不贴了。

G题 Expanding Array

位运算

VP的时候做到这题已经猜到结论了，但是写了一半代码出去上了个很长时间的厕所，被队友怀疑偷看题解了（然而我是在刷王者荣耀视频QAQ）

题意

一个整数数组，可以无限次进行以下操作：选择两个相邻的数，将其按位与、或、异或的三个结果中的一个插入到这两个数之间。问最后数组元素个数的最大值。

题解

可以猜到证明对于相邻的两个数 x,y 在无限次操作后能产生的数只有：

全部放进set里，输出size()即可。VP时我为了谨慎起见还加了很多额外的数进去，不影响结果和复杂度。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
ll n, m;
int a[100005];
set<int> s;
int main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    for (int i = 0; i < n - 1; i++) {
        int x = a[i] ^ a[i + 1];
        int y = a[i] & a[i + 1];
        int z = a[i] | a[i + 1];
        s.insert(x);
        s.insert(y);
        s.insert(z);
        s.insert(x & y);
        s.insert(x & z);
        s.insert(y & z);
        s.insert(x ^ y);
        s.insert(x ^ z);
        s.insert(y ^ z);
        s.insert(x | y);
        s.insert(x | z);
        s.insert(y | z);
        s.insert(a[i] & x);
        s.insert(a[i] & y);
        s.insert(a[i] & z);
        s.insert(a[i] ^ x);
        s.insert(a[i] ^ y);
        s.insert(a[i] ^ z);
        s.insert(a[i] | x);
        s.insert(a[i] | y);
        s.insert(a[i] | z);
        s.insert(a[i + 1] & x);
        s.insert(a[i + 1] & y);
        s.insert(a[i + 1] & z);
        s.insert(a[i + 1] ^ x);
        s.insert(a[i + 1] ^ y);
        s.insert(a[i + 1] ^ z);
        s.insert(a[i + 1] | x);
        s.insert(a[i + 1] | y);
        s.insert(a[i + 1] | z);
    }
    s.insert(0);
    cout << s.size();
}

I题 Good Partitions

数学、线段树

这题做出来应该就有Ag了，可惜可惜。

题意

给定一个长度为 n 的序列，如果从第一项开始每 k 个元素一组将其划分为 \lceil \frac{n}{k} \rceil 个子序列（最后一个子序列元素个数可能不满 k 个），且每个子序列都是单调不减的，则称这种划分为好的划分。

有 q次 修改，每次修改序列中一个位置的元素值。询问每次修改前后好的划分的数量。