4615. 相遇问题

原题链接

题目大意：

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

思想：

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

代码：

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

typedef long long LL;

void sovle(){

    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(_ --) sovle();

    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;
    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] << ' ';

    return ;

}

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\oplus 0 = 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 << (1 << cnt) << endl;

}

int main(){

    int _ = 1; cin >> _;

    while(_ --) solve();

    return 0;

}