欢乐赛#42
2025-03-10 20:21:27
发布于：浙江
虽然本题解所讲述的不是最优解，但是能过
T1
数据范围
1≤T≤100
1≤a,b≤1000
可以考虑直接暴力，使用O(t*min(a,b))的时间复杂度来过。
#include<bits/stdc++.h>
using namespace std;
int t,a,b;
void solve(){
//记录有几个公约数
int num=0;
for(int i=min(a,b);i>0;i--){
// 如果i是a和b的公约数
if(a%i==0 && b%i==0){
//已经有一个公约数，即i是次大公约数
if(num){
cout<<i<<endl;
return ;
}
else num++;
}
}
cout<<-1<<endl;
return ;
}
int main(){
cin>>t;
while(t--){
cin>>a>>b;
solve();
}
return 0;
}
T2
已知4！=1* 2 * 3 * 4 = 24
已知num!=num*(num-1)!
所以只要x>=4,则x!包含4，即x是24的倍数
#include<bits/stdc++.h>
using namespace std;
int x;
int main(){
cin>>x;
if(x>3) cout<<"YES";
else cout<<"NO";
return 0;
}
T3
这真的不应该是第一题吗？
第三题肥肠简单，直接输出
#include<bits/stdc++.h>
using namespace std;
int n;
char c;
int main(){
cin>>n;
for(int i=1;i<n+1;i++){
cin>>c;
for(int j=0;j<i;j++) cout<<c;
}
return 0;
}
T4
如果我没记错的话
科普小知识：有一个函数叫做"next_permutation"
作用：搞出下一个排列
返回值:能否生成下一个更大的排列
时间复杂度：O(n) (n:数组的长度）
食用用方法：和sort一样。例：next_permutation(v.begin(),v.end());
如果运运用这个函数，则时间复杂度为O(nm)，可以通过（当n=10时，max(m)=3628800)
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>num;
int main(){
cin>>n>>m;
for(int i=1;i<n+1;i++) num.push_back(i);
for(int i=1;i<m;i++){
next_permutation(num.begin(),num.end());
}
for(int i=0;i<n;i++) cout<<num[i]<<" ";
return 0;
}
T5
个人感觉这道题比第六题难
”小王的任务是找到一个最大的数 y“
能量值相同时，y的位数越多，则y越大（无前导零）
如何使y变大呢？
例：x=6,能量值=6！
6！=5！*6=5！*3！
所以y=6或53
当然选53啦~
根据观察，5、7只能等于5！、7！,但其它数字都可以改变。
以下是每个数字的最优解：
1：1
2：2
3：3
4：22
5：5
6：53
7：7
8：7222
9：7332
#include<bits/stdc++.h>
using namespace std;
long long x,z;
int l[10][5];
void check(){
l[2][0]=2;
l[3][0]=3;
l[4][0]=3;
l[4][1]=2;
l[4][2]=2;
l[5][0]=5;
l[6][0]=5;
l[6][1]=3;
l[7][0]=7;
l[8][0]=7;
l[8][1]=2;
l[8][2]=2;
l[8][3]=2;
l[9][0]=7;
l[9][1]=3;
l[9][2]=3;
l[9][3]=2;
}
vector<int> y;
bool bmp(int a,int b){
return a>b;
}
int main(){
cin>>x;
check();
while(x){
z=x%10;
for(int i=0;i<5;i++){
if(l[z][i]==0) break;
y.push_back(l[z][i]);
}
x/=10;
}
sort(y.begin(),y.end(),bmp);
for(int i=0;i<y.size();i++) cout<<y[i];
return 0;
}
作者代码有点丑QAQ
T6
”可以自由地将这个数组进行重新排列，并依照重新排列后的顺序逐个取出数组中的元素。小王可以选择任何一个元素作为开始。而之后，每次取出的元素如果比上一次取出的元素大，作为奖励，小明就会获得一束精美的玫瑰花，取第一个元素的时候，没有花“
则可以将原来的数组分为几个数组。
怎样使玫瑰花数量最多呢？
当数组为升序时，玫瑰花数量最多。
但是——排序之后，可能会出现l[i]==l[i+1]的现象。
所以我们可以将原来的单调不减数组弄成几个升序数组，这样就可以使玫瑰花的数量最多了。
#include<bits/stdc++.h>
using namespace std;
int n,ans,cnt;
int l[1005];
vector<int> v[1005];
bool check(){
bool flag=0;
int j=0,s=v[cnt].size();
for(int i=1;i<v[cnt].size();i++){
//cout<<v[cnt][i]<<" "<<v[cnt][j]<<endl;
if(v[cnt][i]==v[cnt][j]){
v[cnt+1].push_back(v[cnt][i]);
flag=1;
}
else{
v[cnt][++j]=v[cnt][i];
}
}
ans+=j;
return flag;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>l[i];
sort(l,l+n);
for(int i=0;i<n;i++) v[cnt].push_back(l[i]);
while(check()) cnt++;
cout<<ans;
return 0;
}
太好了，终于写完了！
有帮助，赞一个