CodeforcesRound#686(Div.3)(AE)

A.Special Permutation

给你一个长度为 $n$ 的数组 $a$，使得第 $i$ 位数不等于 $a_i$。

把一个从 $1-n$ 的数组向右移动一位就好了。

#include
#include
#include
#include
#include
#include

using namespace std;

const int N=150;

int n,t,a[N];

int main(){
// freopen("snakes.in","r",stdin);
// freopen("snakes.out","w",stdout);
cin>>t;
while(t--){
cin>>n;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
if(i!=1)a[i]=i-1;
else a[i]=n;
}
for(int i=1;i<=n;i++){
cout<" ";
}
cout<<endl;
}
return 0;
}

View Code

 B.Unique Bid Auction

给你一个长度为 $n$ 的数组，求出只出现一次且最小的数。

模拟就行。

#include
#include
#include
#include
#include
#include

using namespace std;

const int N=200050;

int n,t,a[N],b[N];

int main(){
// freopen("snakes.in","r",stdin);
// freopen("snakes.out","w",stdout);
cin>>t;
while(t--){
cin>>n;int o=0;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
int x;cin>>x;a[x]++;b[x]=i;
}
for(int i=1;i<=n;i++){
if(a[i]==1){cout<1;break;}
}
if(o==0){cout<<-1<<endl;}
}
return 0;
}

View Code

 C.Sequence Transformation

给你一个长度为 $n$ 的数组，选取数组中的一个数，问这个数最少可以把数组分成几段。

注意一个数出现在开头或结尾只会增加一段，其他地方出现且前面的数不等于当前的数就会增加两端。

还有一些细节看代码。

#include
#include
#include
#include
#include
#include

using namespace std;

const int N=200050;

int n,t,a[N],b[N];

int main(){
// freopen("snakes.in","r",stdin);
// freopen("snakes.out","w",stdout);
cin>>t;
while(t--){
cin>>n;int o=0;
for(int i=1;i<=n;i++){
int x;cin>>a[i];b[i]=99999999;
if(a[i]!=a[i-1]&&i!=1)o=1;
}
if(o==0){cout<<0<continue;}
for(int i=1;i<=n;i++){
if(b[a[i]]==99999999){
if(i!=1&&i!=n)
b[a[i]]=2;
else
b[a[i]]=1;
}
else{
if(i!=n&&a[i]!=a[i-1])b[a[i]]++;
if(i==n&&a[i]==a[i-1])b[a[i]]--;
}
}
int mins=99999999;
for(int i=1;i<=n;i++){
mins=min(mins,b[i]);
}
cout<endl;
}
return 0;
}

View Code

D.Number into Sequence

给你一个 $n$，让你构造出一个数组 $a$， 长度为 $k$。

使得 $\prod^{k}_{i=1} a_i=n$

 对于每个 $i$ 来说 $a_{i+1}$ % $a_i =0$。使得 $k$ 最大。

 其实可以发现：$n$ 要被一个质数的平方整除 $k$ 才能加一。

否则不行，所以我们可以从 $2-\sqrt{n}$ 枚举既可以算出。

#include
#include
#include
#include
#include
#include

using namespace std;

const int N=2000500;

long long t,n,a[N],top;

int pd(long long x)
{
int f=2;
if(x==2) return 1;
while(x%f!=0&&f<=sqrt(x))
{
f++;
}
if(x%f==0) return 0;
else return 1;
}

int main(){
// freopen("snakes.in","r",stdin);
// freopen("snakes.out","w",stdout);
cin>>t;
while(t--){
cin>>n;long long o=0;
if(pd(n)==1){
cout<<1<continue;
}
top=0;long long m=n;
for(long long i=2;i<=sqrt(n);i++){
int k=0;
while(n%(i*i)==0&&pd(i)==1){k++;n=n/i;}
if(k>top){o=i;top=k;}
n=m;
}
if(top==0){ cout<<1<continue;}
cout<1<<endl;
while(m%(o*o)==0){cout<" ";m=m/o;}cout<endl;
}
return 0;
}

View Code