Codeforces Round 1122 (Div. 3)

约 18 分钟 5 次浏览作者 暂无评论
喜欢这篇文章就点个赞吧

比赛链接:https://codeforces.com/contest/2266

A. Good Contest

time limit per test: 1 second / memory limit per test: 256 megabytes
input: standard input / output: standard output

The next programming contest has three problems and n participants.
Problem 1 is easy, problem 2 is medium, and problem 3 is hard.
A participant is called weak if they did not solve all three problems.
Unfortunately, the scoreboard was lost. The only remaining information is an array a of length 3, where a_i is the number of participants who solved problem i.
Among all scoreboards consistent with this information, find the minimum possible number of weak participants.

Input
The first line contains an integer t (1 <= t <= 3000) — the number of test cases.
The first line of each test case contains an integer n (1 <= n <= 9) — the number of participants.
The second line of each test case contains three integers a_1, a_2, a_3 (0 <= a_i <= n), where a_i is the number of participants who solved problem i.

Output
For each test case, print a single integer — the minimum possible number of weak participants.

题意大概是有三道题,有n个学生去写,如果一个学生没有全部写对就算weak participants,要求这个weak participants人数的最小值

令p = 三道题中被写出最少的题的次数

容易得到n - p就是答案

因为最多有p个人全对,那么剩下的必然不可能全对,n - p就是最大值

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> a(3);
        cin >> a[0] >> a[1] >> a[2];
        cout << n - min({a[0], a[1], a[2]}) << '\n';
    }
}

B. Three Piles

time limit per test: 1 second / memory limit per test: 256 megabytes
input: standard input / output: standard output

Alice and Bob are playing a game with three piles of stones. Initially, Alice has a stones, Bob has b stones, and the third pile contains c stones.
Alice and Bob take turns, with Alice going first. On each turn, the current player may take any number of stones from the third pile, possibly zero, and add them to their own pile.
If both players take zero stones on two consecutive turns, the game ends.
Let A and B be the final numbers of stones Alice and Bob have, respectively. The score of the game is |A - B|.
Alice wants to maximize the score, while Bob wants to minimize it. Assuming both players play optimally, find the final score.

Input
The first line contains an integer t (1 <= t <= 10^4) — the number of test cases.
Each test case contains three integers a, b, and c (0 <= a, b, c <= 10^9) — the initial numbers of stones Alice has, Bob has, and the third pile has, respectively.

Output
For each test case, output one integer — the final score if both players play optimally.
It is important to use a 64-bit integer type, such as long long in C++.

题目翻译一下大概是这样的:

爱丽丝和鲍勃正在玩一个涉及三堆石头的游戏.最初,爱丽丝有a个石头,鲍勃有b个石头,第三堆中有c个石头

爱丽丝和鲍勃轮流行动,由爱丽丝先手.每轮,当前玩家可以从第三堆中取任意数量的石头(包括零个),并将它们加入自己的堆中

如果双方在连续两轮中都未取石头,游戏结束

设A和B分别表示爱丽丝和鲍勃最终拥有的石头数量.游戏得分是|A - B|

爱丽丝希望将得分最大化,而鲍勃希望将得分最小化.假设双方都采取最优策略,求最终得分

第三堆是双方唯一的石头来源,所以自己的石头只会越加越多,设爱丽丝一共取了x个,答案只可能在x的两个端点上产生.

  1. 全取(x = c):第三堆空了,Bob只能取0,分数只能为|a + c - b|
  2. 全不取(x = 0):若a <= b,Bob多取只会拉大差距,所以他会取0个,得到|a - b|;若a > b,Bob会减小差距,但此时a - b < a + c - b,即|a - b|本来就小于另一端,不影响答案

中间取法都会被Bob抵消到不超过这两端,所以答案就是两端取大:

ans = max(|a - b|, |a - b + c|)

代码里第二项写c + a - b没套abs,因为它为负时必定小于|a - b|

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        long long a, b, c;
        cin >> a >> b >> c;
        long long ans = max(llabs(a - b), c + a - b);
        cout << ans << '\n';
    }
}

C. AND, OR, Sort!

time limit per test: 2 seconds / memory limit per test: 256 megabytes
input: standard input / output: standard output

You are given a binary string s of length n.
You may perform the following operation any number of times (possibly zero):
choose an integer i (1 <= i <= n), and replace s_i with either the bitwise AND or the bitwise OR of s_1, s_2, ..., s_i.
Note that the bitwise AND or the bitwise OR of a single element is equal to the element itself.
Your goal is to make s sorted in non-decreasing order (that is s_1 <= s_2 <= ... <= s_n).
Find the minimum number of operations required to sort s in non-decreasing order.

