2024ICPC网络赛第二场

VP链接
Codeforces：Dashboard - The 2024 ICPC Asia EC Regionals Online Contest (II) - Codeforces
QOJ：The 2024 ICPC Asia East Continent Online Contest (II) - Dashboard - Contest - QOJ.ac
A. Gambling on Choosing Regionals

注意到对于每个队伍来说最坏情况是与所有最强的队一个赛站，那么该队伍的排名会最低，以是为了让自己队伍的排名尽大概地高，最优选择就是去容纳量最小的赛站。
对 c 进行读入的时候只需要记录最小的 c 的值 

，同时利用 unordered_map 记录每一个队伍在学校内的排名，将每个学校前

 支队伍放进一个数组 b 里，再将数组 b 从大到小排序。
输出答案的时候，从头至尾依次遍历每一支队伍

• 如果队伍在学校的名次小于即是 
  
  ，该队伍的最优排名就是在数组 b 里的下标
  
• 如果队伍在学校的名次大于 
  
  ，相称于要把同学校的一支队伍移出这个赛站，再将这支队伍放进这个赛站，那么只需要利用二分找出 b 数组中第一个小于该队伍本领的队伍的位置 pos（题目保证每个队伍本领不同，不存在即是的情况），该队伍终极的排名就是 pos - 1（要将其学校前面即本领较强的队伍移出，以是排名要 -1）。
  

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N = 1e5 + 10;
5. int n, k, c, minc = INT_MAX, idx = 0, b[N];
6. struct node {
7.         int w, id, rnk = 0;
8.         bool operator< (const node &x) const {
9.                 return x.w > w;
10.         }
11. } a[N];
12. unordered_map<string, priority_queue<node>> mp;
14. inline int read() {
15.         int x = 0, f = 1; char c = getchar();
16.         while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
17.         while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
18.         return x * f;
19. }
21. int main() {
22.         n = read(), k = read();
23.         for (int i = 1; i <= k; i++) c = read(), minc = min(minc, c);
24.         for (int i = 1; i <= n; i++) {
25.                 a[i].w = read(), a[i].id = i;
26.                 string s; char c = getchar();
27.                 while (c < 'A' || c > 'Z') c = getchar();
28.                 while (c >= 'A' && c <= 'Z') s += c, c = getchar();
29.         // 时间限制只有 1s，用 cin 怕 TLE
30.                 mp[s].push(a[i]);
31.         }
32.         for (auto& [x, q] : mp) {
33.                 int num = 0;
34.                 while (!q.empty()) {
35.                         node cur = q.top(); q.pop();
36.                         a[cur.id].rnk = ++num; // 记录排名
37.                         if (num <= minc) b[++idx] = a[cur.id].w;
38.                 }
39.         }
40.         sort(b + 1, b + idx + 1, greater<int>()); // 从大到小排序
41.         for (int i = 1; i <= n; i++) {
42.                 int l = 1, r = idx + 1;
43.                 while (l < r) {
44.                         int mid = l + r >> 1;
45.                         if (b[mid] > a[i].w) l = mid + 1;
46.                         else r = mid;
47.                 }
48.                 if (a[i].rnk <= minc) printf("%d\n", l);
49.                 else printf("%d\n", l - 1);
50.         }
51.         return 0;
52. }

复制代码

F. Tourist

签到题，按照题意模拟即可。

1. #include <bits/stdc++.h>
2. using namespace std;
4. #define int long long
6. int n, c, tot = 1500, ans = -1;
8. inline int read() {
9.         int x = 0, f = 1; char c = getchar();
10.         while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
11.         while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
12.         return x * f;
13. }
15. signed main() {
16.         n = read();
17.         for (int i = 1; i <= n; i++) {
18.                 c = read(), tot += c;
19.                 if (ans == -1 && tot >= 4000) ans = i;
20.         }
21.         printf("%d\n", ans);
22.         return 0;
23. }

复制代码

G. Game

可以注意到平局其实是没有用的，以是 Alice 得胜的概率是 

，Bob 得胜的概率是 

。

---

证实：
假设

 为 Alice、Bob 在分别有 x、y 个 chips 且每一局的得胜概率分别为 a、b 的条件下，Alice 终极得胜的概率；

 为 Alice 在当前条件下先赢一局，Alice 终极得胜的概率;

 为 Bob 在当前条件下先赢一局且 Alice 终极得胜的概率。
那么有，

。
移项后有，

。
终极效果就是，

。
从这个式子可以得出，每一种情况下，Alice 终极得胜的概率不受平局的影响。

---

双方的游戏过程现实上是一个辗转相减的过程，可以利用辗转相除来加快。

• 当
  
  时，由于 Alice 得胜的情况较多，为方便统计，可以将问题转换成 1 - （Bob 得胜的概率）
  
• 当 
  
   时，可以让 Alice 先连赢 
  
   次转换成第一种情况。
  

1. #include <bits/stdc++.h>
2. using namespace std;
4. #define int long long
6. const int mod = 998244353;
8. inline int read() {
9.         int x = 0, f = 1; char c = getchar();
10.         while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
11.         while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
12.         return x * f;
13. }
15. int qpow(int x, int k) {
16.         int res = 1LL;
17.         while (k) {
18.                 if (k & 1) res = res * x % mod;
19.                 x = x * x % mod;
20.                 k >>= 1;
21.         }
22.         return res % mod;
23. }
25. int f(int x, int y, int a, int b) {
26.         if (x == 0) return 0;
27.         return qpow(a, y / x) * ((1 - f(y % x, x, b, a) + mod) % mod) % mod;
28. } // 辗转相除求答案
30. signed main() {
31.         int t = read();
32.         while (t--) {
33.                 int x = read(), y = read(), a0 = read(), a1 = read(), b = read();
34.                 int inv = qpow(a0 + a1, mod - 2);
35.                 int A = inv * a0 % mod, B = inv * a1 % mod;
36.         // 利用费马小定理求 Alice、Bob 获胜概率的乘法逆元
37.                 printf("%lld\n", f(x, y, A, B));
38.         }
39.         return 0;
40. }

