USACO 2018 December Silver

一份咕咕了两个月的题解？（其实有两道题的题解都在洛谷上发布了）

A. Convention

题目链接

https://www.luogu.org/problem/P5119

题解

本题可以采用二分答案的方法解决。

先将牛到达的时间排序，然后二分最长等待时间即可。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
 //freopen("convention.in","r",stdin);
 //freopen("convention.out","w",stdout);
 int n,m,c;
 scanf("%d%d%d",&n,&m,&c);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 sort(a+1,a+n+1);
 int l=0,r=a[n]-a[1];
 while(l<r)
 {
  int mid=(l+r)>>1,cnt=1,sta=1;
  for(int i=1;i<=n;i++)
   if(a[i]-a[sta]>mid||i-sta+1>c)
   //如果等待时间超过了二分中点mid或当前车辆已经满载，就重新发一辆车
   {
    cnt++;
    sta=i;
   }
  if(cnt<=m)r=mid;//该时间下车辆数充足，等待时间可以更小
  else l=mid+1;//车辆不足，等待时间要更长
 }
 printf("%d\n",l);
 fclose(stdin);
 fclose(stdout);
 return 0;
}

B. Convention II

题目链接

https://www.luogu.org/problem/P5120

题解

一道很暴力的模拟题。

采用优先队列维护等待序列，每次让等待队列的堆顶出队，并计算答案。

（代码量还不小）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct node
{
 long long id,a,t;
 bool operator<(const node&a)const
 {
  return a.id<id;
 }
}a[100005];
struct lian
{
 long long t;
 vector<int> l;
}b[100005];
priority_queue<node> q;
map<int,int> ma;
bool cmp(const node&a,const node&b)
{
 return a.a<b.a||(a.a==b.a&&a.id<b.id);
}
int main()
{
 long long n,ans=0;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i].a>>a[i].t;
  a[i].id=i;
 }
 sort(a+1,a+n+1,cmp);
 long long x=a[1].a,cnt=1;
 b[1].t=x;
 ma[1]=x;
 for(int i=1;i<=n;i++)
  if(a[i].a==x)b[cnt].l.push_back(i);
  else
  {
   b[++cnt].t=a[i].a;
   ma[cnt]=a[i].a;
   b[cnt].l.push_back(i);
  }
 long long curt=a[1].a,curl=b[1].t,inque=0,pi=1;
 for(vector<int>::iterator it=b[1].l.begin();it!=b[1].l.end();it++)
  q.push(a[*it]),inque++;
 while(!q.empty())
 {
  node eatc=q.top();//队首奶牛出队并计算答案
  ans=max(ans,curt-eatc.a);
  curt+=eatc.t;
  q.pop();
  while(ma[pi+1]<=curt&&ma[pi+1]!=0)//到达的奶牛都入队等待
  {
   for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++)
    q.push(a[*it]),inque++;
   curl=ma[pi];
   if(curl==0)break;
  }
  if(q.empty()&&inque<n)
  {
   for(vector<int>::iterator it=b[++pi].l.begin();it!=b[pi].l.end();it++)
    q.push(a[*it]),inque++;
   curl=ma[pi];
   curt=max(a[inque].a,curt);
  }
 }
 cout<<ans<<endl;
 return 0;
}

C. Mooyo Mooyo

题目链接

https://www.luogu.org/problem/P5121

题解

怎么还是模拟…

本题是一个简单模拟题。

每次按题意 dfs 找出连通块，并将其删除即可。

注意当一个格子下面为空的时候，不要忘了把它往下移动。

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
struct node
{
 int x,y;
 bool operator<(const node&a)const
 {
  return x<a.x||(x==a.x&&y<a.y);
 }
};
set<node> se;
char s[105][15];
int vis[105][15],n,k;
int dfs(int x,int y,char cur)//找连通块
{
 vis[x][y]=1;
 se.insert({x,y});//将找到的格子加入集合，便于后面执行删除操作
 int ans=1;
 if((!vis[x-1][y])&&s[x-1][y]==cur)ans+=dfs(x-1,y,cur);
 if((!vis[x+1][y])&&s[x+1][y]==cur)ans+=dfs(x+1,y,cur);
 if((!vis[x][y-1])&&s[x][y-1]==cur)ans+=dfs(x,y-1,cur);
 if((!vis[x][y+1])&&s[x][y+1]==cur)ans+=dfs(x,y+1,cur);
 return ans;
}
int main()
{
 //freopen("mooyomooyo.in","r",stdin);
 //freopen("mooyomooyo.out","w",stdout);
 scanf("%d%d",&n,&k);
 for(int i=1;i<=n;i++)
  scanf("%s",s[i]+1);
 while(1)
 {
  memset(vis,0,sizeof(vis));
  bool flag=false;
  for(int i=1;i<=n;i++)
   for(int j=1;j<=10;j++)
    if((!vis[i][j])&&s[i][j]!='0')
    {
     int cnt=dfs(i,j,s[i][j]);
     if(cnt>=k)
     {
      for(set<node>::iterator it=se.begin();it!=se.end();it++)
       s[(*it).x][(*it).y]='0';
      flag=true;
     }
     se.clear();
    }
  for(int i=n-1;i>=1;i--)//模拟下落过程
   for(int j=1;j<=10;j++)
   {
    if(s[i][j]=='0')continue;
    int x=i,y=j;
    while(s[x+1][y]=='0')
     swap(s[x][y],s[x+1][y]),x++;
   }
  if(!flag)break;
 }
 for(int i=1;i<=n;i++)
  puts(s[i]+1);
 return 0;
}