HackerRank - string-reduction【反推】【规律】

HackerRank - string-reduction【反推】

题意

给出一串只有字母 a, b, c 组成的字符串，然后没两个不同的字符碰到一起都可以变成另外一个字符，然后变到最后，求最短的字符串长度。

思路

①如果给出的字符串都是相同的字符，那么显然，答案就是这个字符串的长度

②如果不是那么答案可能是1 或者是 2

③我们可以反着推回去。就是假如刚开始的状态的1

我们可以先假定 x = 字符a的数量 y = 字符b的数量 z = 字符c的数量

如果某个字符串是由 1 推过去的

那么刚开始 x, y, z的数量就是 (1, 0, 0) || (0, 1, 0) || (0, 0, 1)

其奇偶状态就是奇，偶，偶，

如果一个字符变成连个字符

其奇偶状态就变为偶，奇，奇

如果继续变

其奇偶状态就变为奇，偶，偶

所以如果答案是1 那么奇偶状态就是两奇一偶或者一奇两偶

如果某个字符串是由 2 推过去的

刚开始的奇偶状态是偶，偶，偶

如果减少一个字符，加另外两个字符

其奇偶状态就变成奇，奇，奇

所以我们可以得出，如果一个字符串的奇偶状态是

全奇或者全偶

那么最后的答案就是2

如果是其他情况

最后的答案就是1

AC代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <cstdlib>

#include <ctype.h>

#include <numeric>

#include <sstream>

using namespace std;

typedef long long LL;

const double PI  = 3.14159265358979323846264338327;

const double E   = 2.718281828459;

const double eps = 1e-6;

const int MAXN   = 0x3f3f3f3f;

const int MINN   = 0xc0c0c0c0;

const int maxn   = 1e5 + 5;

const int MOD    = 1e9 + 7;

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        string s;

        cin >> s;

        int n[3] = {0};

        int len = s.size();

        for (int i = 0; i < len; i++)

        {

            n[s[i] - 'a'] ++;

        }

        if (n[0] == len || n[1] == len || n[2] == len)

        {

            cout << len << endl;

        }

        else if((n[0] % 2 == 1 && n[1] % 2 == 1 && n[2] % 2 == 1) || (n[0] % 2 == 0 && n[1] % 2 == 0 && n[2] % 2 == 0))

            cout << 2 << endl;

        else

            cout << 1 << endl;

    }

}

巴特西

HackerRank - string-reduction【反推】【规律】

最新文章

热门文章