今天来讲解一下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 函数是生成给定序列的上一个较小的排列。

所以代码如下：

#include <iostream>
#include <algorithm> //prev_permutation头文件 
using namespace std;
int a[101];
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    prev_permutation(a,a+n); //使用函数得到上一个排列 
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    return 0;
} 

二. D - Divide by 2 or 3

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

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

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

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

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