简答题
偏难
#13213
二进制串的评分 对于一个给定的二进制串 s(即仅由字符 0 和 1 组成的串),其评分是这样计算的:将原串切分为若干段,使得每段包含的字符是一样的,且相邻两段包…
二进制串的评分
对于一个给定的二进制串 s(即仅由字符 0 和 1 组成的串),其评分是这样计算的:将原串切分为若干段,使得每段包含的字符是一样的,且相邻两段包含的字符是不一样的。该字符串的评分定义为各段长度的异或值(如果只有一段,评分就是这段的长度)。
异或(Exclusive OR,简称 XOR)是一种数学运算符,用于计算机中的位运算。当且仅当两个输入值不同时,异或运算输出为真(1),否则输出为假(0)。
例如,串 "10001100001" 可以切分为 5 段,即 "1"、"000"、"11"、"0000"、"1",其评分就是 1 ^ 3 ^ 2 ^ 4 ^ 1 = 5。
假设每一步我们可以交换 2 个相邻的字符,并且可以这样执行任意多步(当然也可以执行 0 步)。对每个可能的评分 x,你能得到多少个不同的串?将原串 s 通过交换操作变成评分为 x 的串,所用的最少步骤是多少次?
时间限制:1000
内存限制:65536
输入
输入在一行中给出非空的原始二进制串 s,其长度不超过 64。
输出
对每个可能的评分,在一行中输出 3 个空格分隔的整数,依次为:评分值、对 s 执行任意多步交换后能得到的不同串的个数、将 s 通过交换操作变成该评分的串所需要的最少步骤数。 按评分的升序输出。
样例输入
010
样例输出
1 1 0 3 2 1
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
// 计算二进制串的评分
int calcScore(const std::string& s) {
int score = 0, count = 1;
for (int i = 1; i <= s.size(); ++i) {
if (i == s.size() || s[i] != s[i - 1]) {
score ^= count;
count = 1;
} else {
++count;
}
}
return score;
}
// 广度优先搜索
void bfs(const std::string& start, std::unordered_map<int, std::pair<int, int>>& res) {
std::unordered_map<std::string, int> minSteps;
std::queue<std::string> q;
q.push(start);
minSteps[start] = 0;
while (!q.empty()) {
std::string s = q.front();
q.pop();
int score = calcScore(s);
int steps = minSteps[s];
if (res.find(score) == res.end()) {
res[score] = {1, steps};
} else {
res[score].first++;
res[score].second = std::min(res[score].second, steps);
}
for (int i = 0; i < s.size() - 1; ++i) {
std::string newStr = s;
std::swap(newStr[i], newStr[i + 1]);
if (minSteps.find(newStr) == minSteps.end()) {
minSteps[newStr] = steps + 1;
q.push(newStr);
}
}
}
}
int main() {
std::string s;
std::cin >> s;
std::unordered_map<int, std::pair<int, int>> res;
bfs(s, res);
std::vector<int> scores;
for (const auto& p : res) {
scores.push_back(p.first);
}
std::sort(scores.begin(), scores.end());
for (int score : scores) {
std::cout << score << " " << res[score].first << " " << res[score].second << std::endl;
}
return 0;
}</pre>
这道题暂未补解析。