考虑合并若干重叠线段。使其有序化后考虑每两个线段的交，如果其为空则新建一条独立线段，反之合并。
最后应当恰好有$7$条水平线段，$8$条垂直线段，否则依题意不可能拼凑出“$\textbf{THUPC}$”图形。
DFS搜索组成每个字母的所有可能线段组合。需要合理剪枝，亦可以使用二进制状态压缩减小常数。时间复杂度理论上限为$\mathrm{O}(7^5\times 8^5)$，实际远远达不到。
赛时1A（实际上因为无主函数返回值RE了两次）$7\text{KB}$代码：
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline bool read (T &x) {
x = 0; int f = 1; char c = getchar ();
for (; c != EOF && !isdigit (c); c = getchar ())
if (c == '-') f = -1;
if (c == EOF) return 0;
for (; c != EOF && isdigit (c); c = getchar ())
x = (x<<1) + (x<<3) + (c^48);
x *= f; return 1;
}
template <typename T, typename... Targs>
inline bool read (T &x, Targs&... args) {
return read (x) && read (args...); }
template <typename T> void print (T x) {
if (x < 0) putchar ('-'), x = -x;
if (x > 9) print (x / 10);
putchar ('0' + x % 10);
}
template <typename T, typename... Targs>
inline void print (T x, Targs... args) {
print (x), putchar (' '), print (args...); }
#define reint register int
#define inl inline
#define newl putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
constexpr int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, opt, l, r, y, u, v, x;
int gcnt, pcnt, gscnt, pscnt; bool flag;
struct segment {
int st, ed, con;
bool operator < (const segment& b) const {
return con != b.con ? con < b.con :
(st != b.st ? st < b.st : ed < b.ed);
}
} g[N], p[N], gseg[N], pseg[N];
inl bool upd_seg (segment &_g, segment &_t) {
if (_g.con != _t.con) return 0;
if (_t.st >= _g.st && _t.st <= _g.ed) {
_g.ed = max (_g.ed, _t.ed);
return 1;
} else if (_t.ed >= _g.st && _t.ed <= _g.ed) {
_g.st = min (_g.st, _t.st);
return 1;
}
return 0;
}
#define lowbit(x) (x & -x)
int glst[5][10], glcnt[5], saigo[18],
plst[5][10], plcnt[5], log2s[1<<9];
inl void _tenkai (int msk, int lst[], int &lcnt) {
lcnt = 0; int tmp;
while (msk)
tmp = lowbit(msk),
lst[++lcnt] = log2s[tmp],
msk -= tmp;
}
#define tenkai(i) (_tenkai (gmsk, glst[i], glcnt[i]),\
_tenkai (pmsk, plst[i], plcnt[i]))
inl bool diff (int x, int y) {
if (x <= 2) return y > 2;
else if (x <= 5)
return !(y > 2 && y <= 5);
else if (x <= 8)
return !(y > 5 && y <= 8);
else if (x <= 12)
return !(y > 8 && y <= 12);
else return y <= 12;
}
inl bool dir (int x) {
switch (x) {
case 1: case 4: case 7:
case 10: case 11: case 14: case 15:
return 1;
default: return 0;
}
}
inl bool inter (int i, int j) {
int o, q;
o = saigo[i], q = saigo[j];
if (!dir (i)) swap (o, q);
if (gseg[o].ed < pseg[q].con) return 0;
if (gseg[o].st > pseg[q].con) return 0;
if (gseg[o].con > pseg[q].ed) return 0;
if (gseg[o].con < pseg[q].st) return 0;
return 1;
}
inl void check () {
for (int i = 1; i <= 15; ++i)
for (int j = i + 1; j <= 15; ++j) {
if (!diff (i, j)) continue;
if (dir (i) == dir (j)) continue;
if (inter (i, j)) return;
}
flag = 1;
}
inl void C (int gmsk, int pmsk) {
if (flag) return;
tenkai (4); // remain: 2, 1
segment *o = &pseg[plst[4][1]], *q, *r;
saigo[13] = plst[4][1];
for (int j = 1; j <= 2; ++j) {
int k = 3 - j;
q = &gseg[glst[4][j]],
r = &gseg[glst[4][k]];
if (!(o->con == q->st && q->st == r->st
&& q->ed == r->ed && o->ed == q->con
&& o->st == r->con)) continue;
saigo[14] = glst[4][j],
saigo[15] = glst[4][k];
check ();
}
}
inl void P (int gmsk, int pmsk) {
if (flag) return;
tenkai (3); // remain: 4, 3
segment *o, *q, *r, *t;
int *_plst = plst[3], *_glst = glst[3];
for (int i = 1; i <= 3; ++i) {
o = &pseg[_plst[i]];
for (int l = 1; l <= 3; ++l) {
if (l == i) continue;
t = &pseg[_plst[l]];
for (int j = 1; j <= 4; ++j) {
q = &gseg[_glst[j]];
for (int k = 1; k <= 4; ++k) {
if (j == k) continue;
r = &gseg[_glst[k]];
if (!(o->st < r->con && r->con < o->ed
&& o->ed == q->con && o->con == r->st && r->st == q->st
&& q->ed == r->ed && q->con == t->ed
&& t->st == r->con && t->con == q->ed)) continue;
saigo[9] = _plst[i],
saigo[10] = _glst[j],
saigo[11] = _glst[k],
saigo[12] = _plst[l];
C (gmsk ^ (1<<_glst[j] - 1) ^ (1<<_glst[k] - 1),
pmsk ^ (1<<_plst[i] - 1) ^ (1<<_plst[l] - 1));
}
}
}
}
}
inl void U (int gmsk, int pmsk) {
if (flag) return;
tenkai (2); // remain: 5, 5
segment *o, *q, *r;
int *_plst = plst[2], *_glst = glst[2];
for (int i = 1; i <= 5; ++i) {
o = &pseg[_plst[i]];
for (int k = 1; k <= 5; ++k) {
if (i == k) continue;
r = &pseg[_plst[k]];
for (int j = 1; j <= 5; ++j) {
q = &gseg[_glst[j]];
if (!(o->st == r->st && o->ed == r->ed
&& q->con == o->st && q->st == o->con
&& q->ed == r->con)) continue;
saigo[6] = _plst[i],
saigo[7] = _glst[j],
saigo[8] = _plst[k];
P (gmsk ^ (1<<_glst[j] - 1),
pmsk ^ (1<<_plst[i] - 1) ^ (1<<_plst[k] - 1));
}
}
}
}
inl void H (int gmsk, int pmsk) {
if (flag) return;
tenkai (1); // remain: 6, 7
segment *o, *q, *r;
int *_plst = plst[1], *_glst = glst[1];
for (int i = 1; i <= 7; ++i) {
o = &pseg[_plst[i]];
for (int k = 1; k <= 7; ++k) {
if (k == i) continue;
r = &pseg[_plst[k]];
for (int j = 1; j <= 6; ++j) {
q = &gseg[_glst[j]];
if (!(o->st == r->st && o->ed == r->ed
&& q->con > o->st && q->con < o->ed
&& q->st == o->con && q->ed == r->con)) continue;
saigo[3] = _plst[i],
saigo[4] = _glst[j],
saigo[5] = _plst[k];
U (gmsk ^ (1<<_glst[j] - 1),
pmsk ^ (1<<_plst[i] - 1) ^ (1<<_plst[k] - 1));
}
}
}
}
inl void T (int gmsk, int pmsk) {
if (flag) return;
tenkai (0); // remain: 7, 8
int o, q;
for (int i = 1; i <= 7; ++i)
for (int j = 1; j <= 8; ++j) {
o = glst[0][i], q = plst[0][j];
if (!((gseg[o].con == pseg[q].ed) && (gseg[o].ed > pseg[q].con
&& gseg[o].st < pseg[q].con))) continue;
saigo[1] = o,
saigo[2] = q;
H (gmsk ^ (1<<o - 1), pmsk ^ (1<<q - 1));
}
}
int main () {
/* THUPC 2022 初赛 J - 画图 thupc341 */
read (n);
for (int i = 1; i <= n; ++i) {
read (opt);
if (opt == 0) {
read (l, r, y);
g[++gcnt] = { l, r, y };
} else {
read (u, v, x);
p[++pcnt] = { u, v, x };
}
}
sort (g + 1, g + gcnt + 1);
sort (p + 1, p + pcnt + 1);
gseg[0].con = pseg[0].con = -INF;
for (int i = 1; i <= gcnt; ++i)
if (upd_seg (gseg[gscnt], g[i]));
else gseg[++gscnt] = g[i];
for (int i = 1; i <= pcnt; ++i)
if (upd_seg (pseg[pscnt], p[i]));
else pseg[++pscnt] = p[i];
if (gscnt != 7 || pscnt != 8)
return puts ("No"), 0;
for (int i = 0; i < 8; ++i)
log2s[1<<i] = i + 1;
T (0b1111111, 0b11111111);
puts (flag ? "Yes" : "No");
return 0;
}
发表回复