首页 > 试题广场 >

密码生成

[编程题]密码生成
  • 热度指数：6527 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小汪作为一个有数学天分的程序猿，设计了一套密码生成器来搞定自己的密码问题。
密码生成器由 N 个槽位组成，槽位的下标为 0~N-1 ，每个槽位存储一个数。起初每个槽位都是 0 。
密码生成器会进行 M 轮计算，每轮计算，小汪会输入两个数 L , R (L<=R),密码生成器会将这两个数作为下标，将两个下标之间（包含）的所有槽位赋值为 i（ i 为当前的轮次， i ∈ [1,M]）。
M轮计算完成后，密码生成器会根据槽位的最终值生成一条密码，密码的生成规则为：
（0*a[0] + 1*a[1] + 2*a[2] + ... + (N-1)*a[N-1]) mod 100000009
其中a[i]表示第i个槽位的最终值。
请帮助小汪把他的密码生成器实现为代码。

数据范围： 
对于前30%的测试数据，保证 N,M<=10000
对于前50%的测试数据，保证 N,M<=200000
对于100%的测试数据，保证 N<=1.5*10^7,M<=200000

输入描述:
第一行为两个整数N,M,表示槽位个数和计算轮数。
接下来M行，每行两个整数Li,Ri，表示第i轮计算的输入。


输出描述:
输出一行，一个整数A,表示小汪的开机密码。
示例1

输入

5 3
2 3
1 2
1 1

输出

10

说明

对于输入样例，密码生成过程如下：

初始：  0 0 0 0 0
第1轮：0 0 1 1 0
第2轮：0 2 2 1 0
第3轮：0 3 2 1 0
密码生成器最终生成 0 3 2 1 0，则密码为(0*0 + 3*1 + 2*2 + 1*3 + 0*4) mod 100000009 = 10

备注:
mod 表示取余操作，a mod b表示a,b相除得到的余数
对于前30%的测试数据，保证 N,M<=10000
对于前50%的测试数据，保证 N,M<=200000
对于100%的测试数据，保证 N<=1.5*10^7,M<=200000
算法知识视频讲解
添加回答
Python
勇敢牛牛不怕面试头像 勇敢牛牛不怕面试 
NM = input().split()
n,times = int(NM[0]),int(NM[1])
org = [0]*n
for i in range(times):
    LR = input().split()
    L,R = int(LR[0]),int(LR[1])
    org[L:R+1] = [i+1]*(R+1-L)
ans = 0
for j in range(n):
    ans+= j*org[j]
print(ans % 100000009)

只能过30%
```

编辑于 2021-08-17 11:24:14 回复(0)
Python
谈小峰头像 谈小峰 


'只能通过30%的测试用例，时间复杂度太高了，不知道应该怎么修改'

n,m = map(int,input().split())
init = [0]*n
for x in range(1,m+1):
    i,j = map(int,input().split())
    init[i:j+1]=[x]*(j-i+1)
w = list(range(n))
A = sum(map(lambda a, b: a*b,w,init))
print(A % 100000009)

编辑于 2020-07-11 20:12:10 回复(0)
提交观点

问题信息

C++工程师 golang工程师 搜狗 小米集团 测试工程师 PHP工程师 2020 2021 Java工程师
来自：【2021】小米秋招软...
上传者：小小
难度：
2条回答 150656浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号