acwing-第69场周赛

4615. 相遇问题

原题链接

题目大意：

• 求一维数轴上 \(x\) 和 \(y\) 分别以速度 \(a,b\) 相向而行时，相遇所需时间是否为整数。

思路：

• 签到题。
  • 输出判断 \(a + b\) 是否可以整除 \(y - x\) 即可。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

void solve() {
    LL x, y, a, b;
    cin >> x >> y >> a >> b;
    if ((y - x) % (a + b) == 0)
        cout << (y - x) / (a + b) << endl;
    else
        cout << -1 << endl;
}

int main() {
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

---

4616. 击中战舰

原题链接

题目大意：

• 存在长度为 \(n\) 的格子，共 \(a\) 个船，每个船占据连续的 \(b\) 个格子。
  • 给定一个只包含 \(0,1\) 的字符串 \(S\)，包含 \(k\) 个 \(1\)，表示该格子受到打击，保证初始的打击不会击中船。
  • 求最少再打击几个格子可以保证下一次打击绝对命中船。
  • 输出任意方案即可。

思路：

• 思维题。
  • 由于船的位置不确定，那么对于每个包含连续的 \(b\) 个格子的区间一定可以放下一条船。
  • 则我们最终打击的对象在于这些区间中的任意一个格子，因此我们记录所有的这些连续的 \(b\) 个格子中任意一个格子的坐标。
  • 最后，由于无效打击的次数最少，假设所有可打击的区间数量为 \(x\)，则最少打击 \(x - a + 1\) 次后，下一次的打击区间必定命中船。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int num[N];
int idx;

void solve() {
    int n, a, b, k;
    cin >> n >> a >> b >> k;
    string s;
    cin >> s;
    int cnt = 0;
    idx = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') {
            cnt++;
            if (cnt == b) {
                num[idx++] = i + 1;
                cnt = 0;
            }
        } else {
            cnt = 0;
        }
    }
    cout << idx - a + 1 << endl;
    for (int i = 0; i < idx - a + 1; i++) {
        cout << num[i] << ' ';
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

---

4617. 解方程

原题链接

题目大意：

• 给定一个非负整数 \(a\)，请你计算方程 \(a-(a \oplus x)-x=0\) 的非负整数解的数量。

思路：

• 数学思维题。
  • 化简该方程为： \(a - x = a \oplus x\)。
  • 当 \(a\) 二进制上的某一位是 \(1\) 时：
    • \(1-0=1, 1\oplus0=1, 1-1=0, 1\oplus1=0\)
    • 故此时 \(a\) 与 \(x\) 无论是做减法还是异或运算，结果都相同。
  • 当 \(a\) 二进制上的某一位是 \(0\) 时：
    • \(0-0=0, 0\oplus0=0\)
    • 故此时只有 \(x\) 的二进制位也是 \(0\) 才可使得等式成立。
  • 综上，设 \(a\) 的二进制位上共有 \(m\) 个位的值为 \(1\)，则 \(x\) 的可选方案数为 \(2^m\) 种。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

void solve() {
    LL n;
    cin >> n;
    int cnt = 0;
    while (n) {
        cnt += n & 1;
        n >>= 1;
    }
    cout << (1LL << cnt) << endl;
}

int main() {
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}