今天来讲解一下AtCoder Beginner Contest 276C和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 }