首页 > 其他分享 >题解:【ABC168F】 . (Single Dot)

题解:【ABC168F】 . (Single Dot)

时间:2023-06-18 15:56:30浏览次数:48  
标签:int ABC168F read 题解 long ++ Single getchar define

题目链接

挺套路的题。如果值域和线段数量同阶,可以预处理不能越过的线段,使用状压四个方向记录每个节点能不能往这个方向走,然后直接爆搜就好了,标记上能走到哪些地方。但这个值域一看就是没有救的,于是就要拿出来离散化了。把线段的横纵坐标都拎出来离散化,依然是同样的预处理,然后从离散化后的 \((0,0)\) 开始向外爆搜,最后还是扫一遍能够到哪些地方,统计答案只需要变成离散化前的对应位置即可。唯一需要注意的地方是放入边界横纵坐标一定要比数据范围大一点,本人最开始边界放 \(10^9\) 疯狂 WA。于是总复杂度为 \(\mathcal O(nm + n \log n + m \log m)\),分别为搜索和离散化。直接这样说可能还是有些抽象了,不过代码非常清晰。

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y)  (__lg((x),(y)))
using namespace std;

namespace FastIO
{
    template<typename T=int> inline T read()
    {
        T s=0,w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        return s*w;
    }
    template<typename T> inline void read(T &s)
    {
        s=0; int w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        s=s*w;
    }
    template<typename T,typename... Args> inline void read(T &x,Args &...args)
    {
        read(x),read(args...);
    }
    template<typename T> inline void write(T x,char ch)
    {
        if(x<0) x=-x,putchar('-');
        static char stk[25]; int top=0;
        do {stk[top++]=x%10+'0',x/=10;} while(x);
        while(top) putchar(stk[--top]);
        putchar(ch);
        return;
    }
}
using namespace FastIO;

inline void file()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    return;
}

bool Mbe;

namespace LgxTpre
{
    static const int MAX=5010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    static const int mod=1e9+7;
    static const int bas=131;
    
    int n,m,ans;
    int a[MAX],b[MAX],c[MAX],d[MAX],e[MAX],f[MAX];
    int X[MAX],Y[MAX],cntx,cnty;
    #define lbx(x) lower_bound(X+1,X+cntx+1,x)-X
    #define lby(y) lower_bound(Y+1,Y+cnty+1,y)-Y
    
    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};
    int sx,sy,obs[MAX][MAX],vis[MAX][MAX];
    void dfs(int x,int y)
    {
    	if(x<1||y<1||x>cntx||y>cnty||vis[x][y]) return;
    	vis[x][y]=1;
    	for(int i=0;i<4;++i) if(!(obs[x][y]>>i&1)) dfs(x+dx[i],y+dy[i]);
	}
	
    inline void dry()
	{
		X[++cntx]=-1.1e9,X[++cntx]=0,X[++cntx]=1.1e9,
		Y[++cnty]=-1.1e9,Y[++cnty]=0,Y[++cnty]=1.1e9;
		read(n,m);
		for(int i=1;i<=n;++i) read(a[i],b[i],c[i]),X[++cntx]=a[i],X[++cntx]=b[i],Y[++cnty]=c[i];
		for(int i=1;i<=m;++i) read(d[i],e[i],f[i]),X[++cntx]=d[i],Y[++cnty]=e[i],Y[++cnty]=f[i];
		sort(X+1,X+cntx+1),cntx=unique(X+1,X+cntx+1)-X-1;
		sort(Y+1,Y+cnty+1),cnty=unique(Y+1,Y+cnty+1)-Y-1;
		for(int i=1;i<=n;++i) 
		{
			int l=lbx(a[i]),r=lbx(b[i]),y=lby(c[i]);
			for(int j=l;j<r;++j) obs[j][y]|=1<<1,obs[j][y-1]|=1<<0;
		}
		for(int i=1;i<=m;++i)
		{
			int x=lbx(d[i]),l=lby(e[i]),r=lby(f[i]);
			for(int j=l;j<r;++j) obs[x][j]|=1<<3,obs[x-1][j]|=1<<2;
		}
		sx=lbx(0),sy=lby(0),dfs(sx,sy);
		for(int i=1;i<=cntx;++i) if(vis[i][1]||vis[i][cnty]) return puts("INF"),void();
		for(int i=1;i<=cnty;++i) if(vis[1][i]||vis[cntx][i]) return puts("INF"),void();
		for(int i=2;i<cntx;++i) for(int j=2;j<cnty;++j) if(vis[i][j]) ans+=(X[i+1]-X[i])*(Y[j+1]-Y[j]);
		write(ans,'\n');
    }
}

