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 << '
';
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;
}