首页 > 代码库 > HDU 5312(数学推导+技巧)
HDU 5312(数学推导+技巧)
首先说一下。N*(N-1)/2为三角形数,随意一个自然数都最多可由三个三角形数表示。
对于,对于给定的要求值 V, 那么其一组解可表示为 V = 6*(K个三角形数的和)+K; 即随意由k个数组成的解 都有 (V-K)%6==0;
那么仅仅须要找到最小的K(1,2须要特判,结论最小值为3);
在对2进行特判时候,能够从两端到中间的线性扫描来做。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <map> using namespace std; typedef long long LL; const int N = 100005; int n,f[N]; void init(){ for(int i=1;;i++){ int num= 3*i*(i-1)+1; f[i]=num; if(num>1e9){ n=i; break; } } } int get(int v){ int p = lower_bound(f+1,f+1+n,v)-f; return f[p]==v; } int find_(int v){ int l=1,r=n; while(l<=r){ if(f[l] + f[r] < v) return 0; while(l<=r){ if(f[l]+f[r] < v) {r++; break;} else if(f[l]+f[r]==v) return 1; else r--; } l++; } return 0; } int main() { init(); int T; scanf("%d",&T); while(T--){ int k; scanf("%d",&k); if(get(k)) printf("1\n"); else{ int ok=0; if((k-2)%6 == 0){ if(find_(k)) {ok=1;} } if(ok) printf("2\n"); else { for(int i=3;i<=8;i++){ if((k-i)%6 == 0){ printf("%d\n",i); break; } } } } } return 0; }
HDU 5312(数学推导+技巧)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。