atcoder beginner contest336B题（AtCoder Beginner Contest 276）

时间2025-05-01 08:25:00分类IT科技浏览5150

导读：今天来讲解一下AtCoder Beginner Contest 276C和D...

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

所以代码如下：

二.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 }

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。