Skip to content

2024年10场Div3训练

约 2522 个字 484 行代码 预计阅读时间 14 分钟

[toc]

Codeforces Round 916

2023年12月26日

C. Quests

模拟 *1100

枚举要开到第几个任务，剩下的次数全部去完成第二次经验给的最多的任务。

发现最优的操作序列一定等价于：

  • 首先连续地取 \(a_1,a_2,⋯,a_m(m \le k)\)。
  • 然后不断地取 \(\max_{1 \le i \le m} \le b_i\) 。

时间复杂度：\(O(n)\)

代码 
void solve()
{   
    int n,k;
    cin >> n >> k;
    vector<int> a(n,0),b(n,0);
    vector<vector<int>> dp(n,vector<int>(2,0));
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++) cin >> b[i];

    int mx = 0;
    int res = 0,cur = 0;
    for(int i = 0; i < min(k,n); i++) {
        mx = max(mx,b[i]); 
        cur += a[i];
        int now = cur + max(k-i-1,0)*mx;
        res = max(res,now);
    }
    cout << res << "\n";
}

D. Three Activities

模拟 排序 *1200

The sum of \(n\) over all testcases doesn't exceed \(10^5\).

将三个序列排序，然后 3*3*3 中选出符合条件的最大的一个

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

代码 
void solve()
{   
    int n;
    cin >> n;
    vector<pair<int,int>>a(n),b(n),c(n);
    int x;
    for(int i = 0; i < n; i ++) cin >> x,a[i] = {x,i};
    for(int i = 0; i < n; i ++) cin >> x,b[i] = {x,i};
    for(int i = 0; i < n; i ++) cin >> x,c[i] = {x,i};

    sort(a.begin(),a.end(),greater<>());
    sort(b.begin(),b.end(),greater<>());
    sort(c.begin(),c.end(),greater<>());

    int mx = 0;
    for(int i = 0; i < 3; i ++)
        for(int j = 0; j < 3; j ++) 
            for(int k = 0; k < 3; k ++) {
                if(a[i].second != b[j].second && a[i].second != c[k].second && b[j].second != c[k].second) {
                    mx = max(mx,a[i].first + b[j].first + c[k].first);
                }
            }
    cout << mx << "\n";
}

E2 - Game with Marbles (Hard Version)

排序 *1400

思路：我们可以想一下，每个人操作后获得的价值是多少，如果是 A 操作，则获得的价值是 a[i] − 1 + b[i] ,如果是 B 操作，则获得的价值是 b[i] − 1 + a[i]，可以发现两个式子是一样的，最有这个操作一定是从大的开始轮流操作，排序即可

从总贡献上想，每个单独的对最后贡献多少。而不是从上一层贡献中来思考

代码 
void solve()
{   
    int n;
    cin >> n;

    vector<int> a(n),b(n);
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++) cin >> b[i];

    vector<pair<int,int>> c(n);
    for(int i = 0; i < n; i ++) 
        c[i] = {a[i] + b[i],i};

    sort(c.begin(),c.end(),greater<>());

    ll res = 0;
    for(int i = 0; i < n; i ++) {
        int x = c[i].second;
        if(i%2 == 0)
            res += a[x] - 1;
        else 
            res -= b[x] - 1;

    }
    cout << res << "\n";
}

Codeforces Round 760

2023年12月27日

B. Missing Bigram

string *800

思路：字符串拼接

代码 
void solve()
{   
    int n;
    cin >> n;
    string s;
    cin >> s;

    bool f = false;
    for(int i = 2; i <= n-2; i ++) {
        string t;
        cin >> t;
        if(s.back() == t.front()) s += t.back();
        else {
            f = true;
            s += t;
        }
    }
    if(!f) s += 'a';
    cout << s << "\n";
}

C. Paint the Array

模拟 思维 *1100

思路：在奇数子列和偶数子列 分别求出最大公因数，设为 \(x\),\(y\) respectly

  • x 在偶数子列中验证是否符合，符合即输出
  • y 在奇数子列中验证是否符合，符合即输出
  • 都不符合，输出 \(0\)

时间复杂度：\(O(n^2)\)

代码 
void solve()
{   
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i ++) cin >> a[i];

    ll x = a[0],y = a[1];
    for(int i = 2; i < n; i += 2) x = gcd(x,a[i]);
    for(int i = 3; i < n; i += 2) y = gcd(y,a[i]);
    // cout << x << " " << y << "\n";

    bool f = true;
    for(int i = 0; i < n; i += 2) {
        if(a[i]%y == 0) {
            f = false;
        }
    }
    if(f) {
        cout << y << "\n";
        return;
    }
    f = true;
    for(int i = 1; i < n; i += 2) {
        if(a[i]%x == 0) {
            f = false;
        }
    }
    if(f) {
        cout << x << "\n";
        return;
    }

    cout << "0\n";
}

