首页 > 牛客春招第二次模拟全AC
头像
媚笑呀
编辑于 2021-04-17 16:03
+ 关注

牛客春招第二次模拟全AC

第一题

  • 贪心
  • 计算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;
    }

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