您现在的位置是:首页 >其他 >Educational Codeforces Round #148 (Rated for Div.2) A~C网站首页其他
Educational Codeforces Round #148 (Rated for Div.2) A~C
A. New Palindrome
题意:
给定一个回文字符串,问是否可以调换其中两个字符,得到另一个不同的回文字符串。
思路:
题目的条件给的宽松,只是询问是否可以调换,并没有要求调换的位置。
方法一:统计不同的字符是否超过两个即可。超过两个那就一定可以调换。
方法二:依次遍历,只要找个两个不同的相邻字符,直接调换即可。
代码:
#include <bits/stdc++.h>
#define ll long long
#define endl '
'
using namespace std;
const int N = 2e5 + 10;
void solve()
{
string s;
cin >> s;
int n = s.size();
//给出的字符串已经是回文串了
for (int i = 1; i < n / 2; i++){
if (s[i] != s[i - 1]){
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
int main()
{
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
B. Maximum Sum
题意:
给定一个长度为 n n n 的数组,可以进行 k k k 次操作。
有两种操作:
- 操作一:删除数组中的两个最小元素
- 操作二:删除数组中的最大元素
求所得数组的最大元素之和。
思路:
先排序预处理出前缀和。
如果我们直接模拟,每次选择两种操作中最大的值,那么会发现样例 5 5 5 成功 w a wa wa 掉了。。。
换个思路
我们先处理出只执行操作一得到的最后结果,也就是每次操作都删掉最大数,只保留两个最小数的情况,
然后枚举 k k k 次,从只保留两个最小数一直枚举到只保留最大数,每次都删掉两个最小数,加入最大数,比较大小,最后的答案一定能在这之间找到。
代码:
#include <bits/stdc++.h>
#define ll long long
#define endl '
'
using namespace std;
const int N = 2e5 + 10;
int n, k;
int a[N];
ll s[N];
void solve()
{
cin >> n >> k;
ll sum = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
ll ans = 0;
for (int i = 0; i <= k; i++)
{
ll now = s[n - (k - i)] - s[2 * i];
ans = max(ans, now);
}
cout << ans << endl;
}
int main()
{
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
C. Contrast Value
题意:
给定一个长度为 n n n 的数组 a a a ,规定该数组的对比度为 ∣ a 1 − a 2 ∣ + ∣ a 2 − a 3 ∣ + ⋯ + ∣ a n − 1 − a n ∣ |a_1-a_2|+|a_2-a_3|+⋯+|a_{n-1}-a_n| ∣a1−a2∣+∣a2−a3∣+⋯+∣an−1−an∣ .
现在要求构造一个数组 b b b ,满足 b b b 不为空是 a a a 的子序列,且 b b b 的对比度等于 a a a 的对比度,求 b b b 的最小长度。
思路:
仔细观察会发现,如果是一个单调递增或递减的序列,那么它的对比度就等于最大值减最小值。
所以我们只需要找到 a a a 数组单调性改变的点并加入到 b b b 数组中就可以了,也就是说,我们要构造的 b b b 数组的长度,就是 a a a 数组中极值点的个数。
另外还要注意边界的情况,初始化 ans = 1
,表示先加入第一个点,然后开始判断单调性即可。
代码:
#include <bits/stdc++.h>
#define ll long long
#define endl '
'
using namespace std;
const int N = 3e5 + 10;
int n;
int a[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
int ans = 1;
int f = -1;
for (int i = 2; i <= n; i++)
{
if (f != 1 && a[i - 1] < a[i]){ // f=1代表单调递增
ans++;
f = 1;
continue;
}
if (f != 0 && a[i - 1] > a[i]){ // f=0代表单调递减
ans++;
f = 0;
continue;
}
}
cout << ans << endl;
}
int main()
{
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}