c题也是好题啊
暴力水过之后 又重判了 额 有点悲哀 不过这也是一种 一种学习的机会啊 哈哈 废话不多说了
c题之前应该做过类似的题 在网上说是腾讯的笔试题 解法不难想到
题目是这样的 :
C.孟婆汤 | |||||
| |||||
Description | |||||
男从戎,女守家。一夜,狼烟四起,男战死沙场。从此一道黄泉,两地离别。最后,女终于在等待中老去逝去。逝去的最后是换尽一生等到的相逢和团圆。 某日两人至奈何桥前,服下孟婆汤。 每滴孟婆汤都有强度不一的药效,设一碗孟婆汤共N滴(0<N<100000),其中第i滴(0≤i<N)用b[i]表示。 孟婆汤的药效与原料有关,设熬制前同样有N滴原料,第i滴原料用a[i]表示,0≤a[i]<2^32。 药效b[i]的计算方法为b[i]=(a[0]*a[1]*...*a[N-1]/a[i])%m(假设0/0=1),0<b[i]<2^32。 | |||||
Input | |||||
多组输入数据。 每组第一行给出原料数量N,取模数m,紧接着的一行按顺序给出原料a[i]。 | |||||
Output | |||||
求出熬制所成每份孟婆汤的药效b[i],每份之间用空格隔开,每组数据之后以换行结尾。 | |||||
Sample Input | |||||
5 11 2 7 5 3 9 3 7 9 8 5 | |||||
Sample Output | |||||
10 6 4 3 1 5 3 2 |
第一眼我们就能看出来 b[i]就是除了a[i]项之外所有的项相乘;
肿么办??
求每个元素都便利一遍?肯定是不行的时间复杂度o(n*n) 额……
所以肯定不能那么暴力
不过 我们这样想 b[i]不就是前面的乘积乘上后面的乘积吗 就差一点就找到出路了
是不是很兴奋 啊啊啊啊啊 是啊
我们可以开两个数组 :
第一个数组 第i项表示前i项的乘积
的二个数组 第i项表示i+1项到最后一项的乘积
问题迎刃而解 时间复杂度完全降下来
是不是很开森呐 是啊
那我们用代码来实现吧:
#include<iostream>
#include<string.h>
using namespace std;
long long int a[100001];
long long int Start[100001],End[100001];
int main()
{
long long int n;
long long int mod;
std::ios::sync_with_stdio(false);
while(cin>>n>>mod)
{
Start[0]=1;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]%=mod;
Start[i]=Start[i-1]*a[i];
Start[i]%=mod;
}
End[n+1]=1;
for(int i=n;i>=1;i--){
End[i]=End[i+1]*a[i];
End[i]%=mod;
}
cout<<End[2];
for(int i=2;i<=n;i++)
cout<<" "<<(Start[i-1]*End[i+1])%mod;
cout<<endl;
}
return 0;
}
///代码没有注解 主要是理解 思路 思路理解 代码便是傻瓜代码了
腾讯笔试原题是这样的:
分类: 笔试题2012-08-07 23:07 2278人阅读 评论(3) 收藏 举报
给定一个数组a[N],我们希望构造数组b [N],其中b[j]=a[0]*a[1]…a[N-1] / a[j],在构造过程中,不允许使用除法:要求O(1)空间复杂度和O(n)的时间复杂度;除遍历计数器与a[N] b[N]外,不可使用新的变量(包括栈临时变量、堆空间和全局静态变量等)
解析:设b[0]=1
由b[i]=b[i-1]*a[i-1]可得
b[1] = a[0]
b[2] = a[0]a[1]
…
b[i] = a[0]a[1]a[2]…a[i-1]
…
b[n-1] = a[0]a[1]…a[n-2]
那么再通过b[0]这个变量来迭代出1, a[n-1], a[n-2]a[n-1], a[n-3]a[n-2]a[n-1], … , a[1]a[2]a[3]…a[n-1],迭代过程中分别乘以b[n-1], b[n-2], … , b[0]
代码如下
1 for (int i = 1; i <= n-1; i++)
2 {
3 b[i] = b[i-1]*a[i-1];
4 }
5
6 for (int i = n-1; i >= 1; i--)
7 {
8 b[i] *= b[0];
9 b[0] *= a[i];
10 }