第一题

• 贪心
• 计算1的区间及每个区间的个数，排序。交替赋给niumei niuniu。

  #include
  using namespace std;
  int main(){
    int T;
    cin>>T;
    while(T--){
        string s;
        cin>>s;
        vector cnt1;
        int cnt=0;
        for(char c:s){
            if(c=='1')
                cnt++;
            else{
                cnt1.push_back(cnt);
                cnt=0;
            }
        }
        cnt1.push_back(cnt);
        sort(cnt1.rbegin(),cnt1.rend());
        int ans = 0;
        for(int i=0;i<cnt1.size();i++){
            if(i%2==0)
                ans+=cnt1[i];
            else ans-=cnt1[i];
        }
        if(ans==0) cout<<"Draw"<<endl;
        else if(ans>0){
            cout<<"Niumei"<<endl<<ans<<endl;
        }else
            cout<<"Niuniu"<<endl<<-ans<<endl;       
    }
    //system("pause");
    return 0;
  }

  第二题

• 贪心
• 以{attack,money}为二元组进行排序，money为第一关键字降序，attack为第二关键字升序。最后求结果。

  #include<bits/stdc++.h>
  using namespace std;
  int main(){
    int n,k;
    cin>>n>>k;
    vector<int> attack(n),money(n);
    vector<vector<int>> mh(n,vector<int>(3));
    for(int i=0;i<n;i++){
        cin>>mh[i][1];
        attack[i] = mh[i][1];
    }       
    for(int i=0;i<n;i++){
        cin>>mh[i][2];
        money[i] = mh[i][2];
    }   
    sort(mh.begin(),mh.end(),[](vector<int> &m1,vector<int> &m2){
        return m1[2]>m2[2]||m1[2]==m2[2]&&m1[1]>m2[1];
    });
    for(int i=0;i<n;i++){
        int j=0,t=0;
        long long sum=0;
        while(j<n&&attack[i]<=mh[j][1]) j++;
        while(t<k&&j<n){
            if(attack[i]>mh[j][1]){
                sum+=mh[j][2];
                t++;
            }
            j++;
        }
        sum+=money[i];
        if(i!=n-1)
            cout<<sum<<" ";
        else cout<<sum<<endl;
    }
    //system("pause");
    return 0;
  }

  字典树

• 首先对数据库的身份证号建立字典树,属性多加一个个数，表示以该节点为前缀的身份证号个数。
• 然后用目标串搜索字典树，最大相似度就是最长前缀。

  #include<bits/stdc++.h>
  using namespace std;
  class Trie{  
  public:
    bool isEnd;
    vector<Trie*> next;
    int num;
    vector<int> search(string &s){
        Trie* node = this;
        int l  = s.size();
        for(int i=0;i<l;i++){
            char c = s[i];
            if(node->next[c-'0']==nullptr){
                return {i,node->num};
            }
            node = node->next[c-'0'];
        }
        return {l,node->num};
    }
    Trie():isEnd(false),next(10),num(0){}
    void insert(string &s){
        Trie* node = this;
        int l  = s.size();
        for(int i=0;i<l;i++){
            char c = s[i];
            if(node->next[c-'0']==nullptr){
                node->next[c-'0'] = new Trie();
                node->next[c-'0']->num = 1;
            }else{
                node->next[c-'0']->num++;
            }
            node = node->next[c-'0'];
        }
        node->isEnd = true;
    }
  };
  int main(){
    int n,q;
    cin>>n>>q;
    string s;
    Trie* trie = new Trie();
    for(int i=0;i<n;i++){    
        cin>>s;
        trie->insert(s);
    }
    for(int i=0;i<q;i++){
        cin>>s;
        vector<int> ans = trie->search(s);
        if(ans[0]==0)
            ans[1] = n;
        cout<<ans[0]<<" "<<ans[1]<<endl;
    }
    //system("pause");
    return 0;
  }