cf2022年5月14日div4

A：A. Lucky?

A ticket is a string consisting of six digits. A ticket is considered lucky if the sum of the first three digits is equal to the sum of the last three digits. Given a ticket, output if it is lucky or not. Note that a ticket can have leading zeroes.

纯模拟计算

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans=0;
inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    string s;
    cin>>s;
    int x=0,y=0;
    x=s[0]+s[1]+s[2]-'0'-'0'-'0';
    y=s[3]+s[4]+s[5]-'0'-'0'-'0';
    if(x==y){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B. Equal Candies

There are n boxes with different quantities of candies in each of them. The i-th box has ai candies inside.You also have n

friends that you want to give the candies to, so you decided to give each friend a box of candies. But, you don't want any friends to get upset so you decided to eat some (possibly none) candies from each box so that all boxes have the same quantity of candies in them. Note that you may eat a different number of candies from different boxes and you cannot add candies to any of the boxes.

What's the minimum total number of candies you have to eat to satisfy the requirements?

分糖果，最后让每个box的个数相同，就是都是最小嘛，求和减去最终

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans=0;
inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n;
    cin>>n;
    ll sum=0;
    ll mins=0x3f3f3f3f;
    for(int i = 0;i<n;i++){
        ll x;
        cin>>x;
        sum+=x;
        mins=min(mins,x);
    }
    cout<<sum-n*mins<<endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C：C. Most Similar Words

You are given n words of equal length m, consisting of lowercase Latin alphabet letters. The i-th word is denoted si.

In one move you can choose any position in any single word and change the letter at that position to the previous or next letter in alphabetical order. For example:

you can change 'e' to 'd' or to 'f';
'a' can only be changed to 'b';
'z' can only be changed to 'y'. 

The difference between two words is the minimum number of moves required to make them equal. For example, the difference between "best" and "cost" is 1+10+0+0=11.

Find the minimum difference of si and sj such that (i<j). In other words, find the minimum difference over all possible pairs of the n words.

啥意思呢吗，就是有n个字符串，然后距离呢就是所有字母的差值，找个最小差值，数据量n<50，直接双for

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans=0;
inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n,m;
    cin>>n>>m;
    vector<string> s(n);
    for(int i =0;i<n;i++){
        cin>>s[i];
    }
    int ans=0x3f3f3f3f;
    for(int i =0 ; i<n-1;i++){
        for(int j =i+1;j<n;j++){
            int cnt=0;
            for(int k = 0;k<m;k++){
                cnt+=abs(s[i][k]-s[j][k]);
            }
            ans=min(ans,cnt);
        }
    }
    cout<<ans<<endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D. X-Sum

Timur's grandfather gifted him a chessboard to practice his chess skills. This chessboard is a grid a with n rows and m columns with each cell having a non-negative integer written on it.

Timur's challenge is to place a bishop on the board such that the sum of all cells attacked by the bishop is maximal. The bishop attacks in all directions diagonally, and there is no limit to the distance which the bishop can attack. Note that the cell on which the bishop is placed is also considered attacked. Help him find the maximal sum he can get.

N皇后？不带对角线，找个最大值。就扫每个格子的两条对角线的值就OK，找个最大

梦醒战士，困

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans = 0;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int cnt = grid[i][j];
            int x = i - 1, y = j - 1;
            while (x >= 0 && y >= 0) {
                cnt += grid[x--][y--];
            }
            x = i - 1;
            y = j + 1;
            while (x >= 0 && y < m) {
                cnt += grid[x--][y++];
            }
            x = i + 1;
            y = j + 1;
            while (x < n && y < m) {
                cnt += grid[x++][y++];
            }
            x = i + 1;
            y = j - 1;
            while (x < n && y >= 0) {
                cnt += grid[x++][y--];
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E. Eating Queries

Timur has n candies. The i-th candy has a quantity of sugar equal to ai. So, by eating the i-th candy, Timur consumes a quantity of sugar equal to ai.

Timur will ask you q queries regarding his candies. For the j-th query you have to answer what is the minimum number of candies he needs to eat in order to reach a quantity of sugar greater than or equal toxj or print -1 if it's not possible to obtain such a quantity. In other words, you should print the minimum possible k such that after eating k candies, Timur consumes a quantity of sugar of at least xj or say that no possible k exists.

Note that he can't eat the same candy twice and queries are independent of each other (Timur can use the same candy in different queries).

有n个糖，然后每次吃一个，糖的糖分不一样，要让他吃够一个数，最少要吃几个，就是个前缀和，一直吃最大的，然后二分？试一下

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans = 0;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> mp(n);
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
    }
    sort(mp.begin(), mp.end(), [&](int a, int b) {
        return a > b;
    });
    for (int i = 1; i < n; i++) {
        mp[i] += mp[i - 1];
    }
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        if (x > mp[n - 1]) {
            cout << -1 << endl;
            continue;
        }
        int n = lower_bound(mp.begin(), mp.end(), x) - mp.begin();
        cout << n+1 << endl;
    }
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F. Longest Strike

