麦芽雪冷萃

题目描述：

神奇字符串的定义为: 只含有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;
}