【百度之星2014~初赛(第二轮)解题报告】JZP Set 博客分类: 百度之星 百度之星解题报告acmhdu
声明
笔者最近意外的发现 笔者的个人网站 http://tiankonguse.com/ 的很多文章被其它网站转载,但是转载时未声明文章来源或参考自 http://tiankonguse.com/ 网站,因此,笔者添加此条声明。
郑重声明:这篇记录《【百度之星2014~初赛(第二轮)解题报告】JZP Set》转载自 http://tiankonguse.com/ 的这条记录:http://tiankonguse.com/record/record.php?id=668
前言
最近要毕业了,有半年没做比赛了.
这次参加百度之星第二轮娱乐一下.
现在写一下 JZP Set 这道题的的解题报告.
正文
题意
题意是:给你n个数(1到n),给你一个规则,问用这个规则可以得到多少个合法的集合.
具体规则是:一个合法集合里任意挑两个数,如果这两个数之和是偶数,这个偶数除以2得到的数也要在这个合法集合里.
比如: 3 和9 在集合里,3+9是偶数,所以 (3+9)/2 = 6 也要在这个集合里.然后 {3,6,9}就是一个合法的集合.
起初我理解错题意了,以为是任意的两个数字之和除以2.比如 (3 + 6)/2 = 4, 我以为4也要在集合里.
于是很快得到一个 (n+1)*n/2 的公式.
后来学弟告诉我正确的题意.
分析
这个题的样例有10^5个,每个样例最大是10^7.
错误题意
首先来看看我理解错误题意时,是怎么做的.
假设 F(n) 是 n 的答案的话, 则 F(n + 1) = F(n) + f(n+1).
f(n+1)里面肯定有 n+1, 我假设f(n+1) 这些集合的任一个集合 S 里的最小值是 a, 则 (a+n+1)/2 肯定在 S 里面,然后这样递归下去发现 a到n+1的所有数字都必须在 S 里面.
于是 f(n+1) 就是 n+ 1 了.
于是最终方程就是 F(n+1) = F(n) + n+ 1.
只可惜这是错误的题意的做法.
正确题意
学弟告诉我正确的题意,还是可以很快写出方程来
F(n+1) = F(n) + f(n + 1).
其中f(n+1) 是含有 n+ 1的合法的集合.
奇数偶数合法<
首先对于我上面找到的那些肯定是合法集合的一部分,只是我遗漏了一些合法集合.
遗漏的肯定是非连续的了.
然后很快可以想到 一个奇数和一个偶数构成的集合都是合法集合.
于是 f(n + 1) 就又加上含有一奇一偶的合法集合的数量了,只是提交后WA了.
等差为奇数的组合
然后学弟随手写了一个集合 {3, 6, 9 } 发现也是合法集合.
然后我无意见把12添加进去后发现还是合法集合.
于是我们得出结论:等差为奇数的数列都是合法集合,对于连续的那个只不过是等差为1罢了.
于是我们假设 i/x 的个数为 num(i/x),
于是有
则最终答案是
C( num (n / 1) , 2) + C( num (n / 3) , 2) + C( num (n / 5) , 2) + ...
也就是等差位 x 的数列里,我们随便挑一段都是合法集合.
只是到这一步我们发现这样做还是超时.
递推的等差数列
由于F(n+1) 与 F(n) 有很大的关系,所以我们尝试找找递推行不行.
还是这个公式
F(n) = F(n-1) + f(n).
f(n) 代表含有 n 的合法集合.
然后这些集合需要全是等差数列.
于是写了这么一个公式
f(n-1) =
n/1 + n/3 + n/5 + ....
然后就没什么想法了.
今天看了这个解题报告才知道可以这样做.
发现我们如果写出 f(n-2) 那一项的公式
(n-1)/1 + (n-1)/3 + (n-1)/5 + ...
这两个公式大部分项是相等的,只有个别的几个不相等.
自己举了几个例子发现 n 整除 下面的项时,这个除式会多一个.
比如 n = 12 则 12/3 = 4, 11/3 = 3.
这样这个f(n)函数就可以转化为
f( n ) = f( n - 1) + Count( n -1 ).
其中 Count( n ) 代表 n 的奇数约数个数.
然后小舟学长的模板上刚好有求关于小于 n 的所有数的约数的个数.其中有 O( n*log(n) ) 的模板,也有 O( n ) 的模板,
由于 n*log(n) 的模板比较简单,也可以过这道题,于是我就是用 n*log(n) 的模板了.
代码
/************************************************************************* > File Name: 4.2.cpp > Author: tiankonguse > Mail: i@tiankonguse.com > Created Time: Mon 26 May 2014 01:06:18 PM CST ***********************************************************************/ #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<string> #include<queue> #include<map> #include<cmath> #include<stack> #include<algorithm> #include<functional> #include<stdarg.h> using namespace std; #ifdef __int64 typedef __int64 LL; #else typedef long long LL; #endif const int N = 10000010; LL nod[N]; LL count[N]; LL ans[N]; void __sieve_nod() { memset(nod, 0,sizeof(nod)); for (int i = 1; i < N; i+=2) { for (int j = i; j < N; j += i) { ++nod[j]; } } } void init(){ ans[0] = 1; ans[1] = 2; LL count = 1; for(int i=2;i<N;i++){ count += nod[i-1]; ans[i] = ans[i-1] + count; } } int main() { __sieve_nod(); init(); int t,n; scanf("%d",&t); for(int i=1; i<=t; i++) { scanf("%d",&n); printf("Case #%d:\n%I64d\n",i,ans[n]); } return 0; }
参考
下一篇: php文件下传介绍