#P2244. 时间复杂度3
时间复杂度3
这是代码阅读单选题,每小题10分,共100分。
采用本题专用的理想模型:1秒最多执行 次基本操作。只将一次 work() 调用计为一次基本操作;循环控制、比较、赋值、函数调用和其他语句的开销均忽略。基本操作次数超过 才判为超时,恰好等于时不超时。这是学习用模型,不代表实际评测机耗时。
代码使用 C++14,work() 已定义且会正常返回。整数类型足够大,没有溢出;循环均会正常结束。代码片段按给定常量独立执行。请选择基本操作次数和是否超时均正确的一项。
1. 单选题(10分)
阅读下列代码:
const int n=24;
for(unsigned long long mask=0;mask<(1ULL<<n);++mask) work();
{{ select(1) }}
- 基本操作共 8,388,608 次,不会超时。
- 基本操作共 16,777,216 次,不会超时。
- 基本操作共 16,777,217 次,不会超时。
- 基本操作共 33,554,432 次,不会超时。
2. 单选题(10分)
阅读下列代码:
const int n=28;
for(unsigned long long mask=0;mask<(1ULL<<n);++mask) work();
{{ select(2) }}
- 基本操作共 268,435,456 次,会超时。
- 基本操作共 536,870,912 次,会超时。
- 基本操作共 134,217,728 次,不会超时。
- 基本操作共 268,435,457 次,会超时。
3. 单选题(10分)
阅读下列代码:
void dfs(int k){
if(k==0){work();return;}
dfs(k-1);dfs(k-1);
}
// 执行:dfs(27);
{{ select(3) }}
- 基本操作共 134,217,729 次,不会超时。
- 基本操作共 134,217,728 次,不会超时。
- 基本操作共 268,435,456 次,会超时。
- 基本操作共 67,108,864 次,不会超时。
4. 单选题(10分)
阅读下列代码:
void dfs(int k){
work();
if(k==0)return;
dfs(k-1);dfs(k-1);
}
// 执行:dfs(27);
{{ select(4) }}
- 基本操作共 268,435,456 次,会超时。
- 基本操作共 536,870,910 次,会超时。
- 基本操作共 268,435,455 次,会超时。
- 基本操作共 134,217,727 次,不会超时。
5. 单选题(10分)
阅读下列代码:
void dfs(int k){
if(k==0){work();return;}
for(int i=0;i<3;++i)dfs(k-1);
}
// 执行:dfs(17);
{{ select(5) }}
- 基本操作共 258,280,326 次,会超时。
- 基本操作共 64,570,081 次,不会超时。
- 基本操作共 129,140,164 次,不会超时。
- 基本操作共 129,140,163 次,不会超时。
6. 单选题(10分)
阅读下列代码:
void dfs(int k){
if(k==0){work();return;}
for(int i=0;i<3;++i)dfs(k-1);
}
// 执行:dfs(18);
{{ select(6) }}
- 基本操作共 387,420,490 次,会超时。
- 基本操作共 193,710,244 次,不会超时。
- 基本操作共 387,420,489 次,会超时。
- 基本操作共 774,840,978 次,会超时。
7. 单选题(10分)
阅读下列代码:
// a初始为1,2,...,11,已包含<algorithm>
int a[11];
for(int i=0;i<11;++i)a[i]=i+1;
do{work();}while(std::next_permutation(a,a+11));
{{ select(7) }}
- 基本操作共 79,833,600 次,不会超时。
- 基本操作共 39,916,801 次,不会超时。
- 基本操作共 39,916,800 次,不会超时。
- 基本操作共 19,958,400 次,不会超时。
8. 单选题(10分)
阅读下列代码:
// a初始为1,2,...,12,已包含<algorithm>
int a[12];
for(int i=0;i<12;++i)a[i]=i+1;
do{work();}while(std::next_permutation(a,a+12));
{{ select(8) }}
- 基本操作共 479,001,601 次,会超时。
- 基本操作共 958,003,200 次,会超时。
- 基本操作共 479,001,600 次,会超时。
- 基本操作共 239,500,800 次,会超时。
9. 单选题(10分)
阅读下列代码:
long long f(int n){
work();
if(n<=1)return n;
return f(n-1)+f(n-2);
}
// 执行:f(40);
{{ select(9) }}
- 基本操作共 662,320,562 次,会超时。
- 基本操作共 331,160,281 次,会超时。
- 基本操作共 331,160,282 次,会超时。
- 基本操作共 165,580,140 次,不会超时。
10. 单选题(10分)
阅读下列代码:
const int n=24;
for(unsigned long long mask=0;mask<(1ULL<<n);++mask)
for(int bit=0;bit<n;++bit)work();
{{ select(10) }}
- 基本操作共 201,326,592 次,会超时。
- 基本操作共 402,653,184 次,会超时。
- 基本操作共 805,306,368 次,会超时。
- 基本操作共 402,653,185 次,会超时。