codeforces 806 div 4 (D~G) 题解

D. Double Strings （暴力枚举）

题意：有1~n个字符串，输出s[ i ]是否可以用2个子串拼接而成，是输出1，否则0

题解：注意到字符串长度不超过8，可以用set存每个字符串，再枚举一下每个字符串是否可以拆成set中的字符串

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
string s[100010];
void solve()
{
    int n;
    cin >> n;

    set x;
    string ans;
    for (int i = 0; i < n; i ++) {
        cin >> s[i];
        x.insert(s[i]);
    }

    for (int i = 0; i < n; i ++) {
        int ok = 0;
        for (int j = 0; j < s[i].size(); j ++) {
            string a = s[i].substr(0, j), b = s[i].substr(j);
            if (x.count(a) && x.count(b)) { 
                ok = 1;
            }
        }
        ans.push_back(ok + '0');
    }
    cout << ans << "n";
}       
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;

    while (t --) {
        solve();    
    }
    return 0;
}

E. Mirror Grid

题意：给一个n * n 只有0 或 1组成的单元格，给定操作：翻转0或1。输出最少操作次数使得每个单元格每次翻转0°, 90°, 180° 和 270°后仍不变.

题解：下标从0开始，对于(x, y) 翻转后的坐标为(y, n - x - 1)只需枚举每一个单元格翻转4次后累加0或1翻转的最小次数

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
string s[100010];
void solve()
{
    int n;
    cin >> n;

    char s[110][110];
    for (int i = 0; i < n; i ++) {
        cin >> s[i];
    }

    int ans = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            int x = i, y = j, cnt = 0;
            for (int k = 0; k < 4; k ++) {
                cnt += s[x][y] == '0';
                int ox = x, oy = y;
                x = oy;
                y = n - ox - 1;
            }
            if (cnt == 0 || cnt == 4) continue;
            char w;
            ans += min(cnt, 4 - cnt);
        }
    }
    cout << ans / 4 << "n";
}       
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;

    while (t --) {
        solve();    
    }
    return 0;
}

F. Yet Another Problem About Pairs Satisfying an Inequality (前缀和）

题意：给定一个数组，输出满足 ( 1 ≤ i , j ≤ n ) 存在 ai < i < aj < j 的数目 .

题解：开一个前缀和数组存储 ai < i ，再枚举一下满足 aj < j 的数目

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
string s[100010];
void solve()
{
    int n;
    cin >> n;

    ll ans = 0;
    std::vector s(n + 1);
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        s[i] = s[i - 1] + (x < i);
        if (x < i && x >= 1) {
            ans += s[x - 1];
        }
    }
    cout << ans << "n";
}       
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;

    while (t --) {
        solve();    
    }
    return 0;
}

G. Good Key, Bad Key (贪心)

题意：有两种钥匙，一把好钥匙：需要花费 k 个金币，坏钥匙：不需要金币，但会让当前和后面的宝箱金币数量减半，可以负债，求获得最大的金币数量

题解：前 x 个全部用好钥匙sum1 = a[ i ] - x * k，(x + 1) ~ n 全部用坏钥匙 sum2 = a[ i ] / 2 。a[ i ] <= 1e9, 最多用坏钥匙32次后宝箱金币全部为0

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll a[100010], m[40] = {1}, s[100010];
void solve()
{
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    ll ans = 0, ANS = -1;
    for (int x = 0; x <= n; x ++) {
        ans = s[x] - k * 1ll * x;
        for (int i = x + 1; i <= min(x + 32, n); i ++) {
            ans += a[i] >> (i - x);
        }
        ANS = max(ANS, ans);
    }
    cout << ANS << "n";
}       
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;

    while (t --) {
        solve();    
    }
    return 0;
}

codeforces 806 div 4 (D~G) 题解

C/C++/C#相关栏目本月热门文章