2016"百度之星" - 初赛(Astar Round2B)解题报告

此文章可以使用目录功能哟↑(点击上方[+])

被自己蠢哭,去年还能进一下复赛,今年复赛都没戏了...

链接→2016"百度之星" - 初赛(Astar Round2B)

 Problem 1001 区间的价值

Accept: 0    Submit: 0
Time Limit: 10000/5000 mSec(Java/Others)    Memory Limit : 65536 KB

 Problem Description

 Input

 Output

 Sample Input

5
1 6 2 4 4

 Sample Output

36
16
12
12
6

 Problem Idea

解题思路:首先,我们可以用RMQ(理论上来说线段树也是可以的,查询O(logn),n次正好为O(nlogn),而ST算法预处理O(nlogn),查询O(1))预处理O(nlogn)出区间最大值,然后枚举区间的最小值点
为了枚举最小值点,我们需要知道每一个点作为最小值点左右可以延伸的最大范围l[i],r[i],求这两个数组可以用dp来做
预处理完之后,枚举最小值点,更新长度为r[i]-l[i]+1的区间的答案
枚举完之后,我们得到了一组值,但这并不是最后的答案
这是因为我们发现假如有一个最优区间,我们一定可以正好处理到或者处理到比这个区间的区间,也就是说我们求的区间最大的值具有向下的包含性
举例来说,假如当前处理的区间为l[i],r[i],得到了答案ans,那么任何长度小于等于r[l]-l[I]+1的区间的答案都至少为ans
所以我们再用线性的时间递推求出答案即可

题目链接→HDU 5696 区间的价值

 Source Code

[cpp] view
plain
 copy

 print?

  1. /*Sherlock and Watson and Adler*/  
  2. #pragma comment(linker, "/STACK:1024000000,1024000000")  
  3. #include<stdio.h>  
  4. #include<string.h>  
  5. #include<stdlib.h>  
  6. #include<queue>  
  7. #include<stack>  
  8. #include<math.h>  
  9. #include<vector>  
  10. #include<map>  
  11. #include<set>  
  12. #include<cmath>  
  13. #include<complex>  
  14. #include<string>  
  15. #include<algorithm>  
  16. #include<iostream>  
  17. #define exp 1e-10  
  18. using namespace std;  
  19. const int N = 100005;  
  20. const int M = 40;  
  21. const int inf = 100000000;  
  22. const int mod = 2009;  
  23. int s[N],n,maxnum[N][20],l[N],r[N];  
  24. __int64 ans[N];  
  25. void RMQ()          //预处理  O(nlogn)  
  26. {  
  27.     int i,j;  
  28.     int m=(int)(log(n*1.0)/log(2.0));  
  29.     for(i=1;i<=n;i++)  
  30.         maxnum[i][0]=s[i];  
  31.     for(j=1;j<=m;j++)  
  32.         for(i=1;i+(1<<j)-1<=n;i++)  
  33.             maxnum[i][j]=max(maxnum[i][j-1],maxnum[i+(1<<(j-1))][j-1]);  
  34. }  
  35. int Ask_MAX (int a,int b)   //O(1)  
  36. {  
  37.     int k=int(log(b-a+1.0)/log(2.0));  
  38.     return max(maxnum[a][k],maxnum[b-(1<<k)+1][k]);  
  39. }  
  40. int main()  
  41. {  
  42.     int i,k;  
  43.     while(~scanf("%d",&n))  
  44.     {  
  45.         memset(ans,0,sizeof(ans));  
  46.         for(i=1;i<=n;i++)  
  47.         {  
  48.             scanf("%d",&s[i]);  
  49.             l[i]=r[i]=i;  
  50.         }  
  51.         RMQ();  
  52.         for(i=2;i<=n;i++)  
  53.         {  
  54.             k=i-1;  
  55.             while(s[i]<=s[k])  
  56.                 k=l[k]-1;  
  57.             l[i]=k+1;  
  58.         }  
  59.         for(i=n-1;i>0;i--)  
  60.         {  
  61.             k=i+1;  
  62.             while(s[i]<=s[k])  
  63.                 k=r[k]+1;  
  64.             r[i]=k-1;  
  65.         }  
  66.         for(i=1;i<=n;i++)  
  67.             ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],(__int64)Ask_MAX(l[i],r[i])*s[i]);  
  68.         for(i=n-1;i>0;i--)  
  69.             ans[i]=max(ans[i+1],ans[i]);  
  70.         for(i=1;i<=n;i++)  
  71.             printf("%I64d\n",ans[i]);  
  72.     }  
  73.     return 0;  
  74. }  

 Problem 1003 瞬间移动

