https://codeforces.com/contest/1593
A
Ask everyone the minimum extra points needed to be strict first. The three people are independent
- Calculate the minimum bonus points that the current person needs to exceed others, and finally take the maximum value
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int a, b, c;
cin >> a >> b >> c;
cout << max({0, b - a + 1, c - a + 1}) << ' ';
cout << max({0, a - b + 1, c - b + 1}) << ' ';
cout << max({0, a - c + 1, b - c + 1}) << '\n';
}
return 0;
}
B
Give a number n n n. One digit of this number can be deleted each time. The leading zero is automatically deleted to ensure a solution. Ask how many digits can be deleted at least to ensure that the remaining number is 25 25 Multiple of 25
- We can find that if a number is 25 25 25, then its last two numbers must be 25 , 50 , 75 , 00 25,50,75,00 25, 50, 75 and 00, so you can find them from the back to the front 0 0 0 and 5 5 5 such two cases can be discussed separately
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
string s;
while(t--){
cin >> s;
int len = s.length();
int ans = INT_MAX;
for(int i=len-1;i>=0;i--){
if(s[i] == '0'){
for(int j=i-1;j>=0;j--){
if(s[j] == '0' || s[j] == '5'){
ans = min(ans, len - 2 - j);
break;
}
}
}
if(s[i] == '5'){
for(int j=i-1;j>=0;j--){
if(s[j] == '2' || s[j] == '7'){
ans = min(ans, len - 2 - j);
break;
}
}
}
}
cout << ans << '\n';
}
return 0;
}
C
A number axis, where is the cat 0 0 At position 0, the hole is n n At position n, there are many mice between the two. The cat can only walk one unit to the right at each time point, and only one mouse can walk one unit to the right at each time point. The mouse moves first. Now ask how many mice can run into the hole at most
- Obviously, we should greedily let the mouse closest to the hole go first. If we let other mice in, it will affect other mice, so let the mouse on the far right enter the hole every time, record the position of the cat and compare it
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> a(k);
long long cat = 0;
for(int i=0;i<k;i++){
cin >> a[i];
}sort(a.rbegin(), a.rend());
int ans = 0;
for(int i=0;i<k;i++){
if(a[i] > cat){
ans += 1;
}
cat += n - a[i];
}
cout << ans << '\n';
}
return 0;
}
D1
Altogether n n n numbers, now you have to find a maximum number x x x. Make some numbers by adding several x x x makes all numbers the same size if x x x can be infinity, then the output ā 1 -1 − 1, otherwise output x x x
- Obviously, if now all n n If the number of n is already the same, it should be output ā 1 -1 ā1
- Otherwise, a certain number can be found to achieve the goal. Consider 1 1 1. This is a special number that can be satisfied in any case, so we began to find the largest possible number by enumerating the difference between each two numbers g c d gcd gcd to record all possible numbers, and then enumerate them violently. In each case, it is calculated if it can make all n n If n numbers are equal, update the answer
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> a(n);
bool f = false;
unordered_map<int, int> mp;
for(int i=0;i<n;i++){
cin >> a[i];
mp[a[i]] += 1;
if(mp[a[i]] == n) f = true;
}
if(f){
cout << -1 << '\n';
continue;
}
set<int> gcds, st;
for(auto i : a){
for(auto j : a){
if(i != j) st.insert(abs(i - j));
}
}
for(auto i : st){
for(auto j : st){
gcds.insert(__gcd(i, j));
}
}
int ans = INT_MIN;
for(auto x : gcds){
for(auto i : a){
int nm = 0;
for(auto j : a){
if((i - j) % x == 0){
nm += 1;
}
}
if(nm == n){
ans = max(ans, x);
break;
}
}
}
cout << ans << '\n';
}
return 0;
}
D2
- The idea is the same as above, but it will n n n replace with n 2 \frac n 2 2nā
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> a(n);
bool f = false;
unordered_map<int, int> mp;
for(int i=0;i<n;i++){
cin >> a[i];
mp[a[i]] += 1;
if(mp[a[i]] >= n / 2) f = true;
}
if(f){
cout << -1 << '\n';
continue;
}
set<int> gcds, st;
for(auto i : a){
for(auto j : a){
if(i != j) st.insert(abs(i - j));
}
}
for(auto i : st){
for(auto j : st){
gcds.insert(__gcd(i, j));
}
}
int ans = INT_MIN;
for(auto x : gcds){
for(auto i : a){
int nm = 0;
for(auto j : a){
if((i - j) % x == 0){
nm += 1;
}
}
if(nm >= n / 2){
ans = max(ans, x);
break;
}
}
}
cout << ans << '\n';
}
return 0;
}
E
Remove all leaf nodes in each operation. If it is an empty tree, do not move it; If there is only one node, remove it; If there are two nodes connected, they should be removed. Q k k How many leaf nodes are left after k operations
- Obviously, it's a topological sort. Just take it down one layer at a time
- Note that there is only one node in the special judgment
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, k, u, v;
cin >> n >> k;
vector<vector<int> > g(n);
vector<int> degree(n);
for(int i=1;i<n;i++){
cin >> u >> v;
u -= 1;
v -= 1;
g[u].push_back(v);
g[v].push_back(u);
degree[v] += 1;
degree[u] += 1;
}
queue<int> q;
for(int i=0;i<n;i++){
if(degree[i] == 1){
q.push(i);
}
}
int ans = n;
while(k-- && !q.empty()){
ans -= q.size();
queue<int> q2;
while(!q.empty()){
u = q.front();
q.pop();
degree[u] = 0;
for(auto i : g[u]){
if(degree[i] == 0) continue;
degree[i] -= 1;
if(degree[i] == 1){
q2.push(i);
}
}
}
q = q2;
}
cout << (n == 1 ? 0 : ans) << '\n';
}
return 0;
}