UOJ142 【UER #5】万圣节的南瓜灯 题解
题意:
cxy 是
一个心灵手巧的女孩纸。今天是万圣节, cxy 正在家里制作南瓜灯。这时候一群熊孩子们敲开了 cxy 家的门,他们高呼着 “不用给糖,只要捣蛋” 的口号把 cxy 的南瓜灯弄坏了。这让 cxy 很难过,于是她打算把这些被弄坏的南瓜灯做成其他的工艺品。
cxy 把她的南瓜灯划分成了 \(n \times m\) 的网格,并用 \((x,y)\) 表示第 \(x\) 行,第 \(y\) 列的格子。两个格子是相邻的当且仅当它们有一条公共边,特殊地, \((x,1)\) 和 \((x,m)\) cxy 也视为是相邻的,但是他不把 \((1,x)\) 和 \((n,x)\) 当做是相邻的。
对于一个有 \(k\) 个格子被弄坏的南瓜灯,如果它能被制作成工艺品,当且仅当对于任意两个没有被弄坏的格子,都存在且仅存在一条连接它们的简单路径。一条简单路径定义为一个只包含没有被弄坏的格子的序列 \(A_1\) 至 \(A_n\) ,其中对于任意的 \(1 \leq i < n\) 都有 \(A_i\) 和 \(A_{i+1}\) 是相邻的,且每一个格子在序列中至多出现了一次。
现在 cxy 有 \(T\) 个南瓜灯,她想让你帮她分别判断每一个南瓜灯能不能被做成工艺品。
输入格式:
第一行一个正整数 \(T\),表示南瓜灯数目。
对于每一个南瓜灯,第一行是三个整数 \(n,m,k\),表示南瓜灯的大小和被弄坏的格子数。
接下来 \(k\) 行每行包含两个整数 \(x,y\)(\(1 \leq x \leq n,1 \leq y \leq m\)),表示第 \(x\) 行第 \(y\) 列的格子被弄坏了。
数据保证 \(n,m \geq 3\),\(0 \leq k < nm\) 且不会重复描述一个被弄坏的格子。
输出格式:
对于每一个南瓜灯,输出一行,如果这个南瓜灯能被做成工艺品,那么输出 "Yes",否则输出"No"。
数据范围:
\(n,m \le 10^9,~k\le 10^5\)
直接暴力建图坑定是不行滴。
但是我们可以从 \(k\) 的范围估测出有效点数
因为当点数很多的时候,很难产生一棵树,因此这一定有个上界
点数很简单,肯定是 \(|V|=nm-k\)
考虑边数,\(nm\) 条横向边 + \((n-1)m\) 条纵向边 = \((2n-1)m\) 条边
而每次删掉一条边至多删去 \(4\)
条边,故 \[
|E| \ge (2n-1)m - 4k
\] 由于 \(|E|=|V|-1\) ,则 \[
nm-k-1 \ge (2n-1)m-4k
\] 即 \[
3k \ge (n-1)m+1
\] 如果不满足这个条件直接输出No
就好了
你看这个 \((n-1)\)
,是不是很难看,于是尝试要找到 \(n\) 与 \(n-1\) 的关系
离谱的来了 \[
n\ge 3 \Rightarrow n \le \dfrac{3}{2} (n-1)
\] 因此 \[
|V| < nm \le \dfrac{3}{2}(n-1)m < \dfrac{9}{2}k \le 4.5\times 10^5
\] 于是直接 \(\mathtt{dfs}\)
就好啦!
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(5e5+15))
#define cxy static int x;
#define is for(int i=1; i<=k; i++)
#define very cin >> x >> x;
#define cute return 0
#define haha(r,c) ((r-1) * m + c)
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
int n,m,k,used[N],ck[N];
bool dfs(int x,int y,int la=0)
{
int cur=haha(x,y),tx,ty,nx;
used[cur] = 1;
for(int d=0; d<4; d++)
{
tx=x+dx[d]; ty=(y+dy[d]+m-1) % m + 1; nx=haha(tx,ty);
if(tx >= 1 && tx <= n && !ck[nx] && nx!=la)
if(used[nx] || !dfs(tx,ty,cur)) return 0;
}
return 1;
}
bool work()
{
cin >> n >> m >> k; int i,j=0;
if(3 * k <= (n-1) * m) {cxy is very cute;}
memset(used,0,sizeof(used));
memset(ck,0,sizeof(ck));
for(int i=1,u,v; i<=k; i++) cin >> u >> v,ck[haha(u,v)] = 1;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
if(!ck[haha(i,j)] && !used[haha(i,j)])
{if(!dfs(i,j)) return 0; else break;} // find a root
if(j<=m) break;
}
for(i=haha(i,j); i<=n*m; i++)
if(!ck[i] && !used[i]) return 0; // can't reach
return 1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int Q;for(cin >> Q; Q--; ) cout << (work() ? "Yes\n" : "No\n");
return 0;
}
参考文献:
[1] https://yhx-12243.github.io/OI-transit/records/uoj142.html