D. Array and Operations

贪心 *1300

思路：将前 \(2k\) 大的都化简掉，使得答案最小。

用 \(k\) 个最大元素做分母使得总分最小，并且我们要使剩下元素最小，所以选第 \(k+1\) 到 第 \(2k\) 的元素做分子

并且此时每个分数的值向下取整只能是 \(0,1\) 中的一个，所以我们尽量减少分子和分母相等的分数的数量。于是可以想到头尾配对。

代码 
void solve()
{   
    int n,k;
    cin >> n >> k;
    vector<int> a(n),st(n,0);
    for(auto& it: a) cin >> it;
    sort(a.begin(),a.end(),greater<>());

    // 将大的尽量都化简掉，剩下的就小。
    // 将 前 2k 个大的都化简掉
    int res = 0;
    for(int i = 0; i < k; i ++) 
        res += a[i+k]/a[i];

    for(int i = 2*k; i < n; i ++) 
        res += a[i];
    cout << res << "\n";
}

Codeforces Round 913

2023年12月28日

D. Jumping Through Segments

二分 *1400

思路：二分枚举答案即可，check 时判断两线段是否相交，然后更新线段。

代码 
void solve()
{   
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    for(int i = 0; i < n; i ++) {
        int x,y;
        cin >> x >> y;
        a[i] = {x,y};
    }
    auto check = [&](int k) {
        int l = 0,r = 0;
        for(int i = 0; i < n; i ++) {
            l -= k, r += k;
            // 两条线段没有交点
            if(l > a[i].second || r < a[i].first) {
                return false;
            }
            l = max(l,a[i].first),r = min(r,a[i].second);
        }
        return true;
    };

    int l = 0,r = 1e9+10;
    while(l < r) { 
        int mid = l + r  >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << "\n";
}

Codeforces Round 918 (Div. 4)

2023年12月29日

E. Romantic Glasses

找规律 *1381

leetcode的类似题目：和为 k 的子数组

思路：\(sum[i] - 2 * odd[i]\) 这个值如果之前出现过，比如在前面的 \(j\), 即 \(sum[j] - 2 * odd[j] = sum[i] - 2 * odd[i]\)

经过整理可以得到，从 \(j\) 到 \(i\) 的序列，符合规律。

开头插入零，如果有等于零的，直接就符合捏

时间复杂度：\(O(n)\)

代码 
void solve()
{   
    int n;
    cin >> n;
    vector<ll> a(n+1),sum(n+1),odd(n+1);
    set<ll> s;
    bool f = false;
    s.insert(0);

    for(int i = 1; i <= n; i ++) {
        cin >> a[i];

        sum[i] = sum[i-1] + a[i];
        if(i% 2== 1) {
            odd[i] = odd[i-1] + a[i];
        }else odd[i] = odd[i-1];

        if(s.count(sum[i] - 2ll*odd[i])) f = true;
        s.insert(sum[i] - 2ll*odd[i]);
    }

if(f) cout << "YES\n";
else cout << "NO\n";
}

F. Greetings

Fenwick *1618

思路：求集合中比某个数大的数目的个数，离散化 + 树状数组

代码 
void solve()
{   
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    set<int> s;
    for(int i = 0; i < n; i ++) {
        int x,y;
        cin >> x >> y;
        a[i] = {x,y};
        s.insert(x),s.insert(y);
    }
    sort(a.begin(),a.end(),[&](auto &x,auto &y){
        if(x.first != y.first) return x.first < y.first;
        return x.second > y.second;
    });

    vector<int> b(s.begin(),s.end());
    auto find = [&](int x) {
        return lower_bound(b.begin(),b.end(),x) - b.begin();
    };

    Fenwick<ll> tr(2*n+1);
    ll res = 0;
    for(auto [x,y]: a) {
        x = find(x);
        y = find(y);
        res += tr.rangeSum(y,2*n+1);
        tr.add(y,1);
    }
    cout << res <<"\n";
}

Good Bye 2023

2024年1月4日

C. Training Before the Olympiad

构造 找规律 *1200

思路：这是一个典型的找规律题，借由此题我们耐下心来记录下找规律的过程。

可以发现，

  1. 奇偶性不同的组合在一起会损失
  2. 每次操作至多损失 \(1\)
  3. 每次操作数组的长度减 \(1\)
  4. 每次操作后都会产生一个偶数
  5. 结果大概率与 奇数和偶数的个数有关

分析样例是第一步，

input 

6
6 3 7 2 5 4
output

6 8 16 18 22 26

前一个，显然直接结束

前两个，有一个奇数，一个偶数，6 3, sum = 9

  • 最大化它的操作：\(6\) 和 \(3\) 组合，产生 \(8\)

前三个，有两个奇数，一个偶数，6 3 7, sum = 16

  • 最大化它的操作：选两个奇数 \(3\) 和 \(7\)，产生 \(10\)
  • 最小化它的操作：\(10\) 和 \(16\) 组合，产生 \(16\)

前四个，有两个奇数，两个偶数，6 3 7 2，sum = 18

  • 最大化它的操作：选两个奇数 \(3\) 和 \(7\)，产生 \(10\)，此时数组：6,2,10
  • 最小化它的操作：\(6\) 和 \(2\) 组合，产生 \(8\)，此时数组：8,10
  • 最大化它的操作：\(8\) 和 \(10\) 组合，产生 \(18\)

前五个，有三个奇数，两个偶数 6 3 7 2 5，sum = 23

  • 最大化它的操作：选两个奇数 \(3\) 和 \(7\)，产生 \(10\)，此时数组：6,2,5,10
  • 最小化它的操作：\(6\) 和 \(5\) 组合，产生 \(10\)，此时数组：2,10,10
  • 最大化它的操作：\(10\) 和 \(10\) 组合，产生 \(20\)，此时数组：2,20
  • 最小化它的操作：\(20\) 和 \(2\) 组合，产生 \(22\)

前六个，有三个奇数，三个偶数 6 3 7 2 5 4，sum = 27

  • 最大化它的操作：选两个奇数 \(3\) 和 \(7\)，产生 \(10\)，此时数组：6,2,5,4,10
  • 最小化它的操作：\(6\) 和 \(5\) 组合，产生 \(10\)，此时数组：2,4,10,10
  • 最大化它的操作：\(10\) 和 \(10\) 组合，产生 \(20\)，此时数组：2,4,20
  • 最小化它的操作：\(20\) 和 \(2\) 组合，产生 \(22\)，此时数组：4,22
  • 最大化它的操作：\(22\) 和 \(4\) 组合，产生 \(26\)

至此，我们可以发现

  1. 有三个奇数时，会损失 \(1\)
  2. 有一个奇数时，会损失 \(1\)
  3. 考虑三个奇数：第一步最大化，会产生一个偶数；第二步最小化，会损失 \(1\)
  4. 所以每当有三个奇数的时候一定会损失 \(1\)
  5. 当只存在两个奇数的时候，不产生损失
  6. 当只存在一个奇数的时候，产生损失 \(1\)
代码 
void solve()
{   
    int n;
    cin >> n;
    ll sum = 0;
    cin >> sum;
    cout << sum <<" ";
    int odd = sum%2;
    for(int i = 1; i < n; i ++) {
        ll x;
        cin >> x;
        sum += x;
        odd += x%2;
        cout << sum - odd/3 - (odd%3 == 1) << " ";
    }
    cout << "\n";

}

Codeforces Round 834 (Div. 3)

2024年1月7日

D. Make It Round

让 \(2\) 和 \(5\) 尽可能的匹配

答案是 \(n \cdot k\) 。

首先统计两个数字： \(cnt_2, cnt_5\) ，分别表示数字 \(n\) 中 \(2\) 和 \(5\) 出现的程度，即 \(n = 2^cnt_2 \cdot 5^cnt_5 \cdot d\) 。其中 \(d\) 不能被 \(2\) 或 \(5\) 整除。现在当 \(cnt_2 \neq cnt_5\) 时我们将增加相应的值。例如，如果是 \(cnt_2 \lt cnt_5\) ，那么只要 \(cnt_2 \neq cnt_5\) ，在该 \(k \cdot 2 \le m\) 处，我们就会将 \(cnt_2\) 增加 \(1\) ，并将 \(k\) 乘以 \(2\) 倍。

这样我们就可以通过花费尽可能少的 \(k\) 来获得尽可能多的整数。

现在我们要么有 \(cnt_2 = cnt_5\) ，要么有 \(k \cdot 5 \gt m\) ，要么有 \(k \cdot 2 \gt m\) 。那么在第一种情况下，我们将尽可能地将数字 \(k\) 乘以 \(10\) 。也就是说，直到 \(k \cdot 10 \le m\) 。

现在无论哪种情况我们都有： \(k \cdot 10 \gt m\) 。然后 \(\lfloor \frac{m}{k} \rfloor = x \lt 10\) 。然后我们将 \(k\) 乘以 \(x\) 倍，得到我们想要的答案。

在最后一步中，我们不能再得到一个四舍五入的数字，而只是找到最大可能的数字。

代码 
void solve()
{
    ll n, m;
    cin >> n >> m;
    ll tn = n, tm = m;
    ll td = 1;
    while(tn % 10 == 0) {
    tn /= 10;
    td *= 10;
    }
    ll tq = 1;
    while(tn % 5 == 0 and tq * 2 <= m){
    tq *= 2;
    tn /= 5;
    }
    while(tn % 2 == 0 and tq * 5 <= m){
    tq *= 5;
    tn /= 2;
    }
    while(tq * 10 <= m) tq *= 10;
    if(tq == 1){
    cout << n * m << endl;
    }else{
    cout << tq * n * (m / tq) << endl;
    }
}

Codeforces Round 909 (Div. 3)

2024年1月8日

D. Yarik and Musical Notes

\((2^{a_i})^{2^{a_j}} =(2^{a_j})^{2^{a_i}}\) 转化为 \(a_i*log_2(2) - log_2(a_i) = a_j*log_2(2) - log_2(a_j)\)

代码 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &it: a) cin >> it;
    ll res = 0;
    map<double,int> mp;
    for(auto c: a) {
        double t = (double)c*log2(2) - (double)log2(c);
        if(mp[t] > 0) res += mp[t];
        mp[t] ++;
    }

    cout << res << "\n";
}

