网站运营方案策划技巧-大眼的网站运营知识分享博客

网站运营

网站运营技巧策划方案分享
网站运营知识分享

站长资讯网站运营博客中心

day 15 我变强了!,今天模拟赛我第11!!!,得分200/300,感谢良心数据!; 以下是总结:

T1贪心,排序后第K大乘第K小即可,long long可过;

T2我不会做,得了三十分暴力分,听说有原题,题面是  1/x+1/y=1/(n!)  ,求有多少种x,y符合题意;

T3其实是二分图匹配,但我不会,写了个贪心+搜索,还好数据没卡我,得了70分;

于是得分100+30+70=200!;

开心开心。

T1

库特的向量(code)  #include<iostream> #include<cstdio> #include<cctype> #include<algorithm> using namespace std; long long a[1010],b[1010],n; long long ans; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } inline int cmp(int x,int y) { return x<y; } inline int cmp1(int x,int y) { return x>y; } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=read(); sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp1); for(int i=1;i<=n;i++) ans+=a[i]*b[i]; printf("%lld",ans); return 0; } View Code

T2

恭介的法则(rule)

经过我苦思冥想一顿调试,找出了一个方法:

1.分解n!的质因数,由于要分解的是(n!)2

但只需要将分解出的质数指数乘2即可,由约数个数定理可得出答案;

2.但这和原题(bzoj2721)(洛谷1445)不太一样,它不取模!;

于是,我们还需要高精度乘法;而且要压位!不然存不下;

于是,一段好看丑陋的代码产生了

#pragma GCC optimize(2) #include<iostream> #include<cstdio> using namespace std; const int maxn=3000000; long long n,num[maxn],ans[3000000]={0,1},size=1; void dec(int x) { while(x%2==0){ num[2]++;x/=2; } for(int i=3;i*i<=x;i+=2) while(x%i==0) num[i]++,x=x/i; if(x!=1) num[x]++; } void mul(long long x) { for(int i=1;i<=size;i++) ans[i]*=x; for(int i=1;i<size;i++) { if(ans[i]>=10000) { int temp=ans[i]/10000; ans[i]%=10000; ans[i+1]+=temp; } } while(ans[size]>=10000) { int temp=ans[size]/10000; ans[size]%=10000; ans[++size]+=temp; } } int main() { cin>>n; for(int i=1;i<=n;i++) dec(i); for(int i=1;i<=n;i++) if(num[i]) { mul(num[i]*2+1); } printf("%lld",ans[size]); for(int i=size-1;i>=1;i--) { printf("%lld",ans[i]/1000); printf("%lld",ans[i]/100%10); printf("%lld",ans[i]/10%10); printf("%lld",ans[i]%10); } printf("\n"); return 0; } View Code

但是,它tle了!于是,我继续修改;

经过同宿舍dalao——lx指点;

我AC了!

想法:由于每个num中的值可能很小,所以我们只要累积到一定大小再乘入答案;

这样就可以跑的飞快!

首页   建站经验   网站运营策划   网站运营方案   网站运营技巧   关于本站   地图