Given an array a of length n and an integer k, you are tasked to find any two numbers l and r (l≤r) such that:

For each x(l≤x≤r), x appears in a at least k times (i.e. k or more array elements are equal to x).

The value r−l is maximized.

If no numbers satisfy the conditions, output -1.For example, if a=[11,11,12,13,13,14,14] and k=2, then: for l=12, r=14 the first condition fails because 12 does not appear at least k=2 times.

for l=13, r=14 the first condition holds, because 13 occurs at least k=2 times in a and 14 occurs at least k=2 times in a.

for l=11, r=11 the first condition holds, because 11 occurs at least k=2 times in a.

A pair of l and r for which the first condition holds and r−l is maximal is l=13, r=14.

裸题吧， 俩拼的，统计出现次数大于K的列表，然后在这个列表找连续出现的个数最大值

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans = 0;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void solve() {
    int n, k;
    n = read();
    k = read();
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        mp[read()]++;
    }
    vector<int> bk;
    for (auto &i: mp) {
        if (i.second >= k) {
            bk.push_back(i.first);
        }
    }
    if (bk.size() == 0) {
        cout << -1 << endl;
        return;
    }
    sort(bk.begin(), bk.end());
    vector<int> dp(bk.size(), 1);
    for (int i = 1; i < bk.size(); i++) {
        if (bk[i] - bk[i - 1] == 1) {
            dp[i] = dp[i - 1] + 1;
        }
    }
    int maxidx = max_element(dp.begin(), dp.end()) - dp.begin();
    cout << bk[maxidx] - dp[maxidx] + 1 << " " << bk[maxidx] << endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

G. White-Black Balanced Subtrees

You are given a rooted tree consisting of n vertices numbered from 1 to n. The root is vertex 1. There is also a string s denoting the color of each vertex: if si=B, then vertex i is black, and if si=W, then vertex iis white.

A subtree of the tree is called balanced if the number of white vertices equals the number of black vertices. Count the number of balanced subtrees.

A tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root. In this problem, all trees have root 1.

The tree is specified by an array of parents a2,…,an containing n−1 numbers: ai is the parent of the vertex with the number i for all i=2,…,n. The parent of a vertex u is a vertex that is the next vertex on a simple path from u to the root.

The subtree of a vertex u is the set of all vertices that pass through u on a simple path to the root. For example, in the picture below, 7 is in the subtree of 3 because the simple path 7→5→3→1 passes through 3. Note that a vertex is included in its subtree, and the subtree of the root is the entire tree.

有一棵树，知道父子关系

找树上黑色节点和白色节点数量相同的子树的数目？

就是后序遍历吧，找从下往上推，不知道DFS会不会炸，赖亚飞

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

vector<vector<int>> edge;
string s;
vector<pair<int, int>> dp;
int ans;
inline void dfs(int x) {
    if(s[x-1]=='B'){
        dp[x].first++;
    }else{
        dp[x].second++;
    }
    for(auto & point : edge[x]){
        dfs(point);
        dp[x].first+=dp[point].first;
        dp[x].second+=dp[point].second;
    }
    if(dp[x].first==dp[x].second){
        ans++;
    }

}

void solve() {
    int n;
    cin>>n;
    edge = vector<vector<int>>(n + 1);
    dp = vector<pair<int, int>>(n + 1, {0, 0});
    for (int i = 2; i <= n; i++) {
        int x = read();
        edge[x].push_back(i);
    }
    cin >> s;
    ans=0;
    dfs(1);
    cout<<ans<<endl;

}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

H2. Maximum Crossings (Hard Version)

A terminal is a row of n equal segments numbered 1 to n in order. There are two terminals, one above the other.

You are given an array a of length n. For all i=1,2,…,n, there should be a straight wire from some point on segment i of the top terminal to some point on segment ai of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if n=7 and a=[4,1,4,6,7,7,5].

A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?

放左边一点就，多一个，少一点就少一个。从右往左，看大于这个的数字的个数。树状数组维护一下

这板子第一次用耶。。

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;

inline long long read(void) {
    char c = getchar();
    long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

vector<int> tr;

void add(int x, int c) {
    for (int i = x; i < tr.size(); i += i & -i) tr[i] += c;
}

int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= i & -i) res += tr[i];
    return res;
}

void solve() {
    int n;
    cin >> n;
    vector<int> mp(n+1);
    tr = vector<int>(n+1,0);
    for (int i = 1; i <= n; i++) {
        mp[i] = read();
    }
    long long ans = 0;
    for (int i = n ; i ; i--) {
        ans += sum(mp[i]);
        add(mp[i], 1);
    }
    cout << ans << endl;

}

int main() {
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}