Accept: 0    Submit: 0
Time Limit: 4000/2000 mSec(Java/Others)    Memory Limit : 65536 KB

 Problem Description

有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第n行第m列的格子有几种方案,答案对1000000007取模。

 Input

多组测试数据。

两个整数n,m(2≤n,m≤100000)

 Output

一个整数表示答案

 Sample Input

4 5

 Sample Output

10

 Problem Idea

解题思路:除去起点(1,1)和终点(n,m)已经固定,中间能经过的是一个(n-2)*(m-2)的矩阵

然后我们可以在这个矩阵里取0个(就是直接从起点跳到终点)、1个、2个……min(n,m)-2个间接点

而对于取i个间接点,其实就是确定这i个间接点行数与列数有多少种取法

于是,我们得到了组合数公式(假设n<m,此题n,m和m,n结果是一样的,过我们可以交换n,m实现n<m)

组合数的求解我们可以交给Lucas定理,但是这个公式,我们还需要化简,不然计算100000项的组合数还是会超时

为了让式子看起来更简洁,对于输入的n与m,我们预处理-2,即n-=2,m-=2,这样上述式子就变成了

化简

剩下的就是套Lucas模板了,嫌时间长的还可以进行阶乘预处理

题目链接→HDU 5698 瞬间移动

 Source Code

[cpp] view
plain
 copy

 print?

  1. /*Sherlock and Watson and Adler*/  
  2. #pragma comment(linker, "/STACK:1024000000,1024000000")  
  3. #include<stdio.h>  
  4. #include<string.h>  
  5. #include<stdlib.h>  
  6. #include<queue>  
  7. #include<stack>  
  8. #include<math.h>  
  9. #include<vector>  
  10. #include<map>  
  11. #include<set>  
  12. #include<cmath>  
  13. #include<complex>  
  14. #include<string>  
  15. #include<algorithm>  
  16. #include<iostream>  
  17. #define exp 1e-10  
  18. using namespace std;  
  19. const int N = 100005;  
  20. const int M = 100;  
  21. const int inf = 1600000000;  
  22. const int p = 1000000007;  
  23. typedef long long LL;  
  24.   
  25. LL quick_mod(LL a, LL b)  
  26. {  
  27.     LL ans = 1;  
  28.     a %= p;  
  29.     while(b)  
  30.     {  
  31.         if(b & 1)  
  32.         {  
  33.             ans = ans * a % p;  
  34.             b--;  
  35.         }  
  36.         b >>= 1;  
  37.         a = a * a % p;  
  38.     }  
  39.     return ans;  
  40. }  
  41.   
  42. LL C(LL n, LL m)  
  43. {  
  44.     if(m > n) return 0;  
  45.     LL ans = 1;  
  46.     for(int i=1; i<=m; i++)  
  47.     {  
  48.         LL a = (n + i - m) % p;  
  49.         LL b = i % p;  
  50.         ans = ans * (a * quick_mod(b, p-2) % p) % p;  
  51.     }  
  52.     return ans;  
  53. }  
  54.   
  55. LL Lucas(LL n, LL m)  
  56. {  
  57.     if(m == 0) return 1;  
  58.     return C(n % p, m % p) * Lucas(n / p, m / p) % p;  
  59. }  
  60.   
  61. int main()  
  62. {  
  63.     __int64 n,m;  
  64.     int i;  
  65.     while(~scanf("%I64d%I64d",&n,&m))  
  66.     {  
  67.         n-=2,m-=2;  
  68.         if(n>m)  
  69.             swap(n,m);  
  70.         printf("%I64d\n",Lucas(m+n,n));  
  71.     }  
  72.     return 0;  
  73. }  

