神奇字符串

正文索引 [隐藏]

题目描述:

神奇字符串的定义为: 只含有1和2, 且将其按照连续的1和2拆开后,对应的每部分数字数量恰好和原字符串相同 例如: 1 22 11 2 1 22 1 22 11 2 11 22 …… 每部分对应的1和2个数为 1 2 2 1 1 2 1 2 2 1 2 2 …… 恰好等于原串 现给定N,求神奇串的前N位中有多少个1 .

输入描述:

第一行输入一个T,代表数据组数 接下来的T行,输入N 1 <= N <= 100000

输出描述:

对每一组输入,在一行中输出前N位中1的个数。

输入样例:

1
6

输出样例:

3

解题思路:

找规律,根据第三个数字2开始往后生成数字,此时生成两个1,然后根据第四个数字1,生成一个2,再根据第五个数字1,生成一个1,以此类推,生成的数字1或2可以通过异或3来交替生成,最后统计前n位神奇字符串中1的个数即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        string str = "122";
        int i = 2;
        while(str.length() < n)   //生成一个长度为n的神奇字符串
        {
            str += string(str[i++]-'0',str.back()^3);  //str.back()就相当于str[str.length()-1]
        }
        int cnt = count(str.begin(),str.begin()+n,'1');
        cout << cnt << endl;
    }
    return 0;
}