devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Codeforces Round #700 (Div. 2)ABCD1D2_codeforces round 700 (div. 2)

作者：Gausst松鼠会 | 2024-02-09 10:30:29

赞

踩

codeforces round 700 (div. 2)

Codeforces Round #700 (Div. 2)ABCD1D2

A - Yet Another String Game

题意

给定一个由小写字母组成的字符串，每次选择一个尚未被选取过的字符进行修改（范围：小写字母a~z）——必须修改成除当前字母以外的小写字母，直至没有字符可以选取。A的目标是使它字典序越小越好，B的目标是使它字典序越大越好，A先开始修改，两个人都选择最佳策略进行游戏。问最终这个串会变成什么样？

思路

选过就不能再选，所以一定是选剩下的里面最靠前的修改，无论是改大还是改小。遇到a、z，就改成b、y。

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e3 + 19;
const ll mod = 1e9 + 7;

char str[N];

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> str;
        int n = strlen(str);
        for(int i = 0; i < n; i++)
        {
            if(i % 2)
            {
                str[i] = str[i] == 'z' ? 'y' : 'z';
            }
            else
            {
                str[i] = str[i] == 'a' ? 'b' : 'a';
            }
            cout << str[i];
        }
        cout << endl;
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

B - The Great Hero

题意

英雄有 A A A 点伤害， B B B 点生命； n n n 只怪兽的伤害值和初始生命值分别为 a 1 , a 2 , … , a n a_1, a_2, … , a_n a1​,a2​,…,an​ 和 b 1 , b 2 , … , b n b_1, b_2, … , b_n b1​,b2​,…,bn​ ，英雄和怪兽每次交战，英雄掉 a i a_i ai​ 点血，怪兽掉 B B B 点血。英雄可以和怪兽多次交战。问英雄能否杀死所有怪兽？

思路

这题最需要注意的点在样例中已经指出了：如果最后一个怪兽和英雄交战时，英雄死了，怪兽也死了，那么英雄虽死犹荣，他还是算杀死了所有的怪兽。我最开始WA的三发都是在这里。假设有一个伤害极高的怪兽，和一群几乎没伤害的怪兽，我们应该先杀死没伤害的怪兽，把伤害越高的怪兽放在越后面，不然英雄在第一轮就被gank了，把伤害高的放在后面，那么英雄虽然仍然会死亡，但是能杀死所有怪兽。

其他点都挺简单的。

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;

struct node
{
    ll a, b;
    bool operator < (const node& x)
    {
        return a < x.a;
    }
} c[N];