Input
The first line contains a single integer t (1 <= t <= 10^4) — the number of test cases.
The first line of each test case contains a single integer n (2 <= n <= 2*10^5) — the length of the binary string s.
The second line of each test case contains the binary string s of length n. Each character of s is either 0 or 1.
It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.

Output
For each test case, print a single integer — the minimum number of operations required to sort s in non-decreasing order.

这道题给了两种操作,一种是AND一种是OR

要求把一个二进制字符串变成非递减排序的(也就是递增排序),答案格式会是00000...11111这样的,从中间某个地方开始后面全是1前面全是0

AND能把第i位变成前i位的AND:只要前i位里有0就能把这一位改成0.因为第一位就是0,所以任何1都能变0(变变你的)

对称地,OR能把第i位变成前i位的OR:只有前i位里出现过1,才能把这一位的0变成1

一次操作只改一位,先做OR再做AND互不干扰,所以代价就等于需要改的位数

当第一个位是1时,前缀的AND和OR恒为1,也就是1永远变不回0,最终必定全是1,操作次数就是0的个数zeros

方便起见我们用zeros表示0的个数

不妨设答案在p处分界,前p个字符全是0,后n - p个字符全是1

那么就有ans = ones(p) + ( zeros - zeros(p) ),前一项是把前p位的1改成0,后一项是把后段的0改成1

不妨令bal = ones(p) - zeros(p),那么ans = zeros + bal,只要枚举p = 0, 1, ..., n取bal的最小值(p = 0时bal = 0,所以代码里m初值取0)

ans = zeros + min(bal(p))

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int zeros = 0;
        for (char ch : s)
            if (ch == '0')
                zeros++;
        if (s[0] == '1')
        {
            cout << zeros << '\n';
        }
        else
        {
            int bal = 0, m = 0;
            for (char ch : s)
            {
                bal += (ch == '1') ? 1 : -1;
                m = min(m, bal);
            }
            cout << zeros + m << '\n';
        }
    }
}

D. Falling Concrete

time limit per test: 2 seconds / memory limit per test: 256 megabytes
input: standard input / output: standard output

Vihaan is repairing a road consisting of n sections. The height of the i-th section is a_i.
He has a forklift which can move road sections. In one operation, Vihaan chooses two indices i and j (1 <= i < j <= n), picks up the j-th section, and moves it backwards to position i.
As the section is carried backwards, one unit of concrete falls from it onto each section it passes over. Then, the carried section is inserted at position i.
More formally, the subarray [a_i, a_{i+1}, ..., a_{j-1}, a_j] is replaced with [a_j - (j - i), a_i + 1, a_{i+1} + 1, ..., a_{j-1} + 1].
A part of the road is called flat if it is a contiguous segment of sections with equal heights.
Vihaan may perform any number of operations, possibly zero.
Find the maximum possible length of a flat part of the road.

Input
The first line contains an integer t (1 <= t <= 10^4) — the number of test cases.
The first line of each test case contains an integer n (1 <= n <= 2*10^5) — the number of sections of the road.
The second line contains n integers a_1, a_2, ..., a_n (n <= a_i <= 10^9) — the initial heights of the sections.
It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.
It can be shown that under the given constraints, the height of every section remains positive after any sequence of operations.

Output
For each test case, print a single integer — the maximum possible length of a flat part of the road.

令v[i] = a_i - i,一次操作恰好等价于把v的区间循环右移

因为操作后第i位是a_j - (j - i),减掉下标正好是v[j];后面每一位都+1而下标也+1,v的值不变,只是整体后挪一格.也就是说,操作只是把v[j]搬到v[i](虽然位置变了,但是差值没变)

当j = i + 1时,就变成了交换相邻两个值,可以得到v是可以重排的

一段等高h(第l位到第r位)意味着v[l] = h - l, v[l+1] = h - l - 1, ...,也就是v里的一串连续整数

所以答案就是v的不同值中最长的连续整数链长度:算出所有v[i],排序去重后扫一遍相邻差恰为1的最长连续段就能得到答案

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<long long> v(n);
        for (int i = 0; i < n; i++)
        {
            long long x;
            cin >> x;
            v[i] = x - i;
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        int m = 1, cur = 1;
        for (int i = 1; i < v.size(); i++)
        {
            cur = (v[i] == v[i - 1] + 1) ? cur + 1 : 1;
            m = max(m, cur);
        }
        cout << m << '\n';
    }
}

附件下载

ruosha 一个热爱计算机的普通人。这里记录算法竞赛题解与学习笔记，顺带折腾服务器。

发表评论

评论需要经过审核后才会公开显示，请耐心等待。

冀ICP备2026040623号