C. Division by Two and Permutation

原题描述

题意理解

给一个大小为n的数组，对数组中的某个数a可以进行这样的操作：删掉a并将a/2（向下取整）放入数组中。我们可以进行很多次该操作，如果可以通过多次操作得到1到n的全排列就输出YES,否则输出NO。

比如数组[1,8,25,2]。

第一次取8，删掉8，加入4，现数组元素[1,4,25,2].

第二次取25，删掉25，加入12，现数组元素[1,4,12,2].

第三次取12，删掉12，加入6，现数组元素[1,4,6,2].

第三次取6，删掉6，加入3，现数组元素[1,4,3,2].

现在我们得到了1到4的全排列，输出YES.

题解

我们先将数组中的每一个数除以很多次2，直到等于0为止，记录每个数在除以2过程中小于n的中间数，比如8，8/2=4，4/2=2，2/2=1，1/2=0。我们记录4，2，1是8可能最终会成为1到n排列中对应的数。

这样我们将原数组中的每个数可能对应的1到n排列中的数都求出来了。有的数只能对应到1到n排列中的一个数，我们直接将原数组中只有一种可能的数放到结果数组中，并记录他们。然后将原数组中有两种可能的数放到结果数组中，因为在此前我们记录了一些数，所以这是两种可能会排除掉一种，只剩一种，转化为一种可能的情况，直接放到结果数组中。以此类推。最后，遍历结果数组看1到n是不是全部出现。可能有点逻辑不是很清晰，我现在有点困。代码比较简洁。

我使用结构体数组来储存这些信息，结构体中的i对应原数组中的数，ans对应原数组中的数可能变成的数。

AC代码

/*@_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;}
}

这里一并附上A,B两题的代码，这两题比较简单就不复述题意了。

A. Plus One on the Subset

原题描述

题解

直接找数组中的最大值和最小值，然后相减输出即可。

AC代码

/*@_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

原题描述

题解

a,b,c,取一个数乘正整数m，使得这三个数构成等差数列（顺序不可以交换）。

三种情况，2b=am+c，m=(2b-c)/a;

2b=a+cm，m=(2b-a)/c;

2mb=a+c，m=(a+c)/2b;

然后判断m是不是正整数就行了。

AC代码

/*@_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;}
}

够简单吧！

如果对您有帮助，点个赞鼓励我一下，我会因此开心一小会。