玩水 (water) 100pts
一道结论题，考场一眼出，结果认为不对，然后被硬控了2h结果打出了个抽象DP然后过了；
赛后发现，这DP和那个结论是等价的。。。；
首先考虑只有两个人怎么做，那么我们只需找出一个位置 $ (i, j) $ 满足 $ a_{i + 1, j} = a_{i, j + 1} $ 即可；
那么三个人呢？
设现在有两个满足上述性质的位置 $ (x_1, y_1) \ (x_2, y_2) $，不难想到这三种情况：
-
$ x_1 < x_2, y_1 < y_2 $；
-
$ y_1 = y_2, x_1 = x_2 + 1 $；
-
$ x_1 = x_2, y_1 = y_2 + 1 $；
反之同理；
那么这三种情况就包含了所有情况，因为这玩意是有一个传递性的（就是三条路组成的字符串都要完全相同）；
这DP太抽象，所以代码仅供参考；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n, m;
char a[1005][1005];
bool f[1005][1005][5][2];
int main() {
freopen("water.in", "r", stdin);
freopen("water.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= 3; k++) {
f[i][j][k][0] = false;
f[i][j][k][1] = false;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j][1][0] = true;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
for (int k = 2; k <= 3; k++) {
f[i][j][k][0] |= (f[i - 1][j][k][0] | f[i][j - 1][k][0]);
if (i + 1 <= n && j - 1 >= 1 && a[i][j] == a[i + 1][j - 1]) {
f[i][j][k][1] |= f[i][j - 1][k - 1][0];
}
if (i - 1 >= 1 && j + 1 <= m && a[i][j] == a[i - 1][j + 1]) {
f[i][j][k][1] |= f[i - 1][j][k - 1][0];
}
if (i - 1 >= 1 && j - 1 >= 1) {
if (a[i - 1][j] == a[i][j - 1]) {
f[i][j][k][0] |= (f[i - 1][j - 1][k - 1][1] | f[i - 1][j - 1][k - 1][0]);
}
}
}
}
}
if (f[n][m][3][0]) cout << 1 << '\n';
else cout << 0 << '\n';
}
return 0;
}
限速（speed）100pts
可以说是思维题了；
考虑求出原树的最小生成树，那么如果树边都小于等于 $ k $，就直接输出所有边中最靠近 $ k $ 的边与 $ k $ 的差，否则输出所有树边中大于 $ k $ 的边与 $ k $ 的差之和；
考虑这为什么是对的，因为 Kruskal 本质上就是在尽可能多的选小的边，每次找的都是链接两个连通块的最小的边，而小的边越多越好，所以是对的；
从另一个角度说，Kruskal 不对，当且仅当我们判断连通性舍弃边时出现问题，那我们分情况考虑：
-
当舍弃的边 $ > k $ 时，不管我们以前的边的大小如何，舍弃这条边都是更优的；
-
当 $ < k $ 时，这两个点已经联通说明其至少一条边直接或间接的联通而且呈链状，那么我们删掉这条边自然是不劣的（因为如果选这条边，其不会带来更多的小边）；
所以是对的；
时间复杂度：$ \Theta(m \log m) $，瓶颈在排序；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m;
long long k;
struct sss{
int f, t;
long long w;
}e[500005];
bool cmp(sss x, sss y) {
return x.w < y.w;
}
bool da, xiao;
int fa[500005];
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
long long Kru() {
long long ans = 0;
for (int i = 1; i <= n; i++) fa[i] = i;
int sum = 0;
for (int i = 1; i <= m; i++) {
if (sum == n - 1) break;
int x = find(e[i].f);
int y = find(e[i].t);
if (x != y) {
fa[x] = y;
ans += e[i].w;
sum++;
}
}
return ans;
}
int main() {
freopen("speed.in", "r", stdin);
freopen("speed.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> k;
xiao = da = true;
for (int i = 1; i <= m; i++) {
cin >> e[i].f >> e[i].t >> e[i].w;
if (e[i].w < k) da = false;
if (e[i].w > k) xiao = false;
}
if (xiao) {
long long ma = 0;
for (int i = 1; i <= m; i++) {
ma = max(ma, e[i].w);
}
cout << k - ma;
return 0;
}
if (da) {
sort(e + 1, e + 1 + m, cmp);
long long now = Kru();
cout << now - (n - 1) * k;
return 0;
}
sort(e + 1, e + 1 + m, cmp);
for (int i = 1; i <= n; i++) fa[i] = i;
int sum = 0;
long long mi = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= m; i++) {
mi = min(mi, 1ll * abs(k - e[i].w));
}
long long ans = 0;
for (int i = 1; i <= m; i++) {
if (sum == n - 1) break;
int x = find(e[i].f);
int y = find(e[i].t);
if (x != y) {
fa[x] = y;
if (e[i].w > k) ans += (e[i].w - k);
sum++;
}
}
if (ans == 0) cout << mi;
else cout << ans;
return 0;
}
酒鬼 （drunkard）27pts
赛时打了两个特殊性质27pts；
考虑正解，其实是一堆特判？
是的，所以不太想写了；
溜了。。。；
点击查看代码
#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <cmath>
using namespace std;
int n, m;
set<pair<int, int> > s;
int main() {
freopen("drunkard.in", "r", stdin);
freopen("drunkard.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
string ss;
int x, t;
int ma = 2e9, pos = 2e9, ls = -1;
bool vis = true;
for (int i = 1; i <= m; i++) {
cin >> ss;
if (ss == "clue") {
cin >> x >> t;
if (x - 1 > t) {
vis = false;
continue;
}
if (x > 1) {
ma = min(ma, t - (x - 1));
pos = min(pos, t);
}
s.insert({t, x});
auto ptr = s.find({t, x});
if (ptr != s.begin() && next(ptr) != s.end() && ls == (next(ptr) -> first)) ls = -1;
if (ptr != s.begin()) {
auto pp = prev(ptr);
if ((t - pp -> first) < abs(x - pp -> second)) {
vis = false;
continue;
}
if ((pp -> first + pp -> second) % 2 != (x + t) % 2) ls = max(ls, t);
}
if (next(ptr) != s.end()) {
auto pp = next(ptr);
if ((pp -> first - t) < abs(x - pp -> second)) {
vis = false;
continue;
}
if ((pp -> first + pp -> second) % 2 != (x + t) % 2) ls = max(ls, pp -> first);
}
if (pos < ls) {
vis = false;
continue;
}
}
if (ss == "min") {
if (!vis) {
cout << "bad" << '\n';
continue;
}
if (ls != -1) {
auto ptr = s.lower_bound({ls, 0});
cout << ((prev(ptr) -> first) + 1) << '\n';
} else {
if (s.empty()) cout << 0 << '\n';
else {
auto ptr = s.begin();
cout << (ptr -> first + ptr -> second + 1) % 2 << '\n';
}
}
}
if (ss == "max") {
if (!vis) {
cout << "bad" << '\n';
continue;
}
if (ma == 2e9) cout << "inf" << '\n';
else cout << ma << '\n';
}
}
return 0;
}
距离（distance）40pts
赛时居然没有打出 $ \Theta(n^2) $ 暴力？还是太菜；
对于暴力，$ \Theta(n^3) $ 很好打，$ \Theta(n^2) $ 考虑枚举每一对点，计算其贡献并加到其对应的祖先上，这个可以用树上差分解决（实在不行套个树剖也行）；
考虑正解，首先如果把 $ \min $ 换成 $ \max $ 的话，那么我们把 $ (a_x, b_x) \ (a_y, b_y) $ 看成两个点，所求即它们两个的切比雪夫距离；
所以用 $ \min-\max $ 容斥，即 $ a + b = \min(a, b) + \max(a, b) $，将要求的式子 $ \min(|a_x - a_y|, |b_x - b_y|) $ 换成 $ |a_x - a_y| + |b_x - b_y| - \max(|a_x - a_y|, |b_x - b_y|) $；
发现后面的那个还是不好求，所以考虑将切比雪夫距离转化为曼哈顿距离；
设 $ p_i = \frac{a_i + b_i}{2} \ q_i = \frac{a_i - b_i}{2} $，则 $ \max(|a_x - a_y|, |b_x - b_y|) = |p_x - p_y| + |q_x - q_y| $；
证明展开 $ \max(|a_x - a_y|, |b_x - b_y|) $ 中的绝对值即可（或者考虑曼哈顿距离转化为切比雪夫距离，然后逆推即可）；
所以原式就转化成了 $ |a_x - a_y| + |b_x - b_y| - |p_x - p_y| + |q_x - q_y| $，那么我们只需处理 $ 4 $ 个形如 $ |a - b| $ 的问题即可；
一种比较容易的想法是合并（毕竟好像只能从下往上合并），有两种，一种启发式合并，一种线段树合并，后一种比较好想，且时间复杂度较优；
那么我们的问题就转化为了如何在值域线段树上进行 push_up 操作；
首先离散化，因为有小数，所以可以都乘 $ 2 $；
考虑左对右的对答案的贡献，可以发现其贡献为 $ cnt_l \times sum_r - cnt_r \times sum_l $，其中 $ cnt $ 代表数出现的次数，$ sum $ 代表数的和；
这是大数减小数，反之同理，要乘 $ 2 $，但因为我们离散化的时候已经乘了，所以就不用乘了（居然形成了闭环！我现在才发现）；
所以我们就维护完了；
因为这个题卡空间，所以要分四次做，并且每次要清空线段树，所以常数很大，时间复杂度 $ \Theta(n \log n) $，挂一个 $ 7, 8 $ 的常数；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const long long mod = 1e9 + 7;
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define Flush FastIO::Fflush()
namespace FastIO {
const int SIZE = 1 << 16;
char buf[SIZE], obuf[SIZE], str[60];
int bi = SIZE, bn = SIZE, opt;
inline int read(register char *s) {
while(bn) {
for (; bi < bn && buf[bi] <= ' '; bi = -~bi);
if (bi < bn) break;
bn = fread(buf, 1, SIZE, stdin);
bi &= 0;
}
register int sn=0;
while(bn) {
for (; bi < bn && buf[bi] > ' '; bi = -~bi) s[sn++] = buf[bi];
if(bi < bn) break;
bn = fread(buf,1,SIZE,stdin);
bi &= 0;
}
s[sn] &= 0;
return sn;
}
inline bool read(register int &x){
int n = read(str), bf = 0;
if(!n) return 0;
register int i=0;
(str[i] == '-') && (bf = 1, i = -~i);
(str[i] == '+') && (i = -~i);
for (x = 0; i < n; i = -~i) x = (x << 3) + (x << 1) + (str[i] ^ 48);
bf && (x = ~x + 1);
return 1;
}
inline bool read(register long long &x) {
int n = read(str), bf = 1;
if(!n) return 0;
register int i=0;
(str[i] == '-') && (bf = -1,i = -~i);
for (x = 0; i < n; i= -~i) x = (x << 3) + (x << 1) + (str[i] ^ 48);
(bf < 0) && (x = ~x + 1);
return 1;
}
inline void write(register int x) {
if(!x) obuf[opt++] = '0';
else {
(x < 0) && (obuf[opt++] = '-', x = ~x + 1);
register int sn = 0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1; i >= 0; i = ~-i) obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void write(register long long x) {
if(!x) obuf[opt++] = '0';
else {
(x < 0) && (obuf[opt++] = '-', x = ~x + 1);
register int sn = 0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1; i >= 0; i = ~-i) obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void write(register unsigned long long x){
if(!x) obuf[opt++] = '0';
else {
register int sn=0;
while(x) str[sn++] = x % 10 + '0', x /= 10;
for (register int i = sn - 1 ; i >= 0 ; i = ~-i)obuf[opt++] = str[i];
}
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void write(register char x) {
obuf[opt++] = x;
(opt >= (SIZE >> 1)) && (fwrite(obuf, 1, opt, stdout), opt &= 0);
}
inline void Fflush(){
opt && fwrite(obuf, 1, opt, stdout);
opt &= 0;
}
}
int n;
struct sss{
int t, ne;
}e[2000005];
int h[2000005], cnt;
void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
long long a[500005], b[500005], c[2000005], ans[500005];
int len;
int rt[500005], tot;
namespace SEG{
struct sss{
int ls, rs;
int cnt;
long long sum, ans;
}tr[15000005];
inline void push_up(int id) {
tr[id].ans = (tr[tr[id].ls].ans + tr[tr[id].rs].ans) % mod;
tr[id].ans = (tr[id].ans + (tr[tr[id].ls].cnt * tr[tr[id].rs].sum % mod - tr[tr[id].rs].cnt * tr[tr[id].ls].sum % mod + mod) % mod) % mod;
tr[id].cnt = (tr[tr[id].ls].cnt + tr[tr[id].rs].cnt) % mod;
tr[id].sum = (tr[tr[id].ls].sum + tr[tr[id].rs].sum) % mod;
}
void add(int &id, int l, int r, int pos, long long val) {
if (!id) id = ++tot;
if (l == r) {
tr[id].cnt++;
tr[id].cnt %= mod;
tr[id].sum += val;
tr[id].sum %= mod;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) add(tr[id].ls, l, mid, pos, val);
else add(tr[id].rs, mid + 1, r, pos, val);
push_up(id);
}
int merge(int x, int y, int l, int r) {
if (!x || !y) return x + y;
if (l == r) {
tr[x].ans += tr[y].ans;
tr[x].ans %= mod;
tr[x].sum += tr[y].sum;
tr[x].sum %= mod;
tr[x].cnt += tr[y].cnt;
tr[x].cnt %= mod;
return x;
}
int mid = (l + r) >> 1;
tr[x].ls = merge(tr[x].ls, tr[y].ls, l, mid);
tr[x].rs = merge(tr[x].rs, tr[y].rs, mid + 1, r);
push_up(x);
return x;
}
}
void dfs(int x, int fa, int s) {
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (u == fa) continue;
dfs(u, x, s);
rt[x] = SEG::merge(rt[x], rt[u], 1, len);
}
if (s == 1) SEG::add(rt[x], 1, len, lower_bound(c + 1, c + 1 + len, 2 * a[x]) - c, 2 * a[x]);
if (s == 2) SEG::add(rt[x], 1, len, lower_bound(c + 1, c + 1 + len, 2 * b[x]) - c, 2 * b[x]);
if (s == 3) SEG::add(rt[x], 1, len, lower_bound(c + 1, c + 1 + len, a[x] + b[x]) - c, a[x] + b[x]);
if (s == 4) SEG::add(rt[x], 1, len, lower_bound(c + 1, c + 1 + len, a[x] - b[x]) - c, a[x] - b[x]);
if (s <= 2) ans[x] = (ans[x] + SEG::tr[rt[x]].ans) % mod;
else ans[x] = (ans[x] - SEG::tr[rt[x]].ans + mod) % mod;
}
int main() {
freopen("distance.in", "r", stdin);
freopen("distance.out", "w", stdout);
FI(n);
int x, y;
for (int i = 1; i <= n - 1; i++) {
FI(x);
FI(y);
add(x, y);
add(y, x);
}
for (int i = 1; i <= n; i++) {
FI(a[i]);
FI(b[i]);
c[++len] = 2 * a[i];
c[++len] = 2 * b[i];
c[++len] = a[i] + b[i];
c[++len] = a[i] - b[i];
}
sort(c + 1, c + 1 + len);
len = unique(c + 1, c + 1 + len) - c - 1;
for (int i = 1; i <= 4; i++) {
dfs(1, 0, i);
for (int j = 1; j <= n; j++) rt[j] = 0;
for (int j = 1; j <= tot; j++) {
SEG::tr[j].ls = SEG::tr[j].rs = SEG::tr[j].cnt = SEG::tr[j].sum = SEG::tr[j].ans = 0;
}
tot = 0;
}
for (int i = 1; i <= n; i++) {
FO(ans[i]);
FO('\n');
}
Flush;
return 0;
}