A. Add Odd or Subtract Even
time limit per test2 seconds memory limit per test256 megabytes
You are given two positive integers a and b.
In one move, you can change a in the following way:
- Choose any positive odd integer x (x > 0) and replace a with a+x;
- choose any positive even integer y (y > 0) and replace a with a-y.
You can perform as many such operations as you want. You can choose the same numbers x and y in different moves.
Your task is to find the minimum number of moves required to obtain b from a. It is guaranteed that you can always obtain b from a.
You have to answer t independent test cases.Input
The first line of the input contains one integer t \((1 \le t \le 10^4) \)— the number of test cases.
Then t test cases follow. Each test case is given as two space-separated integers a and b \((1 \le a, b \le 10^9)\).Output
For each test case, print the answer — the minimum number of moves required to obtain b from a if you can perform any number of moves described in the problem statement. It is guaranteed that you can always obtain b from a.ExampleinputCopy
5 2 3 10 10 2 4 7 4 9 3
outputCopy
1 0 2 2 1
Note
In the first test case, you can just add 1.
In the second test case, you don't need to do anything.
In the third test case, you can add 1 two times.
In the fourth test case, you can subtract 4 and add 1.
In the fifth test case, you can just subtract 6.
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
void solve(){
int a,b;scanf("%d%d",&a,&b);
if(a==b) puts("0");
else if(a>b) puts((a-b)%2?"2":"1");
else puts((b-a)%2?"1":"2");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. WeirdSort
time limit per test2 seconds memory limit per test256 megabytes
You are given an array a of length n.
You are also given a set of distinct positions \(p_1, p_2, \dots, p_m\), where \(1 \le p_i < n\). The position p_i means that you can swap elements \(a[p_i] and a[p_i + 1]\). You can apply this operation any number of times for each of the given positions.
Your task is to determine if it is possible to sort the initial array in non-decreasing order \((a_1 \le a_2 \le \dots \le a_n)\) using only allowed swaps.
For example, if a = [3, 2, 1] and p = [1, 2], then we can first swap elements a[2] and a[3] (because position 2 is contained in the given set p). We get the array a = [3, 1, 2]. Then we swap a[1] and a[2] (position 1 is also contained in p). We get the array a = [1, 3, 2]. Finally, we swap a[2] and a[3] again and get the array a = [1, 2, 3], sorted in non-decreasing order.
You can see that if a = [4, 1, 2, 3] and p = [3, 2] then you cannot sort the array.
You have to answer t independent test cases.Input
The first line of the input contains one integer t \((1 \le t \le 100)\) — the number of test cases.
Then t test cases follow. The first line of each test case contains two integers n and m \((1 \le m < n \le 100)\) — the number of elements in a and the number of elements in p. The second line of the test case contains n integers \(a_1, a_2, \dots, a_n (1 \le a_i \le 100)\). The third line of the test case contains m integers \(p_1, p_2, \dots, p_m (1 \le p_i < n, all p_i are distinct)\) — the set of positions described in the problem statement.Output
For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order \((a_1 \le a_2 \le \dots \le a_n)\) using only allowed swaps. Otherwise, print "NO".ExampleinputCopy
6 3 2 3 2 1 1 2 4 2 4 1 2 3 3 2 5 1 1 2 3 4 5 1 4 2 2 1 4 3 1 3 4 2 4 3 2 1 1 3 5 2 2 1 2 3 3 1 4
outputCopy
YES NO YES YES NO YES
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m,x,a[maxn],b[maxn],c[maxn],p[110];
void solve(){
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d",&a[i]),c[i]=a[i],b[i]=0;
rep(i,1,m) scanf("%d",&x),b[x]=1;
sort(c+1,c+1+n);
rep(i,1,n) p[c[i]]=i;
int ok=1;
rep(i,1,n) rep(j,p[a[i]],i-1) if(!b[j]) ok=0;
puts(ok?"YES":"NO");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C. Perform the Combo
time limit per test2 seconds memory limit per test256 megabytes
You want to perform the combo on your opponent in one popular fighting game. The combo is the string s consisting of n lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in s. I.e. if s="abca" then you have to press 'a', then 'b', 'c' and 'a' again.
You know that you will spend m wrong tries to perform the combo and during the i-th try you will make a mistake right after p_i-th button\( (1 \le p_i < n)\) (i.e. you will press first p_i buttons right and start performing the combo from the beginning). It is guaranteed that during the m+1-th try you press all buttons right and finally perform the combo.
I.e. if s="abca", m=2 and p = [1, 3] then the sequence of pressed buttons will be 'a' (here you're making a mistake and start performing the combo from the beginning), 'a', 'b', 'c', (here you're making a mistake and start performing the combo from the beginning), 'a' (note that at this point you will not perform the combo because of the mistake), 'b', 'c', 'a'.
Your task is to calculate for each button (letter) the number of times you'll press it.
You have to answer t independent test cases.Input
The first line of the input contains one integer t \((1 \le t \le 10^4) \)— the number of test cases.
Then t test cases follow.
The first line of each test case contains two integers n and m\( (2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5)\) — the length of s and the number of tries correspondingly.
The second line of each test case contains the string s consisting of n lowercase Latin letters.
The third line of each test case contains m integers \(p_1, p_2, \dots, p_m (1 \le p_i < n)\) — the number of characters pressed right during the i-th try.
It is guaranteed that the sum of n and the sum of m both does not exceed \(2 \cdot 10^5 (\sum n \le 2 \cdot 10^5, \sum m \le 2 \cdot 10^5)\).
It is guaranteed that the answer for each letter does not exceed \(2 \cdot 10^9\).Output
For each test case, print the answer — 26 integers: the number of times you press the button 'a', the number of times you press the button 'b', \dots, the number of times you press the button 'z'.ExampleinputCopy
3 4 2 abca 1 3 10 5 codeforces 2 8 3 2 9 26 10 qwertyuioplkjhgfdsazxcvbnm 20 10 1 2 3 5 10 5 9 4
outputCopy
4 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 4 5 3 0 0 0 0 0 0 0 0 9 0 0 3 1 0 0 0 0 0 0 0 2 1 1 2 9 2 2 2 5 2 2 2 1 1 5 4 11 8 2 7 5 1 10 1 5 2
Note
The first test case is described in the problem statement. Wrong tries are "a", "abc" and the final try is "abca". The number of times you press 'a' is 4, 'b' is 2 and 'c' is 2.
In the second test case, there are five wrong tries: "co", "codeforc", "cod", "co", "codeforce" and the final try is "codeforces". The number of times you press 'c' is 9, 'd' is 4, 'e' is 5, 'f' is 3, 'o' is 9, 'r' is 3 and 's' is 1.
签到，前缀和记一下就好啦
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m,ans[30],b[maxn][30];
char s[maxn];
void solve(){
scanf("%d%d%s",&n,&m,s+1);
rep(i,0,26) ans[i]=0;
rep(i,1,n) rep(j,0,25) b[i][j]=b[i-1][j]+(s[i]-'a'==j);
rep(i,1,m){
int x;scanf("%d",&x);
rep(j,0,25) ans[j]+=b[x][j];
}
rep(i,0,25) ans[i]+=b[n][i];
rep(i,0,25) printf(i==25?"%d\n":"%d ",ans[i]);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
D. Three Integers
time limit per test2 seconds memory limit per test256 megabytes
You are given three integers\( a \le b \le c\).
In one move, you can add +1 or -1 to any of these integers (i.e. increase or decrease any number by one). You can perform such operation any (possibly, zero) number of times, you can even perform this operation several times with one number. Note that you cannot make non-positive numbers using such operations.
You have to perform the minimum number of such operations in order to obtain three integers \(A \le B \le C\) such that B is divisible by A and C is divisible by B.
You have to answer t independent test cases.Input
The first line of the input contains one integer t \((1 \le t \le 100) \)— the number of test cases.
The next t lines describe test cases. Each test case is given on a separate line as three space-separated integers a, b and c\( (1 \le a \le b \le c \le 10^4)\).Output
For each test case, print the answer. In the first line print res — the minimum number of operations you have to perform to obtain three integers \(A \le B \le C\) such that B is divisible by A and C is divisible by B. On the second line print any suitable triple A, B and C.ExampleinputCopy
8 1 2 3 123 321 456 5 10 15 15 18 21 100 100 101 1 22 29 3 19 38 6 30 46
outputCopy
1 1 1 3 102 114 228 456 4 4 8 16 6 18 18 18 1 100 100 100 7 1 22 22 2 1 19 38 8 6 24 48
很显然暴力枚举A,B,C即可，范围就是[1,2*a]
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int a,b,c;
void solve(){
scanf("%d%d%d",&a,&b,&c);
int mx=mod,aa=0,bb=0,cc=0;
rep(i,1,min((int)1e4,2*a)){
rep(k1,1,1e4){
rep(k2,1,1e4){
int x=i,y=i*k1,z=i*k1*k2;
int tmp=abs(a-x)+abs(b-y)+abs(c-z);
if(tmp<mx) mx=tmp,aa=x,bb=y,cc=z;
if(z>c||z>2*c) break;
}
if(i*k1>2*b) break;
}
}
printf("%d\n%d %d %d\n",mx,aa,bb,cc);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
E. Construct the Binary Tree
time limit per test2 seconds memory limit per test256 megabytes
You are given two integers n and d. You need to construct a rooted binary tree consisting of n vertices with a root at the vertex 1 and the sum of depths of all vertices equals to d.
A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a vertex v is the last different from v vertex on the path from the root to the vertex v. The depth of the vertex v is the length of the path from the root to the vertex v. Children of vertex v are all vertices for which v is the parent. The binary tree is such a tree that no vertex has more than 2 children.
You have to answer t independent test cases.Input
The first line of the input contains one integer t \((1 \le t \le 1000)\) — the number of test cases.
The only line of each test case contains two integers n and d\( (2 \le n, d \le 5000)\) — the number of vertices in the tree and the required sum of depths of all vertices.
It is guaranteed that the sum of n and the sum of d both does not exceed 5000 \((\sum n \le 5000, \sum d \le 5000)\).Output
For each test case, print the answer.
If it is impossible to construct such a tree, print "NO" (without quotes) in the first line. Otherwise, print "{YES}" in the first line. Then print n-1 integers p_2, p_3, \dots, p_n in the second line, where p_i is the parent of the vertex i. Note that the sequence of parents you print should describe some binary tree.ExampleinputCopy
3 5 7 10 19 10 18
outputCopy
YES 1 2 1 3 YES 1 2 3 3 9 9 2 1 6 NO
Note
Pictures corresponding to the first and the second test cases of the example:
构造题，dep表示的是深度为i的点数，很显然知道n之后我们可以知道深度和的上下界，那么我们就从一条链开始，此时深度和最大，我们可以把最下面的点往上移使得这个和减少，模拟即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e4+100;
const int mod=(int)1e9+7;
int n,d,ans[maxn],sum[maxn],dep[maxn];
void solve(){
scanf("%d%d",&n,&d); d=n*(n-1)/2-d;
rep(i,1,n+1) dep[i]=1;
int l=2,r=n;
for(;l<r;r--){
while(l<r&&(d-r+l<0||dep[l]==dep[l-1]*2)) ++l;
if(l>=r) break;
d=d-r+l;dep[r]--;dep[l]++;
}
if(d!=0) return (void)puts("NO");
puts("YES");
rep(i,1,r) sum[i]=sum[i-1]+dep[i];
rep(i,2,r) rep(j,1,dep[i]) printf("%d ",sum[i-2]+1+(j-1)/2);puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
F. Moving Points
time limit per test2 seconds memory limit per test256 megabytes
There are n points on a coordinate axis OX. The i-th point is located at the integer point x_i and has a speed v_i. It is guaranteed that no two points occupy the same coordinate. All n points move with the constant speed, the coordinate of the i-th point at the moment t (t can be non-integer) is calculated as \(x_i + t \cdot v_i\).
Consider two points i and j. Let d(i, j) be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points i and j coincide at some moment, the value d(i, j) will be 0.
Your task is to calculate the value \(\sum\limits_{1 \le i < j \le n} d(i, j)\) (the sum of minimum distances over all pairs of points).Input
The first line of the input contains one integer n\( (2 \le n \le 2 \cdot 10^5) \)— the number of points.
The second line of the input contains n integers \(x_1, x_2, \dots, x_n (1 \le x_i \le 10^8)\), where x_i is the initial coordinate of the i-th point. It is guaranteed that all x_i are distinct.
The third line of the input contains n integers \(v_1, v_2, \dots, v_n (-10^8 \le v_i \le 10^8)\), where v_i is the speed of the i-th point.Output
Print one integer — the value \(\sum\limits_{1 \le i < j \le n} d(i, j) \)(the sum of minimum distances over all pairs of points).ExamplesinputCopy
3 1 3 2 -100 2 3
outputCopy
3
inputCopy
5 2 1 4 3 5 2 2 2 3 4
outputCopy
19
inputCopy
2 2 1 -3 0
outputCopy
0
对于一条线段i，它对答案贡献的\(x_i\)值是这几个：
1）对于所有\(v_j < v_i\)并且\(x_j < x_i\)，这些线段j会使答案加上\(x_i\)
2）对于所有的\(v_j > v_i\)并且\(x_j > x_i\)，这些线段j会使答案减去\(x_i\)
那很显然每条线段的x对于答案贡献了（v比vi小的线段数-x比xi大的线段数）次
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define v first
#define x second
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,c[maxn];ll ans;
pair<int,int> a[maxn];
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i].x),c[i]=a[i].x;
rep(i,1,n) scanf("%d",&a[i].v);
sort(a+1,a+1+n);sort(c+1,c+1+n);
rep(i,1,n) ans+=(i-1-n+lower_bound(c+1,c+1+n,a[i].x)-c)*(ll)a[i].x;
printf("%lld\n",ans);
}
