牛牛爱字符串

题意：给出一个字符串，提取出这个字符串中的所有的数字，然后依次输出这些数字。
思路：简单模拟。但是这里要注意的是不能有前导0，还有全为0的情况输出即可。
代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(getline(cin,s)){
        string ans[1000];
        int len=s.size();
        int num=0;
        for(int i=0;i<len;i++){
            if(s[i]<='9'&&s[i]>='0')  ans[num]+=s[i];
            if(i>0){
                if(s[i-1]<='9'&&s[i-1]>='0'&&(s[i]<'0'||s[i]>'9')) num++; 
            }
        }
        if(s[len-1]>='0'&&s[len-1]<='9')  num++;
        for(int i=0;i<num;i++){
            len=ans[i].size();
            int j;
            for(j=0;j<len;j++){
                if(ans[i][j]!='0') break;
            }
            for(;j<len;j++){
                cout<<ans[i][j];
            }
            if(i<num-1)  cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

牛牛爱位运算

题意：给出一个数组，求数组里面的所有的数且之后的最大值。
思路：对于每个数字写出它的二进制表示后，我们会发现且之后1&1=1，1&0=0，0&1=0，0&0=0，那么我们就想，如果我们要求最大的话，如果这个位置为0的话，那么它无论如何都不会成为1，如果为1的话，它很可能会变成0。最后下来，我们得到一个结论就是找出最大的那个值就是本题的答案了。
代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int mx=-1;
        for(int i=0;i<n;i++){
            cin>>a[i];
            mx=max(mx,a[i]);
        }
        cout<<mx<<endl;
    }
    return 0;
}

牛牛爱博弈

题意：一共有n堆棋子，两人轮流取石子，但是要求取的数量必须为2^k次方，取走最后一颗石头的那一方获胜。
思路：经过模拟，我们发现1，2对先手方为必赢态，而3对后手方为必赢态（因为先手会把石头拿成对后手有利的那个局面，对于此时的局面，先手方变为后手方。然后4，5对先手方为必赢态，6对后手方为必赢态。这样模拟下来的话，我们发现，n为3的倍数的话后手方赢，否则为先手方赢。
代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        if(n%3==0)  cout<<"Frame"<<endl;
        else  cout<<"Alan"<<endl;
    }
    return 0;
}

牛妹爱数列

题意：给出一个01序列，然后对这个序列可以进行一下两种操作，1、反转序列中的某个序列的值（0或1），2、反转前x个序列的值（0或1），问最小的操作数使得最后的序列变成全0.
思路：一个很显然的dp的思想。我们用一个二维dp数组表示对这个序列进行处理的步数最小。dp[i][0]表示的是前i个数全变成0的所需的最小的数。dp[i][1]表示这个序列全部变成1所需的最小的操作数。当我们遍历到这个序列的i时，如果此时的a[i]为1的话，那么dp[i][0]就可以向min(dp[i-1][0]+1,dp[i-1][1]+1)转移，dp[i][1]可以向min(dp[i-1][1],dp[i-1][0]+1)转移。同理a[i]=0的时候类似的进行转移即可。
代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int dp[100010][2];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)  cin>>a[i];
    for(int i=1;i<=n;i++){
        if(a[i]){
            dp[i][0]=min(dp[i-1][1]+1,dp[i-1][0]+1);
            dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1);
        }else{
            dp[i][0]=min(dp[i-1][1]+1,dp[i-1][0]);
            dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+1);
        }
    }
    cout<<dp[n][0]<<endl;
    return 0;
}

牛妹游历城市

题意：给出n个节点，然后每个结点都有一个值，这两个结点之间有无连边取决于两者的且值，如果不为0表示这两个点之间有一天连边，然后这条边的权值为lowbit(a[i]&a[j])。
思路：我们发现，当务之急就是先将这n个点连接起来，但是我们会发现点的数量太多了，怎么办呢？我们看题目出现了&这个符号，那么我们很显然可以往位运算那方面考虑。我们观察数据都是在int范围内的，那么我们就对这n个点的a进行一个处理，提取出这n个数的位进制位，然后遍历这32位二进制就可以实现判断这两个点之间是否存在连边。同时我们建立若干个虚点来方便找出存在连边的那些点，也就是我们把在第j位（1<=j<32)为1的a[i]存放在一个结构体里面，然后两者相互映射，当我们遍历到i的时候，我们可以通过映射找到存储与之存在连边的点的那个结构体，这样我们就可以快速的找到存在连边的那些点了（这个方法确实十分的巧妙666）然后跑一遍Dijkstra即可。
代码：

#include<bits/stdc++.h>
#define lowbit(x) (x&)-x)
using namespace std;
typedef long long ll;
const int N=1e5+100;
ll a[N],dis[N],len;
int book[N],s=1,t,n;
struct node{
    int v;
    ll val;
};
vector<node> e[N];
void solve(){
    queue<int> q;
    memset(book,0,sizeof(book));
    q.push(s);
    book[s]=1;
    dis[s]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        book[x]=0;
        for(int i=0;i<e[x].size();i++){
            node to=e[x][i];
            if(dis[to.v]>dis[x]+to.val){
                dis[to.v]=dis[x]+to.val;
                if(book[to.v]==0){
                    q.push(to.v);
                    book[to.v]=1;
                }
            }
        }
    }
    if(dis[n]!=1e18)  cout<<dis[n]<<endl;
    else  cout<<"Impossible"<<endl;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n+50;i++){
            e[i].clear();
            dis[i]=1e18;
        }
        for(int i=1;i<=n;i++)  cin>>a[i];
        for(int i=1;i<=n;i++){
            for(int j=0;j<32;j++){
                if(a[i]&(1ll<<j)){  //二进制下的第j位为1的话 
                    e[i].push_back({n+1+j,1ll<<j});
                    e[n+1+j].push_back({i,0});
                }
            }
        }
        solve();
    }
    return 0;
}