\(\text{[AGC034C] Tests}\)
很容想到二分答案和 \(c_i\) 比较固定的选取方法
然后就不会了。。。
接下来就是要发现性质的时候
固定答案时，若此时已有了一组 \(a\)，考虑对于 \(0<a_i,a_j<X\) 的 \(a_i,a_j\) 加减 \(1\)
发现给 \(c\) 值大的 \(+1\)，小的 \(-1\)，新方案必然不劣
于是可以得到 \(a_i\) 是一堆 \(0,X\) 和一个 \(r(0<r<X)\)，这个 \(r\) 的位置可以枚举
那么按 \(calc(i,X)-calc(i,0)\) 排序后就可以二分 \(O(n) \text{ check}\) 了
$\text{Code}$
#include <cstdio>
#include <iostream>
#include <algorithm>
#define IN inline
using namespace std;
template <typename T>
IN void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
if (f) x = ~x + 1;
}
typedef long long LL;
const int N = 1e5 + 5;
int n, X;
LL s0[N], sx[N];
struct node{int b, l, r; LL v;}a[N];
IN bool cmp(node a, node c){return a.v > c.v;}
IN LL calc(int i, int x){return (LL)(x < a[i].b ? a[i].l : a[i].r) * (x - a[i].b);}
IN int check(LL mid) {
int nx = mid / X, nr = mid - (LL)nx * X; LL res = (nx == n ? sx[nx] : s0[1]);
for(int i = 1; i <= n; i++)
if (i <= nx) res = max(res, sx[nx + 1] + s0[nx + 2] - calc(i, X) + calc(i, nr));
else res = max(res, sx[nx] + s0[nx + 1] - calc(i, 0) + calc(i, nr));
return res >= 0;
}
int main() {
read(n), read(X);
for(int i = 1; i <= n; i++)
read(a[i].b), read(a[i].l), read(a[i].r), a[i].v = calc(i, X) - calc(i, 0);
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++) sx[i] = sx[i - 1] + calc(i, X);
for(int i = n; i; i--) s0[i] = s0[i + 1] + calc(i, 0);
LL l = 0, r = (LL)X * n, mid = l + r >> 1, ans = r;
for(; l <= r; mid = l + r >> 1)
if (check(mid)) ans = mid, r = mid - 1; else l = mid + 1;
printf("%lld\n", ans);
}
\(\text{[AGC001C] Shorten Diameter}\)
从最终状态考虑，找到最终状态的中心
那么从中心出发路径长度不超过 \(\frac k 2\)
直接枚举中心，\(dfs\) 把多余的删去即可，注意分 \(k\) 的奇偶
\(\text{[AGC003D] Anticube}\)
每个数改为对其质因数分解后的指数模 \(3\)之后的数，那么一个数只能与另一个可确定的数相乘为完全立方数
于是讨论每对数即可
注意到分解后大于等于 \(\sqrt[3]{x}\) 的因数最多有两个，所以分解时只需枚举到 \(\sqrt[3]{x}\)
\(\text{P2714}\) 四元组统计
不得不说莫反反傻了，容斥即可
记 \(g(i)\) 为四元组 \(\gcd\) 为 \(i\) 的倍数的方案数，\(f(i)\) 则是恰好为 \(i\) 的方案数
那么 \(f(i)=g(i)-\sum_{i|j}f(j)\)，于是从大到小算 \(f\) 即可
\(\text{CF853C Boredom}\)
矩阵有交比较难处理，那么容斥
发现就是要算八处而已，上下左右可以直接算，四个角落二维数点即可
为简化代码，可以四次翻转矩形
\(\text{[AGC003C] BBuBBBlesort!}\)
发现使用操作二可以对奇数位和偶数位免费排序，但不能改变一个数所在位置的奇偶
所以离散化后等价于求用操作一将奇数放到奇数位，偶数放到偶数位的最小次数
一次明智的操作一显然是让两个不在正确奇偶位的奇偶数归位
那么统计每个数与当前位置奇偶性不同的数量除以二即可
\(\text{[AGC010C] Cleaning}\)
想象乱七八糟的路径情况。。。
先找个度数大于一的为根
那么考虑一个非叶子结点 \(x\)，经过它的路径为子树中取两个叶子结点形成的路径和从它向祖先延伸出去的路径
考虑最终 \(a_x\) 要为 \(0\)
记从它向祖先延伸出去的路径个数为 \(f_x\)，则经过它的总路径为 \(s_x=\sum_{v\in son_x} f_v\)
那么要有 \(a_x=\frac{s_x-f_x}2+f_x\)， \(s_x-f_x\) 表示由子树内两个叶子结点形成路径
可以得到 \(f_x=2a_x-s_x\)，也就是说要延伸出去的路径数量一定
那判断是否可行则是要求 \(0\le f_x\le a_x\)
结束了！！！？
注意到过 \(x\) 且在 \(x\) 子树内的路径是要两两匹配的，从一个儿子出来的路径要配上从另一个儿子出来的路径
这个不一定可行
先考虑这样一个问题
若干个数，每次可取两个大于 0 的数，令它们同时减 1，问能否将所有数变为 0
结论：能的充要条件为所有数的总和为偶数且最大值不超过总和的一半
方案数是每次取出最大的两个数减 \(1\)
回到这题，我们有 \(f_x\) 次机会先让一些数减 \(1\)，然后满足结论：\(\forall v\in son_x ,f_v \le \frac{s_x-f_x}2=s_x-a_x\)
算出把 \(f_v\) 变得满足结论的最少次数与 \(f_x\) 比较即可
$\text{Code}$
#include <cstdio>
#include <iostream>
#define IN inline
using namespace std;
template <typename T>
IN void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
if (f) x = ~x + 1;
}
typedef long long LL;
const int N = 1e5 + 5;
int n, deg[N], h[N], tot, flag, rt;
LL a[N], f[N];
struct edge{int to, nxt;}e[N << 1];
IN void add(int x, int y){e[++tot] = edge{y, h[x]}, h[x] = tot;}
void dfs(int x, int fa) {
if (deg[x] == 1) return f[x] = a[x], void();
LL s = 0, ss = 0;
for(int i = h[x]; i; i = e[i].nxt) {
int v = e[i].to;
if (v == fa) continue;
dfs(v, x), s += f[v], ss += (f[v] > a[x] ? f[v] - a[x] : 0);
if (flag) return;
}
f[x] = a[x] * 2 - s;
if (f[x] < 0 || f[x] > a[x] || ss > f[x]) flag = 1;
if (x == rt && f[x] != 0) flag = 1;
}
int main() {
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 1, x, y; i < n; i++)
read(x), read(y), add(x, y), add(y, x), ++deg[x], ++deg[y], rt = (deg[x] > 1 ? x : rt), rt = (deg[y] > 1 ? y : rt);
if (rt) dfs(rt, 0); else flag = !(a[1] == a[2]);
if (flag) puts("NO"); else puts("YES");
}
\(\text{[AGC010B] Boxes}\)
区间操作不难想到差分，然后问题转化为一次操作给一个数加 \(n-1\)，其余均 \(-1\)，问能否全变为 \(0\)
注意到操作总次数一定，对每个数设 \(x_i\) 表示加 \(x_i\) 次 \(n-1\) 解方程即可
$\text{Code}$
#include <cstdio>
#include <iostream>
#define IN inline
using namespace std;
template <typename T>
IN void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); f = (ch == '-' ? 1 : f), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
if (f) x = ~x + 1;
}
typedef long long LL;
const int N = 1e5 + 5;
int n, a[N], b[N];
int main() {
read(n); LL s = 0, t = (LL)n * (n + 1) / 2;
for(int i = 1; i <= n; i++) read(b[i]), s += b[i];
if (s % t != 0) return puts("NO"), 0;
a[1] = b[1] - b[n];
for(int i = 2; i <= n; i++) a[i] = b[i] - b[i - 1];
s /= t;
int flag = 1;
for(int i = 1; i <= n; i++) flag &= (s - a[i] >= 0 && (s - a[i]) % n == 0);
if (flag) puts("YES"); else puts("NO");
}