4.3 淘天

T1 询问区间 的元素拼接起来是不是 的倍数，正解是计算拆位前缀和，但是我直接用数的前缀和居然也过了，为什么呢？因为拼接相当于 x*10..0+y，而 x%3 和 x*10..0%3 是等价的，因为 x*10..0=99.9x+x，而前者模 是不算的，所以得证，假如拼接起来可以，数字和也可以，反之亦然

T2 问区间染色的最少次数，条件是单个元素或者 满足 ，采用分类讨论思想，如果 ，就是 次；否则设 ，试图找到一个位置 ，满足 and ，就是 次；否则，发现一个性质，任意位置 ， 和 必有一个是 ，说明非 元素一定是单个单个存在的，且把数组分成若干段 ，总是得选择一段，一个个染色，那么结果就是 len(最短的一段)+2，或 min(t[0],t[1])+1 二者最小值

T3 是树状数组裸题，不记录了

3.22 美团

T4 输入格式是 a(2)b(3)a(2) 这样表示字符和出现次数的，问最大切割的字段个数，满足 种类*长度>=k，直接贪心，能割就割，就是细节比较多

char a[N], s[N];
LL num[N];
LL cnt[30];
int len, i, j;
LL n, k;
    
    scanf("%lld%lld%s", &n, &k, a + 1);
    len = strlen(a + 1);
    for (i = 1, k = 1; i <= len; ) {
        if (a[i] >= 'a' && a[i] <= 'z') {
            s[j] = a[i];
            i += 2;
            if (i <= len) {
                LL tmp = 0;
                while (a[i] != '(') {
                    tmp = tmp * 10 + (a[i] - '0');
                    i ++;
                }
            }
            i ++;
            num[j ++] = tmp;
        } else {
            break;
        }
    }
    LL diff = 0, tmp = 0, res = 0;
    for (int i = 1; i < j; ) {
        // 没出现过
        if (cnt[s[i] - 'a'] == 0) {
            diff ++;
            cnt[s[i] - 'a'] ++;
        } 
        // 如果符合条件
        if ((tmp + num[i]) * diff >= k) {
            // 计算符合条件的最小数量
            LL sub = max(k / diff - tmp, 1LL);
            // 循环次数很少
            while ((tmp + sub) * diff < k) sub ++;
            num[i] -= sub;
            // 如果最小数量也用光了当前字母 移动到下一个字母
            if (num[i] == 0) i ++;
            // 若还有剩余 i 不变
            memset(cnt, 0, sizeof cnt);
            diff = tmp = 0;
            res ++;            
        } else {
            tmp += num[i];
            i ++;
        }
    }
    if (res == 0) puts("-1");
    else printf("%lld\n", res);

T5 给定一棵树，每次询问求 走到 的概率，规定是不走回头路的，思路就是求 到 的路径，端点外每个点的 连乘，最后乘上 ，然后 就是概率，由于要输出 的这个 ，还要用逆元求一下，下面代码是用倍增，维护开区间 的 乘积，能跑样例但未经 oj 验证，感觉是对的（upd：已 ac）

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

using LL = long long;
const int N = 200010;
const int MOD = 1e9 + 7;

int n, q, S, T;
vector<int> g[N];
int sz[N], d[N];
int p[N][21];
LL cnt[N][21];

void dfs(int u, int fa) {
    d[u] = d[fa] + 1;
    for (int v: g[u]) 
        if (v != fa) {
            p[v][0] = u;
            cnt[v][0] = 1;
            dfs(v, u);
        }
}

LL get(int s, int t) {
    if (d[s] > d[t]) swap(s, t);
    LL res = 1;
    int k = d[t] - d[s];
    for (int i = 0; i <= 20; i++) {
        if (k >> i & 1) {
            if (p[t][i] != s) {
                res = (res * cnt[t][i] % MOD * (sz[p[t][i]] - 1)) % MOD;
            } else {
                res = (res * cnt[t][i]) % MOD;
            }
            t = p[t][i];
        }
    }
    if (s == t) return res;
    for (int i = 20; i >= 0; i--) {
        int ps = p[s][i], pt = p[t][i];
        if (ps != pt) {
            res = (res * cnt[s][i] % MOD * (sz[ps] - 1) % MOD) * cnt[t][i] % MOD * (sz[pt] - 1) % MOD;
            s = ps, t = pt;
        }
    }
    return (res * (sz[p[s][0]] - 1)) % MOD;
}

LL qmi(LL x, LL p) {
    LL res = 1;
    while (p) {
        if (p & 1) res = (res * x) % MOD;
        x = x * x % MOD;
        p >>= 1;
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
        sz[x] ++, sz[y] ++;
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 20; j++) {
            p[i][j] = p[p[i][j - 1]][j - 1];
            cnt[i][j] = (cnt[i][j - 1] * cnt[p[i][j - 1]][j - 1] % MOD * (sz[p[i][j - 1]] - 1)) % MOD;
        }
    
    scanf("%d", &q);
    while (q -- ) {
        scanf("%d%d", &S, &T);
        LL ans = get(S, T);
        printf("%lld\n", qmi(ans * sz[S] % MOD, MOD - 2));
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

3.17 米哈游

T1 排序后贪心，正确性是因为考虑到每一个怪物时，当前的 cntE 都是满足刚好把它干掉的量。无脑累加 cntR，最后记得特判最后一个元素并更新 cntR 即可

void solve() {
    int n;
    cin >> n;
    vector<LL> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    LL E, R;
    cin >> E >> R;
    int cntE = 0, cntR = 0;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        LL cur = a[i] - E * cntE - R * cntR;
        if (cur + cur <= a[i]) cntR ++;
        else {
            LL tmp = cur - a[i] / 2;
            cntE += (tmp + E - 1) / E;
            cntR ++;
        }
    }
    LL lst = a[n - 1] - E * cntE;
    if (lst - R * cntR > 0) cntE += (lst - R * cntR + E - 1) / E;
    else {
        int nR = (lst + R - 1) / R;
        cntR = min(cntR, nR);
    }
    cout << cntE << ' ' << cntR << endl;
}

T3 定义 表示考虑前 台机，启动第 台机，此时左边最靠近的启动机是 的最大数量。转移时需要考虑 这样的三元组，满足 ，即只考虑 在某个范围内的那些 ，取最大的 。查询这个数，可以对每个 都记录一个离散化的权值树状数组，单点修改+区间查询即可

另一种思路：本质是寻找子序列 满足 ，可以用 表示以 结尾，差值为 的最大长度，则 ，其中 大于 ，这个就可以二分查找出来了（类似于 map 的思路，不直接维护所有差值，而是用 pair 记录出现了哪些差值），最后为了省略掉树状数组，每次求完 后直接求一个后缀最大值

    int n;
    cin >> n;
    vector<LL> a(n);
    vector<vector<PLI>> f(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        f[i].push_back({0x3f3f3f3f3f3f3f3f, 1});
    }
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
        // 寻找最小的 v 满足 f[j][v]>a[i]-a[j]
            int l = 0, r = f[j].size() - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (f[j][mid].x > a[i] - a[j]) r = mid;
                else l = mid + 1;
            }
            f[i].push_back({a[i] - a[j], f[j][l].y + 1});
            res = max(res, f[j][l].y + 1);
        }
        sort(f[i].begin(), f[i].end());
        int sz = f[i].size();
        int mx = f[i][sz - 1].y;
        // 后缀最大值代替树状数组
        for (int j = f[i].size() - 1; j >= 0; j--) {
            mx = max(mx, f[i][j].y);
            f[i][j].y = mx;
        }
    }
    cout << res << endl;