注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1156.变态的数学题  

2010-04-25 21:56:47|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Description

  zzz曾经遇到一个非常喜欢整人的老师,平时总喜欢出一些题目来刁难下同学。今天zzz和同学一起去海边烧烤去了,很晚才回到宿舍,更糟的是发现那老师留的、明天上课就要交的变态题目还没有做。题目给定数组A[1,...,N],数组B[1,...,N-K]由A生成,B[i] = A[1]*A[2]*...*A[N]/(A[i]*A[i+1]*...*A[i+K]),最终要求算出数组B中各元素累加之和。看完题目的数据量,zzz当时就傻了,想想这漫漫长夜又得无眠了,心情就变得无比的差,所以请你帮帮他吧,让累了一天的zzz能好好的睡一觉吧。

Input

  第一行输入两个正整数N,K(0<=K<=50, K < N <= 10000)。
  接下来N行给出数组A中的数,每个数字一行,且0<=A[i]<=32767 。

Output

  数组B中各元素累加之和,由于数字可能很大,请将结果模9973输出。

Sample Input

6 2
1
3
5
7
9
10

Sample Output

765

Source
xmu
 
题目意思很简单。如果直接按照题意去做的话会超时。时间复杂度为O(n^2),开始没有想到,后来朋友告诉,才知道是要用类似动态规划的备忘录来保存下来。还有一个致命的错误就是,刚开始以为如果a[i]中有一个是0的话,那么最后答案一定会是0,贡献了无数的WA。还是朋友比较强,推荐我再去学学高数,0/0不是0汗死。。可怜我的高数啊、别的不多讲了,直接贴个代码:
 
#include <iostream>
using namespace std;
int main()
{
 int n, k, a[10001], sum1[10001], sum2[10001];
 cin >> n >> k;
 int i;
 for(i = 1; i <= n; i++) cin >> a[i];
 sum1[0] = 1; sum2[n-k-1] = 1;
 for(i = 1; i < n - k; i++)
  sum1[i] = (sum1[i-1] * a[i]) % 9973;
 for(i = 1; i < n - k; i++)
  sum2[n-k-i-1] = (sum2[n-k-i] * a[n-i+1]) % 9973;
 int sum = 0;
 for(i = 0; i < n - k; i++)
  sum = (sum + sum1[i] * sum2[i] % 9973) % 9973;
 cout << sum << endl;
return 0;
}
  评论这张
 
阅读(178)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017