Codeforces Round 806 (Div. 4)

A. YES or YES?

思路：

• 直接全部转换为小写字符或者大写字符，然后判断是否相等即可

时间复杂度：\(O(1)\)

void solve() {
    std::string s;
    std::cin >> s;

    for (char &c : s) {
        c = std::tolower(c);
    }
    std::cout << (s == "yes" ? "YES\n" : "NO\n");
}

B. ICPC Balloons

思路：

• 就把第一次出现的字符 \(+2\)，大于等于 \(2\) 次出现的字符就 \(+1\)

时间复杂度：\(O(n)\)

void solve() {
    int n;
    std::cin >> n;
    
    std::string s;
    std::cin >> s;

    int ans = 0;
    std::map<char, int> mp;
    for (char c : s) {
        mp[c]++;
        if (mp[c] == 1) {
            ans += 2;
        } else {
            ans += 1;
        }
    }
    std::cout << ans << "\n";
}

C. Cypher

思路：

• 倒着操作，当遇到 \(U\) 的时候就向上滑动，否则向下滑动，然后每次滑动都取模

时间复杂度：\(O(n \times k)\)

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        int k;
        std::cin >> k;

        std::string s;
        std::cin >> s;

        for (char c : s) {
            c == 'D' ? a[i]++ : a[i]--;
            a[i] = (a[i] + 10) % 10;
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
}

D. Double Strings

思路：

• 直接用 \(map\) 或者 \(set\) 来查询是否存在即可

时间复杂度：\(O(8 \times nlogn)\)

void solve() {
    int n;
    std::cin >> n;

    std::set<std::string> st;
    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
        st.insert(s[i]);
    }

    for (int i = 0; i < n; i++) {
        bool ok = false;
        for (int j = 0; j < s[i].size(); j++) {
            std::string a = s[i].substr(0, j);
            std::string b = s[i].substr(j);
            if (st.count(a) && st.count(b)) {
                ok = true;
                break;
            }
        }
        std::cout << ok;
    }
    std::cout << "\n";
}

E. Mirror Grid

思路：

• 枚举左上角的 \(\frac{1}{4}\) 方格，然后计算中心对称需要修改的点数

时间复杂度：\(O(\frac{n^2}{4})\)

void solve() {
    int n;
    std::cin >> n;
 
    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
    }
 
    int ans = 0;
    for (int i = 0; i < (n + 1) / 2; i++) {
        for (int j = 0; j < n / 2; j++) {
            int sum = 0;
            int A = s[i][j] - '0';
            int B = s[n - j - 1][i] - '0';
            int C = s[j][n - i - 1] - '0';
            int D = s[n - i - 1][n - j - 1] - '0';
            sum += A + B + C + D;
            ans += std::min(sum, 4 - sum);
        }
    }   
    std::cout << ans << "\n";
}

F. Yet Another Problem About Pairs Satisfying an Inequality

思路：

• 这个公式是单调的，所以我们直接边插入边二分求个数，然后累加即可

时间复杂度：\(O(nlogn)\)

void solve() {
    int n;
    std::cin >> n;
 
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
 
    i64 ans = 0;
    std::vector<int> v;
    for (int i = 0; i < n; i++) {
        if (a[i] < i + 1) {
            ans += std::lower_bound(v.begin(), v.end(), a[i]) - v.begin();
            v.push_back(i + 1);
        }
    }
    std::cout << ans << "\n";
}

G. Good Key, Bad Key

思路：

• 如果我们在第 \(i\) 个位置使用了 \(bad \space key\)，然后使用继续使用 \(good \space key\)，那么后面的可获得的密钥之和就为 \(\lfloor \frac{a_i}{2} \rfloor + \lfloor \frac{a_{i+ 1}}{2} \rfloor - k\)。
• 如果我们在第 \(i\) 个位置使用了 \(good \space key\)，然后使用继续使用 \(bad \space key\)，那么后面的可获得的密钥之和就为 \(a_i + \lfloor \frac{a_{i+ 1}}{2} \rfloor - k\)​。
• 第二种显然比第一种大，所以我们一定是先使用好的密钥，然后使用坏的密钥，这样得到的值一定最大

时间复杂度：\(O(nlogn)\)

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    i64 ans = 0, sum = 0;
    for (int i = -1; i < n; i++) {
        i64 now = sum;
        for (int j = i + 1; j < std::min(n, i + 32); j++) { // 如果后面全部使用 bad key
            int copy = a[j];
            copy >>= j - i;
            now += copy;
        }
        ans = std::max(ans, now);
        if (i + 1 != n) {
            sum += a[i + 1] - k; // 当前使用 good key
        }
    }
    std::cout << ans << "\n";
}