int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        ll A, B, n;
        bool flag = 0;
        cin >> A >> B >> n;
        for(int i = 0; i < n; i++)
        {
            cin >> c[i].a;
        }
        for(int i = 0; i < n; i++)
        {
            cin >> c[i].b;
        }
        sort(c, c + n);
        for(int i = 0; i < n; i++)
        {
            ll time =  min((B + c[i].a - 1) / c[i].a , (c[i].b + A - 1) / A);
            B -= time * c[i].a;
            if(B <= 0)
            {
                if(i < n - 1)
                    flag = 1;
                else if(c[i].b > time * A)
                    flag = 1;
                break;
            }
        }
        if(flag)
        {
            cout << "NO" << endl;
        }
        else
        {
            cout << "YES" << endl;
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

C - Searching Local Minimum

题意

给定一个从1到n的排列 p p p ，每次可以询问一个位置的数字，要求你在100次询问内，找到一个位置 i i i ，有 a i − 1 > a i , a i < a i + 1 a_{i - 1} \gt a_i,a_i \lt a_{i + 1} ai−1​>ai​,ai​<ai+1​ 。

思路

参考：(4条消息) 1480 C. Searching Local Minimum(新颖的二分查找)

挺有意思的题目，赛场上是真的想不出

代码

（其实和参考写的挺像的，可以直接去参考看思路和代码）

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;

int a[N];
int n;

void query(int x)
{
    if(x > n || x < 1 || a[x])
        return ;
    cout << "? " << x << endl;
    cout.flush();
    cin >> a[x];
}

int main()
{
    cin >> n;
    int l = 1, r = n;
    a[0] = INF, a[n + 1] = INF;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        query(mid);
        query(mid + 1);
        if(a[mid] > a[mid + 1])
        {
            l = mid + 1;
        }

        else
        {
            r = mid;
        }
    }
    cout << "! " << l << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

D1 - Painting the Array I

题意

给你一个数组，把他不打乱顺序的分成两半，并合并这分开的两个数组中所有的连续重复元素。问两个数组最终长度和最大是多少？

思路

其实是很简单的一道题，赛场上的思路也很完美，就是细节太多，死得很惨。思路如下：

  1. 把原数组中的数字拆分存储成 { \{ { 1 1 1 个 2 2 2， 3 3 3 个 1 , … , k 1,…,k 1,…,k 个 n } n\} n} 的形式，即合并连续相同的数字，之后以这样的形式从头到尾遍历；

  2. 我们很容易看出，其实情况完全可以归为两种：

    1. 数字个数为 1 1 1 ；
    2. 数字个数大于 1 1 1 。
       

    为什么直接把其他情况都合并到2呢？因为不管多少个最后肯定都是分成两堆。所以多少个到最后最多都是合并成两个。

    第一种情况，肯定能给答案增加1的贡献1；第二种情况则需要特判当前分出来的两个队列末尾的字符，会有两种情况，第一种是有一个队列的末尾和当前数字相同，第二个情况是两个队列的末尾都不和当前数字相同2。第一种情况只能提供1的贡献，第二种情况提供2的贡献。

    实现方法很多，就不详细讲实现了（代码应该还是容易看懂的qwq）。

代码

//这题如果很难理解可以画图看看，就能明白了
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;

queue<P> que;

int main()
{
    int n;
    cin >> n;
    int cur;
    int cnt = 1;
    cin >> cur;
    for(int i = 1; i < n; i++)
    {
        int x;
        cin >> x;
        if(x != cur)
        {
            que.push(P(cur, cnt));//转化成数字cur有cnt个的形式
            cur = x;
            cnt = 1;
        }
        else
        {
            cnt++;
        }
    }
    que.push(P(cur, cnt));
    ll ans = 0;
    int flag = 0;
    int tmp;
    while(!que.empty())
    {
        P p = que.front();
        if(flag)//flag > 0标志着如果我要把现在手上这堆数字分成两半，有可能出现贡献只有1的情况
        {
            if(p.second > 1)//当前这堆个数超过1
            {
                if(p.first == tmp)
                    ans++;
                else
                    ans += 2;
                flag = 2;
                tmp = p.first;
            }
            else//为什么当前这堆个数不超过1也要判断？因为也会影响到flag的值，这就是我赛场上错的地方
            {
                if(p.first != tmp)
                {
                    flag--;
                }
                else
                {
                    flag = 2;
                }
                ans++;
            }
        }
        else
        {
            if(p.second > 1)
            {
                ans += 2;
                flag = 2;
                tmp = p.first;
            }
            else
            {
                ans += 1;
            }
        }
        que.pop();
    }
    cout << ans << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83

D2 - Painting the Array II

题意

和D1的区别仅在于，D1求最大长度，D2求最短长度。

思路

参考：Submission #107024651 - Codeforces

看了很多人的博客，做法从贪心到堆优化dp、线段树dp都有，贪心的实现很多使用的是记录下一个该数字出现的位置 next[i]，dp也比较复杂。最后在看codeforces的status的时候看到了这份代码，感觉实现的很简单、清晰，所以就参考他的代码写出了我的。

主要思路：（下面将0 1区分开后的两个数组称为两个队伍）

  1. 把所有的多个数字都合并成一个（这点应该不用我多说），使得变化后的数组中没有连续相同的数字；

  2. 从头到尾遍历，用set来记录可能是两个队伍末尾的数字。这样说可能很难理解，那么我们先分类讨论set如何变化：

    1. 如果当前数字不能在set中，则加入set；
    2. 如果当前数字在set中，清空set，将当前位置与当前位置的前一个位置的两个数组加入set。

     
    显然，set维护的其实是一连串不同的数字，通过不同的划分方案，这些数字都有可能成为两条队伍的末尾。

    遍历过程中一旦出现一个数字，它在set中已经有了对应元素，那么这两个相同的数字一定能通过一个划分方案位置相邻，完成我们缩短队伍长度的目的。

    在相邻之后，队伍末尾就确定下来了，一定是当前数字和上一个数字（可以理解为，把两个相同数字中间夹着的数字全部移动到另一个队伍里去了，那么最末尾的数字肯定是这个数的上一个数了）。

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1e6 + 19;
const ll mod = 1e9 + 7;

int a[N];
vector<int> vec;

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if(a[i] != a[i - 1])
            vec.push_back(a[i]);
    }
    if(vec.back() != a[n])
        vec.push_back(a[n]);
    set<int> st;
    ll ans = 0;
    for(int i = 0; i < vec.size(); i++)
    {
        if(st.find(vec[i]) != st.end())
        {
            st.clear();
            st.insert(vec[i]);
            st.insert(vec[i - 1]);
        }
        else
        {
            st.insert(vec[i]);
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

总结

还是心态问题+身体问题，导致继续掉分。B卡了之后没有重新思考是不是从方法上有问题，而是一意孤行认为是数据范围的问题；D1思路完全正确，却因为细节败的很惨。做题的时候就安心做题，是否放弃比赛应该在赛前想好，出错了应该冷静思考，而不是一边想着放弃一边因为掉分急得无法思考。以后的现场赛更考验心态呀！要加油了

多多包涵，共同进步

  1. 因为经过第一步的转换后，这个单独的数字一定和它前后都是不同的 ↩︎

  2. 为什么不会有都相同的情况？和这段开头的注释1一样 ↩︎

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/71364
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号