比赛总结：

杭电杯7

赛中：

赛后补题：

Triangle Game

很傻逼的一个题目就是没有想到，要是补了牛客的蔚蓝杯7的话就很容易猜到结论了。

有了结论代码就是几行而已！！！

 Problem - 7216

 牛客的博弈题目：

登录—专业IT笔试面试备考平台_牛客网 Great Party，这个还用了前缀和分块，有点抽象，有点难理解。

有点莫队，然后就是排序时要分块，否则莫队跳动太大还是会T。

杭电杯8

赛中：

 赛后补题：

Ironforge        

Problem - 7224

这个题目与答案还差一点，主要是从后面更新之后，然后再从前面更新的时候有的变动会影响后面更新出来的答案，然后就是这里卡了，没有想到直接while消除影响为止，没有想到时间竟然够够的！！！！

 

Darnassus

Problem - 7226

这个题目主要就是想到surt(n-1)，想到就好写了，但是这个题目实在是太卡时间了！！！

第一种：

#include 
#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 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 
#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 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 
#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 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刷题：