Codeforces Round #703 (Div. 2)

D. Max Median

题意：

求所有长度不小于\(k\)的子区间中中位数最大值

思路：

二分答案，记当前答案为\(x\)，判断所有长度不小于\(k\)的子区间中是否存在中位数大于等于\(x\)的区间，即判断区间大于等于\(x\)的数的数量是否大于小于\(x\)的数的数量

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int a[maxn], s[maxn], mn[maxn], n, k;
bool check(int x){
    for(int i = 1; i <= n; ++i){
        s[i] = s[i - 1] + (a[i] >= x ? 1 : -1);
        mn[i] = min(mn[i - 1], s[i]);
    }
    for(int i = k; i <= n; ++i)
        if(s[i] > mn[i - k]) return 1;
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    int l = 1, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)) l = mid + 1;
        else r = mid -1;
    }
    cout << l - 1 << ‘\n‘;
    return 0;
}

E. Paired Payment

题意：

无向图，但是只能以两条连续的边为单位移动，权值为\((a + b)^2\)，求\(1\)出发的最短路

思路：

建图之后跑\(Dijkstra\)，直接建图肯定不行，对于\(1-n\)每个点，额外建\(50\)个点，那么这\(n\)个点不直接相连，通过这\(50n\)个点相连
对于每条边\((x,y,z)\)，建单向边\(<x,(y,z),0>\)，\(<y,(x,z),0>\)，\(<(x,i),y,(z+i)^2>\)，\(<(y,i),x,(z+i)^2>\) \((1 <= i <= 50)\)(\((x,i)\)表示属于点\(x\)的第\(i\)个点)
跑\(Dijkstra\)即可
因为对于边\((x,y,z)\)，我们不知道\(x\)可以通过\(y\)连到谁，也不知道\(y\)通过\(x\)可以连到谁
所以我们就用中介节点用来存这些信息
假设\(x\)通过\(y\)能连到\(u\)，那我们就把\(x\)和点\((y,z)\)相连
相当于一个东西要从\(x\)到\(u\)，先把它暂存在\((y,z)\)
在未来如果遇到了边\((y,u,z)\)，那么\((y,1)...(y,50)\)都会连一条有向边到u
那么之前暂存在\((y,z)\)的东西就可以顺利到达\(u\)了
原来按照题意应该是从\(x\)到\(u\)是一条路直达，现在变成了\(x\)到\((y,z)\)再到\(u\)
所以这两条边的边权应该选择一条置零，考虑到效率问题，应该把\(<x,(y,z)>\)置零

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5100010;
vector<pii> d[maxn];
int n, m, x, y, z;
int getNode(int u, int w) {
    return n + (u - 1) * 50 + w;
}
struct node {
    int v, c;
    node(int _v = 0, int _c = 0) : v(_v), c(_c) {}
    bool operator<(const node& a) const {
        return c > a.c;
    }
};
int dis[maxn], vis[maxn];
void dijkstra(int st) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node> q;
    dis[st] = 0;
    q.push(node(st, 0));
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int u = tmp.v;
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto i : d[u]) {
            if (!vis[i.first] && dis[i.first] > dis[u] + i.second) {
                dis[i.first] = dis[u] + i.second;
                q.push(node(i.first, dis[i.first]));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    while (m--) {
        cin >> x >> y >> z;
        d[x].push_back(pii(getNode(y, z), 0));
        d[y].push_back(pii(getNode(x, z), 0));
        for (int i = 1; i <= 50; ++i) {
            d[getNode(y, i)].push_back(pii(x, (z + i) * (z + i)));
            d[getNode(x, i)].push_back(pii(y, (z + i) * (z + i)));
        }
    }
    dijkstra(1);
    for (int i = 1; i <= n; ++i) {
        if (dis[i] == 0x3f3f3f3f)
            cout << -1 << ‘ ‘;
        else
            cout << dis[i] << ‘ ‘;
    }
    return 0;
}

Codeforces Round #703 (Div. 2)

原文：https://www.cnblogs.com/Zeronera/p/14417684.html