【编程题解】2021春招第2次牛客模考笔试题技术方向

消消看

知识点：贪心，排序
题意：给定一个01串，每次可以选择一个连续的0或者1子串消除。两个人轮流消除，求双方都最优选择时，胜者是谁以及分数之差。
思路：显然不可能选择'0'子串。并且有多个'1'子串时会选择最长的那个1串。因此用贪心策略即可，预处理出所有'1'子串的长度，然后从大到小选择即可。
复杂度

#include<bits/stdc++.h>
using namespace std;
int main(){

    int t;
    cin>>t;
    while(t--){
        vector<int>v;
        int n,i,cnt=0;
        string s;
        cin>>s;
        for(i=0;i<s.length();i++){
            if(s[i]=='1')cnt++;
            else v.push_back(cnt),cnt=0;
        }
        v.push_back(cnt);
        sort(v.begin(),v.end());
        int c1=0,c2=0;
        for(i=0;i<v.size();i++){
            if(i%2)c2+=v[i];
            else c1+=v[i];
        }
        if(c1<c2)cout<<"Niumei\n"<<c2-c1<<endl;
        else if(c1==c2)cout<<"Draw\n";
        else cout<<"Niumei\n"<<c1-c2<<endl;
    }
}

赏金猎人

知识点：贪心，排序，优先队列
题意：每个人有一个战斗力和金钱。每个人只能击杀比自己战斗力低的人，并获得他的金钱。问在最多击杀 个人的前提下，每个人最多的钱是多少？
思路：对于每个人而言，只需要在战斗力比他小的人里，找出 个最大的金钱即可。观察到 的范围不超过10，因此可以用优先队列（最大堆）解决这个问题。
写代码的时候要注意细节，处理“战斗力相等”的人的时候要格外小心。
复杂度

using namespace std;
struct people{
    int attack,money,id,res;
};

people a[100010];
bool cmp(people a,people b){
    return a.attack<b.attack;
}
bool cmp_by_id(people a,people b){
    return a.id<b.id;
}
priority_queue<int>q;
int main(){
    int n,k,i,j;
    cin>>n>>k;
    for(i=0;i<n;i++)cin>>a[i].attack;
    for(i=0;i<n;i++){
        cin>>a[i].money;
        a[i].id=i;
        a[i].res=a[i].money;
    }
    sort(a,a+n,cmp);
    vector<int>temp;
    for(i=0;i<n;i++){
        vector<int>to_be_killed;
        int now=q.size();
        for(j=0;j<min(k,now);j++){
            a[i].res+=q.top();
            to_be_killed.push_back(q.top());
            q.pop();
        }
        for(j=0;j<to_be_killed.size();j++){
            q.push(to_be_killed[j]);
        }
        temp.push_back(a[i].money);
        to_be_killed.clear();
        if(i<n-1&&a[i].attack<a[i+1].attack){
            for(j=0;j<temp.size();j++){
                q.push(temp[j]);
            }
            temp.clear();
        }
    }
    sort(a,a+n,cmp_by_id);
    for(i=0;i<n;i++){
        cout<<a[i].res<<" ";
    }

}

身份证

解法一

知识点：排序、二分
思路：可以发现每个数都在 的数据范围内。对于一个十八位数 而言， 和它前 个数字相等意味着除了前 个数字以外， 的后 个数字一定在 000..00到 999..99范围内。
例如，对于数字123451234512345123，如果另一个数和它有长度为5的公共前缀，那么这个数的取值范围是 123450000000000000到123459999999999999。
所以这道题可以用二分来解，对于每个数，二分去找其前缀长度为 的合法上界和下界，若该上界和下界中包含的数不为零，那么意味着存在该公共前缀的数。
复杂度

解法二

知识点：字典树
思路：如果熟悉字典树的话可以发现这是一道字典树的裸题。建一棵字典树，每个节点上存该前缀的字符串数量。然后就可以做到每次 进行查询了。
复杂度
参考代码（二分解法）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<long long>v;
ll pow10[20];
int main(){
    int n,q,i;
    pow10[0]=1;
    for(i=1;i<18;i++)pow10[i]=pow10[i-1]*10;
    cin>>n>>q;
    for(i=0;i<n;i++){
        ll x;
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    while(q--){
        ll x;
        cin>>x;
        ll j=17;
        ll out1=0,out2=0;
        for(i=1;i<=18;i++,j--){
            ll l=x/pow10[j]*pow10[j],r=(x/pow10[j]+1)*pow10[j];
            ll c1=lower_bound(v.begin(),v.end(),l)-v.begin();
            ll c2=upper_bound(v.begin(),v.end(),r)-v.begin();
            if(c1==c2)break;
            out1=i,out2=c2-c1;
        }
        if(out1==0)out2=n;
        cout<<out1<<" "<<out2<<endl;
    }
}