Deltix Round, Summer 2021 (Div. 1 + Div. 2)
A
Explanation:
Let a < B, the operation can be constructed in one step ( − x , x ) (-x,x) (− x,x) operation again can make a and b complete the 2x difference between a and b. when x is an odd number, there is no solution.
Special judgment: when x is 0 and a=0, operate step 0. When x is 0 and a=0, operation step.
To sum up, let x = b - a
- x % 2 != 0, no solution
- x = 0
- a = 0, 0
- a != 0 ,1
- x % 2 = 0 && x != 0, 2
code
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
#define int long long
typedef long long ll;
signed main(){
IOS
int tt; cin>>tt;
while(tt --){
int a,b; cin>>a>>b;
int t = abs(a-b);
if(t % 2) cout<<-1<<endl;
else{
if(t == 0){
if(a == 0) cout<<0<<endl;
else cout<<1<<endl;
}else cout<<2<<endl;
}
}
return 0;
}
B
explain
The legal status must be odd and even. You might as well put all odd numbers in place first, so even numbers are also equivalent to putting them in place.
Deal with the positions of all odd numbers. When the number is equal to the even number, or one more or one less than the even number, there is a solution.
For various cases, the placement position must be (1, 3, 5, 7, 9,...), (2, 4, 6, 8, 10,...)
Just find the minimum value.
code
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
#define int long long
typedef long long ll;
signed main(){
IOS
int tt; cin>>tt;
while(tt --){
int n; cin>>n;
vector<int> ve;
for(int i=1;i<=n;i++){
int a; cin>>a;
if(a % 2) ve.push_back(i);
}
if((n%2 == 0 && (int)ve.size() == n/2) || (n%2 == 1 && ((int)ve.size() == n/2 || (int)ve.size() == n/2+1))){
int ans = 1e18;
if(n%2 == 0){
int res = 0;
for(int i=0;i<n/2;i++) res += abs(ve[i]-i*2-1);
ans = min(ans,res);
res = 0;
for(int i=0;i<n/2;i++) res += abs(ve[i]-i*2-2);
ans = min(ans,res);
}else if(n%2 && (int)ve.size() == n/2){
int res = 0;
for(int i=0;i<n/2;i++) res += abs(ve[i]-i*2-2);
ans = min(ans,res);
}else{
int res = 0;
for(int i=0;i<n/2+1;i++) res += abs(ve[i]-i*2-1);
ans = min(ans,res);
}
cout<<ans<<endl;
}else{
cout<<-1<<endl;
}
}
return 0;
}
C
explain
Bind (1, 2), (3, 4)... (n-1, n) together, enumerate the starting point and then the ending point.
The left and right endpoints of the enumeration determine the number that can match any one of the left parentheses of the current starting point in the enumeration interval.
In the process of enumerating to the right, a pair of left and right numbers may not be equal
- If there are many left parentheses, record the quantity. Then, if you want to match the starting left parentheses, you must match these parentheses first,
- If the right bracket is larger than the left bracket, the more part will be taken to offset the non starting point left bracket left before, and then the rest will be taken to match the remaining starting point left bracket
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e3+10;
const int mod = 1e9+7;
#define int long long
int a[N];
signed main(){
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int ans = 0;
for(int i=1;i<=n;i+=2) {
int num1 = a[i]-a[i+1],num2 = 0;
ans += min(a[i],a[i+1]);
for(int j=i+3;j<=n;j+=2) {
if(num1 < 0) break;
if(a[j-1] > a[j]) {
num2 += a[j-1] - a[j];
continue;
}
int t = a[j] - a[j-1];
if(t < num2) num2 -= t;
else if(t == num2) {
num2 = 0;
ans ++;
}else {
t -= num2;
num2 = 0;
ans += min(num1,t) + 1;
num1 -= t;
}
}
}
cout<<ans<<endl;
return 0;
}
D
explain
A + B = a | B + A & B, first find the addition of the first three.
code
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e4+10;
const int mod = 1e9+7;
#define int long long
int a[N];
int query(int i,int j) {
cout<<"or "<<i<<" "<<j<<endl;
int a; cin>>a;
cout<<"and "<<i<<" "<<j<<endl;
int b; cin>>b;
return a+b;
}
signed main(){
int n,k; cin>>n>>k;
int q1 = query(1,2);
int q2 = query(2,3);
int q3 = query(1,3);
a[1] = (q1 - q2 + q3) / 2;
a[2] = q1 - a[1];
a[3] = q2 - a[2];
for(int i=4;i<=n;i++) {
int t = query(i-1,i);
a[i] = t - a[i-1];
}
sort(a+1,a+n+1);
cout<<"finish "<<a[k]<<endl;
return 0;
}
E
explain
Maintain difference sequence c ( i ) = b ( i ) − a ( i ) c(i) = b(i) - a(i) c(i)=b(i) − a(i). For each different parity position, one +, one -, can be regarded as the matching problem of bracket sequence. Those greater than 0 are left parentheses, and those less than 0 are right parentheses.
Maintain prefix and s u m n sum_n sumn, if can become equal if and only if ( l , r ) (l,r) (l,r) is a legal sequence of parentheses.
The following must be met: s u m r − s u m l − 1 = = 0 & & m i n { s u m l . . . s u m r } > = s u m l − 1 sum_r - sum_{l-1} == 0 \&\& min\{sum_l...sum_r\} >= sum_{l-1} sumr−suml−1==0&&min{suml...sumr}>=suml−1
The final answer is: m a x { s u m l . . . s u m r } max\{sum_l...sum_r\} max{suml...sumr}
Because subsequences like () () () ()... () are removed each time, two separated left parentheses can be selected at the same time. When the right parentheses separated from them are matched, they cannot be selected at the same time.
Then use ST table or segment tree to find the interval maximum value.
code
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
typedef long long ll;
int a[N],Log[N];
int mx[N][20],mn[N][20];
void init() {
for(int i=1;(1<<i)<N;i++) Log[1<<i] ++;
for(int i=1;i<N;i++) Log[i] += Log[i-1];
}
void ST(int n) {
for(int i=1;i<=n;i++)
for(int j=0;j<20;j++)
mx[i][j] = 0,mn[i][j] = 1e18;
for(int i=1;i<=n;i++) mx[i][0] = mn[i][0] = a[i];
for(int j=1;j<=Log[n];j++)
for(int i=1;i<=n-(1 << j)+1;i++){
mn[i][j] = min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
int query_max(int l,int r) {
int k = Log[r - l + 1];
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int query_min(int l,int r) {
int k = Log[r - l + 1];
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
signed main(){
IOS
init();
int n,q; cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int b; cin>>b;
a[i] = b - a[i];
a[i] += a[i-1];
}
ST(n);
while(q --){
int l,r; cin>>l>>r;
if(a[l-1] != a[r] || query_min(l,r) < a[l-1]) cout<<"-1\n";
else cout<<(query_max(l,r) - a[l-1])<<"\n";
}
return 0;
}