#P2244. 时间复杂度3

时间复杂度3

这是代码阅读单选题,每小题10分,共100分。

采用本题专用的理想模型:1秒最多执行 2×1082\times10^8 次基本操作。只将一次 work() 调用计为一次基本操作;循环控制、比较、赋值、函数调用和其他语句的开销均忽略。基本操作次数超过 2×1082\times10^8 才判为超时,恰好等于时不超时。这是学习用模型,不代表实际评测机耗时。

代码使用 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 次,会超时。