首页 > 代码库 > HDU 4961(杭电多校#9 1002题)Boring Sum(瞎搞)
HDU 4961(杭电多校#9 1002题)Boring Sum(瞎搞)
题目地址:HDU 4961
看来这题的测试数据是随机的。不然出了极限数据还真过不了。。。这题我的方法是建一个哈希结构体,记录两个变量,分别是num位置,然后是f,f==0表示这个数没出现过,f==1表示这个数出现过。然后分别从前面和后面扫一遍。每次扫的时候,对每一个出现的数都进行标记。然后对当前的数枚举该数的倍数,全部枚举完,取位置num最大的。然后找完之后,对哈希结构体进行更新。如果前面曾经出现过的话,就直接换掉,因为后面的数总比前面的更优。最后扫完两遍之后两个数组就能求出来了。计算就行了。
代码如下:
#include <cstring> #include <cstdio> #include <math.h> #include <algorithm> using namespace std; #define LL __int64 struct node { LL num, f; }_hash[110000]; LL a[110000], b[110000], c[110000]; int main() { LL n, i, j, sum, max1, mmax; LL ans; while(scanf("%I64d",&n)!=EOF&&n) { max1=-1; for(i=1;i<=n;i++) { scanf("%I64d",&a[i]); if(max1<a[i]) max1=a[i]; } for(i=1;i<=max1;i++) _hash[i].f=0; for(i=1;i<=n;i++) { mmax=-1; for(j=a[i];j<=max1;j+=a[i]) { if(_hash[j].f) { if(mmax<_hash[j].num) { mmax=_hash[j].num; } } } _hash[a[i]].f=1; _hash[a[i]].num=i; if(mmax==-1) b[i]=a[i]; else b[i]=a[mmax]; } for(i=1;i<=max1;i++) _hash[i].f=0; for(i=n;i>=1;i--) { mmax=1e7;; for(j=a[i];j<=max1;j+=a[i]) { if(_hash[j].f) { if(mmax>_hash[j].num) { mmax=_hash[j].num; } } } _hash[a[i]].f=1; _hash[a[i]].num=i; if(mmax==1e7) c[i]=a[i]; else c[i]=a[mmax]; } ans=0; for(i=1;i<=n;i++) { ans+=b[i]*c[i]; //printf("b==%d c==%d\n",b[i],c[i]); } printf("%I64d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。