比赛总结：
杭电杯7
赛中：
赛后补题：
Triangle Game
很傻逼的一个题目就是没有想到，要是补了牛客的蔚蓝杯7的话就很容易猜到结论了。
有了结论代码就是几行而已！！！
牛客的博弈题目：
登录—专业IT笔试面试备考平台_牛客网 Great Party，这个还用了前缀和分块，有点抽象，有点难理解。
有点莫队，然后就是排序时要分块，否则莫队跳动太大还是会T。
杭电杯8
赛中：
赛后补题：
Ironforge
这个题目与答案还差一点，主要是从后面更新之后，然后再从前面更新的时候有的变动会影响后面更新出来的答案，然后就是这里卡了，没有想到直接while消除影响为止，没有想到时间竟然够够的！！！！
Darnassus
这个题目主要就是想到surt(n-1)，想到就好写了，但是这个题目实在是太卡时间了！！！
第一种：
#include <bits/stdc++.h>
#define OST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
using namespace std;
const int N = 50000 + 5;
int n;
int a[N], b[N], f[N];
struct node {
int x, y, v;
};
bool cmp(node x1, node x2) { return x1.v < x2.v; }
int find(int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], b[a[i]] = i, f[i] = i;
vector<node> res;
int len = sqrt(n - 1);
for (int i = 1; i < n; i++) {
int maxn = n - 1, idx = i + 1;
for (int j = i + 1; j <= min(n, i + len); j++) {
int tmp = (j - i) * abs(a[j] - a[i]);
if (tmp < maxn) {
maxn = tmp;
idx = j;
}
}
res.push_back({i, idx, maxn});
}
for (int i = 1; i < n; i++) {
int maxn = n - 1, idx = i + 1;
for (int j = i + 1; j <= min(n, i + len); j++) {
int tmp = (j - i) * abs(b[j] - b[i]);
if (tmp < maxn) {
maxn = tmp;
idx = j;
}
}
res.push_back({b[i], b[idx], maxn});
}
// cout << res.size() << endl;
sort(res.begin(), res.end(), cmp);
long long sum = 0, cnt = 0;
for (int i = 0; i < (int) res.size(); i++) {
int fx = find(res[i].x);
int fy = find(res[i].y);
if (fx == fy) { continue; }
f[fx] = fy;
cnt++;
sum += res[i].v;
if (cnt == n) { break; }
}
cout << sum << endl;
}
signed main() {
OST;
int T = 1;
cin >> T;
while (T--) { solve(); }
return 0;
}第二种：
#include <bits/stdc++.h>
#define OST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
using namespace std;
const int N = 50000 + 5;
int n;
int a[N], b[N], f[N];
struct node {
int x, y, v;
};
vector<node> res[N];
// bool cmp(node x1, node x2) { return x1.v < x2.v; }
int find(int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], b[a[i]] = i, res[i].clear(), f[i] = i;
int len = sqrt(n);
for (int i = 1; i <= n; i++) {
int maxn = n;
for (int j = i + 1; j <= min(n, i + len); j++) {
int tmp = (j - i) * abs(a[j] - a[i]);
if (tmp < maxn) { res[tmp].push_back({i, j, tmp}); }
tmp = (j - i) * abs(b[j] - b[i]);
if (tmp < maxn) { res[tmp].push_back({b[i], b[j], tmp}); }
}
}
// cout << res.size() << endl;
long long sum = 0, cnt = 1;
for (int i = 1; i < n; i++) {
for (auto x : res[i]) {
int fx = find(x.x);
int fy = find(x.y);
if (fx == fy) continue;
f[fx] = fy;
sum += x.v;
cnt++;
if (cnt == n) break;
}
if (cnt == n) break;
}
cout << sum << endl;
}
signed main() {
OST;
int T = 1;
cin >> T;
while (T--) { solve(); }
return 0;
}最后才过的！！！
#include <bits/stdc++.h>
#define OST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define endl "\n"
using namespace std;
const int N = 50000 + 5;
int n;
int a[N], b[N], f[N];
struct node {
int x, y, v;
};
vector<node> res[N];
// bool cmp(node x1, node x2) { return x1.v < x2.v; }
struct node2 {
int x, y, nxt;
} e[460 * N];
int eCnt, first[N];
void add(int x, int y, int w) {
e[++eCnt].x = x;
e[eCnt].y = y;
e[eCnt].nxt = first[w];
first[w] = eCnt;
}
int find(int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], b[a[i]] = i, first[i] = 0, f[i] = i;
eCnt = 0;
int len = sqrt(n);
for (int i = 1; i <= n; i++) {
int maxn = n;
for (int j = i + 1; j <= min(n, i + len); j++) {
int tmp = (j - i) * abs(a[j] - a[i]);
// if (tmp < maxn) { res[tmp].push_back({i, j, tmp}); }
if (tmp < maxn) add(i, j, tmp);
tmp = (j - i) * abs(b[j] - b[i]);
// if (tmp < maxn) { res[tmp].push_back({b[i], b[j], tmp}); }
if (tmp < maxn) add(b[i], b[j], tmp);
}
}
// cout << res.size() << endl;
long long sum = 0, cnt = 1;
// for (int i = 1; i < n; i++) {
// for (auto x : res[i]) {
// int fx = find(x.x);
// int fy = find(x.y);
// if (fx == fy) continue;
// f[fx] = fy;
// sum += x.v;
// cnt++;
// if (cnt == n) break;
// }
// }
for (int i = 1; i < n; i++) {
for (int j = first[i]; j; j = e[j].nxt) {
int fx = find(e[j].x);
int fy = find(e[j].y);
if (fx == fy) continue;
f[fx] = fy;
cnt++;
sum += i;
if (cnt == n) break;
}
if (cnt == n) break;
}
cout << sum << endl;
}
signed main() {
OST;
int T = 1;
cin >> T;
while (T--) { solve(); }
return 0;
}CF刷题：
本文含有隐藏内容，请 开通VIP 后查看