2024ICPC网络赛第一场

nuo534202 2024-10-05 10:37:00 阅读 64

VP链接:https://qoj.ac/contest/1794

A. World Cup

最终答案与中国队能力值的排名有关,具体每个情况手推一下,用 if else 即可通过。

如果输出 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 支队伍比中国队弱。

<code>#include <bits/stdc++.h>

using namespace std;

int main() {

ios::sync_with_stdio(false); cin.tie(0);

int t, a[40];

cin >> t;

while (t--) {

int num = 0;

for (int i = 0; i < 32; i++) {

cin >> a[i];

if (a[i] <= a[0]) 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

问题可以等价于由所有边 

eq?%28l_%7Bi%7D%20-%201%2Cr_i%29

 构成的图是不是一棵树。

假设有一个矩阵 

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。然后从前往后依次执行前一列减后一列的操作,那么对于每一行 

eq?1%20%5Cle%20i%20%5Cle%20n

,都有 

eq?A_%7Bi%2C%20l_i%20-%201%7D%20%3D%20-1

eq?A_%7Bi%2C%20r_i%7D%20%3D%201

,剩余位置都是 0。

如果 

eq?%28l_%7Bi%7D%20-%201%2Cr_i%29

 这些边成环,成环的边对应的矩阵的行一定是线性相关的,即行列式为 0。否则根据行列式定义展开,一定会有一项是非零的,行列式不为零。

可以借助并查集来简单判断图中是否有环。

<code>#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int t, n, f[N];

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

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] = 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(l - 1)] = find(r);

}

cout << ok << '\n';

}

return 0;

}

F. Make Max

每一个数都能更新左右比它小的数,直到遇到一个大于等于它的数为止。从小到大一个个更新,更新次数一定最多,但在计算结果的时候只需要计算数量,不用考虑计算顺序。

利用单调栈求出每一个 

eq?a_i

 左边第一个大于等于它的数的位置 

eq?lef_i

 和右边第一个大于等于它的数的位置 

eq?rig_i

计算结果的时候要注意,如果 

eq?a_i%20%3D%20a_%7Blef_i%7D

,即

eq?a_i

 与左边第一个大于等于它的数相等的时候,只需要记右边小于它的数的个数,不然会跟前面的算重;其余情况都要加上左右小于它的数的个数。

<code>#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, a[N], lef[N], rig[N];

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[i] = read();

for (int i = 1; i <= n; i++) {

if (s.empty() || a[i] < a[s.top()]) s.push(i);

else {

while (!s.empty() && a[i] >= a[s.top()]) {

rig[s.top()] = i;

s.pop();

}

s.push(i);

}

}

while (!s.empty()) rig[s.top()] = n + 1, s.pop();

for (int i = n; i; i--) {

if (s.empty() || a[i] < a[s.top()]) s.push(i);

else {

while (!s.empty() && a[i] >= a[s.top()]) {

lef[s.top()] = i;

s.pop();

}

s.push(i);

}

}

while (!s.empty()) lef[s.top()] = 0, s.pop();

long long ans = 0LL;

for (int i = 1; i <= n; i++) {

if (!lef[i] || a[lef[i]] != a[i]) ans += rig[i] - lef[i] - 2;

else ans += rig[i] - i - 1;

}

printf("%lld\n", ans);

}

return 0;

}

G. The Median of the Median of the Median

总体思路:先二分最终的中位数,再判断实际中位数是否大于等于二分的中位数

利用 suma 数组记录 a[i] 大于等于二分的中位数 x 的数量的前缀和。

eq?b_%7Bi%2Cj%7D

 记录 a 数组该区间内的中位数是否大于等于 x(如果 a 数组该区间内的中位数是大于等于 x的,那么至少有一半,即 

eq?%5Cfrac%7Bj%20-%20i%20&plus;%201%7D%7B2%7D

 个 a 要大于等于 x)。

eq?c_%7Bi%2C%20j%7D

 同样记录对应区间内的中位数是否大于等于 x 且原理与 b 相同。

最后判断 c 数组中是否有超过一半的数是大于等于二分的中位数的。

c 数组的前缀和处理(根据样例 1 举例说明):1 3 1 7

b 1 2 3 4
1 1 1 1 1
2 3 1 3
3 1 1
4 7
c 1 2 3 4
1 1 1 1 1
2 3 1 1
3 1 1
4 7

以上是按照定义,b,c 数组对应区间内的中位数,两个数组存有数据的部分都类似于一个倒三角形。

可以发现原定义的 

eq?c_%7Bi%2C%20j%7D

 是 

eq?i%20%5Cle%20x%20%5Cle%20j%2C%20i%20%5Cle%20y%20%5Cle%20j

 这个倒三角区域内所有的数中位数,这个倒三角正好是以 (i,j)为右上角的倒三角。所以代码中 c 数组的每一个 

eq?c_%7Bi%2C%20j%7D

 记录的是:在原定义的 b 数组中,以(i,j)为右上角的倒三角区域内,大于等于二分的中位数x的数量。

<code>#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

int n, suma[N], a[N], b[N][N], c[N][N];

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[i] = suma[i - 1] + (a[i] >= x);

// 记录大于等于 x 的 a[i] 的数量

for (int i = 1; i <= n; i++)

for (int j = i; j <= n; j++)

c[i][j] = b[i][j] = (2 * (suma[j] - suma[i - 1]) > (j - i + 1));

for (int i = 1; i <= n; i++)

for (int j = i + 1; j <= n; j++) c[i][j] += c[i][j - 1];

// 统计 b 数组倒三角左边区域大于等于 x 的数量

for (int j = 1; j <= n; j++)

for (int i = j - 1; i >= 1; i--) c[i][j] += c[i + 1][j];

// 统计 b 数组倒三角下面区域大于等于 x 的数量

int sumc = 0;

for (int i = 1; i <= n; i++)

for (int j = i; j <= n; j++)

sumc += (2 * c[i][j]) > (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[i] = 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[30];

for (int i = 1; i <= n; i++) {

cin >> team >> prob >> status;

if (status == "accepted") st[prob - 'A'].insert(team);

}

int idx = 0;

for (int i = 1; i <= 'Z' - 'A'; i++) {

if (st[idx].size() < st[i].size()) idx = i;

}

printf("%c\n", 'A' + idx);

}

return 0;

}



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。