牛客周赛 Round 56

\(A\) 牛客 NC277678 面包店故事 \(AC\)

• 选择结构。

  点击查看代码

  int main()
  {
      int x,y,n;
      cin>>x>>y>>n;
      if(x+y<=n)
      {
          cout<<"YES"<<endl;
      }
      else
      {
          cout<<"NO"<<endl;
      }
      return 0;
  }
  

\(B\) 牛客 NC277594 放课后故事 \(AC\)

• 顺序结构。

  点击查看代码

  int main()
  {
      ll n,m,k,x,sum=0,i;
      cin>>n>>m>>k;
      for(i=1;i<=n;i++)
      {
          cin>>x;
          sum+=x;
      }
      cout<<min(m+1,sum/k)<<endl;
      return 0;
  }
  

\(C\) 牛客 NC277217 异或故事 \(AC\)

• 考虑钦定一个数 \(b\) ，然后令 \(c=a \bigoplus b\) 。

• 不妨让 \(b,c \le a\) 那么 \(b=\operatorname{lowbit}(a)\) 是个不错的选择。

• 特判 \(2^{k}(k \in \mathbb{N})\) 的情况。

  点击查看代码

  int lowbit(int x)
  {
      return (x&(-x));
  }
  int main()
  {
      int t,x,i;
      cin>>t;
      for(i=1;i<=t;i++)
      {
          cin>>x;
          if(x==1)
          {
              cout<<2<<" "<<(x^2)<<endl;
          }
          else
          {
              if(__builtin_popcount(x)==1)
              {
                  cout<<1<<" "<<(x^1)<<endl;	
              }
              else
              {
                  cout<<lowbit(x)<<" "<<(x^lowbit(x))<<endl;
              }
          }
      }
      return 0;
  }
  

\(D\) 牛客 NC277596 构造故事 \(AC\)

• 排序后枚举相邻 \(3\) 个数判断即可。

  点击查看代码

  ll a[10010];
  int main()
  {
      ll t,n,ans,i,j;
      cin>>t;
      for(j=1;j<=t;j++)
      {
          cin>>n;
          ans=-1;
          for(i=1;i<=n;i++)
          {
              cin>>a[i];
          }
          sort(a+1,a+1+n);
          for(i=n;i>=3;i--)
          {
              if(a[i-2]+a[i-1]>a[i])
              {
                  ans=max(ans,a[i-2]+a[i-1]+a[i]);
              }
          }
          cout<<ans<<endl;
      }
      return 0;
  }
  

\(E\) 牛客 NC277601 约会故事 \(AC\)

• 将时间转化成 \(4\) 位数后就是一个简单的小模拟了。

• 注意开心的起止时间不在同一天的情况。

  点击查看代码

  int happy[3000];
  map<string,int>vis;
  char tmp[10];
  string s;
  int val(char x)
  {
      return x-'0';
  }
  int to(char s[])
  {
      return val(s[1])*1000+val(s[2])*100+val(s[4])*10+val(s[5]);
  }
  int main()
  {
      int n,m,q,st,ed,x,i,j,k;
      cin>>n>>m;
      for(i=1;i<=n;i++)
      {
          cin>>(tmp+1);
          st=to(tmp);
          cin>>(tmp+1);
          ed=to(tmp);
          if(st==ed)
          {
              fill(happy+0,happy+2600,1);
          }
          else
          {
              if(st<ed)
              {
                  fill(happy+st,happy+ed+1,1);
              }
              else
              {
                  fill(happy+st,happy+2600,1);
                  fill(happy+0,happy+ed+1,1);
              }
          }
      }
      for(i=1;i<=m;i++)
      {
          cin>>s;
          vis[s]=1;
      }
      cin>>q;
      for(i=1;i<=q;i++)
      {
          cin>>(tmp+1);
          x=to(tmp);
          cin>>(tmp+1);
          st=to(tmp);
          cin>>(tmp+1);
          ed=to(tmp);
          cin>>s;
          if(0<=x&&x<=159)
          {
              if(happy[x]==0)
              {
                  cout<<"Loser xqq"<<endl;
              }
              else
              {
                  if(st>ed||vis.find(s)==vis.end())
                  {
                      cout<<"Joker xqq"<<endl;
                  }
                  else 
                  {
                      cout<<"Winner xqq"<<endl;
                  }
              }
          }
          else
          {
              cout<<"Loser xqq"<<endl;
          }
      }
      return 0;
  }
  

\(F\) 牛客 NC277160 不是烤串故事

总结

• \(F\) 没立刻明白反转是什么意思，尝试 \(KMP,Trie\) 树，后缀树组无果。最后发现还得是二分哈希。

后记

• \(E\) 没明确说明开心的起止时间不在同一天时怎么处理，感觉和没说开心的开始时间与结束时间相等怎么处理一样恶劣。