一月17日新生冬季练习赛解题报告C.孟婆汤

c也是好题啊

 

暴力水过之后  又重判了 额 有点悲哀   不过这也是一种 一种学习的机会啊  哈哈   废话不多说了  

 

c题之前应该做过类似的题   在网上说是腾讯的笔试题  解法不难想到  

 

题目是这样的 :

C.孟婆汤

Time Limit: 1000 MS

Memory Limit: 32768 K

 

Total Submit: 48 (19 users)

Total Accepted: 5 (5 users)

Special Judge: No

 

Description

男从戎,女守家。一夜,狼烟四起,男战死沙场。从此一道黄泉,两地离别。最后,女终于在等待中老去逝去。逝去的最后是换尽一生等到的相逢和团圆。

某日两人至奈何桥前,服下孟婆汤。

每滴孟婆汤都有强度不一的药效,设一碗孟婆汤共N(0N100000),其中第i滴(0iN)用b[i]表示。

孟婆汤的药效与原料有关,设熬制前同样有N滴原料,第i滴原料用a[i]表示,0a[i]2^32

药效b[i]的计算方法为b[i]=(a[0]*a[1]*...*a[N-1]/a[i])%m(假设0/0=1),0b[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]项之外所有的项相乘;

 

肿么办??

 

求每个元素都便利一遍?肯定是不行的时间复杂度on*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;

}

///代码没有注解   主要是理解  思路  思路理解  代码便是傻瓜代码了

 

 

腾讯笔试原题是这样的:

 

给定数组a[N]构造数组b [N]——腾讯笔试

分类: 笔试题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     }  

一月17日新生冬季练习赛解题报告C.孟婆汤

上一篇:POJ 2153 Rank List (map映射)


下一篇:explorer.exe进程简单介绍