欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Codeforces Round #656 (Div. 3) (C、D题)

程序员文章站 2022-07-06 13:39:44
C. Make It Good题意 :(多组输入)给定 长度为 n 的 数组a,可以将其前x个元素删除(从头删起),得到一个新数组b然后每次都选择拿新数组b的 首或尾 一个元素 放入新数组c必须满足 数组c是非递减数组问题 :求x的最小值(最少删除的元素个数)思路 :b数组 只要保证从一个元素开始 向两边单调递减(在这定义为 峰 )又因为 a数组 的删除是从头开始的我们只需要从尾开始跑 a数组 找到 最长的峰的左边界 pos(此处 峰的右边界必须是n)pos 之前的元素都是要删除...

C. Make It Good

题意 :
(多组输入)
给定 长度为 n数组a,可以将其前x个元素删除(从头删起),得到一个新数组b
然后每次都选择拿新数组b首或尾 一个元素 放入新数组c
必须满足 数组c非递减数组

问题 :
x的最小值(最少删除的元素个数)

思路 :
b数组 只要保证从一个元素开始 向两边单调递减(在这定义为 )
又因为 a数组 的删除是从头开始的
我们只需要从尾开始跑 a数组 找到 最长的峰的左边界 pos
(此处 峰的右边界必须是n)
pos 之前的元素都是要删除的元素,因此 pos = x

AC代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#define ll long long
#define pb push_back
const int MAX = 2e5 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
int a[MAX];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t, n;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        int pos = n - 1, mx = 0;
        while (pos && a[pos] >= a[pos + 1])
            pos--;
        while (pos && a[pos] >= a[pos - 1])
            pos--;
        cout << pos << endl;
    }
    return 0;
}

D. a-Good String

题意 :
给定一个 n(n = 2^k) 和 一个字符串 s (长度为 n)
通过将替换s中的元素让其变成 ‘a’-good string
good string必须满足以下一种条件 :

  1. s长度 = 1时,若由字符 ‘c’ 构成,则称为 ‘c’-good string

  2. s的长度 > 1时,字符串的前半部分仅包含字符c,而字符串的后半部分‘(c + 1)’-good string (c+1表示字符c的下一位)

  3. s的长度 > 1时,字符串的后半部分仅包含字符c,而字符串的前半部分‘(c + 1)’-good string

问题 :
最少的替换次数

思路 :
从 字符a 开始,一直到字符 (a + k)
每次都有两种决定,前或后 放 该字符
将每次得到的字符串s比较 保存替换次数

AC代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#define ll long long
#define pb push_back
const int MAX = 2e5 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
int a[MAX];
string s;
int dfs(string s, char c, int st)
{
//s为剩余字符串, c为目前字符,  st为选择前或后
    int ans = 0;
    if (s.size() == 1)
        return s[0] != c;
    if (st == 0)//选择前半部分
    {
        string p(s.begin() + s.size() / 2, s.end());
        for (int i = 0; i < s.size() / 2; i++)
            if (s[i] != c)
                ans++;
        return ans + min(dfs(p, c + 1, 0), dfs(p, c + 1, 1));
    }
    else//选择后半部分
    {
        string p(s.begin(), s.begin() + s.size() / 2);
        for (int i = s.size() / 2; i < s.size(); i++)
            if (s[i] != c)
                ans++;
        return ans + min(dfs(p, c + 1, 0), dfs(p, c + 1, 1));
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t, n;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        cin >> s;
        cout << min(dfs(s, 'a', 0), dfs(s, 'a', 1)) << endl;
    }
    return 0;
}

本文地址:https://blog.csdn.net/qq_14904619/article/details/107442356