codeforces 706 div2题解-白红宇的个人博客

codeforces 706 div2题解

发布日期：2021-05-10 04:58:51 浏览次数：25 分类：精选文章

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

A Split it!

思路：

将字符串反转后，检查前k个字符是否与原字符串的前k个字符相等，并满足k*2+1 ≤ n的条件。

代码：

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const int maxn = 200005;
const int base = 131;
int main() {
    // 读取输入
    int t, n, k;
    string s, s1;
    while (--t >= 0) {
        cin >> n >> k >> s;
        s1 = s;
        reverse(s.begin(), s.end());
        
        int cnt = 0;
        bool flag = false;
        for (int i = 0; i < n; ++i) {
            if (s[i] != s1[i]) {
                if (cnt >= k) flag = true; break;
            }
            ++cnt;
            if (cnt >= k) {
                flag = true; break;
            }
        }
        if (k == 0 || (flag && (k*2+1 <= n))) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

B Max and Mex

思路：

如果b不在序列中且序列不是连续的，则mex < max，b的最小值为 (mex + mex + 1 + 1)/2。如果b不在序列中且序列是连续的，则mex > max，b的最小值为 (max + max + 1 + 1)/2。

代码：

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const int maxn = 200005;
const int base = 131;
int main() {
    int t, n, k;
    string s, s1;
    while (--t >= 0) {
        cin >> n >> k;
        set
      
        vis;
        vector
       
         a(n);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            vis.insert(a[i]);
        }
        sort(a.begin(), a.end());
        int bb = a.back();
        int cnt = 0;
        bool found = false;
        for (int i = 1; i <= n; ++i) {
            if (a[i] == bb) {
                ++cnt;
                if (cnt > 1) break;
            } else {
                ++cnt;
                if (cnt > 1) break;
            }
        }
        if (k == 0) {
            cout << vis.size() << endl;
            continue;
        }
        if (found) {
            int b = (a[i-1] + a[i] + 1 + 1) / 2;
            cout << b << endl;
        } else {
            int b = (a[i-1] + a[i] + 1 + 1) / 2;
            cout << b << endl;
        }
    }
    return 0;
}

C Diamond Miner

思路：

将所有点映射到第一象限，计算每个点与其对应点的最小距离。

代码：

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const int maxn = 200005;
const int base = 131;
int main() {
    int t, n, k;
    while (--t >= 0) {
        cin >> n;
        vector
      
        x(n), y(n);
        for (int i = 0; i < n; ++i) {
            cin >> x[i] >> y[i];
        }
        vector
       
         a(n), b(n);
        for (int i = 0; i < n; ++i) {
            if (x[i] == 0) {
                a[i] = y[i] > 0 ? y[i] : -y[i];
            } else {
                a[i] = x[i] > 0 ? x[i] : -x[i];
            }
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        double ans = 0.0;
        for (int i = 0; i < n; ++i) {
            ans += sqrt(a[i] * a[i] + b[i] * b[i]);
        }
        cout << fixed << setprecision(15) << ans << endl;
    }
    return 0;
}

D Let's Go Hiking

思路：

找到最长单调递增或递减子序列的长度。如果长度为奇数，先手方必输；如果长度为偶数，后手方必输。

代码：

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const int maxn = 200005;
const int base = 131;
int main() {
    int n;
    cin >> n;
    vector
      
        p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    vector
       
         l(n), r(n);
    l[0] = 1;
    r[n-1] = 1;
    for (int i = 1; i < n; ++i) {
        l[i] = (p[i] > p[i-1]) ? l[i-1] + 1 : 1;
    }
    for (int i = n-2; i >= 0; --i) {
        r[i] = (p[i] > p[i+1]) ? r[i+1] + 1 : 1;
    }
    int max_len = 0, start = 0;
    for (int i = 0; i < n; ++i) {
        if (l[i] > max_len || r[i] > max_len) {
            max_len = max(l[i], r[i]);
            start = i;
        } else if (l[i] == max_len || r[i] == max_len) {
            max_len = 0;
        }
    }
    int mx = (l[start] > r[start]) ? l[start] : r[start];
    int mi = (l[start] > r[start]) ? r[start] : l[start];
    int ans = (mx % 2) ? 1 : 0;
    cout << ans << endl;
}

E Garden of the Sun

思路：

每三行清空中间一行，保持其他行的连通性。

代码：

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const int maxn = 60005;
const int base = 131;
int main() {
    int t, n, m;
    while (--t >= 0) {
        cin >> n >> m;
        vector
      
        g(n);
        for (int i = 0; i < n; ++i) {
            g[i].clear();
            cin >> g[i];
        }
        for (int i = (n % 3 == 0) ? 1 : 0; i < n; i += 3) {
            for (int j = 0; j < m; ++j) {
                g[i][j] = 'X';
            }
            if (i > 0 && (m == 1 || (g[i-1][1] != 'X' || g[i-2][1] != 'X'))) {
                g[i-1][1] = 'X';
                g[i-2][1] = 'X';
            }
        }
        for (int i = 0; i < n; ++i) {
            cout << g[i] << endl;
        }
    }
}

上一篇：2016ACM ECfinal补题题解

下一篇：最短路

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！