USACO 2018 December Silver

一份咕咕了两个月的题解?(其实有两道题的题解都在洛谷上发布了)

A. Convention

题目链接

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

题解

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

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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

题解

一道很暴力的模拟题。

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

(代码量还不小)

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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 找出连通块,并将其删除即可。

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理