题目均来自去年的省赛原题
参考资料
A题送分题，跳过
B 位运算lowbit函数
题目大意：
对一个数（二进制）进行操作，询问使其变成0的最短操作步骤。 操作方式：x+=lowbit(x) 或者 x−=lowbit(x)
解题思路：
经过观察
单独的 "1" 只需经过一次操作即可转为 "0"，即x−=lowbit(x)
连续的 "1" 只需经过两次次操作即可转为 "0"，比如
1111 -> x+=lowbit(x) -> 10000 -> x−=lowbit(x) -> 0
为了更好处理（避免进位到最前面一位时需要前补0），可以先进行翻转（reverse），并在末尾加上两个字符 "00"。
然后从左往右扫描字符串。如果扫描到一个字符为 '1'，就检查它右边的字符。
如果右边的字符是 '0'，说明这是一个独立的 "1"，计数加一；
如果右边的字符也是 '1'，说明这是一个连续的 "11"，就将这个连续段的第一个 '1' 改为 '0'，并将前面的 '1' 变成 '0'，直到遇到一个 '0' 为止，再将最后一个 '0' 变成 '1'。然后回退一格继续扫描。
参考代码c++
#include <iostream>
#include <algorithm>
using namespace std;
signed main() {
// 加快输入输出速度，常用方法
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string s;
cin >> s;
reverse(s.begin(), s.end());
s += "00";
int cnt = 0, n = s.size();
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
if (i == n - 1 || s[i + 1] == '0')
cnt++;
else {
while (i < n - 1 && s[i] == '1')
s[i++] = '0';
s[i] = '1';
i--;
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}
C 家庭作业
题目大意：
有很多份作业要写，每份作业字数（所需时间）不同。但是可以先写完一份，然后其他的抄这一份，当然不同作业抄是需要花不同时间的。
解题思路：
首先我们肯定至少要写最多的那一份的数量的字，其余的我们都可以用复制粘贴来解决。
但不是说我们先把最多的那一份作业写完，比如三个作业子数是100，200，300对应的复制时间是99，199，1。那么显然我们先写完200的字，再复制给作业1和3，最后补足作业三缺少的字更省时间。
既然我们要写的字数已经固定，那初步时间就可以知道了，然后只有第一份是不能粘贴的，所以我们第一份作业选的就是复制时间用时最多的那一个。
即总时间是：最大字数+除去一份最大复制时间后其它复制时间的总和。
参考代码c++
#include <iostream>
#include <vector>
using namespace std;
signed main() {
// 加快输入输出速度，常用方法
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, cnt = 0, ans = 0;
cin >> n;
vector<int>a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
cnt = max(cnt, a[i]);
}
for (int i = 0; i < n; i++) {
cin >> b[i];
cnt += b[i];
ans = max(ans, b[i]);
}
cout << cnt - ans;
return 0;
}
D 没有羡慕
题目大意：
有两个人，相同商品在他们眼中价值不同。需要对前i件商品中，自己的东西价值 和 对方的东西价值 进行比较。
解题思路：
题目很长，但算是签到题（网上的大佬说的）。
记录一下两边自己物品在自己眼里的最大值和在对面眼里的最大值，以及对面认为我的价值最大和最小的两个物品。
- 只要两边都认为自己的东西价值最大，就输出EF。
- 如果对面物品减去最小的货物后价值比我的小，输出EFX。
- 如果对面物品减去最大的货物后价值比我的小，输出EF！。
- 其它情况输出E。
使用pair处理会方便许多。
参考代码c++
#include <iostream>
using namespace std;
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
signed main() {
// 加快输入输出速度，常用方法
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//max表示对面认为我的价值最高的物品，min表示对面认为我的价值最低的物品
int n, a, b, c, maxx = 0, maxy = 0, minx = 1e9, miny = 1e9;
//first表示自己拥有的自己眼里物品总价值，second表示自己拥有的对面眼里物品总价值
PII x, y;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a >> b >> c;
if (c == 0) { // 物品属于第一个人
x.first += a;
x.second += b;
maxx = max(maxx, b);
minx = min(minx, b);
} else { // 物品属于第二个人
y.first += b;
y.second += a;
maxy = max(maxy, a);
miny = min(miny, a);
}
// 对应四种情况
if (x.first >= y.second && y.first >= x.second) {
cout << "EF" << endl;
} else if (x.first >= y.second - miny && y.first >= x.second - minx) {
cout << "EFX" << endl;
} else if (x.first >= y.second - maxy && y.first >= x.second - maxx) {
cout << "EF1" << endl;
} else
cout << "E" << endl;
}
return 0;
}
京公网安备 11010502036488号