2024ICPC网络赛第一场
VP链接：https://qoj.ac/contest/1794A. World Cup
最终答案与中国队本领值的排名有关，具体每个情况手推一下，用 if else 即可通过。
https://i-blog.csdnimg.cn/direct/77e1577b396942e2bac69bd6a4b24012.png
[*]如果输出 1，中国队是冠军，那么本领值一定第 1。
[*]如果输出 2，中国队是亚军，那么只能在决赛被打败排名一定在前 5，至少 27 支队伍比中国队弱（8强中另一个半区的4 支队伍都可以比中国队强）。
[*]如果输出 4，中国队是 4 强，那么就是在半决赛被打败，即在 1 / 4 和 1 / 8 决赛中得胜。中国队从 1 / 8 中得胜那么说明中国队至少强于 6 支队伍，中国队在 1 / 4 中的对手也强于 6 支队伍（具体原因看 4）。中国又比 1 / 4 决赛中的对手强，那么中国队至少强于 13 支队伍。
[*]如果输出 8，中国队是 8 强，那么是在 1 / 4 决赛被打败，即只需在 1 / 8 中得胜。如果中国队以小组第一出线，那么1 / 8 决赛对手地点组至少 3 队比中国队弱；如果中国队以小组第二出线，那么对手地点组全队伍伍都比中国队弱。以上两种情况都是至少有 6 支队伍比中国队弱。
[*]如果输出 16，中国队是 16 强，那么是在 1 / 8 决赛被打败。中国队只必要保证小组出线，以是至少 2 队比中国队弱。
[*]如果输出 32，中国队是 32 强，那么小组没出线，最多只有 1 支队伍比中国队弱。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t, a;
cin >> t;
while (t--) {
int num = 0;
for (int i = 0; i < 32; i++) {
cin >> a;
if (a <= a) num++;
}
if (num == 32) puts("1");
else if (num >= 28) puts("2");
else if (num >= 14) puts("4");
else if (num >= 7) puts("8");
else if (num >= 3) puts("16");
else puts("32");
}
return 0;
} C. Permutation Counting 4
问题可以等价于由全部边 https://latex.csdn.net/eq?%28l_%7Bi%7D%20-%201%2Cr_i%29 构成的图是不是一棵树。
假设有一个矩阵 https://latex.csdn.net/eq?A_%7Bi%2Cj%7D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%201%20%26%20j%20%5Cin%20%5Bl_i%2C%20r_i%5D%5C%5C%200%20%26%20j%20%5Cnot%5Cin%20%5Bl_i%2C%20r_i%5D%20%5Cend%7Bmatrix%7D%5Cright. ，问题可以等价于求 A 矩阵的行列式 det(A)：方案数为奇数，det(A) 不等于零；方案数为偶数，det(A) = 0。
对于这个矩阵可以在上边和左边分别补上一行一列，而且除了左上角是 1，剩余都是 0。然后从前去后依次执行前一列减后一列的利用，那么对于每一行 https://latex.csdn.net/eq?1%20%5Cle%20i%20%5Cle%20n，都有 https://latex.csdn.net/eq?A_%7Bi%2C%20l_i%20-%201%7D%20%3D%20-1，https://latex.csdn.net/eq?A_%7Bi%2C%20r_i%7D%20%3D%201，剩余位置都是 0。
如果 https://latex.csdn.net/eq?%28l_%7Bi%7D%20-%201%2Cr_i%29 这些边成环，成环的边对应的矩阵的行一定是线性相干的，即行列式为 0。否则根据行列式界说睁开，一定会有一项是非零的，行列式不为零。
可以借助并查集来简单判断图中是否有环。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int t, n, f;
int find(int x) { return f == x ? x : f = find(f); }
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i <= n; i++) f = i;
int ok = 1;
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
if (find(l - 1) == find(r)) ok = 0;
else f = find(r);
}
cout << ok << '\n';
}
return 0;
} F. Make Max
每一个数都能更新左右比它小的数，直到遇到一个大于等于它的数为止。从小到大一个个更新，更新次数一定最多，但在计算结果的时间只必要计算数目，不用考虑计算顺序。
利用单调栈求出每一个 https://latex.csdn.net/eq?a_i 左边第一个大于等于它的数的位置 https://latex.csdn.net/eq?lef_i 和右边第一个大于等于它的数的位置 https://latex.csdn.net/eq?rig_i。
计算结果的时间要注意，如果 https://latex.csdn.net/eq?a_i%20%3D%20a_%7Blef_i%7D，即 https://latex.csdn.net/eq?a_i 与左边第一个大于等于它的数相称的时间，只必要记右边小于它的数的个数，不然会跟前面的算重；别的情况都要加上左右小于它的数的个数。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a, lef, rig;
stack<int> s;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int main () {
int t = read();
while (t--) {
n = read();
for (int i = 1; i <= n; i++) a = read();
for (int i = 1; i <= n; i++) {
if (s.empty() || a < a) s.push(i);
else {
while (!s.empty() && a >= a) {
rig = i;
s.pop();
}
s.push(i);
}
}
while (!s.empty()) rig = n + 1, s.pop();
for (int i = n; i; i--) {
if (s.empty() || a < a) s.push(i);
else {
while (!s.empty() && a >= a) {
lef = i;
s.pop();
}
s.push(i);
}
}
while (!s.empty()) lef = 0, s.pop();
long long ans = 0LL;
for (int i = 1; i <= n; i++) {
if (!lef || a] != a) ans += rig - lef - 2;
else ans += rig - i - 1;
}
printf("%lld\n", ans);
}
return 0;
} G. The Median of the Median of the Median
总体思路：先二分最终的中位数，再判断现实中位数是否大于等于二分的中位数
利用 suma 数组记录 a 大于等于二分的中位数 x 的数目的前缀和。
https://latex.csdn.net/eq?b_%7Bi%2Cj%7D 记录 a 数组该区间内的中位数是否大于等于 x（如果 a 数组该区间内的中位数是大于等于 x的，那么至少有一半，即 https://latex.csdn.net/eq?%5Cfrac%7Bj%20-%20i%20+%201%7D%7B2%7D 个 a 要大于等于 x）。
https://latex.csdn.net/eq?c_%7Bi%2C%20j%7D 同样记录对应区间内的中位数是否大于等于 x 且原理与 b 相同。
最后判断 c 数组中是否有凌驾一半的数是大于等于二分的中位数的。
c 数组的前缀和处理（根据样例 1 举例说明）：1 3 1 7
b123411111231331147 c123411111231131147 以上是按照界说，b，c 数组对应区间内的中位数，两个数组存有数据的部分都类似于一个倒三角形。
可以发现原界说的 https://latex.csdn.net/eq?c_%7Bi%2C%20j%7D 是 https://latex.csdn.net/eq?i%20%5Cle%20x%20%5Cle%20j%2C%20i%20%5Cle%20y%20%5Cle%20j 这个倒三角区域内全部的数中位数，这个倒三角恰好是以 （i，j）为右上角的倒三角。以是代码中 c 数组的每一个 https://latex.csdn.net/eq?c_%7Bi%2C%20j%7D 记录的是：在原界说的 b 数组中，以（i，j）为右上角的倒三角区域内，大于等于二分的中位数x的数目。
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, suma, a, b, c;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
bool check(int x) {
for (int i = 1; i <= n; i++) suma = suma + (a >= x);
// 记录大于等于 x 的 a 的数量
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
c = b = (2 * (suma - suma) > (j - i + 1));
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) c += c;
// 统计 b 数组倒三角左边区域大于等于 x 的数量
for (int j = 1; j <= n; j++)
for (int i = j - 1; i >= 1; i--) c += c;
// 统计 b 数组倒三角下面区域大于等于 x 的数量
int sumc = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
sumc += (2 * c) > (j - i + 1) * (j - i + 2) / 2;
// (j - i + 1) * (j - i + 2) / 2 是对应区间内 b 数量的一半
return 2 * sumc > n * (n + 1) / 2; // n * (n + 1) / 2 就是 c 数量的一半
}
int main() {
n = read();
for (int i = 1; i <= n; i++) a = read();
int l = 0, r = 1e9 + 1;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) l = mid;
else r = mid;
} // 二分中位数
printf("%d\n", l);
return 0;
} M. Find The Easiest Problem
用 set 记录每一个题目通过的队伍的名字，最后比力队伍数目。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t, n;
string team, status;
char prob;
cin >> t;
while (t--) {
cin >> n;
set<string> st;
for (int i = 1; i <= n; i++) {
cin >> team >> prob >> status;
if (status == "accepted") st.insert(team);
}
int idx = 0;
for (int i = 1; i <= 'Z' - 'A'; i++) {
if (st.size() < st.size()) idx = i;
}
printf("%c\n", 'A' + idx);
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]