本文最后更新于 857 天前,其中的信息可能已经有所发展或是发生改变。
原题链接
题目大意:
- 求一维数轴上 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; |
| |
| } |
原题链接
题目大意:
- 存在长度为 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; |
| |
| } |
原题链接
题目大意:
- 给定一个非负整数 a,请你计算方程 a−(a⊕x)−x=0 的非负整数解的数量。
思想:
- 数学思维题。
- 化简该方程为: a−x=a⊕x。
- 当 a 二进制上的某一位是 1 时:
- 1−0=1,1⊕0=1,1−1=0,1⊕1=0
- 故此时 a 与 x 无论是做减法还是异或运算,结果都相同。
- 当 a 二进制上的某一位是 0 时:
- 0−0=0,0⊕0=0
- 故此时只有 x 的二进制位也是 0 才可使得等式成立。
- 综上,设 a 的二进制位上共有 m 个位的值为 1 ,则 x 的可选方案数为 2m 种。
代码:
| #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; |
| |
| } |