复制代码

I. Strange Binary

所有数字都能进行二进制拆分，由十进制数转换为二进制数，但是大概会由于存在一连的 0 因而不符合题目的条件。
注意到 

，因此对于每一个二进制数，相邻两位如果是 0 1 的话，那么可以将其转换成 1 -1，如许就不会存在一连的 0 了。
但如果该二进制数末端有两个及以上的一连的 0 的时候，即 n 为 4 的倍数 时，那么将无法进行转换使得其满足题目条件。

1. #include <bits/stdc++.h>
2. using namespace std;
4. int n, a[32];
6. inline int read() {
7.         int x = 0, f = 1; char c = getchar();
8.         while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
9.         while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
10.         return x * f;
11. }
13. signed main() {
14.         int t = read();
15.         while (t--) {
16.                 n = read();
17.                 if (n % 4 == 0) {
18.                         puts("NO");
19.                         continue;
20.                 }
21.                 for (int i = 0; i < 32; i++) a[i] = 0; // 初始化
22.                 int idx = -1;
23.                 while (n) {
24.                         a[++idx] = n & 1;
25.                         n >>= 1;
26.                 } // 二进制拆分
27.                 for (int i = 0; i < 32; i++) {
28.                         while (i + 1 < 32 && a[i] != 0 && a[i + 1] == 0) {
29.                                 a[i] = -1, a[i + 1] = 1;
30.                                 i++;
31.                         }
32.                 } // 去 0 操作
33.                 puts("YES");
34.                 for (int i = 0; i < 32; i++) {
35.                         printf("%d ", a[i]);
36.                         if ((i + 1) % 8 == 0) puts("");
37.                 } // 输出答案
38.         }
39.         return 0;
40. }

复制代码

J. Stacking of Goods

贪心，考虑所有物品以什么顺序叠放是最优的。
假设有两个相邻的物品 1 和 2（1 在上，2 在下），其对应的重量、体积、压缩系数分别表示为，

 、

 、

 和 

 、

 、

，这两个物品上面的物品重量的和记为 W。两个物品要交换的条件就是，交换后所有物体的终极体积更小。所有物体的终极体积可以表示为，所有物体的总体积 - 每个物体的压缩系数 * 该物体上面所有物体的重量和。由于所有物体的总体积永远稳定，以是要让 每个物体的压缩系数 * 该物体上面所有物体的重量和 尽大概大。
即只需要满足 

，那么就将物体 1 和 2 交换位置（无论这两个物体是否交换位置，对其他物体的压缩体积不会造成任何影响）。化简之后，这个式子就变成了 

。
要特别注意，有大概会出现一连多个 

 的情况，这种情况下要让重量大的物品放在上面，如许重量大的物品贡献就最多，压缩的体积就更大。

1. #include <bits/stdc++.h>
2. using namespace std;
4. #define int long long
6. const int N = 1e5 + 10;
7. int n;
8. struct node { int w, v, c; } a[N];
10. inline int read() {
11.         int x = 0, f = 1; char c = getchar();
12.         while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
13.         while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
14.         return x * f;
15. }
17. bool cmp(node x, node y) {
18.         if (x.c * y.w == x.w * y.c) return x.w > y.w;
19.         return x.c * y.w < x.w * y.c;
20. }
22. signed main() {
23.         n = read();
24.         for (int i = 1; i <= n; i++) a[i].w = read(), a[i].v = read(), a[i].c = read();
25.         sort(a + 1, a + n + 1, cmp); // 排序
26.         int W = 0, V = 0;
27.         for (int i = 1; i <= n; i++) {
28.                 V += a[i].v - a[i].c * W;
29.                 W += a[i].w;
30.         } // 记录答案
31.         printf("%lld\n", V);
32.         return 0;
33. }

复制代码

L. 502 Bad Gateway

假设最优的操作是一直进行第二个操作直到数字小于即是 c 以后再进行第一个操作。对于第二个操作，选到小于即是 c 的数的概率是 

，那么盼望的操作时间就是 

。对于第一个操作，由于取到每个数的概率是相等的，以是盼望的操作此时是 

。由于是从第 0 秒开始操作，以是最后的效果是 

，当 

 或 

 的时候这个式子取得最小值。

1. #include <bits/stdc++.h>
2. using namespace std;
4. #define int long long
6. int n, T;
8. int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
10. signed main() {
11.     ios::sync_with_stdio(false); cin.tie(0);
12.     cin >> n;
13.     while (n--) {
14.         cin >> T;
15.         int num1 = floor(sqrt(1.0 * 2 * T)), num2 = ceil(sqrt(1.0 * 2 * T));
16.         int x1 = 2 * T + num1 * (num1 - 1), y1 = 2 * num1;
17.         int x2 = 2 * T + num2 * (num2 - 1), y2 = 2 * num2;
18.         int GCD;
19.         if (x1 * y2 < x2 * y1) {
20.             GCD = gcd(x1, y1);
21.             x1 /= GCD, y1 /= GCD;
22.             printf("%lld %lld\n", x1, y1);
23.         } else {
24.             GCD = gcd(x2, y2);
25.             x2 /= GCD, y2 /= GCD;
26.             printf("%lld %lld\n", x2, y2);
27.         }
28.     }
29.     return 0;
30. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。