暴力错解大赛
玩游戏 82pts
乱糊的错解，正确性和时间复杂度都不对，但是拿了82pts；
对于正解，考虑从 $ k $ 将原序列分成两个部分，左边和右边，然后分别求一次前缀和（注意这里，可以省去很多分讨和常数），设前一个前缀和数组为 $ a $，后一个为 $ b $，那么问题就转化成有两个指针 $ i, j $，可以任意移动，询问是否可以将其都移到数组最后，但在每一个时刻都要满足 $ a_i + b_j \leq 0 $；
那么贪心的思路是每次看看能不能将 $ i $ 或 $ j $ 移动到下一个比它小的位置，如果能就移过去，正确性挺对；
但是这样只能将这两个指针移动到数组中最小的位置，考虑到后面的移动其实就是前面的移动的反方向，所以将数组倒过来再做一遍即可，时间复杂度 $ \Theta(Tn) $，常数有些大；
注意实现时有很多细节，要小心处理，注意边界，要不然一不小心时间复杂度就炸了；
注意为了保证时间复杂度，在实现过程中要时刻保证 $ i, j $ 单调，具体的，可以开一个 $ pos $ 数组存储现在这一位到的位置，然后下次遍历时直接从这里遍历即可；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int t;
int n, k;
long long a[500005], b[500005], c[500005], bmi, cmi;
int blen, clen, bpos, cpos;
int pos[2][500005];
bool ans;
void w() {
int l = 0, r = 0;
long long sum = 0;
while(1) {
if (l == bpos && r == cpos) break;
long long now = 0;
bool vis = false;
if (l != bpos) {
for (int i = pos[0][l]; i <= blen; i++) {
now = sum - b[l] + b[i];
if (now > 0) {
pos[0][l] = i;
break;
}
if (now <= sum) {
l = i;
sum = now;
vis = true;
break;
}
if (i == blen) pos[0][l] = blen;
}
}
if (r != cpos) {
for (int i = pos[1][r]; i <= clen; i++) {
now = sum - c[r] + c[i];
if (now > 0) {
pos[1][r] = i;
break;
}
if (now <= sum) {
r = i;
sum = now;
vis = true;
break;
}
if (i == clen) pos[1][r] = clen;
}
}
if (!vis) {
if (r == 0) {
r = 1;
sum = b[l] + c[r];
if (sum > 0) {
ans = false;
break;
}
} else if (l == 0) {
l = 1;
sum = b[l] + c[r];
if (sum > 0) {
ans = false;
break;
}
} else {
ans = false;
break;
}
}
}
}
int main() {
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
bmi = 2e18;
cmi = 2e18;
cpos = bpos = 0;
for (int i = k; i >= 2; i--) {
blen++;
b[blen] = b[blen - 1] + a[i];
if (bmi >= b[blen]) {
bmi = b[blen];
bpos = blen;
}
}
b[blen + 1] = 2e18;
for (int i = k + 1; i <= n; i++) {
clen++;
c[clen] = c[clen - 1] + a[i];
if (cmi >= c[clen]) {
cmi = c[clen];
cpos = clen;
}
}
c[clen + 1] = 2e18;
for (int i = 0; i <= blen; i++) pos[0][i] = i + 1;
for (int i = 0; i <= clen; i++) pos[1][i] = i + 1;
ans = true;
w();
reverse(b + 1, b + 1 + blen);
reverse(c + 1, c + 1 + clen);
if (bpos != 0) bpos = blen - bpos + 1;
if (cpos != 0) cpos = clen - cpos + 1;
for (int i = 0; i <= blen; i++) pos[0][i] = i + 1;
for (int i = 0; i <= clen; i++) pos[1][i] = i + 1;
w();
if (c[1] == 2e18) c[1] = 0;
if (b[1] == 2e18) b[1] = 0;
if (c[1] + b[1] > 0) ans = false;
if (ans) cout << "Yes" << '\n';
else cout << "No" << '\n';
for (int i = 1; i <= blen + 1; i++) b[i] = 0;
for (int i = 1; i <= clen + 1; i++) c[i] = 0;
for (int i = 0; i <= blen; i++) pos[0][i] = 0;
for (int i = 0; i <= clen; i++) pos[1][i] = 0;
blen = 0;
clen = 0;
}
return 0;
}
矩形 20pts
不喷了，题解错了，std和题解写的根本不是一个东西；
然后我没发现，就按照题解打了三个树套树，然后就没然后了；
其实好像上个扫描线就行，没写，被题解恶心到了；
想看正解请自行翻阅其它博客；
选彩笔（rgb）60pts
赛时树套树求解三维数点 + 二分答案假了，60pts；
其实正解就是三维数点，先二分一个答案 $ mid $，考虑一个 $ mid \times mid \times mid $ 的立方体，只要我们在这个由值域 $ V $ 所组成的三维空间 $ V \times V \times V $ 中找到这样一个立方体，满足其内部的点数 $ \geq k $ 即可；
那么可以 三维前缀和 + 容斥 处理，时间复杂度：$ \Theta(V^3 \log V) $；
注意原题中有 $ 0 $，所以要将输入的三个参数都 $ + 1 $；
经验：一般想到树套树的题都不用树套树做（可能能拿部分分或者错解骗分）；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, kk;
int sum[266][266][266];
bool ck(int x) {
int su = 0;
for (int i = 1; i + x <= 256; i++) {
for (int j = 1; j + x <= 256; j++) {
for (int k = 1; k + x <= 256; k++) {
su = sum[i + x][j + x][k + x] - sum[i - 1][j + x][k + x] - sum[i + x][j - 1][k + x] - sum[i + x][j + x][k - 1] + sum[i - 1][j - 1][k + x] + sum[i - 1][j + x][k - 1] + sum[i + x][j - 1][k - 1] - sum[i - 1][j - 1][k - 1];
if (su >= kk) return true;
}
}
}
return false;
}
int main() {
freopen("rgb.in", "r", stdin);
freopen("rgb.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> kk;
int x, y, z;
for (int i = 1; i <= n; i++) {
cin >> x >> y >> z;
sum[++x][++y][++z]++;
}
for (int i = 1; i <= 256; i++) {
for (int j = 1; j <= 256; j++) {
for (int k = 1; k <= 256; k++) {
sum[i][j][k] += sum[i - 1][j][k] + sum[i][j - 1][k] + sum[i][j][k - 1] - sum[i - 1][j - 1][k] - sum[i - 1][j][k - 1] - sum[i][j - 1][k - 1] + sum[i - 1][j - 1][k - 1];
}
}
}
int l = 0;
int r = 225;
int ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if (ck(mid)) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
cout << ans;
return 0;
}
兵蚁排序（sort）100pts
按照样例二模拟即可；
因为操作数 $ \leq n^2 $ 所以我们尽量让操作数等于 $ n^2 $；
每次将大的一步一步向前交换过来就行；
正确性：因为这样会尽可能的保留 $ a $ 原来的结构以便下一次操作，贪心的想一想是对的；
时间复杂度：$ \Theta(Tn^2) $；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n;
int a[500005], b[500005];
pair<int, int> an[500005];
int cnt;
int main() {
freopen("sort.in", "r", stdin);
freopen("sort.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--) {
cin >> n;
cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
bool ans = true;
for (int i = 1; i <= n; i++) {
if (a[i] == b[i]) continue;
int mi = 0x3f3f3f3f;
int pos = 0;
for (int j = i; j <= n; j++) {
mi = min(mi, a[j]);
if (a[j] == b[i]) {
pos = j;
break;
}
}
if (mi < b[i] || !pos) {
ans = false;
break;
}
for (int j = pos - 1; j >= i; j--) {
an[++cnt] = {j, j + 1};
swap(a[j], a[j + 1]);
}
}
if (!ans) {
cout << -1 << '\n';
} else {
cout << 0 << '\n';
cout << cnt << '\n';
for (int i = 1; i <= cnt; i++) {
cout << an[i].first << ' ' << an[i].second << '\n';
}
}
}
return 0;
}
银行的源起（banking）10pts
按照题意模拟10pts；
考虑正解，首先考虑只有一个银行怎么做；
那么对于这种题，我们有一种套路，就是考虑每条边的贡献；
首先钦定 $ 1 $ 为根；
那么考虑走这条边的人数，发现银行只可能在子树里或者在子树外，所以一条边 $ (x, u) $ （其中 $ u $ 为儿子）的贡献为 $ w \times \min(siz_u, siz_1 - siz_u) $；
考虑为什么是对的，因为在这棵树上，会有一个节点满足其儿子的 $ siz < siz_1 - siz_u $ ，但是其自身的 $ siz \geq siz_1 - siz $，这个节点就可以是银行，并且它上面的点都满足 $ siz > siz_1 - siz $，所以是对的；
这个问题直接 $ \Theta(n) $ 就做完了；
考虑两个银行的情况，我们不难发现，原图中会有一条边没人走，因为这两个节点的最近的银行不一样，且只会有一条边，因为只有两个银行，原图只能被分成两个连通块；
那么我们可以枚举这一条边，然后对这两个连通块分别做一次 $ \Theta(n) $ 的做法，就得到了 $ \Theta(n^2) $ 的做法；
考虑如何优化；
对式子 $ w \times \min(siz_u, siz_1 - siz_u) $ 下手，此时对于这条边 $ (x, u) $，我们钦定把它断开，于是原图分成两部分，我们以 $ u $ 子树为例，拆开这个式子：
设 $ X = siz_u $；
原式可以化为（其中 $ y $ 是 $ u $ 的后代）：
\[w \times siz_y [siz_y \leq \frac{X}{2}] + w \times X [siz_y > \frac{X}{2}] - w \times siz_y [siz_y > \frac{X}{2}] \]那么对于一条边 $ (x, u) $，其中 $ u $ 为儿子，我们将 $ u $ 和这条边 $ (x, u) $ 看作一体，这样的话我们直接开两棵以 $ siz $ 为下标的动态开点线段树，一棵记录 $ \sum w $，一棵记录 $ \sum w \times siz $ 就解决了这个问题；
对于 $ u $ 子树外的点同理，但是要特殊判断 $ 1 $ 到 $ u $ （不包含 $ u $）的这条链的情况，因为它们的 $ siz $ 不同；
这样的话，我们在全局开两棵线段树记录所有的 $ \sum w $ 和 $ \sum w \times siz $ （一棵也行），然后对于链再开两棵线段树记录一下这个链的情况，注意在递归向下的时候对全局的线段树进行删除操作，回溯的时候进行加操作，对于链正好反过来；
因为我们要查询某一个子树，所以对子树在开两棵线段树，并且回溯的时候进行合并即可；
这样我们开了六棵线段树就解决了这个问题；
时间复杂度：$ \Theta(n \log V) $，其中 $ V $ 是 $ \max siz $，常数极大，只能拿82pts（具体见[PEP] 关于卡场）；
点击查看代码
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include <iostream>
#include <cstdio>
using namespace std;
#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 t;
int n;
long long a[500005];
struct sss{
int t, ne;
long long w;
}e[500005];
int h[500005], cnt;
inline void add(int u, int v, long long ww) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
e[cnt].w = ww;
}
long long siz[500005];
long long tt;
int rt[500005], tot[2];
namespace top_tr{
struct sss{
int ls, rs;
long long sum;
}tr[2][6500005];
inline void push_up(long long s, long long id) {
tr[s][id].sum = tr[s][tr[s][id].ls].sum + tr[s][tr[s][id].rs].sum;
}
void add(long long s, int &id, long long l, long long r, long long pos, long long d) {
if (!id) id = ++tot[s];
if (l == r) {
tr[s][id].sum += d;
return;
}
long long mid = (l + r) >> 1;
if (pos <= mid) add(s, tr[s][id].ls, l, mid, pos, d);
else add(s, tr[s][id].rs, mid + 1, r, pos, d);
push_up(s, id);
}
long long merge(int s, long long x, long long y, long long l, long long r) {
if (!x || !y) return x + y;
if (l == r) {
tr[s][x].sum += tr[s][y].sum;
return x;
}
long long mid = (l + r) >> 1;
tr[s][x].ls = merge(s, tr[s][x].ls, tr[s][y].ls, l, mid);
tr[s][x].rs = merge(s, tr[s][x].rs, tr[s][y].rs, mid + 1, r);
push_up(s, x);
return x;
}
long long ask(int s, int id, long long L, long long R, long long l, long long r) {
if (l > r) return 0;
if (!id) return 0;
if (L >= l && R <= r) return tr[s][id].sum;
long long mid = (L + R) >> 1;
if (r <= mid) return ask(s, tr[s][id].ls, L, mid, l, r);
else if (l > mid) return ask(s, tr[s][id].rs, mid + 1, R, l, r);
else return ask(s, tr[s][id].ls, L, mid, l, mid) + ask(s, tr[s][id].rs, mid + 1, R, mid + 1, r);
}
}
long long ans;
void sfs(long long x, long long fa) {
siz[x] = a[x];
for (long long i = h[x]; i; i = e[i].ne) {
long long u = e[i].t;
if (u == fa) continue;
sfs(u, x);
siz[x] += siz[u];
rt[x] = top_tr::merge(0, rt[x], rt[u], 1, tt);
rt[x + n + 1] = top_tr::merge(1, rt[x + n + 1], rt[u + n + 1], 1, tt);
top_tr::add(0, rt[x], 1, tt, siz[u], e[i].w * siz[u]);
top_tr::add(1, rt[x + n + 1], 1, tt, siz[u], e[i].w);
}
}
void dfs(long long x, long long fa) {
for (long long i = h[x]; i; i = e[i].ne) {
long long u = e[i].t;
if (u == fa) continue;
top_tr::add(0, rt[0], 1, tt, siz[u], e[i].w * siz[u]);
top_tr::add(1, rt[0 + n + 1], 1, tt, siz[u], e[i].w);
top_tr::add(0, rt[1], 1, tt, siz[u], -e[i].w * siz[u]);
top_tr::add(1, rt[1 + n + 1], 1, tt, siz[u], -e[i].w);
dfs(u, x);
top_tr::add(0, rt[0], 1, tt, siz[u], -e[i].w * siz[u]);
top_tr::add(1, rt[0 + n + 1], 1, tt, siz[u], -e[i].w);
long long an = 0;
long long X = siz[u];
long long Y = siz[1] - siz[u];
long long sum = 0;
sum = top_tr::ask(0, rt[u + 2 * n + 1], 1, tt, 1, X / 2);
long long su = 0;
su = top_tr::ask(1, rt[u + 3 * n + 1], 1, tt, X / 2 + 1, tt);
su *= X;
su -= top_tr::ask(0, rt[u + 2 * n + 1], 1, tt, X / 2 + 1, tt);
an += sum + su;
sum = top_tr::ask(0, rt[1], 1, tt, 1, Y / 2) - top_tr::ask(0, rt[u + 2 * n + 1], 1, tt, 1, Y / 2);
su = top_tr::ask(1, rt[1 + n + 1], 1, tt, Y / 2 + 1, tt) - top_tr::ask(1, rt[u + 3 * n + 1], 1, tt, Y / 2 + 1, tt);
su *= Y;
su -= (top_tr::ask(0, rt[1], 1, tt, Y / 2 + 1, tt) - top_tr::ask(0, rt[u + 2 * n + 1], 1, tt, Y / 2 + 1, tt));
an += sum + su;
sum = top_tr::ask(0, rt[0], 1, tt, siz[u], Y / 2 + siz[u]);
long long ss = top_tr::ask(1, rt[0 + n + 1], 1, tt, siz[u], Y / 2 + siz[u]);
ss *= siz[u];
sum -= ss;
long long sss = top_tr::ask(1, rt[0 + n + 1], 1, tt, Y / 2 + siz[u] + 1, tt);
su = sss;
su *= Y;
su -= top_tr::ask(0, rt[0], 1, tt, Y / 2 + siz[u] + 1, tt);
ss = sss;
ss *= siz[u];
su += ss;
an += sum + su;
ans = min(ans, an);
top_tr::add(0, rt[1], 1, tt, siz[u], e[i].w * siz[u]);
top_tr::add(1, rt[1 + n + 1], 1, tt, siz[u], e[i].w);
rt[x + 2 * n + 1] = top_tr::merge(0, rt[x + 2 * n + 1], rt[u + 2 * n + 1], 1, tt);
rt[x + 3 * n + 1] = top_tr::merge(1, rt[x + 3 * n + 1], rt[u + 3 * n + 1], 1, tt);
top_tr::add(0, rt[x + 2 * n + 1], 1, tt, siz[u], e[i].w * siz[u]);
top_tr::add(1, rt[x + 3 * n + 1], 1, tt, siz[u], e[i].w);
}
}
int main() {
freopen("banking.in", "r", stdin);
freopen("banking.out", "w", stdout);
FI(t);
while(t--) {
FI(n);
for (long long i = 1; i <= n; i++) {
FI(a[i]);
tt += a[i];
}
long long x, y;
long long w;
ans = 2e18;
for (long long i = 1; i <= n - 1; i++) {
FI(x); FI(y); FI(w);
add(x, y, w);
add(y, x, w);
}
sfs(1, 0);
dfs(1, 0);
FO(ans);
FO('\n');
for (long long i = 1; i <= n; i++) {
h[i] = 0;
}
cnt = 0;
for (long long s = 0; s <= 1; s++) {
for (long long i = 1; i <= tot[s]; i++) {
top_tr::tr[s][i].ls = top_tr::tr[s][i].rs = top_tr::tr[s][i].sum = 0;
}
}
for (long long i = 0; i <= 4 * n + 1; i++) {
rt[i] = 0;
siz[i] = 0;
}
tt = 0;
tot[0] = tot[1] = 0;
}
Flush;
return 0;
}