正文
2020 NUC 19级第一次训练赛
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
感染(low)
Description
n户人家住在一条直线上，从左往右依次编号为1，2，...，n。起初，有m户人家感染了COVID-19，而接下来的每天感染的人家都会感染他家左右两家的人，问t天后总共有多少人家会感染。
Input
第一行输入三个整数n(1 <= n <= 2e5)，m(0 <= m <= n)，t(1<= t <= 2e5)。
第二行m个整数ai(1 <= ai <= n)，代表最初感染的m户人家的编号。
Output
输出一个整数，代表最后会有多少人家感染。
Sample Input 1
10 3 2
1 3 4
Sample Output 1
6 分析：这个题实际上就是以m个点为中心，生成了m条长度最多为2*m的线段，然后合并这m条线段就可以了。
第i条线段的信息可以表示为[max(1, a[i] - t), min(n, a[i] + t)}。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + ;
int a[maxn];
vector<pair<int, int> > v;
int main() {
int n, m, t;
cin >> n >> m >> t;
for (int i = ; i <= m; i++)
cin >> a[i];
sort(a + , a + + m);
for (int i = ; i <= m; i++) {
int l = max(, a[i] - t);
int r = min(n, a[i] + t);
v.push_back(make_pair(l, r));
}
int i = , res = ;
while (i < m) {
int j = i + ;
while (j < m && v[j].first <= v[j - ].second) {
j++;
}
res += v[j - ].second - v[i].first + ;
i = j;
}
cout << res <<endl;
return ;
}
第k短路
Description
一天，HighLights实在是闲的不行，他选取了n个地点，n各地点之间共有m条路径，他想找到这m条路径组成的第k短路，你能帮助他嘛？
Input
第一行三个正整数，地点的数量n（2 <= n <= 2e5），边的数量m（1 <= m <= 2e5），k（1 <= k <= min(m, 200)）。
接下来m行，每行三个整数，边的一个顶点u（1<=u<=n），边的另一个顶点v(1<=v<=n)，边的权值w(1<=w<=1e5)，代表u有一条到v权值为w的单向边。
Output
输出第k短路的权值。
Sample Input 1
4 4 3
1 3 27
1 4 16
1 2 15
2 4 3
Sample Output 1
16 分析：这个题可以刚开始看的时候被吓到了，但是实际上这个题比较简单。因为k被限制了，k比较小，保证了k不大于m。
也就是第k短路是由权值前k小的边产生的子图构成的。
那么我们就可以对边进行权值从小到大排序，然后取权值前k的边，重新建图。
这里对顶点需要进行重新编号，可以使用map或set，然后建立一个新的单向图。
再对这个图跑个floyd，最后把G[i][j](i != j)都取出来，
从小到大排个序，那么排序完后第k个就是我们想要的第k短路了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + ;
const int maxm = 4e2 + ;
struct node{
int u, v, w;
} e[maxn];
bool cmp(node a, node b) {
return a.w < b.w;
}
set<int> st;
int G[maxm][maxm];
map<int, int> id;
vector<int> res;
int main() { int n, m, t;
memset(G, 0x3f, sizeof(G));
for (int i = ; i < maxm; i++) {
G[i][i] = ;
}
cin >> n >> m >> t;
for (int i = ; i < m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e, e + m, cmp);
for (int i = ; i < t; i++) {
st.insert(e[i].u);
st.insert(e[i].v);
}
int len = ;
for (auto p = st.begin(); p != st.end(); p++) {
id[*p] = ++len;
}
for (int i = ; i < t; i++) {
G[id[e[i].u]][id[e[i].v]] = min(G[id[e[i].u]][id[e[i].v]], e[i].w);
}
for (int i = ; i <= len; i++) {
for (int j = ; j <= len; j++) {
for (int k = ; k <= len; k++) {
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
}
}
for (int i = ; i <= len; i++) {
for (int j = ; j <= len; j++) {
if (i == j) continue;
res.push_back(G[i][j]);
}
}
sort(res.begin(), res.end());
cout << res[t - ] << endl;
return ;
}