[cpp] view
plain
 copy

 print?

  1. /*Sherlock and Watson and Adler*/  
  2. #pragma comment(linker, "/STACK:1024000000,1024000000")  
  3. #include<stdio.h>  
  4. #include<string.h>  
  5. #include<stdlib.h>  
  6. #include<queue>  
  7. #include<stack>  
  8. #include<math.h>  
  9. #include<vector>  
  10. #include<map>  
  11. #include<set>  
  12. #include<cmath>  
  13. #include<complex>  
  14. #include<string>  
  15. #include<algorithm>  
  16. #include<iostream>  
  17. #define exp 1e-10  
  18. using namespace std;  
  19. const int N = 200005;  
  20. const int M = 40;  
  21. const int inf = 100000000;  
  22. const int mod = 1000000007;  
  23. __int64 fac[N];  
  24. void init()//阶乘预处理  
  25. {  
  26.     fac[0]=1;  
  27.     for(int i=1;i<=N;i++)  
  28.         fac[i]=i*fac[i-1]%mod;  
  29. }  
  30. __int64 pow_mod(__int64 a,__int64 b)  
  31. {  
  32.     __int64 s=1;  
  33.     a=a%mod;  
  34.     while(b)  
  35.     {  
  36.         if(b&1)  
  37.             s=s*a%mod;  
  38.         a=a*a%mod;  
  39.         b>>=1;  
  40.     }  
  41.     return s;  
  42. }  
  43. __int64 C(int n,int m)  
  44. {  
  45.     if(n==0||m==0)  
  46.         return 1;  
  47.     return  fac[n]*pow_mod(fac[m]*fac[n-m]%mod,mod-2)%mod;  
  48. }  
  49. int main()  
  50. {  
  51.     int n,m;  
  52.     init();  
  53.     while(~scanf("%d%d",&n,&m))  
  54.     {  
  55.         n-=2;m-=2;  
  56.         printf("%I64d\n",C(m+n,min(n,m))%mod);  
  57.     }  
  58.     return 0;  
  59. }  

 Problem 1005 区间交

Accept: 0    Submit: 0
Time Limit: 8000/4000 mSec(Java/Others)    Memory Limit : 65536 KB

 Problem Description

 Input

 Output

一行表示答案

 Sample Input

5 2 3
1 2 3 4 6
4 5
2 5
1 4

 Sample Output

10

 Problem Idea

解题思路:此题的做法有很多种,不过有种利用STL来解的做法,我觉得挺巧妙的

首先利用vector将区间分组,将所有具有公共左端点的区间划分成一组,比如[3,7],[3,11],[3,4]等,这些都是一组的

接下来就是利用multiset来进行模拟了(顺带提一句,这里不能用set,而用multiset,是因为set无法存储重复相同的数)

对于当前所在位置i,将所有以i作为左端点的区间右端点值插入multiset(multiset内的数默认从小到大排列)中

若multiset的大小超过了k,那我就删除multiset内最小的值直到小于等于k(之所以删除最小的值,是因为在左端点固定的情况下,右端点越小,会使得区间交的位置数越少)

当且仅当multiset大小恰好等于k,且multiset中当前最小的右端点值≥i时,我们找到了一种符合题目要求的区间取法,于是我们更新答案

当然,在开始的时候,我们需要预处理前n项和sum[n]

题目链接→HDU 5700 区间交

 Source Code

