AtCoder Beginner Contest 376

\(A\) Candy Button

• 贪心，模拟。

  点击查看代码

  int main()
  {
      ll n,c,x,last=-0x3f3f3f3f,ans=0,i;
      cin>>n>>c;
      for(i=1;i<=n;i++)
      {
          cin>>x;
          if(x-last>=c)
          {
              last=x;
              ans++;
          }
      }
      cout<<ans<<endl;
      return 0;
  }
  

\(B\) Hands on Ring (Easy)

• 每次移动都选近的一遍。正确性好像不是很显然？

  点击查看代码

  int main()
  {
      int n,q,t,ans=0,l=1,r=2,i;
      char h;
      cin>>n>>q;
      for(i=1;i<=q;i++)
      {
          cin>>h>>t;
          if(h=='L')
          {
              if(l>t)
              {
                  if(t<=r&&r<=l)	
                  {
                      ans+=n-(l-t);
                  }
                  else
                  {
                      ans+=l-t;
                  }
                  
              }
              else
              {
                  if(l<=r&&r<=t)	
                  {
                      ans+=n-(t-l);
                  }
                  else
                  {
                      ans+=t-l;
                  }
              }
              l=t;
          }
          else
          {
              if(r>t)
              {
                  if(t<=l&&l<=r)	
                  {
                      ans+=n-(r-t);
                  }
                  else
                  {
                      ans+=r-t;
                  }
              }
              else
              {
                  if(r<=l&&l<=t)	
                  {
                      ans+=n-(t-r);
                  }
                  else
                  {
                      ans+=t-r;
                  }
              }
              r=t;
          }
      }
      cout<<ans<<endl;
      return 0;
  }
  

\(C\) Prepare Another Box

• 模拟，懒得写双指针，所以用 multiset 代替了。

  点击查看代码

  ll a[200010];
  multiset<ll>f;
  multiset<ll>::iterator it;
  int main()
  {
      ll n,ans=-1,x,pos,i;
      cin>>n;
      for(i=1;i<=n;i++)
      {
          cin>>a[i];
      }
      for(i=1;i<=n-1;i++)
      {
          cin>>x;
          f.insert(x);
      }
      sort(a+1,a+1+n);
      for(i=n;i>=1;i--)
      {
          it=f.lower_bound(a[i]);
          if(it!=f.end())
          {
              f.erase(it);
          }
          else
          {
              if(ans==-1)
              {
                  ans=a[i];
              }
              else
              {
                  ans=-1;
                  break;
              }
          }
      }
      cout<<ans<<endl;
      return 0;
  }
  

\(D\) Cycle

• 如果是无向图（不能重复走某条边）的话，就是 暑假集训CSP提高模拟19 T2 P160. 那一天她离我而去 了。

• 因为是有向图，所以处理出到指向 \(1\) 的节点的最短路再多走一条边即可。

  点击查看代码

  int vis[200010],dis[200010];
  vector<pair<int,int> >broke,e[200010];
  void add(int u,int v,int w)
  {
      e[u].push_back(make_pair(v,w));
  }
  void dijkstra(int s)
  {
      memset(dis,0x3f,sizeof(dis));
      memset(vis,0,sizeof(vis));
      priority_queue<pair<int,int> >q;
      dis[s]=0;
      q.push(make_pair(-dis[s],-s));
      while(q.empty()==0)
      {
          int x=-q.top().second;
          q.pop();
          if(vis[x]==0)
          {
              vis[x]=1;
              for(int i=0;i<e[x].size();i++)
              {
                  if(dis[e[x][i].first]>dis[x]+e[x][i].second)
                  {
                      dis[e[x][i].first]=dis[x]+e[x][i].second;
                      q.push(make_pair(-dis[e[x][i].first],-e[x][i].first));
                  }
              }
          }
      }
  }
  int main()
  {
      int n,m,ans=0x3f3f3f3f,u,v,w,i;
      cin>>n>>m;
      for(i=1;i<=m;i++)
      {
          cin>>u>>v;
          w=1;
          if(v==1)
          {
              broke.push_back(make_pair(u,w));
          }
          add(u,v,w);
      }
      dijkstra(1);
      for(i=0;i<broke.size();i++)
      {
          ans=min(ans,dis[broke[i].first]+broke[i].second);
      }
      cout<<((ans==0x3f3f3f3f)?-1:ans)<<endl;
      return 0;
  }
  
  

\(E\) Max × Sum

• 按 \(\{ a \}\) 排序后钦定选择某个数再在前缀中选前 \(k-1\) 小的数加和。

• 优先队列维护即可。

  点击查看代码

  struct node
  {
      ll a,b;
  }e[200010];
  bool cmp(node a,node b)
  {
      return a.a<b.a;
  }
  priority_queue<ll>q;
  int main()
  {
      ll t,n,k,ans,sum,i,j;
      cin>>t;
      for(j=1;j<=t;j++)
      {
          ans=1e18;
          sum=0;
          cin>>n>>k;
          while(q.empty()==0)
          {
              q.pop();
          }
          for(i=1;i<=n;i++)
          {
              cin>>e[i].a;
          }
          for(i=1;i<=n;i++)
          {
              cin>>e[i].b;
          }
          sort(e+1,e+1+n,cmp);
          for(i=1;i<=k-1;i++)
          {
              q.push(e[i].b);
              sum+=e[i].b;
          }
          for(i=k;i<=n;i++)
          {	
              ans=min(ans,e[i].a*(sum+e[i].b));
              q.push(e[i].b);
              sum-=q.top();
              sum+=e[i].b;
              q.pop();
          }
          cout<<ans<<endl;
      }
      return 0;
  }
  

\(F\) Hands on Ring (Hard)

• 等有时间再来补。

\(G\) Treasure Hunting

• 等有时间再来补。

总结

• \(D\) 把无向图做法贺过来就直接交了，然后吃了 \(2\) 发罚时。
• \(E\) 原权值线段树找到第 \(k-1\) 小的数然后求前缀和的做法假了，原因是若第 \(k-1\) 小的数如果有多个，就会额外统计。