2秒时间限制下的可执行操作数

一般经验估算

  • 保守估计：C++在2秒内可执行约 $210^8-410^8$ 次基本操作（加减、比较、赋值等）
  • 实际表现：
    • 简单循环操作：约$110^8-210^8$
    • 复杂操作（除法、取模、函数调用）：约$0.510^8-110^8$
    • 浮点运算：约$0.310^8-0.510^8$

      不同复杂度对应的最大数据规模

      1
      2
      3
      4
      5
      6
      7
      8
      9
      O(1)        -> 几乎无限（>10^9）
      O(logn)     -> 几乎无限（>10^9）
      O(n)        -> 约 2×10^8
      O(nlogn)    -> 约 2×10^7（2000万）
      O(n√n)      -> 约 2×10^6（200万）
      O(n²)       -> 约 2×10^4（2万）
      O(n³)       -> 约 2×10^3（2000）
      O(2ⁿ)       -> 约 n ≤ 25
      O(n!)       -> 约 n ≤ 11

实战参考表

数据规模 可接受的复杂度 常见算法
n ≤ 10 任意（包括O(n!)） 全排列、暴力搜索
n ≤ 20 O(2ⁿ) 子集枚举、状态压缩DP
n ≤ 100 O(n³) Floyd、简单DP
n ≤ 1000 O(n²) 二维DP、Dijkstra朴素版
n ≤ 10^4 O(n√n) 数论分块
n ≤ 10^5 O(nlogn) 线段树、树状数组、堆
n ≤ 10^6 O(n) 或 O(nlogn) 前缀和、KMP、单调栈
n ≤ 10^7 O(n) 筛法、线性DP
n ≤ 10^8 O(n)（必须常数小） 位运算、简单遍历

256MB内存限制下的数组大小

不同数据类型可开数组大小

数据类型 字节大小 最大元素数 备注
bool 1字节 约 2.68亿 实际比赛中常设为 bool 数组
char 1字节 约 2.68亿
int 4字节 约 6700万 常用
long long 8字节 约 3300万
double 8字节 约 3300万
结构体（16字节） 16字节 约 1600万 视具体结构而定 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 安全范围（考虑程序其他部分占用）
int arr1[10000000];     // 4000万字节 ≈ 38MB ✅
int arr2[50000000];     // 2亿字节 ≈ 190MB ✅（接近极限）

int matrix1[5000][5000]; // 1亿字节 ≈ 95MB ✅
int matrix2[10000][10000]; // 4亿字节 ≈ 381MB ❌（超限）

// 多个数组时需累加
int arrA[30000000];  // 114MB
int arrB[30000000];  // 114MB
// 总计228MB ✅（但接近极限）

// 危险情况
vector<vector<int>> graph(100000);  // 每个vector开销
// 虽可能未立即超限，但动态扩展时可能意外超限

实用安全上限表

数组类型 推荐最大规模 实际内存占用 安全系数
一维int数组 ≤ 5×10⁷ ≤ 200MB 留有余地
一维long long数组 ≤ 2.5×10⁷ ≤ 200MB
二维int数组[n][m] n×m ≤ 3×10⁷ ≤ 120MB 常用
邻接表（图） 边数 ≤ 2×10⁶ 变长，通常安全
位集bitset ≤ 2×10⁸位 ≤ 25MB 非常节省

快速判断方法

时间判断口诀

1
2
3
4
n=10⁵ → 想想O(nlogn)
n=10⁶ → 必须O(n)或优化常数
n≤5000 → O(n²)或许可行
n≤20 → 可能是状压

空间判断口诀

1
2
3
4
int数组：百万级安全，千万级要小心
二维数组：相乘别超千万
结构体：注意对齐开销
STL容器：额外开销约50%