本文最后更新于 328 天前，其中的信息可能已经有所发展或是发生改变。
4615. 相遇问题
原题链接
题目大意：
- 求一维数轴上 x 和 y 分别以速度 a,b 相向而行时，相遇所需时间是否为整数。
思想：
- 签到题。
- 输出判断 a b 是否可以整除 y - x 即可。
代码：
代码语言：javascript复制#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 次后，下一次的打击区间必定命中船。
代码：
代码语言：javascript复制#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,1oplus0=1,1-1=0,1 oplus1 = 0 故此时 a 与 x 无论是做减法还是异或运算，结果都相同。
- 当 a 二进制上的某一位是 0 时： 0 - 0 = 0,0oplus 0 = 0 故此时只有 x 的二进制位也是 0 才可使得等式成立。
- 综上，设 a 的二进制位上共有 m 个位的值为 1 ，则 x 的可选方案数为 2^m 种。
代码：
代码语言：javascript复制#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;
}