[cpp] view
plain
 copy

 print?

  1. /*Sherlock and Watson and Adler*/  
  2. #pragma comment(linker, "/STACK:1024000000,1024000000")  
  3. #include<stdio.h>  
  4. #include<string.h>  
  5. #include<stdlib.h>  
  6. #include<queue>  
  7. #include<stack>  
  8. #include<math.h>  
  9. #include<vector>  
  10. #include<map>  
  11. #include<set>  
  12. #include<cmath>  
  13. #include<complex>  
  14. #include<string>  
  15. #include<algorithm>  
  16. #include<iostream>  
  17. #define exp 1e-10  
  18. #define bitnum(a) __builtin_popcount(a)  
  19. using namespace std;  
  20. const int N = 100005;  
  21. const int M = 10;  
  22. const int inf = 1600000000;  
  23. const int mod = 2009;  
  24. __int64 sum[N],ans;  
  25. multiset<int> s;  
  26. vector<int> v[N];  
  27. int main()  
  28. {  
  29.     int n,k,m,i,j,l,r;  
  30.     while(~scanf("%d%d%d",&n,&k,&m))  
  31.     {  
  32.         s.clear();ans=0;  
  33.         for(i=1;i<=n;i++)  
  34.         {  
  35.             scanf("%I64d",&sum[i]);  
  36.             sum[i]+=sum[i-1];  
  37.             v[i].clear();  
  38.         }  
  39.         for(i=0;i<m;i++)  
  40.         {  
  41.             scanf("%d%d",&l,&r);  
  42.             v[l].push_back(r);  
  43.         }  
  44.         for(i=1;i<=n;i++)  
  45.         {  
  46.             for(j=0;j<v[i].size();j++)  
  47.                 s.insert(v[i][j]);  
  48.             while(s.size()>k)  
  49.                 s.erase(s.begin());  
  50.             if(s.size()==k&&*s.begin()>=i)  
  51.                 ans=max(ans,sum[*s.begin()]-sum[i-1]);  
  52.         }  
  53.         printf("%I64d\n",ans);  
  54.     }  
  55.     return 0;  
  56. }  

 Problem 1006 中位数计数

Accept: 0    Submit: 0
Time Limit: 12000/6000 mSec(Java/Others)    Memory Limit : 65536 KB

 Problem Description

中位数定义为所有值从小到大排序后排在正中间的那个数,如果值有偶数个,通常取最中间的两个数值的平均数作为中位数。

现在有n个数,每个数都是独一无二的,求出每个数在多少个包含其的区间中是中位数。

 Input

多组测试数据

第一行一个数n(n≤8000)

第二行n个数,0≤每个数≤

 Output

N个数,依次表示第i个数在多少包含其的区间中是中位数。

 Sample Input

5
1 2 3 4 5

 Sample Output

1 2 3 2 1

 Problem Idea

解题思路:很显然,此题O(n^2logn)的暴力做法必然会TLE,所以我们要想办法做到O(n^2)的复杂度

首先对于第i个数,我们从i-1个数开始递减,分别与第i个数进行比较,假设比第i个数大的数的个数即为l,比第i个数小的数的个数即为r,dp[l-r=k]则为[比第i个数的数的个数]比[比第i个数的数的个数]多k个的区间个数,那要保证第i个数是区间内的中位数,我只需要在第i个数的右边找有多少个[比第i个数的数的个数]比[比第i个数的数的个数]多k个的区间,这样两个区间连接起来,正好[比第i个数的数的个数]与[比第i个数的数的个数]一样多,这样,第i个数就是此区间内的中位数

另外,因为数组下标必须为非负整数,故把数组的中心点移至8000,即dp[8000+k],这样就保证了下标一定是符合要求的

题目链接→HDU 5701 中位数计数

 Source Code

