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必须满足以下一种条件 :
-
s长度 = 1时,若由字符 ‘c’ 构成,则称为 ‘c’-good string
-
s的长度 > 1时,字符串的前半部分仅包含字符c,而字符串的后半部分是 ‘(c + 1)’-good string (c+1表示字符c的下一位)
-
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
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
A. Add Odd or Subtract Even(思维题) Codeforces Round #624 (Div. 3)
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
Codeforces Round #656 (Div. 3) (C、D题)
-
Codeforces Round #656 (Div. 3) A. Three Pairwise Maximums
-
Codeforces Round #661 (Div. 3) C.Boats CompetitionCompetition
-
Codeforces Round #657 (Div. 2) C题
-
Codeforces Round #277.5 (Div. 2)(C题)_html/css_WEB-ITnose
-
Codeforces Round #483 (Div. 2) (A+B+C+D)