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 的值 https://latex.csdn.net/eq?minc_i，同时利用 unordered_map 记录每一个队伍在学校内的排名，将每个学校前 https://latex.csdn.net/eq?minc_i 支队伍放进一个数组 b 里，再将数组 b 从大到小排序。
输出答案的时候，从头至尾依次遍历每一支队伍
[*]如果队伍在学校的名次小于即是 https://latex.csdn.net/eq?minc_i，该队伍的最优排名就是在数组 b 里的下标
[*]如果队伍在学校的名次大于 https://latex.csdn.net/eq?minc_i，相称于要把同学校的一支队伍移出这个赛站，再将这支队伍放进这个赛站，那么只需要利用二分找出 b 数组中第一个小于该队伍本领的队伍的位置 pos（题目保证每个队伍本领不同，不存在即是的情况），该队伍终极的排名就是 pos - 1（要将其学校前面即本领较强的队伍移出，以是排名要 -1）。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, c, minc = INT_MAX, idx = 0, b;
struct node {
int w, id, rnk = 0;
bool operator< (const node &x) const {
return x.w > w;
}
} a;
unordered_map<string, priority_queue<node>> mp;
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() {
n = read(), k = read();
for (int i = 1; i <= k; i++) c = read(), minc = min(minc, c);
for (int i = 1; i <= n; i++) {
a.w = read(), a.id = i;
string s; char c = getchar();
while (c < 'A' || c > 'Z') c = getchar();
while (c >= 'A' && c <= 'Z') s += c, c = getchar();
// 时间限制只有 1s，用 cin 怕 TLE
mp.push(a);
}
for (auto& : mp) {
int num = 0;
while (!q.empty()) {
node cur = q.top(); q.pop();
a.rnk = ++num; // 记录排名
if (num <= minc) b[++idx] = a.w;
}
}
sort(b + 1, b + idx + 1, greater<int>()); // 从大到小排序
for (int i = 1; i <= n; i++) {
int l = 1, r = idx + 1;
while (l < r) {
int mid = l + r >> 1;
if (b > a.w) l = mid + 1;
else r = mid;
}
if (a.rnk <= minc) printf("%d\n", l);
else printf("%d\n", l - 1);
}
return 0;
} F. Tourist
签到题，按照题意模拟即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, c, tot = 1500, ans = -1;
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;
}
signed main() {
n = read();
for (int i = 1; i <= n; i++) {
c = read(), tot += c;
if (ans == -1 && tot >= 4000) ans = i;
}
printf("%d\n", ans);
return 0;
} G. Game
可以注意到平局其实是没有用的，以是 Alice 得胜的概率是 https://latex.csdn.net/eq?p_0%20%3D%20%5Cfrac%7Ba_0%7D%7Ba_0%20+%20a_1%7D，Bob 得胜的概率是 https://latex.csdn.net/eq?p_1%20%3D%20%5Cfrac%7Ba_1%7D%7Ba_0%20+%20a_1%7D。
证实：
假设 https://latex.csdn.net/eq?P%28x%2Cy%2Ca%2Cb%29 为 Alice、Bob 在分别有 x、y 个 chips 且每一局的得胜概率分别为 a、b 的条件下，Alice 终极得胜的概率；https://latex.csdn.net/eq?P_A%28x%2Cy%2Ca%2Cb%29 为 Alice 在当前条件下先赢一局，Alice 终极得胜的概率; https://latex.csdn.net/eq?P_B%28x%2Cy%2Ca%2Cb%29 为 Bob 在当前条件下先赢一局且 Alice 终极得胜的概率。
那么有，https://latex.csdn.net/eq?P%28x%2Cy%2Ca%2Cb%29%20%3D%20a%20%5Ccdot%20P_A%28x%2Cy%2Ca%2Cb%29%20+%20b%20%5Ccdot%20P_B%28x%2Cy%2Ca%2Cb%29%20+%20%281%20-%20a%20-%20b%29%20%5Ccdot%20P%28x%2Cy%2Ca%2Cb%29。
移项后有，https://latex.csdn.net/eq?%28a%20+%20b%29%20%5Ccdot%20P%28x%2Cy%2Ca%2Cb%29%20%3D%20a%20%5Ccdot%20P_A%28x%2Cy%2Ca%2Cb%29%20+%20b%20%5Ccdot%20P_B%28x%2Cy%2Ca%2Cb%29。
终极效果就是，https://latex.csdn.net/eq?P%28x%2Cy%2Ca%2Cb%29%20%3D%20%5Cfrac%7Ba%7D%7Ba+b%7D%20%5Ccdot%20P_A%28x%2Cy%2Ca%2Cb%29%20+%20%5Cfrac%7Bb%7D%7Ba+b%7D%20%5Ccdot%20P_B%28x%2Cy%2Ca%2Cb%29。
从这个式子可以得出，每一种情况下，Alice 终极得胜的概率不受平局的影响。
双方的游戏过程现实上是一个辗转相减的过程，可以利用辗转相除来加快。
[*]当 https://latex.csdn.net/eq?x%20%5Cge%20y 时，由于 Alice 得胜的情况较多，为方便统计，可以将问题转换成 1 - （Bob 得胜的概率）
[*]当 https://latex.csdn.net/eq?x%20%3C%20y 时，可以让 Alice 先连赢 https://latex.csdn.net/eq?%5Cfrac%7By%7D%7Bx%7D 次转换成第一种情况。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
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 qpow(int x, int k) {
int res = 1LL;
while (k) {
if (k & 1) res = res * x % mod;
x = x * x % mod;
k >>= 1;
}
return res % mod;
}
int f(int x, int y, int a, int b) {
if (x == 0) return 0;
return qpow(a, y / x) * ((1 - f(y % x, x, b, a) + mod) % mod) % mod;
} // 辗转相除求答案
signed main() {
int t = read();
while (t--) {
int x = read(), y = read(), a0 = read(), a1 = read(), b = read();
int inv = qpow(a0 + a1, mod - 2);
int A = inv * a0 % mod, B = inv * a1 % mod;
// 利用费马小定理求 Alice、Bob 获胜概率的乘法逆元
printf("%lld\n", f(x, y, A, B));
}
return 0;
} I. Strange Binary
所有数字都能进行二进制拆分，由十进制数转换为二进制数，但是大概会由于存在一连的 0 因而不符合题目的条件。
注意到 https://latex.csdn.net/eq?2%5E%7Bi%20-%201%7D%20%3D%202%5Ei%20-%202%5E%7Bi%20-%201%7D，因此对于每一个二进制数，相邻两位如果是 0 1 的话，那么可以将其转换成 1 -1，如许就不会存在一连的 0 了。
但如果该二进制数末端有两个及以上的一连的 0 的时候，即 n 为 4 的倍数 时，那么将无法进行转换使得其满足题目条件。
#include <bits/stdc++.h>
using namespace std;
int n, a;
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;
}
signed main() {
int t = read();
while (t--) {
n = read();
if (n % 4 == 0) {
puts("NO");
continue;
}
for (int i = 0; i < 32; i++) a = 0; // 初始化
int idx = -1;
while (n) {
a[++idx] = n & 1;
n >>= 1;
} // 二进制拆分
for (int i = 0; i < 32; i++) {
while (i + 1 < 32 && a != 0 && a == 0) {
a = -1, a = 1;
i++;
}
} // 去 0 操作
puts("YES");
for (int i = 0; i < 32; i++) {
printf("%d ", a);
if ((i + 1) % 8 == 0) puts("");
} // 输出答案
}
return 0;
} J. Stacking of Goods
贪心，考虑所有物品以什么顺序叠放是最优的。
假设有两个相邻的物品 1 和 2（1 在上，2 在下），其对应的重量、体积、压缩系数分别表示为，https://latex.csdn.net/eq?w_1 、https://latex.csdn.net/eq?v_1 、https://latex.csdn.net/eq?c_1 和 https://latex.csdn.net/eq?w_2 、https://latex.csdn.net/eq?v_2 、https://latex.csdn.net/eq?c_2，这两个物品上面的物品重量的和记为 W。两个物品要交换的条件就是，交换后所有物体的终极体积更小。所有物体的终极体积可以表示为，所有物体的总体积 - 每个物体的压缩系数 * 该物体上面所有物体的重量和。由于所有物体的总体积永远稳定，以是要让 每个物体的压缩系数 * 该物体上面所有物体的重量和 尽大概大。
即只需要满足 https://latex.csdn.net/eq?c_1%20%5Ctimes%20W%20+%20c_2%20%5Ctimes%20%28W%20+%20w_1%29%20%3C%20c_2%20%5Ctimes%20W%20+%20c_1%20%5Ctimes%20%28W%20+%20w_2%29，那么就将物体 1 和 2 交换位置（无论这两个物体是否交换位置，对其他物体的压缩体积不会造成任何影响）。化简之后，这个式子就变成了 https://latex.csdn.net/eq?c_2%20%5Ctimes%20w_1%20%3C%20c_1%20%5Ctimes%20w_2。
要特别注意，有大概会出现一连多个 https://latex.csdn.net/eq?c_2%20%5Ctimes%20w_1%20%3D%20c_1%20%5Ctimes%20w_2 的情况，这种情况下要让重量大的物品放在上面，如许重量大的物品贡献就最多，压缩的体积就更大。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n;
struct node { int w, v, c; } a;
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 cmp(node x, node y) {
if (x.c * y.w == x.w * y.c) return x.w > y.w;
return x.c * y.w < x.w * y.c;
}
signed main() {
n = read();
for (int i = 1; i <= n; i++) a.w = read(), a.v = read(), a.c = read();
sort(a + 1, a + n + 1, cmp); // 排序
int W = 0, V = 0;
for (int i = 1; i <= n; i++) {
V += a.v - a.c * W;
W += a.w;
} // 记录答案
printf("%lld\n", V);
return 0;
} L. 502 Bad Gateway
假设最优的操作是一直进行第二个操作直到数字小于即是 c 以后再进行第一个操作。对于第二个操作，选到小于即是 c 的数的概率是 https://latex.csdn.net/eq?%5Cfrac%7Bc%7D%7BT%7D，那么盼望的操作时间就是 https://latex.csdn.net/eq?%5Cfrac%7BT%7D%7Bc%7D。对于第一个操作，由于取到每个数的概率是相等的，以是盼望的操作此时是 https://latex.csdn.net/eq?%5Cfrac%7B1%7D%7Bc%7D%5Csum_%7Bi%20%3D%201%7D%5E%7Bc%7Di%20%3D%20%5Cfrac%7B1%7D%7Bc%7D%20%5Ctimes%20%5Cfrac%7Bc%28c%20+%201%29%7D%7B2%7D%20%3D%20%5Cfrac%7Bc%20+%201%7D%7B2%7D。由于是从第 0 秒开始操作，以是最后的效果是 https://latex.csdn.net/eq?%5Cfrac%7BT%7D%7Bc%7D%20+%20%5Cfrac%7Bc%20+%201%7D%7B2%7D%20-%201%20%3D%20%5Cfrac%7B2T%20+%20c%28c%20-%201%29%7D%7B2c%7D，当 https://latex.csdn.net/eq?c%20%3D%20%5C%20%5Cleft%20%5Clfloor%202T%20%5Cright%20%5Crfloor 或 https://latex.csdn.net/eq?c%20%3D%20%5C%20%5Cleft%20%5Clceil%202T%20%5Cright%20%5Crceil 的时候这个式子取得最小值。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, T;
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
while (n--) {
cin >> T;
int num1 = floor(sqrt(1.0 * 2 * T)), num2 = ceil(sqrt(1.0 * 2 * T));
int x1 = 2 * T + num1 * (num1 - 1), y1 = 2 * num1;
int x2 = 2 * T + num2 * (num2 - 1), y2 = 2 * num2;
int GCD;
if (x1 * y2 < x2 * y1) {
GCD = gcd(x1, y1);
x1 /= GCD, y1 /= GCD;
printf("%lld %lld\n", x1, y1);
} else {
GCD = gcd(x2, y2);
x2 /= GCD, y2 /= GCD;
printf("%lld %lld\n", x2, y2);
}
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]