2019百度之星第二场 度度熊与运算式1

思路：

贪心。

实现：

 1 #include 
 2 using namespace std;
 3 int c[30];
 4 int main()
 5 {
 6     //freopen("in.txt","r",stdin);
 7     ios::sync_with_stdio(false);
 8     int T;cin>>T;
 9     string s;
10     while(T--){
11         fill(c,c+30,0);
12         cin>>s;
13         int n=s.length();
14         int i=0;
15         vector<int>v;
16         int cur=1;
17         while(i<n){
18             if(s[i]=='^'){
19                 v.push_back(cur);
20                 cur=1;
21             }
22             else{
23                 cur++;
24             }
25             i++;
26         }
27         v.push_back(cur);
28         for(auto it:v){
29             while(it){
30                 c[__builtin_ffs(it)]++;
31                 it-=it&-it;
32             }
33         }
34         int res=0;
35         for(int i=29;i>=0;i--){
36             if(c[i]>=2){
37                 res+=(1<1;
38                 break;
39             }
40             else if(c[i]==1){
41                 res+=1<1;
42             }
43         }
44         if(res%2!=(n+1)%2){
45             res^=1;
46         }
47         cout<endl;
48     }
49     return 0;
50 }