# 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;
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+s+s-'0'-'0'-'0';
y=s+s+s-'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?

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans=0;
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.

#include<bits/stdc++.h>

#define endl '\n'
#define ll long long
using namespace std;
int ans=0;
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;

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).

#include<bits/stdc++.h>

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

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 (lr) such that:

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

The value rl 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 rl is maximal is l=13, r=14.

#include<bits/stdc++.h>

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

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;
map<int, int> mp;
for (int i = 0; i < n; i++) {
}
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.

#include<bits/stdc++.h>

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

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++) {
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;

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++) {
}
long long ans = 0;
for (int i = n ; i ; i--) {
ans += sum(mp[i]);
}
cout << ans << endl;

}

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