【BZOJ5288】[HNOI2018]游戏(拓扑排序)
2023-09-11 14:14:40 时间
【BZOJ5288】[HNOI2018]游戏(拓扑排序)
题面
题解
去年省选的时候这题给我乱搞整过去整过去了,也是虐心了。。。。
所以当然是来讲正儿八经的正确做法啦。
很明显,我们需要预处理答案。设\(L[i],R[i]\)表示从\(i\)出发能够到达的区间范围。
现在我们要做的就是预处理这个\(L[i],R[i]\)。
首先考虑一个点如何向外暴力拓展,如果它在拓展过程中碰到了一个已经被拓展过的节点,那么显然也可以到达那个点可以到达的所有位置,然后直接并一下就好啦。
然后现在我们要确定拓展的顺序。
对于一个门\((x,x+1)\)而言,如果钥匙在\([1,x]\)这段内,显然只有在\([1,x]\)这一侧才能拓展到\([x+1,n]\),所以一定先拓展\(x+1\)再拓展\(x\),所以连边\(x+1\rightarrow x\),反过来同理。
然后拓扑序确定拓展顺序。
这样子每个点被拓展的次数就是线性的啦QwQ
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define MAX 1000100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next;}e[MAX];
int h[MAX],cnt=1,dg[MAX];
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;dg[v]+=1;}
int n,m,Q,p[MAX],tot,key[MAX];
void Topsort()
{
queue<int> Q;
for(int i=n;i;--i)if(!dg[i])Q.push(i);
while(!Q.empty())
{
int u=Q.front();Q.pop();p[++tot]=u;
for(int i=h[u];i;i=e[i].next)
if(!--dg[e[i].v])Q.push(e[i].v);
}
}
int L[MAX],R[MAX];
void Calc(int x)
{
int l=x,r=x;
while(233)
{
int pl=l,pr=r;
while(l>1&&(!key[l-1]||(l<=key[l-1]&&key[l-1]<=r)))l=L[l-1];
while(r<n&&(!key[r]||(l<=key[r]&&key[r]<=r)))r=R[r+1];
if(pl==l&&pr==r)break;
}
L[x]=l;R[x]=r;
}
int main()
{
n=read();m=read();Q=read();
for(int i=1;i<=m;++i)
{
int x=read(),y=read();key[x]=y;
if(y<=x)Add(x+1,x);
else Add(x,x+1);
}
Topsort();
for(int i=1;i<=n;++i)L[i]=R[i]=i;
for(int i=1;i<=n;++i)Calc(p[i]);
while(Q--)
{
int S=read(),T=read();
if(L[S]<=T&&T<=R[S])puts("YES");
else puts("NO");
}
return 0;
}
相关文章
- 游戏测试 | 测试工具:做一个可以即时修改卡牌属性的工具方便测试
- 至简至美-ATtiny0 跑的一个游戏
- 《HTML5 2D游戏编程核心技术》——第2章,第2.1节使用开发者工具
- 《HTML5 2D游戏编程核心技术》——第2章,第2.5节缩短编码周期
- 华为联运游戏审核驳回:无法进入游戏,但开发者自己测试登录正常
- 《Android游戏开发详解》一2.9 类
- 《Unity 游戏案例开发大全》一6.6 游戏的优化与改进
- 《Cocos2d 跨平台游戏开发指南(第2版)》一第1章 精灵与动画
- 《点睛:ActionScript3.0游戏互动编程》——导读
- 《Android游戏开发详解》——第2章,第2.8节对象的基础知识
- 《Unity 5.x游戏开发实战》一1.9 添加一个水平面
- 《Android游戏开发详解》——第2章,第2.19节使用字符串
- 《Unity 3.x游戏开发实例》——1.6节先走后跑(或双脚跳)
- 科学好比是开发一款新游戏,技术好比玩游戏,不一定开发游戏的人就能把游戏玩到最好
- 【Unity3D日常开发】Unity3D中数字网格类游戏Demo实现
- C语言选择结构程序设计——“21点”游戏and一元二次方程and能否被3,5,7,9整除
- 会说话的HTML--语义化杂谭-TGideas-腾讯游戏官方设计团队