有2009张卡片,每张卡片一面为金色,另一面为黑色,且在一张长桌子上排成一排.开始时,所有卡片的金色面朝上.两个玩家站在桌子的同侧,且交替地进行操作.每次操作规则如下:选择相邻的5O张卡片,且最左边的一张卡片的金色面朝上,其翻转卡片,使得金色面朝上的变为黑色面朝上,黑色面朝上的变为金色面朝上,并规定最后一个按上述规则操作的玩家获胜.问:(1)操作是否一定会结束?(2)先操作的玩家是否有取胜策略?
A、是,是
B、是,否
C、否,是
D、否,否
区间[1,n]内有n个数字。现在按顺序进行n次操作,操作有以下两种:
1.给你三个整数L,R,K。把[L,R]的数字都修改成k
2.给你两个整数L,R。询问[L,R]的数字之和
对于所有的L,R,K,有
1<=L<=R<=n
k为整数,且绝对值小于10的9次方
访问或修改一个数字需要消耗1个单位的时间
现在要求设计一种效率尽可能高的算法来正确回答所有的操作2。
效率高的算法要求随着n规模增长,所花时间T的增长尽可能慢。
如T与n^2成正比的算法,效率就要低于T与n成正比的算法。
那么最优情况下,T与下列哪个选项成正比?
提示:可以使用额外的空间来记录信息。
A、n^3
B、n^2
C、n*sqrt(n) (sqrt表示平方根)
D、n*log(n) (由于不考虑正比系数,所以log的底数可以忽略)
E、n
F、sqrt(n)
G、log(n)
H、1
新浪微博 70,000+
移动应用