2021NowCoder寒假算法基础集训营3

加法和乘法
如果只有一个数，那么这个数是奇数则牛牛赢，否则牛妹赢。
如果不止一个数，那么假设有奇数个数，显然是牛妹赢。因为剩余2个数的时候，牛妹做最后一次操作，无论什么情况一定都能生成两个偶数（如果剩两个奇数就做加法，如果存在偶数就做乘法）。
假设有偶数个数，牛妹要做的就是让最后剩余2个偶数即可。牛牛每次最多可以消除一个偶数，牛妹每次最多可以生成一个偶数。所以如果初始状态的偶数不小于2个，则牛妹赢；否则牛牛赢。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    cin>>n;
    if(n==1){
        ll x;
        cin>>x;
        if(x&1){
            cout<<"NiuNiu";
        }else{
            cout<<"NiuMei";
        }
        cout<<endl;
        return 0;
    }else if(n==2){
        ll x,y;
        cin>>x>>y;
        ll z1=x*y;
        ll z2=x+y;
        cout<<z1<<" "<<z2<<endl;
        if((z1&1)||(z2&1)){
           cout<<"NiuNiu"<<endl;
        }else{
           cout<<"NiuMei"<<endl; 
        }
        return 0;
    }else{
        ll num=0;
        for(ll i=1;i<=n;i++){
            ll x;
            cin>>x;
            if(!(x&1)){
                num++;
            }
        }
        if(n&1){
            cout<<"NiuMei"<<endl;
            return 0;
        }else{
            if(num<=1){
                cout<<"NiuNiu"<<endl;
            }else{
                    cout<<"NiuMei"<<endl;
                }
         }
            return 0;
        }
    
    return 0;
}

序列的美观度
通过p数组记录上一次某个数出现的位置，但是需要特殊处理一次还没有出现的情况，和dp中求最长上升子序列方法相似

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

匹配串

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    string before="",after="";
    int slen=s.length();
    for(int i=0;i<slen;i++){
        if(s[i]!='#') before+=s[i];
        else break;
    }
    for(int i=s.length()-1;i>=0;i--){
        if(s[i]!='#') after+=s[i];
        else break;
    }
    // cout<<before<<" "<<after<<endl;
    int blen=before.length(),alen=after.length();
    for(int i=2;i<=n;i++){
        string t;
        cin>>t;
        int tlen=t.length();
        for(int j=0;j<tlen;j++){
            if(t[j]=='#'){
                break;
            }
            else{
                if(j<blen){
                    if(t[j]!=before[j]){
                        cout<<0<<endl;
                        return 0;
                    }
                }else{
                    before+=t[j];
                    blen++;
                }
            }
        }
        for(int j=tlen-1;j>=0;j--){
            if(t[j]=='#') break;
            else{
                if(tlen-j-1<alen){
                    if(t[j]!=after[tlen-j-1]){
                        cout<<0<<endl;
                        return 0;
                    }
                }else{
                    after+=t[j];
                    alen++;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

重力坠击
数据样例比较少，可以直接dfs

#include<bits/stdc++.h>
using namespace std;
int n,k,R;
int mp[20][20];
struct node{
    int x,y,r;
}Node[20];
int a[5],b[5];
int dis(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int num=0;
int maxx=-1;
void dfs(int deep){
    if(deep>k){
        int vis[20];
        memset(vis,0,sizeof(vis));
        for(int i=1;i<deep;i++){
            for(int j=1;j<=n;j++){
                if(vis[j]==0){
                   int res = dis(a[i],b[i],Node[j].x,Node[j].y);
                    if((Node[j].r+R)*(Node[j].r+R)>=res){
                        num++;
                        vis[j]=1;
                    } 
                }
                
            }
        }
       maxx=max(maxx,num);
       num=0;
    }else{
        for(int i=-7;i<=7;i++){
            for(int j=-7;j<=7;j++){
                if(mp[i+7][j+7]==0){
                    mp[i+7][j+7]=1;
                    a[deep]=i,b[deep]=j;
                    dfs(deep+1);
                    mp[i+7][j+7]=0;
                }
            }
        }
    }
}
int main(){
   // int n,k,R;
    cin>>n>>k>>R;
    for(int i=1;i<=n;i++){
        cin>>Node[i].x>>Node[i].y>>Node[i].r;
    }
    dfs(1);
    cout<<maxx<<endl;
    return 0;
}