返回题解分享
讨论 / 题解分享/ 帖子详情

铁匠 - 题解

首先,这个题的暴力解法是用DFS,每一个长度的节点选还是不选,只能切割11个位置,所以需要记录切割的个数

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<array>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
using i64=long long;
//using i128=__int128;
//const i64 INF=1e18;
const int mod=998244353;
//const int N=1e9+7;
int l=0,ans=0;
void dfs(int pos,int cuts){
if(cuts==11){
ans++;
return ;
}
if(pos>l-1)return ;
dfs(pos+1,cuts+1);
dfs(pos+1,cuts);
}
void solve(){
cin>>l;
dfs(1,0);
cout<<ans<<'\n';
return ;
}
int main(){
int _=1;
//cin>>_;
while(_--)solve();
return 0;
}
其次,这个题的正解是组合数,但是为了防止爆i64需要在计算中将除法也用上,组合数的求解是C(l-1,11)
正解代码:

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<array>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
using i64=long long;
//using i128=__int128;
//const i64 INF=1e18;
const int mod=998244353;
//const int N=1e9+7;
void solve(){
int l;
cin>>l;
i64 ans=1;
for(int i=1;i<=11;i++){
ans=ans*(l-i)/i;
}
cout<<ans<<'\n';
}
int main(){
int _=1;
//cin>>_;
while(_--)solve();
return 0;
}
```
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!