目录
显示
一份咕咕了两个月的题解？（其实有两道题的题解都在洛谷上发布了）
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;
}