首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;string&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;unordered_map&gt; #include &lt;queue&gt; // 计算二进制串的评分 int calcScore(const std::string&amp; s) {     int score = 0, count = 1;     for (int i = 1; i &lt;= 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&amp; start, std::unordered_map&lt;int, std::pair&lt;int, int&gt;&gt;&amp; res) {     std::unordered_map&lt;std::string, int&gt; minSteps;     std::queue&lt;std::string&gt; 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 &lt; 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 &gt;&gt; s;     std::unordered_map&lt;int, std::pair&lt;int, int&gt;&gt; res;     bfs(s, res);     std::vector&lt;int&gt; scores;     for (const auto&amp; p : res) {         scores.push_back(p.first);     }     std::sort(scores.begin(), scores.end());     for (int score : scores) {         std::cout &lt;&lt; score &lt;&lt; " " &lt;&lt; res[score].first &lt;&lt; " " &lt;&lt; res[score].second &lt;&lt; std::endl;     }     return 0; }</pre>
这道题暂未补解析。