Codeforces Round 918 (Div. 4)

A. Odd One Out

思路：

• 找出出现次数为1的那个数即可

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

void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;

    int ans = -1;
    if (a == b) {
        ans = c;
    } else if (a == c) {
        ans = b;
    } else if (b == c) {
        ans = a;
    }

    std::cout << ans << "\n";
}

B. Not Quite Latin Square

思路：

• 找出有?的行和列，出现次数为0的字母即可

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

void solve() {
    char g[3][3] {};
    int x = -1, y = -1;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            std::cin >> g[i][j];
            if (g[i][j] == '?') {
                x = i, y = j;
            }
        }
    }
    int A = 0, B = 0, C = 0;
    for (int i = 0; i < 3; i++) {
        if (g[x][i] == 'A') {
            A++;
        } else if (g[x][i] == 'B') {
            B++;
        } else if (g[x][i] == 'C') {
            C++;
        }
    }

    for (int i = 0; i < 3; i++) {
        if (g[i][y] == 'A') {
            A++;
        } else if (g[i][y] == 'B') {
            B++;
        } else if (g[i][y] == 'C') {
            C++;
        }
    }	
    if (A == 0) {
        std::cout << "A" << "\n";
    } else if (B == 0) {
        std::cout << 'B' << "\n";
    } else if (C == 0) {
        std::cout << 'C' << "\n";
    }
}

C. Can I Square?

思路：

• 判断这个序列的总和是否是一个完全平方数，注意爆int

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

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

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    i64 sum = std::accumulate(a.begin(), a.end(), 0ll);

    auto check = [&](i64 x) {
        return i64(sqrt(x)) * i64(sqrt(x)) == x;
    };

    if (check(sum)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

D. Unnatural Language Processing

思路：

• 模拟
• 首先预处理所有的合法音节，然后枚举s
• 首先查找长度为3的音节(注意：这个找到的音节后面一位不能是元音字母，不然不合法)，然后再找长度为2的
• 尾部有.的，将尾部多余的.删除

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

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

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

    auto isV = [&](char x) {
        if (x == 'a' || x == 'e') {
            return true;
        }
        return false;
    };

    char c[3] = {'b', 'c', 'd'};
    char v[3] = {'a', 'e'};
    std::set<std::string> st;
    for (int i = 0; i < 3; i++) {
        for (int k = 0; k < 3; k++) {
            for (int j = 0; j < 2; j++) {
                std::string t = "";
                t += c[i];
                t += v[j];
                t += c[k];
                st.insert(t);
            }
        }
    }
    st.insert("ba");st.insert("be");
    st.insert("ca");st.insert("ce");
    st.insert("da");st.insert("de");
    s += "...";
    std::string ans = "";
    for (int i = 0; i < n; i++) {
        std::string t = s.substr(i, 3);
        std::string v = s.substr(i, 2);
        if (st.count(t) && !isV(s[i + 3])) {
            ans += t;
            i += 2;
            ans += '.';
        } else if (st.count(v)) {
            ans += v;
            i += 1;
            ans += '.';
        } else {
            ans += s[i];
        }
    }
    if (ans.back() == '.') ans.pop_back();
    std::cout << ans << "\n";
}

E. Romantic Glasses

思路：

• 枚举奇数和偶数和，在这个过程中，用set哈希一下，注意（不要用unordered_set，会被卡）
• 如果出现当前奇数和等于偶数和的情况，就输出YES
• 每次枚举时，将奇数和偶数的差插入哈希表中，如果这个差值出现过，也就是这个相等的区间找到了，就输出YES
• 否则，输出NO

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

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

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

    std::set<i64> s;
    i64 even = 0, odd = 0;

    for (int i = 0; i < n; i++) {
        if (i & 1) {
            odd += a[i];
        } else {
            even += a[i];
        }

        if (even == odd || s.count(even - odd)) {
            std::cout << "YES\n";
               return ;
        }

        s.insert(even - odd);
    }

    std::cout << "NO\n";
}

F. Greetings

思路：

• 首先将起始点和终点进行映射，它们的相对位置不会发生变化
• 倒着枚举所有可能的终点，如果存在，就先获取一下当前点会经过多少个点，然后统计个数，在继续插入树状数组中，最后 \(ans=\Sigma_{i=1}^{n}num_i\)​

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

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n), b(n), v;
    v.reserve(2 * n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i] >> b[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    std::sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) { // 找到a[i]和b[i]对应序列中的位置并更新
        a[i] = std::lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        b[i] = std::lower_bound(v.begin(), v.end(), b[i]) - v.begin();
    } // 他们的相对位置不会变化

    std::vector<int> f(2 * n, -1);
    for (int i = 0; i < n; i++) {
        f[a[i]] = b[i]; // 将目的地的位置hash映射
    }
    Fenwick<int> fen(2 * n);
    i64 ans = 0;
    for (int i = 2 * n - 1; i >= 0; i--) {
        if (f[i] != -1) { // 如果这个目的的存在
            ans += fen.sum(f[i]);
            fen.add(f[i], 1);
        }
    }
    std::cout << ans << "\n";
}