[cpp] view
plain
 copy

 print?

  1. /*Sherlock and Watson and Adler*/  
  2. #pragma comment(linker, "/STACK:1024000000,1024000000")  
  3. #include<stdio.h>  
  4. #include<string.h>  
  5. #include<stdlib.h>  
  6. #include<queue>  
  7. #include<stack>  
  8. #include<math.h>  
  9. #include<vector>  
  10. #include<map>  
  11. #include<set>  
  12. #include<cmath>  
  13. #include<complex>  
  14. #include<string>  
  15. #include<algorithm>  
  16. #include<iostream>  
  17. #define exp 1e-10  
  18. using namespace std;  
  19. const int N = 8005;  
  20. const int M = 8000;  
  21. const int inf = 100000000;  
  22. const int mod = 1000000007;  
  23. int s[N],dp[2*N];  
  24. int main()  
  25. {  
  26.     int n,i,j,k,ans;  
  27.     while(~scanf("%d",&n))  
  28.     {  
  29.         for(i=0;i<n;i++)  
  30.             scanf("%d",&s[i]);  
  31.         for(i=0;i<n;i++)  
  32.         {  
  33.             memset(dp,0,sizeof(dp));  
  34.             dp[M]=1;  
  35.             for(k=0,j=i-1;j>=0;j--)  
  36.             {  
  37.                 if(s[j]>s[i])  
  38.                     k++;  
  39.                 else  
  40.                     k--;  
  41.                 dp[M+k]++;  
  42.             }  
  43.             for(ans=dp[M],k=0,j=i+1;j<n;j++)  
  44.             {  
  45.                 if(s[j]>s[i])  
  46.                     k++;  
  47.                 else  
  48.                     k--;  
  49.                 ans+=dp[M-k];  
  50.             }  
  51.             printf("%d%c",ans,i!=n-1?' ':'\n');  
  52.         }  
  53.     }  
  54.     return 0;  
  55. }  

菜鸟成长记

时间: 2024-03-23 17:29:18

2016"百度之星" - 初赛(Astar Round2B)解题报告的相关文章

2012“Astar百度之星”大赛启动

近日,"Astar百度之星"编程大赛在清华大学拉开帷幕,旨在让编程爱好者们通过自己擅长的程序代码,获得"改变世界的荣耀感".据悉,本次资格赛的参赛人数将挑战全球"同时参与人数最多的在线编程"纪录,在大赛中脱颖而出的选手还将进入百度公司校园招聘"绿色通道",直接获得加盟百度的优先通行证,与世界顶级工程师共事.同时,本届Astar百度之星还将"公益编程大赛"作为辅线赛事,号召参赛者共同关注社会问题.另外,&qu

第五届“Astar百度之星程序设计大赛”正式向全国高校学生启动

本报讯(记者高天赋 实习生沈梦菲)近日,第五届"Astar百度之星程序设计大赛"正式面向全国高校学生启动. "Astar百度之星程序设计大赛"是百度公司从2005年起创办的一项校园赛事,旨在为广大程序设计爱好者搭建一个比试身手.切磋交流的平台,大赛创办至今已经吸引了数万名参与者,众多程序设计高手通过大赛脱颖而出. 据介绍,今年的"Astar百度之星程序设计大赛"面向全国所有高校的在校学生,不分年级.专业,均可报名参加,通过在线资格赛.晋级赛等一系

第五届Astar百度之星程序设计大赛启动

本报讯(记者高天赋 实习生沈梦菲)近日,第五届"Astar百度之星程序设计大赛"正式面向全国高校学生启动. "Astar百度之星程序设计大赛"是百度公司从2005年起创办的一项校园赛事,旨在为广大程序设计爱好者搭建一个比试身手.切磋交流的平台,大赛创办至今已经吸引了数万名参与者,众多程序设计高手通过大赛脱颖而出. 据介绍,今年的"Astar百度之星程序设计大赛"面向全国所有高校的在校学生,不分年级.专业,均可报名参加,通过在线资格赛.晋级赛等一系

