Codeforces Round 984 (Div. 3)

题目链接

A. Quintomania

题意

思路

模拟即可

示例代码

void solve() {
    int n;
    cin >> n;
    vector<int>arr(n);
    fer(i, 0 ,n) cin >> arr[i];

    fer(i, 1, n){
        if(abs(arr[i] - arr[i - 1]) != 5 && abs(arr[i] - arr[i - 1]) != 7)
        {
            cout << "NO" << '\n';
            return;
        }
    }
    cout << "YES" << '\n';
}

B. Startup

题意

输入

输出

思路

哈希表（数组哈希或者map)，需要注意计算ans时的边界（计算多少个）

示例代码

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

    int *arr = new int[max(n, k) + 2]{};
    fer(i, 0, k){
        int b, c;
        cin >> b >> c;
        arr[b] += c;
    }
    sort(arr, arr + max(n, k) + 2, [&](int a, int b){return a > b;});
    
    int ans = 0;
    fer(i, 0, n) ans += arr[i];
    cout << ans << '\n';
}

void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int>mp;

    fer(i, 0, k){
        int b, c;
        cin >> b >> c;
        mp[b] += c;
    }
    vector<pii>arr(all(mp));
    sort(all(arr), [&](pii a, pii b){return a.second > b.second;});

    int ans = 0;
    fer(i, 0, min((int)arr.size(), n))
        ans += arr[i].second;
    cout << ans << '\n';
}

C. Anya and 1100

题意

输入

输出

思路

先预处理包含的1100的个数，然后计算在改变位置改变后对改变前的影响（可以分别计算在改变位置处1100的个数，计算差值），注意遍历的边界范围

示例代码

void solve() {
    string s;
    cin >> s;
    int q;
    cin >> q;
    int cnt = 0;

    fer(i, 0, s.size() - 3){
        if(s.substr(i, 4) == "1100") cnt++;
    }
    while(q--){
        int ind, v;
        cin >> ind >> v;
        ind--;

        int cnt1 = 0, cnt2 = 0;
        // 改变前
        fer(i, max(0, ind - 3), min((int)s.size() - 3, ind + 1)){
            if(s.substr(i, 4) == "1100") cnt1++;
        }
        // 改变后
        s[ind] = char(v + '0');
        fer(i, max(0, ind - 3), min((int)s.size() - 3, ind + 1)){
            if(s.substr(i, 4) == "1100") cnt2++;
        }
        cnt += cnt2 - cnt1;
        if(cnt >= 1) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}

D. I Love 1543

题意

输入

输出

样例输入及输出

思路

与蛇形填数思路一致，用偏移量法求取每一个外围的字符串，统计这个字符串在循环移位后包含1543子串的最大个数，加到res中输出。注意边界的判断。

示例代码

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int finds(string s){
    int cnt = 0;
    fer(i, 0, s.size() - 3){
        if(s.substr(i, 4) == "1543")
            cnt++;
    }
    return cnt;
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>>arr(n, vector<int>(m));
    fer(i, 0, n){
        string s;
        cin >> s;
        fer(j, 0, s.size())
            arr[i][j] = (int)(s[j] - '0');
    }
    int c = 0;
    int res = 0;
    int nn = n, mm = m;
    while(n && m){
        string s;
        int x = c, y = c, d = 0;
        fer(i, 0, 2 * (n + m - 2)){
            s += to_string(arr[x][y]);
            int a = x + dx[d], b = y + dy[d];
            if(a < c || a >= nn - c || b < c || b >= mm - c){
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        n -= 2, m -= 2;
        c ++;
        string s1 = s.substr(1) + s[0];
        string s2 = s1.substr(1) + s1[0];
        string s3 = s2.substr(1) + s2[0];

        res += max(finds(s), max(finds(s1), max(finds(s2), finds(s3))));
    }
    cout << res << '\n';
}