ACGO挑战赛#14 T1—3
2025-01-27 15:17:25
发布于：山西
啊啊啊啊啊啊！太忙了，昨天忘记（且没时间）打比赛了！！！
好烦
T1
我们可以通过x和y的差值得到x和y的高度
因为“城堡高度分别为1,(1+2),(1+2+3),...,(1+2+...+999)1,(1+2),(1+2+3),...,(1+2+...+999)个方块”、x和y相邻，所以x原本的高度为1+2+3......+(y-x-1)。
我们通过输入的被覆盖后的x的高度和x原本的高度的差值，就可以知道雪块的高度了。
#include<bits/stdc++.h>
using namespace std;
int x,y,ans;
int main(){
cin>>x>>y;
for(int i=1;i<y-x;i++) ans+=i;
cout<<ans-x;
return 0;
}
T2
我们有三种采矿方法：
1.采取1个单位的石头。
2.6个单位或者6的次方个单位的石头,例如6^3=216个单位的石头)。
3.采取9个单位或者9的次方个单位的石头(例如9^2=81个单位的石头)。
由此可知，每次采的石头越多越好，那我们就可以每次都采能采的最多的石头（贪心）
但是有可能不是这样子的!
例:n=108
如果按照贪心的想法，ans=4(81,9,9,9)
但其实ans=3(36,36,36)
所以最优方案应该运用dfs(每次尝试采最多能采6的次方个单位的石头或9的次方个单位的石头
#include<bits/stdc++.h>
using namespace std;
int n,ans=1e9;
int _6(int num){
int x=1;
while(x<=num) x*=6;
x/=6;
return x;
}
int _9(int num){
int x=1;
while(x<=num) x*=9;
x/=9;
return x;
}
void dfs(int num,int sum){
if(num<6){
ans=min(ans,sum+num);
return ;
}
int x=_6(num),y=_9(num);
dfs(num-max(x,y),sum+1);
return ;
}
int main(){
cin>>n;
dfs(n,0);
cout<<ans<<endl;;
return 0;
}
T3
first,简而言之，如果x%y==0,则y为x的正除数（y>0)
N！=1x2x3......xN
我们可以将1，2，3......,N质数分解，N!就等于(1)x(2)x(3)x(2x2)x(5)......x(质数分解后的N)，即N！的所有正除数都是由这一坨些和1组成的
我们还可以将这些用数组统计每一个质数出现的次数
*最后，我们求的的东西就成了有x个质数，每个质数有sum[i]个，求可以相乘组成多少个不同的数的答案+1(因为1不是质数，但也是N！的正除数）
方法：
公式：
ans=1;
for(int i=2;i<n+1;i++){
if(num[i]) ans*=sum[i]+1;//if(num[i]):判断i是否为质数
}
#include<bits/stdc++.h>
using namespace std;
int n,p=1e9+7;
int num[1005],sum[1005];
long long ans;
void check(){
for(int i=2;i<n+1;i++) num[i]=1;
for(int i=2;i<n+1;i++){
if(!num[i]) continue;
for(int j=2;j*i<i+1;j++){
num[i]=0;
}
}
return ;
}
void add(){
for(int i=1;i<n+1;i++){
int x=i;
for(int j=2;j*j<i+1;j++){
while(x%j==0){
sum[j]++;
x/=j;
}
}
if(num[x]) sum[x]++;
}
return ;
}
void solve(){
ans=1;
for(int i=2;i<n+1;i++){
if(num[i]) ans*=sum[i]+1;
ans%=p;
}
return ;
}
int main(){
cin>>n;
//用埃式筛晒出1-n之间的质数
check();
//测量每个质数在N！质数分解后中的个数
add();
//算
solve();
cout<<ans;
return 0;
}
第二次写题解，如有错误，请谅解。
全部评论 3
对不起，T2的代码发错了：“dfs(num-max(x,y),sum+1);”应改为“dfs(num-x,sum+1);dfs(num-y,sum+1;"。错误的代码与我之前所驳的贪心思路相同，但是是acgo数据太水的原因，所以错误代码也AC了。今天重新看了一遍才发现。
2025-01-29 来自 山西
0
有帮助，赞一个