Educational Codeforces Round #148 (Rated for Div.2) A~C

A.

题意:

给定一个回文字符串,问是否可以调换其中两个字符,得到另一个不同的回文字符串。

思路:

题目的条件给的宽松,只是询问是否可以调换,并没有要求调换的位置。

方法一:统计不同的字符是否超过两个即可。超过两个那就一定可以调换。
方法二:依次遍历,只要找个两个不同的相邻字符,直接调换即可。

代码:

#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.

题意:

给定一个长度为 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.

题意:

给定一个长度为 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;
}

经验分享 程序员 微信小程序 职场和发展