Catalog
C. Division by Two and Permutation
C. Division by Two and Permutation
Topic Description
Interpretation
Given a n array of size n, you can do something like delete a and put a/2 (rounding down) into the array. We can do this many times and output YES if we can get a full permutation of 1 to n from multiple operations or NO.
Like arrays [1,8,25,2].
First take 8, delete 8, add 4, present array element [1,4,25,2].
Second take 25, delete 25, add 12, present array element [1,4,12,2].
Take 12 for the third time, delete 12, add 6, present array element [1,4,6,2].
Take 6 the third time, delete 6, add 3, present array element [1,4,3,2].
Now we have a full range of 1 to 4, outputting YES.
Problem
Divide each number in the array by 2 many times until it equals 0. Record the middle number that is less than N in the process of dividing each number by 2, such as 8, 8/2=4, 4/2=2, 2/2=1, 1/2=0. We note that 4, 2, 1 are 8 which may eventually become the corresponding number in the 1 to n order.
In this way, we find out the number in the 1 to n permutation that each number in the original array might correspond to. Some numbers can only correspond to one number in the range 1 to n. We directly put only one possible number in the original array into the result array and record them. We then put two possible numbers from the original array into the result array, because we have recorded some numbers before, so these are two possibilities to exclude one, and only one, to convert it into a possible situation and put it directly into the result array. And so on. Finally, iterate through the result array to see if all 1 to n appear. Maybe the logic is not clear. I'm a little sleepy right now. The code is concise.
i use struct arrays to store this information, where i corresponds to the number in the original array and ans to the number that may become in the original array.
AC Code
/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define N 10001
struct MYSTRUCT{
int i;
int ans[20];
int sum;
};
bool cmp(MYSTRUCT a,MYSTRUCT b){
return a.sum<b.sum;
}
int main(){
int t;
cin>>t;
while(t--){
MYSTRUCT a[N];
int n,flag=0;
int vis[N]={0};
cin>>n;
_for(i,1,n){
cin>>a[i].i;
int temp=a[i].i;
int j;
for(j=1;temp!=0;temp=temp/2){
if(temp<=n)
a[i].ans[j++]=temp;
}
a[i].sum=j-1;
}
sort(a+1,a+1+n,cmp);
_for(i,1,n){
for(int j=1;j<=a[i].sum;j++)
if(!vis[a[i].ans[j]]){
vis[a[i].ans[j]]=true;
break;
}
}
_for(i,1,n) if(!vis[i]&&flag++);
if(flag) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
}This is accompanied by codes for questions A and B, which are relatively simple and will not repeat the topic.
A. Plus One on the Subset
Topic Description
Problem
Directly find the maximum and minimum values in the array and subtract the output.
AC Code
/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define for(i,a,b) for(int i=a;i<=b;i++)
int main(){
int t;
cin>>t;
while(t--){
ll max1=0,min1=LM;
int n;
cin>>n;
for(i,1,n){
ll temp;
cin>>temp;
if(temp>max1) max1=temp;
if(temp<min1) min1=temp;
}
cout<<max1-min1<<endl;
}
}B. Make AP
Topic Description
Questions
a,b,c, take a number multiplied by a positive integer m, so that these three numbers form an equal difference column (the order cannot be exchanged).
3 cases, 2b=a m+c, m=(2b-c)/a;
2b=a+cm，m=(2b-a)/c;
2mb=a+c，m=(a+c)/2b;
Then decide if m is a positive integer.
AC Code
/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define for(i,a,b) for(int i=a;i<=b;i++)
int main(){
int t;
cin>>t;
while(t--){
long double a,b,c;
cin>>a>>b>>c;
if(((a+c)/(2*b)==(int)((a+c)/(2*b))&&(a+c)/(2*b)>0)||((2*b-a)/c==(int)((2*b-a)/c)&&(2*b-a)/c>0)||((2*b-c)/a==(int)((2*b-c)/a)&&(2*b-c)/a>0)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}Simple enough!
If it helps you, give me a pat on the back and I'll have a little fun with it.