1 条题解
-
0
首先,这个题的暴力解法是用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; }
- 1
信息
- ID
- 288
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 91
- 已通过
- 27
- 上传者