随记 – THUPC 2022 初赛 J – 画图 7KB的大模拟……?
考虑合并若干重叠线段。使其有序化后考虑每两个线段的交,如果其为空则新建一条独立线段,反之合并。
最后应当恰好有条水平线段,条垂直线段,否则依题意不可能拼凑出“”图形。
DFS搜索组成每个字母的所有可能线段组合。需要合理剪枝,亦可以使用二进制状态压缩减小常数。时间复杂度理论上限为,实际远远达不到。
赛时1A(实际上因为无主函数返回值RE
了两次)代码:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
#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; }