F. Alex's whims

构造：让叶子尽可能的少：长链

每次修改都只看分支，让分支符合情况。

代码 
void solve()
{
    int n,q;
    cin >> n >> q;

    for(int i = 1; i <= n-1; i ++) {
        cout << i << " " << i + 1 << "\n";
    }
    int pre = n - 1;
    for(int i = 0; i < q; i ++) {
        int x;
        cin >> x;
        if(pre == x) {
            cout << "-1 -1 -1\n";
            continue;
        }
        cout << n << " " << pre << " "<< x <<"\n";
        pre = x;
    }

}

Codeforces Round 891 (Div. 3)

2024年1月8日

E. Power of Points

排序，推公式，模拟

代码 
void solve()
{
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    ll last = 0,pre = 0;
    for(int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        last += x;
        a[i] = {x,i};
    }
    sort(a.begin(),a.end());
    vector<ll> res(n);

    for(int i = 0; i < n; i ++) {
        auto [x,pos] = a[i];
        last -= x;
        if(i != 0) res[pos] += 1ll*i*x - pre + i;
        if(i != n-1) res[pos] += last - 1ll*x*(n-1-i)  + (n-1-i);
        // debug(res[pos]);
        pre += x;
        res[pos] += 1ll;

    }
    for(int i = 0; i < n; i ++) cout << res[i] << " ";
    cout << "\n";
}

