A 修理

思路

大水题，直接开桶计数。

代码

#include <cstdio>
 
int k, n, m, _, t[100001], ans;
int main(){
    scanf("%d%d%d", &k, &n, &m);
    for (int i = 1;i <= n;i ++){
        scanf("%d", &_);
        if (_ <= k) t[_] ++; // 计数
    }
    for (int i = 1;i <= m;i ++){
        scanf("%d", &_);
        if (_ <= k) t[_] --; // 用手里有的零件去满足要求
    }
    for (int i = 1;i <= k;i ++){
        if (t[i] > 0) ans += t[i]; // 统计无法满足的要求数量
    }
    printf("%d", ans);
}

B 开根号

思路

数据范围较大，考虑二分 + 快速幂。

由于需要判断 $x ^ m \le n$，且 $1 \le n \le 10^{18}$，我们考虑极端情况：当 $ans$ 为 $n - 1$，此时将 $ans$ 自乘，则 $ans$ 的值可达 $10^{36}$，会爆炸。

若使用高精度，高精度乘法运算时间复杂度为 $O(n^2)$，且运算后的值可能位数极大，所以 TLE 的风险很大。

而 __int128 有 CE 的风险，所以只好使用 long long。

如果不考虑精度问题，正常情况下的判断语句大概是在快速幂中 ans *= base 前面进行判断。像前面说的一样，$ans$ 乘完之后可能会爆，所以我们考虑在前面这样判断：ans * base > n。但是，前面那一坨依然会爆！

那怎么办呢？我们考虑移项。

显然，若 $a \times b = c$，则 $c \div b = a$。

所以，刚刚的 $ans \times base > n$ 可以变成 $n \div ans < base$，这样子精度就有保证了！！！

另外，还有一个 $base$ 变量也有可能会在快速幂中爆掉，然后再把错误的值更新到 $ans$，使用相似的方法处理即可。

但是，在处理 $base$ 时要加一个特判。当 $p \le 1$ 的时候，下一次循环会直接跳出，所以 $base$ 的值对 $ans$ 的值也没有任何影响了。

时间复杂度为 $O(T \log n \log m)$，稳过！

代码

#include <cstdio>
#include <cctype> // 快读快写需要使用
 
inline long long read(){
    char ch = getchar();
    long long res = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
inline void dwrite(long long x){
    if (!x) return;
    dwrite(x / 10);
    putchar('0' + x % 10);
}
inline void write(long long x){
    if (!x) putchar('0');
    else dwrite(x);
} // 快读快写
int t;
long long n, m, l, r, mid;
bool check(long long x, long long p){ // 快速幂检查
    long long base = x, ans = 1;
    while (p){
        if (p & 1){
            if (n / ans < base) return 0; // 判定
            ans *= base;
        }
        if (n / base < base && p > 1) return 0; // 判定
        base *= base;
        p >>= 1;
    }
    return ans <= n;
}
int main(){
    t = read();
    while (t --){
        n = read(), m = read();
        l = 1, r = n + 1;
        while (r - l > 1){ // 二分
            mid = r + l >> 1;
            if (check(mid, m)) l = mid;
            else r = mid;
        }
        write(l);
        putchar('\n');
    }
}

C 树

思路

又一道大水题。首先离线将修改记录下来，再使用 dfs 直接求出每个点的值。

时间复杂度 $O(n + q)$。

代码

#include <cstdio>
#include <vector>
 
using namespace std;
 
int n, q, u, v, x, y, c[200001], ans[200001];
vector<int> t[200001];
void dfs(int u, int fa, int w){
    ans[u] = w; // 记录自己父亲的点权
    for (int i = 0;i < t[u].size();i ++){
        int v = t[u][i];
        if (v != fa) dfs(v, u, w + c[u]); // 将自己的点权加到自己儿子的点权上
    }
}
int main(){
    scanf("%d%d", &n, &q);
    for (int i = 1;i < n;i ++){
        scanf("%d%d", &u, &v);
        t[u].push_back(v);
        t[v].push_back(u);
    } // 建树
    while (q --){
        scanf("%d%d", &x, &y);
        c[x] += y;
    } // 存储修改
    dfs(1, 0, 0);
    for (int i = 1;i <= n;i ++) printf("%d ", ans[i] + c[i]); // 每个节点的点权 = 自己的点权 + 自己父亲的点权
}

D 排列

思路

单调队列 / 栈模板题。

首先使用单调队列求出 $l_i$ 与 $r_i$。

$l_i$ 的意思是以 $p_i$ 为最大值的最长区间的左端点，$r_i$ 为右端点。

那怎么求呢？

首先，想要维护最大值，我们的单调队列肯定是单调递减的。

当一个数 $a$ 在加入队列时没有弹出 $b$，$p_a$ 肯定小于 $p_b$，且 $a$ 弹出了 $b$ 之前的所有数，所以，$l_a = b + 1$。

当一个数 $a$ 在单调队列里被 $b$ 弹出，$p_a$ 肯定小于 $p_b$，且 $a$ 没有被 $b$ 之前的任何数弹出，所以，$r_a = b - 1$。

注意，最后留在队列里的数的 $r_i = n$。

想让每个区间都包含 $i$，那每个区间的左端点的枚举范围是 $l_i \le l \le i$，右端点的枚举范围是 $i \le l \le r_i$，每一个区间的最大值都是 $p_i$，把它乘上 $p_i$ 就行了！

时间复杂度 $O(n)$。

代码

#include <cstdio>
#define mod 998244353
 
int n, t, p[100002], q[100002], l[100002], r[100002];
long long ans;
int main(){
    scanf("%d", &n);
    for (int i = 1;i <= n;i ++) scanf("%d", &p[i]);
    p[n + 1] = n + 1; // 特殊处理
    for (int i = 1;i <= n + 1;i ++){
        while (t > 0 && p[q[t]] < p[i]){
            r[q[t]] = i - 1; // 求出 r
            t --; // 弹出
        }
        l[i] = q[t] + 1; // 求出 l
        q[++ t] = i; // 插入
    }
    for (int i = 1;i <= n;i ++) ans = (ans + (i - l[i] + 1ll) * (r[i] - i + 1ll) * p[i]) % mod; // 计算答案
    printf("%d", ans);
}