AtCoder Beginner Contest 276

今天来讲解一下AtCoder Beginner Contest 276 C和D

传送地址：https://atcoder.jp/contests/abc276

一. C - Previous Permutation

题目大意：给你一个有数字 1~n 组成的序列，将数字1~n进行全排列并且从小到大排序后，这是第k个。问第k-1个是什么？

这一题由于n<=100，明显不能使用暴力枚举，所以这里引入一个新函数：prev_permutation

这个函数的功能刚好与 next_permutation 的作用相反

prev_permutation 函数是生成给定序列的上一个较小的排列。

所以代码如下：

 1 #include <iostream>
 2 #include <algorithm> //prev_permutation头文件 
 3 using namespace std;
 4 int a[101];
 5 int main()
 6 {
 7     int n;cin>>n;
 8     for(int i=0;i<n;i++) cin>>a[i];
 9     prev_permutation(a,a+n); //使用函数得到上一个排列 
10     for(int i=0;i<n;i++) cout<<a[i]<<" ";
11     return 0;
12 } 

二. D - Divide by 2 or 3

题目大意：给你一个长度为n的数组A。你可以选择一下两个操作中的一个操作任何次数或不操作

                1.选择A其中一个元素，这个元素是2的倍数，把他替换成自己除以2

                2.选择A其中一个元素，这个元素是3的倍数，把他替换成自己除以3

具体就不说了，直接看代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;cin>>n;
 6     int g=0,cnt=0;  
 7     set<int> s;
 8     for(int i=0;i<n;i++){
 9         int a;cin>>a;
10         g=__gcd(g,a);  //找到所有数共同的最大公因数 
11         int tmp=a;
12         while(tmp%2==0) tmp/=2,cnt++;  //累加除以2的次数 
13         while(tmp%3==0) tmp/=3,cnt++;  //累加除以3的次数 
14         s.insert(tmp); //将剩余的质数放进来 
15     }
16     if(s.size()!=1) {  //如果有两个或以上不同的质数，则一定构造不出来 
17         cout<<-1<<endl;
18         return 0;
19     }
20     while(g%2==0) g/=2,cnt-=n;  //如果g是2的倍数，则其他所有数都可以少除2，所以cnt-=n 
21     while(g%3==0) g/=3,cnt-=n;  //如果g是3的倍数，则其他所有数都可以少除3，所以cnt-=n 
22     cout<<cnt<<endl;
23     return 0;
24 }