F. Sum and Product

解一元二次方程

代码 
void solve()
{
    int n;
    cin >> n;
    map<int,int> mp;
    for(int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        mp[x] ++;
    }
    int q;
    cin >> q;
    while(q --) {
        ll x,y;
        cin >> x >> y;
        if(x*x - 4*y < 0) {
            cout << "0\n";
            continue;
        } 
        if(x*x - 4*y == 0 ) {
            if(x%2 == 1) cout << "0 ";
            else 
                cout << 1ll * mp[x / 2] * (mp[x / 2] - 1) / 2 << " ";
            continue;
        }

        ll t = sqrt(x*x - 4*y);
        if(t*t != x*x - 4*y || (x+t)%2 == 1) {
            cout << "0 ";
            continue;
        }

        ll a = (x+t)/2,b = (x-t)/2;
        cout << 1ll * mp[a]*mp[b] << " ";
    }
    cout << "\n";

}

Codeforces Round 905 (Div. 3)

2024年1月10日

题目链接：905

C. Raspberries

math

k 是 \(2,3,5\) 的时候好判断

当 \(k = 4\) 的时候

  • 数组中有 \(4\) 的倍数，零次
  • 数组中只有一个 \(2\) 的倍数，且没有 \(4\) 的倍数，一次
  • 数组中没有 \(2\) 的倍数，即模四余一 或 模四余二 1. 如果数组中不含模四余 \(3\) : 即 1 1，只能找两个奇数都加一，凑出两个 \(2\) 来 2. 如果数组中存在模四余 \(3\) , 只需要把这个数加一，就能凑出 \(4\) 来