百度之星编程大赛落幕六年发掘十万计算机精英

挖贝网7月28日消息 经过两个多月的激烈角逐,2010年7月28日,由百度主办的"2010 Astar百度之星程序设计大赛"正式在京落下帷幕,来自浙江大学的杭航表现出色,从三万多名参赛的程序设计高手中脱颖而出,最终捧得"2010年百度之星"桂冠.而在其余8名二.三等奖获得者中,山东师大附中魏铭等几位高中生的身影,也成为当天比赛的一大亮点. 作为中国互联网中规模最大.最具影响力的程序开发设计赛事,"Astar百度之星程序设计大赛"自2005年创办来

2009百度之星程序设计大赛启动

中介交易 http://www.aliyun.com/zixun/aggregation/6858.html">SEO诊断 淘宝客 云主机 技术大厅 5月5日,a*star2009百度之星程序设计大赛,以"Code人心弦"为宣传口号全面启动. 据悉,从5月5日到5月29日,均可在大赛官网注册.大赛官网包含赛事规则.赛题集锦.答题指南等详细信息,选手可在此处了解最新消息,为比赛做充分准备. 整个赛事一直延续到2009年7月中旬,包括5月底的网络资格赛(初赛).6月中旬的网

百度之星Astar2009程序设计大赛落幕

7月23日消息,由百度举办的"百度之星Astar2009程序设计大赛"在京圆满落幕.来自复旦大学的冯国栋表现出色,从两万多名参赛的程序设计高手中脱颖而出,最终捧得了"2009年百度之星"桂冠. 自2005年创办以来,"Astar百度之星程序设计大赛"已经成为中国互联网中规模最大.最具影响力的程序开发设计赛事.据主办方百度介绍,今年的大赛历时2个月,参赛选手包括清华.北大.复旦.香港中文大学等1000多所高校,以及全国百强中学的部分高中学生,这也代

百度之星Astar2009程序设计大赛落幕 复旦学子夺冠

中介交易 SEO诊断 淘宝客 云主机 技术大厅 2009年7月23日,由全球最大的中文搜索引擎百度举办的"百度之星Astar2009程序设计大赛"在京圆满落幕.来自复旦大学的冯国栋表现出色,从两万多名参赛的程序设计高手中脱颖而出,最终捧得了"2009年百度之星"桂冠. 自2005年创办以来,"Astar百度之星程序设计大赛"已经成为中国互联网中规模最大.最具影响力的程序开发设计赛事.据主办方百度介绍,今年的大赛历时2个月,参赛选手包括清华.北大.

百度之星程序设计大赛开幕

5月20日,百度举办的"2011Astar百度之星程序设计大赛"(http://star.baidu.com/)面向全国高校学生和广大编程爱好者拉开帷幕.本届"Astar大赛"除延续往届的赛程及奖励办法外,还将特别增设不少激烈而极具趣味的"关卡",让众多热爱编程的年轻"极客"们能充分展现自我,从实战中快速获得提升. 已经成功举办六届的"Astar百度之星程序设计大赛"是国内参赛人数最多.影响力最大的程序赛事

2013百度之星冠军乔明达专访:我的冠军之路

硅谷网8月19日讯 从2013百度之星5月东部区域赛冠军,到2013国际信息学奥林匹克(IOI)竞赛第二名,再到2013百度之星总决赛冠军,乔明达2013年的编程之路可谓是一路畅通无阻的冠军之路.在赛后冠军采访的过程中,经常面带微笑的乔明达在镜头前稍显有一点局促,然而就是这样一位腼腆的南京外国语学校的高三学生在比赛现场赢得了最多的掌声和尊重. 在三个月前的区域赛冠军采访中,乔明达告诉我们他学编程的时间比一般人要稍早一些.小学五年级第一次接触编程时他对此一无所知,但当他发现编程是一个可以促进从无到