时间与空间复杂度分析

#include <bits/stdc++.h>
using namespace std;
const int n = 100000;
long long ops;              // 全局计数器，统计核心运算次数

// ① 内层固定 100 次：O(100n) = O(n)
void f1() {
    ops = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 100; j++)   // 内层与 n 无关
            ops++;
}

// ② 内层从 i 开始：n(n+1)/2 次，O(n²)
void f2() {
    ops = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)       // 内层规模随 i 变化
            ops++;
}

// ③ 倍增：每次都乘 2，只需 log₂n 步
void f3() {
    ops = 0;
    for (int i = 1; i <= n; i *= 2)          // 1, 2, 4, 8, ...
        ops++;
}

// ④ 调和级数：n/1 + n/2 + ... + n/n = n·H(n)，O(n log n)
void f4() {
    ops = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)       // 步长是 i，不是 1
            ops++;
}

int main() {
    f1(); cout << "f1: " << ops << endl;
    f2(); cout << "f2: " << ops << endl;
    f3(); cout << "f3: " << ops << endl;
    f4(); cout << "f4: " << ops << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long mergeOps = 0;        // 统计合并阶段的元素搬运次数
vector<int> a, tmp;

void ms(int l, int r) {
    if (l >= r) return;                  // 规模为 1，代价 O(1)
    int mid = (l + r) >> 1;
    ms(l, mid); ms(mid + 1, r);         // 2 个 T(n/2)

    // 合并：把两段有序区间归并到 tmp
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        mergeOps++;                     // 每次比较计一次
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) { tmp[k++] = a[i++]; mergeOps++; }
    while (j <= r)   { tmp[k++] = a[j++]; mergeOps++; }
    for (int t = l; t <= r; t++) a[t] = tmp[t];   // 合并代价 Θ(n)
}

