比赛链接：Here
AB水题，
C - Many Balls
题意：
-
现在有一个数初始为 (0(x)) 以及两种操作
- 操作 (A:) (x + 1)
- 操作 (B: 2 imes x)
数据范围 (n le 1e18)
现在给你一个数 (n) ，问如何通过以上操作将 (0) 变成 (n) ，操作数不超过 (120)
思路：
(2^{119} ge 1e18) 保证一定有解
首先我们肯定是操作(A) 使得 (x=1) 不然执行操作 (B) 无意义
接下来尽可能使得 (x) 接近 (n) 也就是多执行操作(B)
接下来就是补 (A) 了
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll n;
cin >> n;
stack<char>st;
while (n) {
while (n % 2 == 0) {
n /= 2;
st.push('B');
}
while (n % 2 != 0) {
n -= 1;
st.push('A');
}
}
while (!st.empty()) {
cout << st.top();
st.pop();
}
}
思路二：
用二进制的眼光看数字。对一个二进制数字来说要增加一个 (0) 就要乘 (2) ，增加一个 (1) 就要乘 (2) 加 (1) 。从高位到低位看数字 (n) ，第一个出现 (1) 的位置就是一开始的加 (1) ，然后剩下的位置中，如果是 (1) ，就一定是( imes2+1) 得到的，是 (0) 就是 ( imes 2) 得到的。
【AC Code】
int a[120];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll n;
cin >> n;
int cnt = 0;
while (n) {
a[cnt ++] = n % 2;
n /= 2;
}
for (int i = cnt - 1; i >= 0; i -= 1) {
if (i == cnt - 1) {
cout << "A";
continue;
}
if (a[i] == 1)cout << "BA";
else cout << "B";
}
}
D - Pair of Balls
赛时懵逼了，一下子没想到用
map去处理
题意：
- 给 (2N) 个球，编号都在 (1) 到 (N) 的范围内，每个编号的球恰好有两个，放入 (M) 个容器中，每个容器大小为 (K_i) ，现在有一种操作：从某个容器顶部的球（前提是另外一个容器的顶部也是这个球的编号)，然后把这两个球都去掉，重复操作下来，问能否把全部栈清空。
思路：
数组 (mp_i) 代表编号为 (i)的球在哪个容器中，对每一个容器 (i) 顶部依次搜索，如果另一个容器 (j) 顶部跟当前容器顶部相同就去掉，然后再对容器 (j) 搜索，具体看代码。
const int N = 2e5 + 10;
queue<int>q[N];
int mp[N];
void dfs(int i) {
int u = mp[q[i].front()];
q[u].pop();
q[i].pop();
while (!q[u].empty() and mp[q[u].front()]) dfs(u);
if (!q[u].empty()) mp[q[u].front()] = u;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1, k; i <= m; ++i) {
cin >> k;
for (int j = 1, x; j <= k; ++j) {
cin >> x;
q[i].push(x);
}
}
for (int i = 1; i <= m; ++i) {
while (!q[i].empty() and mp[q[i].front()]) dfs(i);
if (!q[i].empty()) mp[q[i].front()] = i;
}
bool f = 0;
for (int i = 1; i <= m; ++i) {
if (!q[i].empty()) {f = 1; break;}
}
cout << (!f ? "Yes
" : "No
");
}
E - Amusement Park
题意：
(RioTian) 来到了一个游乐园，游乐园里有 (N) 个景点，并且第 (i) 个景点的乐趣最开始是 (a_i) 随着 (RioTian) 的游玩，他的满足感数值会增加当前游玩景点乐趣值，但每一次游玩该景点后此景点乐趣值 (-1) ，(RioTian) 最多可以以任何顺序乘坐景点K次。
请问 (RioTian) 能得到的最大可能的满意度是什么？
(eg:) 除了乘坐景点外，没有什么能影响 (RioTian) 的满意度。
思路：
感觉做过哎(雾）
为了使得满意度最大化，肯定是先游玩乐趣值大的那几个景点，并且判断是不是能重复游玩使得值最大化。
详细见代码
const int N = 2e5 + 10;
ll a[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + 1 + n, greater<ll>());
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ll t = i * (a[i] - a[i + 1]);
if (k >= t) k -= t, ans += (a[i] + a[i + 1] + 1) * t / 2;
else {
ll tt = k / i, j = k % i;
ans += (a[i] + a[i] - tt + 1) * tt / 2 * i + j * (a[i] - tt);
break;
}
}
cout << ans;
}