做题记录-JZTXT

一些自己错的题目或者难题的相关记录, 有些错的很不应该.

7月

质数是1 * pr, 而非1 * pr * pr * pr...
线段树要可以维护当前区间没有abc的最少操作(s[x] -> c)

struct node{
    int l, r;
    int a, b, c;// the nums of them
    int ab, bc, abc;// 删除需要的操作
}tr[N << 2];

void pushUp(int u) {
    tr[u].a = tr[ls].a + tr[rs].a;
    tr[u].b = tr[ls].b + tr[rs].b;
    tr[u].c = tr[ls].c + tr[rs].c;// 没有a, 就没有ab了, 继而只用管右边的ab. 下面同理
    tr[u].ab = min(tr[ls].a + tr[rs].ab, tr[ls].ab + tr[rs].b);
    tr[u].bc = min(tr[ls].b + tr[rs].bc, tr[ls].bc + tr[rs].c);
    tr[u].abc = min({tr[ls].a + tr[rs].abc, tr[ls].abc + tr[rs].c, tr[ls].ab + tr[rs].bc});
}

Wonderful Array

n, m太大了, 无法模拟; 反求>的个数.

在b[i]的递推式, 对m取模不影响结果, 继而可以对a[i]取模. 若b[i] = b[i - 1] + a[i % k] % m > m, 则b[i - 1] > b[i], 因为a[i % k] % m一定小于m, 需要b[i - 1]来补

继而转换为求整个过程进行多少次取模操作, 即b[n] / m

注意b[0] = x的">= m"是无贡献的, 他都没有上一个数字, 所以直接b[0] %= m

代码求出周期的a[i]贡献, 再模拟求出res, 最终n - b[n] / m.

C. Particles
删除中间的, 合并两边的, 所以删除和合并的奇偶不同, 且互不影响.

故分别对奇偶的数字随便取, 继而只取正数, 然后取奇偶之和的max

当然, 还可以删两边留一个, 所以再max

String Game
多组输入while (cin >> ...)要开同步
疯狂的馒头
因为只有最后一次染色才算数, 所以倒着染, 已染的就跳过

对区间操作, 用并查集不断连接当前区间的右端点, 使得可以直接跳过已染色的位置

    rtl (i, m, 1) {
        LL l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);

        for (int j = tr.find(l); j <= r; j = tr.find(j)) {
            col[j] = i, tr.merge(j, j + 1);
        }
    }

D. Professor Higashikata

t = s的子串的拼接, 操作是交换两字符

显然若要字典序最大, 那么就是尽可能填满t前面的1, 对离散化的s', 如何确定相对顺序?

按顺序给与优先级, 用并查集(上面疯狂的馒头的思路)来跳过已操作的区间

Kevin的矩阵

开始想法, 二分op, O(n)cal, 但不知道怎么枚举列数

察觉到超过矩阵列数的修改次数过大无用, 可能是根号, 所以直接套个2 * sqrt(n) + 10直接进行枚举列数

若列数 > sqrt(n), 则行数 <= sqrt(n), 在根号下枚举出最优解

若列数 < sqrt(n), 则可以枚举到sqrt(n)列, 2 * sqrt(n)选出最优解