A - 瑞士轮
难度: ⭐⭐⭐
题目大意
现有n个人, n一定是偶数, 每个人都有一个初始分数p和能力值s; 进行进行r轮比赛, 每轮比赛先按分数将n人进行排序, 第一名和第二名比, 第三名和第四名比, 以此类推, 能力值高者获胜, 胜者加一分, 败者不加分; 问r轮过后排名第k的人是谁;
解题思路
本题只给了500ms, 所以不能每轮都sort一遍, 因为sort是插入排序; 本题需要用归并排序, 因为归并排序对于一个有序的序列是不用递归的, 也就是O(n)的复杂度;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, k;
int p[N], s[N], f[N];
PII win[N], lose[N];
bool cmp(int a, int b){
if(p[a] == p[b]) return a < b;
return p[a] > p[b];
}
void merge(int l, int r){
int a = 1, b = 1, c = 0;
while(a <= l && b <= r){
if(win[a].second > lose[b].second){
f[++c] = win[a++].first;
}
else if(win[a].second < lose[b].second){
f[++c] = lose[b++].first;
}
else{
if(win[a].first < lose[b].first) f[++c] = win[a++].first;
else f[++c] = lose[b++].first;
}
}
while(a <= l) f[++c] = win[a++].first;
while(b <= r) f[++c] = lose[b++].first;
}
signed main(){
IOS;
cin >> n >> m >> k;
n *= 2;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= n; i++) cin >> s[i];
sort(f + 1, f + 1 + n, cmp);
while(m--){
int l = 0, r = 0;
for(int i = 1; i <= n; i += 2){
if(s[f[i]] > s[f[i + 1]]){
p[f[i]]++;
win[++l] = {f[i], p[f[i]]};
lose[++r] = {f[i + 1], p[f[i + 1]]};
}
else{
p[f[i + 1]]++;
win[++l] = {f[i + 1], p[f[i + 1]]};
lose[++r] = {f[i], p[f[i]]};
}
}
merge(l, r);
}
cout << f[k] << endl;
return 0;
}
B - 传送门
难度: ⭐⭐⭐
题目大意
给定一个有n个点m条边的无向图; 边权均为正数; 现在我们可以选择两个顶点, 让其连起一条边权为0的边; 请问怎么挑选可以让任意两个顶点的路径长度和最小;
解题思路
一个多源最短路, 再加上100的数据范围不难想到要用floyd; 然后模拟是O(n3)的复杂度, 所以要考虑优化; 根据floyd的内涵, 三层循环k, i, j是把点k作为i到j路径上的一个点进行求解; 现在我们在a和b之间加一条边, 那么我们就可以再把a和b作为路径上的点去再更新一遍路径; 所以我们可以先走一遍floyd把初始路径都预处理除了, 然后遍历要添加的边, 每次用预处理好的数据再进行floyd即可, 因此这里的floyd就不需要再遍历k了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e2 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, res = inf;
string s;
int g[N][N], d[N][N];
void floyd(){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
void query(int u){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
d[i][j] = min(d[i][j], d[i][u] + d[u][j]);
}
}
}
void copy(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
d[i][j] = g[i][j];
}
}
}
void find(){
int sum = 0;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
sum += d[i][j];
}
}
res = min(res, sum);
}
signed main(){
IOS;
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i != j) g[i][j] = inf;
}
}
for(int i = 1; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
floyd();
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
copy();
d[i][j] = d[j][i] = 0;
query(i);
query(j);
find();
}
}
cout << res;
return 0;
}
C - Gardening Friends
难度: ⭐⭐⭐⭐
D - 菜肴制作
难度: ⭐⭐⭐
题目大意
给定一个n个顶点m条边的有向图, 对于边(a, b)要求在输出b之前必须要先输出a, 也就是只能输出当前入度为0的点; 但是对于输出的顺序有以下要求: 必须要尽早输出1, 并且在此之后又要尽早输出2, 然后是3, 依次类推; 也就是说, 1要尽可能地在2之前输出, 同理2也要在3之前输出;
解题思路
这里再明确一下题意, 比如有边(5, 1)和(4, 2); 按照题目要求, 我们的输出顺序是5 1 4 2, 虽然5在4之前输出看似有违题意, 但是注意题目的我加粗的地方, 他的初始要求只是1要尽可能在2之前输出, 在满足这一条之后才会有后面的要求, 也就是说在尚未满足1在2之前输出时, 4和5之间没有约束; 本题很难用普通的拓扑排序来解决该问题, 比如我们输出1后, 当前入度为0的有3, 4, 5; 并且节点2在5的后面, 那么我们需要去遍历图去找2, 复杂度肯定很高; 既然正向走不通, 那么可以考虑反向;
我们把该图看作是若干条相互有连接的链, 入度为0的是链首, 出度为0的链尾; 我们从链尾开始找, 越早选中的自然越晚输出; 对于若干个链尾, 我们优先挑选其中最大的那么一定是有益的, 这不像正向走时不一定挑最小的; 所以我们可以建立反图, 用大根堆进行拓扑排序, 然后将排序反向输出即是答案;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = 2e18;
typedef pair<int, int> PII;
int n, m, res;
int d[N];
vector<int> v[N];
signed main(){
int T;
cin >> T;
while(T--){
vector<int> res;
int idx = 0;
priority_queue<int> q;
cin >> n >> m;
for(int i = 1; i <= n; i++){
v[i].clear();
d[i] = 0;
}
for(int i = 1; i <= m; i++){
int a, b;
cin >> a >> b;
d[a]++;
v[b].push_back(a);
}
for(int i = 1; i <= n; i++){
if(!d[i]) q.push(i);
}
while(q.size()){
int t = q.top();
q.pop();
idx++;
res.push_back(t);
for(int x : v[t]){
d[x]--;
if(!d[x]) q.push(x);
}
}
if(idx == n){
for(int i = n - 1; i >= 0; i--) cout << res[i] << ' ';
cout << endl;
}
else cout << "Impossible!" << endl;
}
return 0;
}