比赛链接:Here
AB水题,
C - Many Balls
题意:
-
现在有一个数初始为 \(0(x)\) 以及两种操作
- 操作 \(A:\) \(x + 1\)
- 操作 \(B: 2\times 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\) ,就一定是\(\times2+1\) 得到的,是 \(0\) 就是 \(\times 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\n" : "No\n");
}