一些自己错的题目或者难题的相关记录, 有些错的很不应该.
7月
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});
}
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);
}
}
t = s的子串的拼接, 操作是交换两字符
显然若要字典序最大, 那么就是尽可能填满t前面的1, 对离散化的s', 如何确定相对顺序?
按顺序给与优先级, 用并查集(上面疯狂的馒头的思路)来跳过已操作的区间
开始想法, 二分op, O(n)cal, 但不知道怎么枚举列数
察觉到超过矩阵列数的修改次数过大无用, 可能是根号, 所以直接套个2 * sqrt(n) + 10直接进行枚举列数
若列数 > sqrt(n), 则行数 <= sqrt(n), 在根号下枚举出最优解
若列数 < sqrt(n), 则可以枚举到sqrt(n)列, 2 * sqrt(n)选出最优解