牛客练习赛67

传送门

A.牛牛爱字符串

大意:提取字符串里面的数字，不含前导零，字符串里面有空格

思路:直接使用getline/cin，加上一些判断就好了

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str;
    while(getline(cin,str)){
        int flag=1;
        for(int i=0;i<str.size();i++){
            if(str[i]>='0'&&str[i]<='9'){
                if(flag&&str[i]=='0'){
                    if(str[i+1]>='0'&&str[i+1]<='9')continue;
                    else cout<<"0"<<" ";
                }
            else{
                if(str[i+1]>='0'&&str[i+1]<='9'){cout<<str[i];flag=0;}
                else{cout<<str[i]<<" ";flag=1;}
                }
            }
        }
        cout<<endl;
    }
    return 0;
}

B.牛牛爱位运算

大意:输入n个数，取经过任意组合&运算最大的数。

思路:输出n个数里最大的数即可。

C.牛牛爱博弈

大意:给定一定数量的石子，两个人轮流取，每次任意取取1，2，4，8....等2的幂次方个石子。问最优策略先手胜还是后手胜

思路:列举一些情况发现，3的倍数为先手必输态，非3的倍数的数可以转化为3的倍数使得先手必胜。

D.牛妹爱数列

大意:给定一串只有0/1的数列，有两种操作，1.使任意一个1变成0或者0变成1  2.使从1...x个数所有数目翻转。问使得序列全部为0最少的操作次数

思路:明显的dp,开一个二维数组,第一维存到该位置操作的次数，第二维表示到当前位置全部为1 or 0。

那么有状态转移方程 当a[i]=1时 dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]);dp[i][0]=min(dp[i][0]+1,dp[i-1][1]+1);

当a[i]=0时,dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1);dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);

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

        }
        else{
            dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
            dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1);
        }
    }
    cout<<min(dp[n-1][0],dp[n-1][1]+1)<<endl;
    return 0;
}

E.牛妹游历城市

传送门

不会，大概是二进制拆点加最短路。拆点那里还不大理解。