A. Who Can Win
https://qoj.ac/contest/2513/problem/14301
思路
按题意模拟，统计第 \(239min\) 时成绩最好的队伍，记为冠军队伍，从 \(240min\) 开始到比赛结束的所有队伍都假设提交通过，实时计算成绩，一旦超过 \(239min\) 前的成绩最好队伍同样记作冠军。
细节：
1.输出时按照字典序输出。
-
\(AC\) 过的题目之后的提交要视为无效。
-
仅第一次 \(AC\) 前的错误提交要计算罚时。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;struct node1{int team;int id;int time;int res;bool operator<(const node1& b)const{return time < b.time;}
};
struct node2{int solv;int cnt[26];int time;int id;bool operator<(const node2& b)const{if(solv == b.solv){return solv > b.solv;}else return time > b.time;}
};void solve(){int n;cin >> n;vector<node1> e(n + 1);int idx = 0;map<string, int> te;map<int, string> et;for(int i = 1; i <= n; i++){string s;char c;int num;string r;cin >> s >> c >> e[i].time >> r;if(!te[s]){te[s] = ++idx;et[idx] = s;}e[i].team = te[s];e[i].id = c - 'A';if(r == "Accepted"){e[i].res = 1;}else if(r == "Unknown"){e[i].res = 2;}else{e[i].res = 3;}}vector<node2> tte(idx + 1);vector<node2> ed(idx + 1);vector<int> vis(idx + 1);sort(e.begin() + 1, e.end());for(int i = 1; i <= n; i++){if(e[i].time >= 240)break;int j = e[i].team;//j是队伍索引，i是题目索引if(e[i].res == 1){if(tte[j].cnt[e[i].id] < 0)continue;tte[j].solv++;tte[j].time+=e[i].time;tte[j].time+=tte[j].cnt[e[i].id] * 20;tte[j].cnt[e[i].id] = -1e9;//确保AC后的提交无效}else tte[j].cnt[e[i].id]++;}int anscnt = 1; int anstime = 1;for(int i = 1; i <= idx; i++){if(tte[i].solv == tte[anscnt].solv){if(tte[anscnt].time > tte[i].time)anscnt = i;}else if(tte[i].solv > tte[anscnt].solv)anscnt = i;}vis[anscnt] = 1;anstime = tte[anscnt].time;anscnt = tte[anscnt].solv;//上面作为索引，下面作为过题数 for(int i = 1; i <= idx; i++){if(tte[i].solv == anscnt){if(anstime >= tte[i].time)vis[i] = 1;}else if(tte[i].solv > anscnt)vis[i] = 1;}for(int i = 1; i <= n; i++){if(e[i].time < 240)continue;int j = e[i].team;if(tte[j].cnt[e[i].id] < 0)continue;tte[j].solv++;tte[j].time+=e[i].time;tte[j].time+=tte[j].cnt[e[i].id] * 20;tte[j].cnt[e[i].id] = -1e9;//确保AC后的提交无效if(tte[j].solv == anscnt){if(anstime >= tte[j].time)vis[j] = 1;}else if(tte[j].solv > anscnt)vis[j] = 1;}vector<string> res;for(int i = 1; i <= idx; i++){if(vis[i])res.push_back(et[i]);}sort(res.begin(), res.end());for(auto v : res){cout << v << " ";}cout << "\n";}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();return 0;
}
B. Creating Chaos
https://qoj.ac/contest/2513/problem/14302
思路
猜的，发现 \(1, 2, ....., k\) 正确。
代码就不贴了
C. Canvas Painting
https://qoj.ac/contest/2513/problem/14303
思路
每次有效操作会使得颜色总数减少，答案即为 \(n\;-\;cnt\)。想办法求有效操作数。
先排序，排完序后，我们从左到右处理，对于相邻的 \(id\) 和 \(id+1\) 我们将其涂成一种颜色，在区间左端小于 \(id\) 的所有区间中，找到最小的区间右端进行操作，记为一次有效操作。
这显然是 \(O(nlog\;n)\) 的复杂度，可行
代码
#include<bits/stdc++.h>using namespace std;
using ll = long long;struct node{int v;int w;bool operator<(const node& b)const{return w > b.w;}
};void solve() {int m, n;cin >> m >> n;vector<pair<int, int>> a(m + 1);for(int i = 1; i <= m; i++){cin >> a[i].first >> a[i].second;}sort(a.begin() + 1, a.end());int idx = 1;int id = a[1].first;int cnt = 0;priority_queue<node> q;while(id <= n){for(; a[idx].first <= id && idx <= m; idx++){q.push({idx, a[idx].second});}while(q.size()){auto [u, r] = q.top();q.pop();if(id + 1 <= r){cnt++;id++;break;} }if(q.empty()){if(idx == m + 1)break;id = a[idx].first;}}cout << n - cnt << "\n";}int main(){ios::sync_with_stdio(0);cin.tie(0);ll t;cin >> t;while(t--)solve();
}
D. Min-Max Tree
https://qoj.ac/contest/2513/problem/14304
题意
把一棵树拆边后分为若干个连通块，每个连通块的贡献为连通块中最大值减去最小值，拆边使得所有连通块的贡献求和最大，求这个值。
思路
贡献为最大值减最小值，易知，最大值贡献为 \(+\,a_i\), 最小值贡献为 \(-\,a_i\), 其他值贡献为 \(0\).
其次，连通块一定是链的形式，若有树的形式，可证明删除支链后贡献不减。
考虑 \(dp\), 设置状态 \(dp_{i, 0/1/2}\)。
其中 \(dp_{i, 0}\) 表示以 \(i\) 为根的子树中所有连通块的贡献和，并且所有连通块已完结。
\(dp_{i, 1}\)表示以 \(i\) 为链端的的连通块中已经找到了最大值，没有最小值。
\(dp_{i, 2}\)表示以 \(i\) 为链端的连通块找到了最小值，没有最大值。
考虑 \(dp\) 转移
dp[u][0] = max(dp[u][0], sum);//所有儿子都完结的情况
\\u为当前子树的根，sum为儿子子树所有完结的和
/*sum += dp[v][0]*/
int mx1 = -1e9;//记录找到最大值的所有子树中贡献最大的
int mx2 = -1e9;//记录找到最小值的所有子树中贡献最大的
for(auto v : e[u]){dp[u][0] = max(dp[u][0], sum - dp[v][0] + dp[v][1] - a[u]);//v儿子已经找到了最大值，现在认为在u处找到了最小值dp[u][0] = max(dp[u][0], sum - dp[v][0] + dp[v][2] + a[u]);//v儿子已经找到了最小值，现在认为在u处找到了最大值mx1 = max(mx1, dp[v][1] - dp[v][0]);//减去dp[v][0]在下面有体现mx2 = max(mx2, dp[v][2] - dp[v][0]);
}
dp[u][0] = max(dp[u][0], sum + mx1 + mx2)//一个找到最大值的儿子和一个找到最小值的儿子结合起来形成完整的连通块，a[u]此时贡献为0
//上面这里要减去1和2的dp[v][0]值，在之前已经减过了dp[u][1] = max(dp[u][1], sum + a[u]);//儿子完结，a[u]单独做有最大值的链头
dp[u][2] = max(dp[u][2], sum + a[u]);//儿子完结，a[u]单独做有最小值的链头
for(auto v : e[u]){dp[u][1] = max(dp[u][1], sum - dp[v][0] + dp[v][1]);//v儿子已经找到了最大值，现在不认为在u处找到了最小值，所以a[u]贡献为0dp[u][2] = max(dp[u][2], sum - dp[v][0] + dp[v][2]);//v儿子已经找到了最小值，现在不认为在u处找到了最大值，所以a[u]贡献为0
}
代码
#include<bits/stdc++.h>using namespace std;
using ll = long long;void solve() {ll n;cin >> n;vector<ll> a(n + 1);vector<vector<ll>> e(n + 1);for(ll i = 1; i <= n; i++){cin >> a[i];}for(ll i = 1; i < n; i++){ll x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}vector<vector<ll>> dp(n + 1, vector<ll>(3, -1e18));ll ans = 0;auto dfs = [&](auto&& dfs, ll u, ll fa) -> void {ll sum = 0;for(auto v : e[u]){if(v == fa)continue;dfs(dfs, v, u);sum += dp[v][0];}for(auto v : e[u]){if(v == fa)continue;dp[u][0] = max(dp[u][0], sum - dp[v][0] + dp[v][1] - a[u]);dp[u][0] = max(dp[u][0], sum - dp[v][0] + dp[v][2] + a[u]);dp[u][1] = max(dp[u][1], sum - dp[v][0] + dp[v][1]);dp[u][2] = max(dp[u][2], sum - dp[v][0] + dp[v][2]);}dp[u][0] = max(dp[u][0], sum);dp[u][1] = max(dp[u][1], sum + a[u]);dp[u][2] = max(dp[u][2], sum - a[u]);ll mx1 = -1e18;ll mx2 = -1e18;for(auto v : e[u]){if(v == fa)continue;mx1 = max(mx1, dp[v][1] - dp[v][0]);mx2 = max(mx2, dp[v][2] - dp[v][0]);}if(mx1 > -1e18 && mx2 > -1e18){dp[u][0] = max(dp[u][0], sum + mx1 + mx2);}};dfs(dfs, 1, 0);cout << dp[1][0] << "\n";}int main(){ios::sync_with_stdio(0);cin.tie(0);solve();
}
G. Sorting
https://qoj.ac/contest/2513/problem/14307
思路
对于位置 \(i\) 和位置 \(j\) 的两个值可以无限次交换，显然连通即可排列有序，但如果需要按照从左到右有序则需要向冒泡排序一样，需要 \(n-1\) 个相邻的交换。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n, m;cin >> n >> m;vector<int> vis(n);for(int i = 1; i <= m; i++){int a, b;cin >> a >> b;if(a > b)swap(a, b);if(b == a + 1){vis[a] = 1;}}for(int i = 1; i < n; i++){if(vis[i] == 0){cout << "No\n";return ;}}cout << "Yes\n";
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// int t;// cin >> t;// while(t--)solve();return 0;
}
I. Knapsack Problem
https://qoj.ac/contest/2513/problem/14309
思路
按题意模拟即可
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;struct edge{int v;int w;
};
struct node{int id;int num;int v;bool operator<(const node & b)const {return v < b.v;}
};void solve(){int n, m, v, t;cin >> n >> m >> v >> t;vector<vector<edge>> e(n + 1);for(int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;e[a].push_back({b, c});e[b].push_back({a, c});}vector<int> ans(n + 1, 1e9);vector<int> vv(n + 1, 0);auto bfs = [&](){priority_queue<node> q;q.push({t, 1, v});while(!q.empty()){auto [u, num, now] = q.top();q.pop();if(num == ans[u]){if(now <= vv[u]){continue;}}else if(num > ans[u])continue;ans[u] = num;vv[u] = now;for(auto [k, w] : e[u]){int temp = ans[u];if(w > vv[u]){temp ++;if(w <= v){q.push({k, temp, v - w});}}else {q.push({k, temp, vv[u] - w});}}}};bfs();for(int i = 1; i <= n; i++){cout << (ans[i] == 1e9 ? -1 : ans[i]) << " ";}
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// int t;// cin >> t;// while(t--)solve();return 0;
}
M. Teleporter
https://qoj.ac/contest/2513/problem/14313
思路
看题意像分层图板子题，但 \(O(nm\,log\;(nm))\) 显然是无法接受的，想到手动在每一层转移（层与层之间单独跑 \(dij\) ）
代码
#include<bits/stdc++.h>using namespace std;
using ll = long long;struct node{ll v;ll w;bool operator<(const node& b)const{return w > b.w;}
};void solve() {ll n, m;cin >> n >> m;vector<vector<node>> e(n + 1);vector<vector<ll>> g(n + 1);for(ll i = 1; i < n; i++){ll x, y, z;cin >> x >> y >> z;e[x].push_back({y, z});e[y].push_back({x, z});} vector<vector<ll>> d(n + 1, vector<ll>(n + 1, 1e18));for(ll i = 1; i <= m; i++){ll x, y;cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}for(ll i = 1; i <= n; i++){g[i].push_back(i);}int ok = 1;auto bfs = [&](){priority_queue<node> q;vector<int> vis(n + 1);q.push({1, 0});while(q.size()){auto [u, w] = q.top();q.pop();if(vis[u])continue;d[u][0] = w;vis[u] = 1;for(auto [v, k] : e[u]){if(!vis[v]){q.push({v, d[u][0] + k});}}}};bfs();auto bfs1 = [&](ll id){priority_queue<node> q;vector<int> vis(n + 1);for(int i = 1; i <= n; i++){for(auto v : g[i]){d[i][id] = min(d[i][id], d[v][id - 1]);if(d[i][id] == 0)break;}}for(int i = 1; i <= n; i++)q.push({i, d[i][id]});while(q.size()){auto [u, w] = q.top();q.pop();if(vis[u])continue;d[u][id] = w;vis[u] = 1;for(auto [v, k] : e[u]){if(d[v][id] > d[u][id] + k){q.push({v, d[u][id] + k});}}}for(ll u = 1; u <= n; u++){for(auto v : g[u]){d[v][id] = min(d[v][id], d[u][id - 1]);}}};for(ll i = 1; i <= n; i++){bfs1(i);}ll sum = 0;for(ll i = 0; i <= n; i++){sum = 0;for(ll j = 1; j <= n; j++){sum += d[j][i];}cout << sum << "\n";}
}int main(){ios::sync_with_stdio(0);cin.tie(0);// ll t;// cin >> t;// while(t--)solve();
}
)
)
)
)
