Codeforces Round #498 (Div. 3) （A+B+C+D+E+F）-白红宇

Codeforces Round #498 (Div. 3) （A+B+C+D+E+F）

阅读量：805 次

发布时间：2019-03-25

本文共 3387 字，大约阅读时间需要 11 分钟。

以下是一些经过优化的代码和解决方案：

A题：

题意： 对一个数组进行操作后，奇数不会变，偶数都会减1，求操作后的数组是多少？思路：

遍历数组中的每个元素。

如果是奇数，不变化。

如果是偶数，减1。优化：代码优化后的版本如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    int n;    vector
      
        a;    scanf("%d", &n);    for (int i = 1; i <= n; ++i) {        int t;        scanf("%d", &t);        if (t % 2 == 0)            a.push_back(t - 1);        else            a.push_back(t);    }    for (int num : a) {        cout << num << " ";    }    return 0;}

B题：

题意： 将一个数组分成k段，求每段的区间最大值的总贡献值的最大值？思路：

找出数组中前k大的元素。

将这些元素按顺序排列，形成前缀最大值序列。

计算各段的贡献值。优化：代码优化后的版本如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct node {    int index, value;    friend bool operator < (const node& a, const node& b) {        if (a.value != b.value)            return a.value > b.value;        else            return a.index > b.index;    }};int main() {    int n, k;    vector
      
        a;    do {        int t;        scanf("%d", &t);        a.push_back({ t, t });    } while (scanf("%d", &t) && t != EOF);    sort(a.begin(), a.end());    vector
       
         sum;    for (int i = k - 1; i >= 0; --i) {        int current = 0;        for (int j = i; j >= 0; --j) {            current = max(current, a[j].value - (i != j ? a[j].index - i - 1 : 0));        }        sum.push_back(current);    }    for (int s : sum)        cout << s << " ";    return 0;}

C题：

题意： 将一个数组分成3段，满足左段和右段的和相等，求最大的左段和？思路：

使用双指针p1和p2，分别指向数组的开头和结尾。

计算左段和右段的和。

如果左段和等于右段和，记录最大的和，并尝试扩展p1和p2。

否则，根据左右哪边和更大，尝试扩展相应的指针。优化：代码优化后的版本如下：

#include 
   
    #include 
    
     using namespace std;int main() {    int n;    vector
     
       a;    do {        int t;        scanf("%d", &t);        a.push_back(t);    } while (scanf("%d", &t) && t != EOF);    int p1 = 0, p2 = n - 1;    long long left = 0, right = 0;    int max_val = 0;    while (p1 <= p2) {        if (left > right) {            p1++;            left += a[p1];        } else {            p2--;            right += a[p2];        }        if (left == right) {            if (left > max_val) {                max_val = left;            }        }    }    cout << max_val << endl;    return 0;}

D题：

题意： 给定两个字符串，通过交换操作使两个字符串相同，求最少预处理次数？思路：

分两种情况讨论：

b[i] == b[n-i+1]：比较a[i]和a[n-i+1]。

b[i] != b[n-i+1]：分别比较a[i]和a[n-i+1]。优化：代码优化后的版本如下：

#include 
   
    #include 
    
     using namespace std;int main() {    int len;    string s1, s2;    do {        scanf("%d", &len);        s1 += ' ';        s2 += ' ';        do {            char c;            scanf("%c", &c);            s1 += c;            s2 += c;        } while (t}        #include 
     
      #include 
      
       #include 
       
        using namespace std;int main() {    int n, k;    vector
        
          a; do { int t; scanf("%d", &t); a.push_back(t); } while (scanf("%d", &t) && t != EOF); sort(a.begin(), a.end()); vector
         
           sum; for (int i = k - 1; i >= 0; --i) { int current = 0; for (int j = i; j >= 0; --j) { current = max(current, a[j].value - (i != j ? a[j].index - i - 1 : 0)); } sum.push_back(current); } for (int s : sum) cout << s << " "; return 0;}