int main() {
    mt19937 rng(12345);
    for (int n = 1000; n <= 256000; n *= 2) {
        a.resize(n); tmp.resize(n);
        for (auto &x : a) x = rng();
        mergeOps = 0;
        ms(0, n - 1);
        double ratio = (double)mergeOps / n;   // 应该恰好约等于 log₂n
        cout << "n = " << setw(7) << n
             << "   mergeOps = " << setw(9) << mergeOps
             << "   ops/n = " << fixed << setprecision(2) << ratio
             << "   log₂n = " << fixed << setprecision(2) << log2(n) << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, a[5005];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long ans = 0;                 // 逆序对最多 n²/2，必须用 long long
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[i] > a[j]) ans++;         // 严格大于才算逆序

    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, a[MAXN], tmp[MAXN];
long long ans = 0;

void ms(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    ms(l, mid); ms(mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            // a[j] 比左半段剩下的 (mid-i+1) 个元素都小
            ans += (mid - i + 1);
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = tmp[t];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ms(1, n);
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
long long s[MAXN];               // s[0] = 0 作哨兵

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;

    // 预处理 O(n)：边读边求前缀和
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        s[i] = s[i - 1] + x;
    }

    // 每次询问 O(1)
    while (q--) {
        int l, r; cin >> l >> r;
        cout << s[r] - s[l - 1] << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 版本一：递归写法 T(b) = T(b/2) + O(1) → O(log b)
ll qpow_rec(ll a, ll b, ll m) {
    if (b == 0) return 1 % m;        // 递归边界，注意 m = 1 的情况
    ll h = qpow_rec(a, b >> 1, m);      // 只递归一次，a^(b/2)
    return (b & 1) ? h * h % m * a % m : h * h % m;
}

// 版本二：迭代写法，常数更小
ll qpow(ll a, ll b, ll m) {
    ll res = 1 % m;
    a %= m;                             // 底数先取模
    while (b) {
        if (b & 1) res = res * a % m;    // 该位为 1，乘进答案
        a = a * a % m;                  // 底数平方：a → a²
        b >>= 1;                        // 指数右移一位
    }
    return res;
}

int main() {
    ll a, b, m; cin >> a >> b >> m;
    int cnt = 0;
    ll aa = a % m, bb = b;
    while (bb) { cnt++; bb >>= 1; }        // 统计循环次数

    cout << qpow(a, b, m) << endl;
    cout << "迭代次数 = " << cnt << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

/* ---------- 方法一：二维 DP，402MB，MLE ---------- */
// int dp2[1005][100005];   // 1005 × 100005 × 4B ≈ 402MB ❌ 注释掉，仅供参考
// 转移：dp2[i][j] = max(dp2[i-1][j], dp2[i-1][j-w[i]] + v[i]);

/* ---------- 方法二：滚动数组，0.4MB，正解 ---------- */
int dp[100005];                // 100005 × 4B ≈ 0.4MB ✅

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i++) {
        // 关键：j 必须倒序遍历！
        for (int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            // dp[j]         : 不选第 i 件（旧值）
            // dp[j-w[i]]+v[i]: 选第 i 件（也必须是旧值）
        }
    }
    cout << dp[m] << endl;
    return 0;
}

// ============ 赛前 30 秒自查表 ============
// Step 1  读数据范围：n 的上限是多少？q 是多少？值域多大？
// Step 2  定复杂度上限：
//         n ≤ 20      → O(2ⁿ) / O(n!)  ← 状压、爆搜
//         n ≤ 100     → O(n³) ~ O(n⁴)
//         n ≤ 500     → O(n³)          ← Floyd、矩阵乘
//         n ≤ 5000    → O(n²)          ← 朴素 DP
//         n ≤ 1e5     → O(n log n)     ← 排序、二分、BIT
//         n ≤ 1e6     → O(n log n) / O(n)
//         n ≥ 1e9     → O(log n) / O(√n) ← 快速幂、二分答案
// Step 3  选算法：在上面的档位里挑最熟的那个
// Step 4  验证最坏情况：极端数据会不会退化？
// Step 5  算空间：Σ(数组元素数 × 字节数) < 2.5 × 10⁸
// Step 6  查溢出：答案范围会不会超 int？是否要 long long？

// ============ 快速自检代码片段 ============
const long long INF = 0x3f3f3f3f3f3f3f3fLL;   // 常用无穷大

// ① 估算允许的数组规模（256MB 预算）
const long long MEM_LIMIT = 256LL * 1024 * 1024;   // 268435456 B
// 可容纳的 int 个数 = MEM_LIMIT / 4 = 67108864 ≈ 6.7e7

// ② 估算允许的运算次数（1s 预算）
const long long OPS_LIMIT = 100000000LL;        // 保守按 1e8 算
// n = 1e5 时：n² = 1e10 > 1e8 ← 否决；n log n ≈ 1.7e6 ← 通过

// ③ 统一用 long long 兜底的三个信号
//    a. 答案涉及乘法或累加且上限超过 2×10⁹
//    b. 题目出现「方案数 mod」，中间量可能达到 1e18
//    c. 出现 10⁹ × 10⁹ 形式的乘法，必须先转 long long

// ④ 深递归防爆栈：把递归改写成显式栈
vector<int> stk; stk.push_back(root);
while (!stk.empty()) {
    int u = stk.back(); stk.pop_back();
    // ... 处理 u，把子节点压栈
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int a[MAXN], ans[MAXN];
long long pushCnt, popCnt;          // 统计入栈 / 出栈总次数

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> st;                    // 单调递减栈，存下标
    pushCnt = popCnt = 0;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] < a[i]) {
            ans[st.back()] = i;           // i 就是它右边第一个更大的位置
            st.pop_back(); popCnt++;
        }
        st.push_back(i); pushCnt++;
    }
    while (!st.empty()) { ans[st.back()] = 0; st.pop_back(); popCnt++; }

    for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
    cout << "push = " << pushCnt << ", pop = " << popCnt << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

/* ---------- 朴素版：O(nS) 时间，每次只处理一个布尔值 ---------- */
bool can[100005];
void solve_plain(int n, const vector<int>& a) {
    can[0] = true;
    for (int i = 0; i < n; i++)
        for (int s = 100000; s >= a[i]; s--)     // 倒序，保证每件只用一次
            if (can[s - a[i]]) can[s] = true;
}

/* ---------- bitset 版：位运算并行，一次处理 64 位 ---------- */
bitset<100005> bs;
void solve_bitset(int n, const vector<int>& a) {
    bs[0] = 1;
    for (int i = 0; i < n; i++)
        bs |= (bs << a[i]);                        // 一行搞定全部状态转移
}

int main() {
    int n, S; cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    cin >> S;

    solve_bitset(n, a);
    cout << (bs[S] ? "YES" : "NO") << endl;
    return 0;
}