Codeforces Round 799 (Div. 4)

A Marathon

void solve() {
    vector<int> a(4);
    int goal;
    cin >> goal;
    int ans = 0;
    for(int i = 0; i < 3; i++) {
        int x;
        cin >> x;
        if(goal < x)ans++;
    }
    cout << ans << endl;
}

B All Distinct

void solve() {
    map<int, int> mp;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[x]++;
    }
    int ans = 0;
    for(auto [x, y] : mp) {
        if(y % 2 == 0)ans++;
    }
    cout << mp.size() - (ans % 2) << endl;
}
 

C Where's the Bishop?

题意：判断这个位置是#字符时i，它的四个角是不是也是#，保证有解

思路：直接暴力每个位置判断一下即可

char g[N][N];
 
void solve() {
    for(int i = 0; i < 8; i++)cin >> g[i];
    for(int i = 1; i < 7; i++) {
        for(int j = 1; j < 7; j++) {
            if(g[i][j] == '#' && g[i - 1][j - 1] == '#' && g[i - 1][j + 1] == '#' && g[i + 1][j - 1] == '#' && g[i + 1][j + 1] == '#') {
                cout << i + 1 << ' ' << j + 1 << endl;
                return ;
            }
        }
    }
}

D The Clock

题意：给你一个起始时间，再给你一个k，让你每次都加k分钟，看看每次加了以后的时间的字符串是不是一个回文串，区间为\(0\dots1440\)的一个环，不段加，直到遇见已经遇到过的时间就停止

思路：按照题目模拟，用set去存遇到过的时间，每次判断一下即可

bool huiwen(int x) {
    int h = x / 60;
    int m = x % 60;
    string s1 = to_string (h);
    if(s1.size() == 1)s1 = '0' + s1;
    string s2 = to_string(m);
    if(s2.size() == 1)s2 = '0' + s2;
    reverse(ALL(s1));
    if(s1 == s2) {
        // cout << s1 << ' ' << s2 << endl;
        return true;
    }
    return false;
}
 
void solve() {
    string s;
    cin >> s;
    int h = (s[0] - '0') * 10 + (s[1] - '0');
    int m = (s[3] - '0') * 10 + (s[4] - '0');
    // cout << h << ' ' << m << endl;
    int x;
    cin >> x;
    int star = h * 60 + m;
    int ans = 0;
    int pos = star;
    set<int> st;
    for(int i = star; ; i += x, pos += x) {
        if(i >= 1440)i %= 1440;
        if(st.count(i))break;
        st.insert(i);
        if(huiwen(i))ans++;
 
    }
    // for(int i = pos % 1440; i < star ; i += x) {
    //     if(huiwen(i))ans++;
    // }
    cout << ans << endl;
    // cout << pos << endl << endl;
}

E Binary Deque

题意：求最长的一段区间和为题目给定的值

思路：直接使用双指针和前缀和即可，每次都更新答案，好像也可以去二分答案，\(O(N)\)去check

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n + 1, 0);
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        a[i] += a[i - 1];
    }
    int ans = INT_MAX;
    for(int i = 1, j = 1; i <= n; i++) {
        while(a[i] - a[j - 1] > x)j++;
        if(a[i] - a[j - 1] == x)ans = min(ans, n - (i - j + 1));
    }
    if(ans == INT_MAX)cout << -1 << endl;
    el

F 3SUM

题意：问你所给的书里面，是否能找到三个数之和的各位是3

思路：这个题直接枚举三个数太大，并且\(n^2\)的枚举前两个数去二分第三个数也不行，所以我们你可以预先把出现过的数的个位存到map里面，如何用三个\(for\)循环判断哪些数的和个位数为3，如何再到相应的map里找所需要的数够不够即可

void solve() {
    int n;
    cin >> n;
    map<int, int> mp;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[x % 10]++;
    }
    // for(auto [x, y] : mp)cout << x << ' ' << y << endl;
    bool ok = false;
    for(int i = 0; i <= 9; i++) {
        for(int j = 0; j <= 9; j++) {
            for(int k = 0; k <= 9; k++) {
                if((i + j + k) % 10 == 3) {
                    if(i == j && j == k && mp[i] >= 3)ok = true;
                    else if(i == j && j != k && mp[i] >= 2 && mp[k] >= 1)ok = true;
                    else if(i == k && k != j && mp[i] >= 2 && mp[j] >= 1)ok = true;
                    else if(k == j && i != k && mp[j] >= 2 && mp[i] >= 1)ok = true;
                    else if(i != j && j != k&&i!=k && mp[j] >= 1 && mp[k] >= 1 && mp[i] >= 1)ok = true;
                    if(ok) {
                    	// cout << mp[i] << ' ' <<LL mp[j] << ' ' << mp[k] << endl;
                        // cout << i << ' ' << j << ' ' << k << endl;
                        cout << "YES" << endl;
                        return ;
                    }
                }
            }
        }
    }
    cout << "NO" << endl;
}

G 2^Sort

题意：给一个数组，问在这个数组里能不能找到连续的\(k+1\)数，更正式地说，计算有多少个索引 \(1 \leq i \leq n - k\)，使得\(2^0 \cdot a_i < 2^1 \cdot a_{i+1} < 2^2 \cdot a_{i+2} < \dots < 2^k \cdot a_{i+k}.\)

思路：题意起始也就是求连续的区间满足后\(a[i]\) \(\times\) \(2\) \(\le\) \(a[i-1]\)，如何这些满足条件的连续区间能够构成多少题目要求的子区间

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), vis(n, false);
    for(auto &i : a)cin >> i;
    int cnt = 1;
    int ans = 0;
    for(int i = 1; i < n; i++) {
        if(a[i] * 2 > a[i - 1]) {
            cnt++;
        } else {
            // cout << cnt << endl;
            if(cnt >= k)ans += (cnt - k - 1) + 1;
            cnt = 1;
        }
    }
    // cout << cnt << endl;
    if(cnt > k)ans += (cnt - k - 1) + 1;
    cout << ans << endl;
}