代码 
void solve()
{
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(auto &x: a) cin >> x;

    if(k != 4) {
        int res = 1110;
        for(auto c: a) {
            int t = c / k;

            if(c%k != 0) t += 1;
            res = min(res,t*k - c);
        }
        cout << res << "\n";
    } else {
        int cnt = 0;
        for(auto c: a) {
            if(c % 4 == 0) cnt += 2;
            else if(c % 2 == 0) cnt += 1;
        }
        if(cnt >= 2) cout << "0\n";
        else if(cnt == 1){
            cout << "1\n";
        }else {
            // 1 3 -> 1
            // 1 1 -> 2
            int res = 2;
            for(auto c: a) {
                if(c % 4 == 3) res = 1;
            }
            cout << res << "\n";
        }
    }
}

D. In Love

multiset

由于删除线段时一定保证该线段存在，所以我们可以分别开两个 multiset，分别维护线段的左端点最大值和右端点最小值，然后就可以判断了。

++it 和 --it 都是对迭代器进行递增和递减的操作。它们分别表示前置递增和前置递减。以下是关于这两个操作的详细介绍：

  1. 前置递增 (++it)： 递增迭代器 it 的位置，使其指向序列中的下一个元素。这是一个原地修改操作，会改变迭代器的状态。
std::set<int> mySet = {1, 2, 3, 4, 5};
auto it = mySet.begin();

// 使用前置递增操作将迭代器指向下一个元素
++it;

// 现在 it 指向集合中的第二个元素
  1. 前置递减 (--it)： 递减迭代器 it 的位置，使其指向序列中的前一个元素。这同样是一个原地修改操作。
std::set<int> mySet = {1, 2, 3, 4, 5};
auto it = mySet.end(); // end() 返回指向集合末尾的迭代器

// 使用前置递减操作将迭代器指向前一个元素
--it;

// 现在 it 指向集合中的最后一个元素
  1. 结合使用 (++it 和 --it)： 在一些情况下，你可能需要在迭代器上进行前置递增和前置递减的混合操作，以在序列中移动到指定位置。
std::set<int> mySet = {1, 2, 3, 4, 5};
auto it = mySet.begin();

// 先递增两步
++it;
++it;

// 再递减一步
--it;

// 现在 it 指向集合中的第二个元素

总体而言，这些操作对于在容器中进行迭代是非常有用的，它们允许你直接修改迭代器的位置，使得在序列中进行导航变得更加灵活。

思路

区间合并问题通常涉及到合并重叠的区间，使得结果集中不再存在重叠的区间。这种问题可以通过排序区间的起始点，然后迭代合并相邻的区间来解决。使用 multiset 可以方便地实现这个过程。

一般的步骤如下：

将区间按照起始点排序： 首先，将所有的区间按照起始点进行排序。这确保了我们可以顺序地处理区间，并且相邻的区间在排序后会紧邻彼此。

迭代合并相邻区间： 然后，迭代排序后的区间集合，逐一合并相邻的区间。如果当前区间的结束点大于等于下一个区间的起始点，说明这两个区间有重叠，需要合并。

输出合并后的区间： 最后，输出合并后的区间。

代码 
void solve()
{
    int n;
    cin >> n;
    multiset<int> sl,sr;
    for(int i = 0; i < n; i ++) {
        ll l,r;
        char c;
        cin >> c;
        cin >> l >> r;
        if(c == '+') {
            sl.insert(l);
            sr.insert(r);
            auto it = sl.end();
            if(*sr.begin() < *(--it)) 
                cout << "YES\n";
            else 
                cout << "NO\n";
        } else{
            sl.erase(sl.find(l));
            sr.erase(sr.find(r));
            auto it = sl.end();
            if(!sr.empty() and !sl.empty() and *sr.begin() < *(--it))
                cout << "YES\n";
            else    
                cout << "NO\n";
        }
    }
}

E. Look Back

Alt text

  1. 只比较两个相邻的数之间差多少个 \(2\)

  2. 最后算的时候前面加了 后面也要加，始终保持他的有序性

代码 
void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for(auto &x: a) cin >> x;
    ll res = 0,sum = 0;

    vector<ll> cnt(n,0);
    for(int i = 1; i < n; i ++) {
        ll l = a[i-1],r = a[i];
        cnt[i] = cnt[i-1];
        while(l < r) l *= 2,cnt[i] --; // 可能不需要那么多次操作就够了
        while(l > r) r *= 2,cnt[i] ++; // 需要在前面加的基础上在加几次
        cnt[i] = max(0LL,cnt[i]);
    }
    cout << accumulate(cnt.begin(),cnt.end() ,0LL) << "\n";
}

Codeforces Round 894 (Div. 3)

2024年1月10日

题目链接：894

Last update: January 11, 2024
Created: December 26, 2023