bool Med;

signed main()
{
//  file();
    fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
    int Tbe=clock();
    LgxTpre::dry();
    int Ted=clock();
    cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}

标签:int,ABC168F,read,题解,long,++,Single,getchar,define
From: https://www.cnblogs.com/LittleTwoawa/p/17489227.html

相关文章

  • 2022 RoboCom 世界机器人开发者大赛-本科组(国赛)个人题解
    RC-u4变牛的最快方法思路最短编辑距离+记录路径板子题,不懂最短编辑距离的可以看看网上的博客。不懂为什么官方题解用的bfs写法,然后网上所有的题解就是bfs了。我这里就是双重for循环实现,参考下写法即可。代码点击查看代码#include<bits/stdc++.h>#definexfirst#definey......
  • CF1840C题解
    题目描述题目传送门\(T\)组数据,每组数据给定\(n\),\(k\),\(q\)和一个长度为\(n\)的数组\(a\),求\(a\)中长度大于等于\(k\)且最大值小于等于\(q\)的序列个数。\(\sum{n}\le2e5\)。题目解析解法一:数据结构解法显然可以利用数据结构维护。考虑ST表预处理出区间最大......
  • JOI Final 2020 题解
    JOI2020JustLongNeckties首先一定是贪心将两个从小到大排。然后考虑维护\(a_i-b_i\)的前缀max与\(a_{i+1}-b_i\)的后缀max即可。https://qoj.ac/submission/113106JOI2020JJOOII2考虑维护出每个点往前跳\(k\)个J/O/I跳到哪里。于是枚举右端点,然后往前跳找......
  • 蓝桥杯嵌入式第十三届客观题解析
    (文章目录)前言本篇文章将带大家来学习蓝桥杯嵌入式的客观题了,蓝桥杯嵌入式的客观题涉及到模电,数电,单片机等知识,需要非常扎实的基础,客观题不能急于求成只能脚踏实地一步步的积累,下面就让我们正式进入客观题的讲解。一、题目1第一题是一个多选题选ABC在参考手册中我们可以清......
  • 【题解】[NOIP2017 提高组] 逛公园
    题目描述:策策同学特别喜欢逛公园。公园可以看成一张\(N\)个点\(M\)条边构成的有向图,且没有自环和重边。其中\(1\)号点是公园的入口,\(N\)号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。策策每天都会去逛公园,他总是从\(1\)号点进去,从\(N\)号......
  • 【题解】Atcoder ABC300 F.More Holidays(线性做法)
    F.MoreHolidays题目描述:给你一个由o和x组成的长度为\(N\)的字符串\(S\),以及整数\(M\)和\(K\)。保证\(S\)至少包含一个x。假设\(T\)是由\(S\)复制\(M\)次而成的长度为\(NM\)的字符串。考虑将\(T\)中的\(K\)个x恰好替换为o。你的目标是在替换后的......
  • P2161 [SHOI2009]会场预约 题解
    蒟蒻提供一种fhq-treap的做法,但是不如其他题解的快(也没有stl快,不开O21.8s),但是比较好想,扩展了fhq的模板,也算是为使用fhq提供一个新方法。首先,fhq-treap是什么,如果有同学不清楚,请点击学习(并非我的blog)那么,由于fhq树的分裂操作,使得我们可以很方便的取出我们想要的区间。那么,在......
  • react经典面试题解析--持续更新--day01
    一、类组件和函数组件的区别(面试常考)简单理解(所有同学都要掌握)1、类组件有生命周期,函数组件没有2、类组件需要继承Class,函数组件不需要3、类组件可以获取实例化的this,并且基于this做各种操作,函数组件不行4、类组件内部可以定义并维护state,函数组件都称为无状态了,那肯定......
  • AtCoder ABC056D 题解
    题目直达0x00思路从大到小枚举每个元素,同时加入\(sum\)进行累计,当\(k\lesum\)时,便会返现之前的元素可以构成“好的组”(因为他们都大于\(p_i\)),即有用的,所以要清空。0x01举个例子36143我们对输入排序后,会得到\(p\)为。431这时,我们的\(i=1\),即\(p_i=......
  • AtCoder ABC228D 题解
    [ABC299D]FindbyQuery题解0x00题目分析题目传送门经过分析,我们得到的几个关键信息:\(n\le2\times10^5\)最多可以问法官\(20\)个问题。s[1]=0,s[n]=1分析\(n\)的范围,发现\(\log_n=17.6096\),刚好比\(20\)小一点点。这时便考虑二分的做法。看到s[1]=0,......