• Published:

A — Intersection

The problem gives two painted intervals with endpoints L1, R1 and L2, R2. The goal is to find the length of the region painted with both colors.

Since the constraints are small, a direct simulation is enough. Mark every integer position covered by the first interval, then do the same for the second interval. A position whose coverage count becomes 2 belongs to the intersection. The number of unit segments in that intersection is the number of doubly covered integer points minus one. If there is no such point, the answer is 0.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int res[N];

int main(){

    int a, b, c, d;

    cin >> a >> b >> c >> d;

    for(int i = a; i <= b; i ++) res[i]++;

    for(int i = c; i <= d; i ++) res[i]++;

    int cnt = 0;
    for(int i = 0; i <= 200; i ++) if(res[i] == 2) cnt++;

    if(cnt) cout << cnt - 1 << endl;
    else cout << 0 << endl;

    return 0;

}

B — Tournament Result

An N x N table records the results between players. For each pair (i, j), the entry says whether player i won, lost, or drew against player j. The table is valid only if every pair of symmetric entries agrees.

Check each row i, and for each column j greater than i, compare A[i][j] with A[j][i]. A draw must be mirrored by a draw, a win must be mirrored by a loss, and a loss must be mirrored by a win. If any pair conflicts, mark the table as incorrect and stop.

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

char mp[N][N];

int n;

int main(){

    cin >> n;

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j++) cin >> mp[i][j];
    }

    bool flag = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = i + 1; j <= n; j ++){
            if(mp[i][j] == 'D' && mp[j][i] != 'D'){
                flag = 0;
                break;
            }
            else if(mp[i][j] == 'W' && mp[j][i] != 'L'){
                flag = 0;
                break;
            }
            else if(mp[i][j] == 'L' && mp[j][i] != 'W'){
                flag = 0;
                break;
            }
        }
        if(!flag) break;
    }

    if(flag) cout << "correct" << endl;
    else cout << "incorrect" << endl;

    return 0;

}

C — NewFolder(1)

Given N strings in order, process each string as follows. If it has not appeared before, output it unchanged. If it has already appeared u times, output the string followed by (u-1) in parentheses. In other words, the first occurrence is plain, the second gets (1), the third gets (2), and so on.

Store the input order in an array, and use a map to count occurrences. For each string, increment its count. Let t be the number of previous occurrences. If t is zero, print the string directly; otherwise print the string with (t) appended.

#include <bits/stdc++.h>
using namespace std;

map<string,int> a;

int n;

const int N = 1e6 + 3;

string s[N];

int main(){

    cin >> n;

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

    for(int i = 0; i < n; i ++){

        a[s[i]]++;
        int t = a[s[i]] - 1;
        if(t != 0){
            cout << s[i] << '(' << t << ')' << endl;
        }
        else cout << s[i] << endl;

    }

    return 0;

}

D — Flipping and Bonus

There are N coin tosses. If the result is heads, the counter increases by one and the player earns X_i; if it is tails, the counter resets to zero. In addition, there are M bonus rules: when the counter reaches C_i, the player receives Y_i. The task is to maximize the total money earned.

Use dynamic programming. Let dp[i][j] be the maximum money after the first i tosses when the current counter value is j. If toss i is heads, the previous counter value must have been j - 1, so dp[i][j] = dp[i - 1][j - 1] + a[i] + b[j]. If toss i is tails, the counter becomes zero, and the new state is the best value among all previous counter values: dp[i][0] = max(dp[i][0], dp[i - 1][j]).

The bonus for a counter value is stored in b, and long long is needed for the totals.

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n,m;

const LL N = 5010;

LL dp[N][N];

LL a[N];
LL b[N];

int main(){

    cin >> n >> m;

    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 0; i < m; i ++){
        int x, y;
        cin >> x >> y;
        b[x] = y;
    }

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= i; j ++){
            dp[i][j] = dp[i - 1][j - 1] + a[i] + b[j];
        }

        for(int j = 0; j < i; j ++){
            dp[i][0] = max(dp[i][0],dp[i - 1][j]);
        }

    }

    LL ans = 0;

    for(int i = 0; i <= n; i ++) ans = max(ans,dp[n][i]);

    cout << ans << endl;

    return 0;

}

Related Posts