B2 - TV Subscriptions (Hard Version)

使用滑动窗口结合集合维护当前区间内各频道的出现次数与唯一频道数。通过 set 记录当前有效频道，set> 维护频道及其频次，实现高效插入、删除和查询。

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

const int maxn = 1e6 + 7;
int ar[maxn], n, m, k;
int cnt[maxn];
set<int> valid;
set<pair<int, int>> freq;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; ++i) scanf("%d", ar + i);

        // 初始化计数
        for (int i = 1; i <= n; ++i) cnt[ar[i]] = 0;

        // 初步填充前k个元素
        for (int i = 1; i <= k; ++i) {
            cnt[ar[i]]++;
        }
        for (int i = 1; i <= k; ++i) {
            valid.insert(ar[i]);
            freq.insert({ar[i], cnt[ar[i]]});
        }

        int res = valid.size();

        // 滑动窗口扩展
        for (int i = k + 1; i <= n; ++i) {
            // 移除左边旧元素
            int left_val = ar[i - k];
            freq.erase({left_val, cnt[left_val]});
            cnt[left_val]--;
            if (cnt[left_val] > 0) {
                freq.insert({left_val, cnt[left_val]});
            } else {
                valid.erase(left_val);
            }

            // 添加新元素
            int right_val = ar[i];
            freq.erase({right_val, cnt[right_val]});
            cnt[right_val]++;
            freq.insert({right_val, cnt[right_val]});
            if (cnt[right_val] == 1) {
                valid.insert(right_val);
            }

            res = min(res, (int)valid.size());
        }

        printf("%d\n", res);
    }
    return 0;
}

C - p-binary

枚举所需 p 的个数，对每个可能值尝试构造目标数 n。核心思想是：若用 i 个 p 构成 n，则剩余部分为 n - i * p，该值必须能表示为 i 个 1 的二进制和（即其二进制中 1 的数量 ≤ i）。

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

int main() {
    ll n, p;
    scanf("%lld%lld", &n, &p);
    bool found = false;

    for (ll count = 1; count <= 300000; ++count) {
        ll rem = n - count * p;
        if (rem < count) continue;  // 不可能用 count 个 1 表示

        int ones = 0;
        ll temp = rem;
        while (temp) {
            ones += temp & 1;
            temp /= 2;
        }

        if (ones <= count) {
            printf("%lld\n", count);
            found = true;
            break;
        }
    }

    if (!found) printf("-1\n");
    return 0;
}

D - Power Products

将每个数分解质因数，对每个质因子的幂模 k 取余，得到"余数向量"。一个数要与另一个数相乘形成 x^k 形式，它们的余数向量之和必须在模 k 意义下为 0。因此，对于每个数，计算其补向量，并统计匹配的数量。

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

const int MAXN = 1e6 + 7;
int a[MAXN], rev[MAXN], cnt[MAXN];
int n, k;

ll get_complement(int x) {
    ll res = 1;
    for (int i = 2; i * i <= x; ++i) {
        int exp = 0;
        while (x % i == 0) {
            x /= i;
            exp++;
        }
        if (exp > 0) {
            int need = (k - (exp % k)) % k;
            if (need != 0) {
                ll base = 1;
                for (int j = 0; j < need; ++j) {
                    base *= i;
                    if (base > 1e5) return 0;
                }
                res *= base;
                if (res > 1e5) return 0;
            }
        }
    }
    if (x > 1) {
        int need = (k - (1 % k)) % k;
        if (need != 0) {
            for (int j = 0; j < need; ++j) {
                res *= x;
                if (res > 1e5) return 0;
            }
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        ll comp = get_complement(a[i]);
        if (comp > 0 && comp <= 1e5) {
            cnt[comp]++;
            rev[i] = comp;
        } else {
            rev[i] = 0;
        }
    }

    ll total = 0;
    for (int i = 1; i <= n; ++i) {
        if (rev[i] == 0) continue;
        total += cnt[rev[i]];
        if (a[i] == rev[i]) total--;  // 自身配对只算一次
    }

    printf("%lld\n", total / 2);
    return 0;
}

E - Rock Is Push

预处理每行每列可向右/向下移动的最大距离。使用二维树状数组分别维护从左向右和从上向下的路径贡献。状态转移时，仅需累加左侧格子向下推的次数和上方格子向右推的次数。

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

const int N = 2005;
const ll MOD = 1e9 + 7;

char grid[N][N];
ll bit[2][N][N * 2];  // [dir][row][col]
int right_dist[N][N], down_dist[N][N];

void update(int dir, int x, int y, ll val) {
    while (y <= N) {
        bit[dir][x][y] = (bit[dir][x][y] + val) % MOD;
        y += y & (-y);
    }
}

ll query(int dir, int x, int y) {
    ll res = 0;
    while (y > 0) {
        res = (res + bit[dir][x][y]) % MOD;
        y -= y & (-y);
    }
    return res;
}

void range_update(int dir, int x, int l, int r, ll val) {
    update(dir, x, l, val);
    update(dir, x, r + 1, -val);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", grid[i] + 1);
    }

    // 预处理向右和向下可达距离
    for (int i = n; i >= 1; --i) {
        for (int j = m; j >= 1; --j) {
            right_dist[i][j] = (grid[i][j] == '.') ? (right_dist[i][j + 1] + 1) : 0;
            down_dist[i][j] = (grid[i][j] == '.') ? (down_dist[i + 1][j] + 1) : 0;
        }
    }

    // DP 计算路径数
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            ll from_left = (j == 1) ? 0 : query(0, i, j);
            ll from_up = (i == 1) ? 0 : query(1, j, i);

            ll total = from_left + from_up;
            if (i == 1 && j == 1) total = 1;

            // 向右推：影响后续列
            int len_r = right_dist[i][j + 1];
            range_update(0, i, j + 1, j + len_r, total);

            // 向下推：影响后续行
            int len_d = down_dist[i + 1][j];
            range_update(1, j, i + 1, i + len_d, total);
        }
    }

    printf("%lld\n", query(0, n, m) % MOD);
    return 0;
}