\n\u3002\u3002\u626b\u63cf\u7ebf\u7684\u8fc7\u7a0b\u7c7b\u4f3c SGU 319. Kalevich Strikes Back \u3002\u3002\u3002<\/a>
\n\u3002\u3002\u548c\u90a3\u9898\u4e00\u6837\u3002\u3002\u8fd9\u9898\u4e5f\u53ef\u4ee5\u76f4\u63a5\u7528 set<int> \u7206\u3002\u3002<\/p>\n
\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e5) + 9;\r\n\r\ntypedef pair<int, PII> rec;\r\n\r\n#define h fi\r\n#define l se.fi\r\n#define r se.se\r\n\r\nset<PII> T; rec A[N];\r\nint f[N], stk[N], nn;\r\nint n, t;\r\n\r\nint overlap(int a, int b){\r\n return min(A[a].r, A[b].r) - max(A[a].l, A[b].l);\r\n}\r\n\r\nbool stem(int a, int b, int c){\r\n return A[a].h > A[b].h && A[b].h > A[c].h && overlap(a, c) && overlap(a, b) && overlap(b, c);\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n RD(n, t); REP(i, n) RD(A[i].h), RDD(A[i].l, A[i].r);\r\n A[n++] = MP(0, MP(-INF, INF)), A[n++] = MP(t, MP(-INF, INF));\r\n\r\n#undef h\r\n#undef l\r\n#undef r\r\n#define h A[i].fi\r\n#define l A[i].se.fi\r\n#define r A[i].se.se\r\n\r\n\r\n T.insert(MP(-INF, 0)), T.insert(MP(INF, 0));\r\n\r\n sort(A, A+n), f[0] = 2*INF; FOR(i, 1, n){\r\n set<PII>::iterator ll = T.lower_bound(MP(l, INF)), rr;\r\n for (rr=--ll,nn=0;rr->fi<r;++rr) stk[++nn]=rr->se;\r\n if(ll->fi!=l) ++ll; stk[nn+1]=0;\r\n\r\n T.erase(ll, rr), T.insert(MP(l, i));\r\n if (rr->fi != r) T.insert(MP(r, stk[nn]));\r\n\r\n \/\/ECH(it, T) cout << it->fi << ", "; cout << endl;\r\n\r\n REP_1(ii, nn){\r\n if (stem(i, stk[ii-1], stk[ii]) || stem(i, stk[ii+1], stk[ii])) continue;\r\n checkMax(f[i], min(f[stk[ii]], overlap(i, stk[ii])));\r\n }\r\n }\r\n OT(f[n-1]);\r\n}\r\n<\/pre>\n\u5b8c\u6574\u4ee3\u7801\u3002\u3002\uff09<\/a><\/p>\nProblem E. Prime Matrix<\/h2>\nBrief description: <\/h3>\nIn this problem we have an n\u2009\u00d7\u2009m rectange. Each unit midpoint is connected with a segment to some other midpoint not on the same side of the rectangle. We can change the order of the columns and rows, but the segments must remain attached to their midpoints. We should find such a rearrangement that no two segments intersect, or tell that there is no solution.<\/p><\/blockquote>\n
\u3002\u3002\u89e3\u9501\u6e38\u620f\u3002\u3002\u7ed9\u5b9a\u4e00\u4e2a\u65b9\u9635\u3002\u3002\u7136\u540e\u4e0a\u4e0b\u5de6\u53f3\u6bcf\u6761\u8fb9\u7684\u4e2d\u70b9\u90fd\u548c\u4e00\u4e2a\u4e0d\u5728\u540c\u4e00\u8fb9\u7684\u4e2d\u70b9\u76f8\u8fde\u3002\u3002
\n\u8981\u6c42\u7ed9\u4e00\u7ec4\u884c\u548c\u5217\u7684\u6392\u5217\u3002\u3002\u3002\u4f7f\u5f97\u91cd\u6392\u540e\u3002\u3002\u65b0\u7684\u56fe\u4e2d\u3002\u3002\u4e0d\u5b58\u5728\u4ea4\u70b9\u3002
\n\u3002\u4efb\u610f\u7ed9\u51fa\u4e00\u79cd\u5408\u6cd5\u65b9\u6848\u6216\u5224\u65ad\u65e0\u89e3\u3002\u3002<\/p>\n
Tags: <\/h3>\n
\u6076\u6a21\u62df\u3001\u7f6e\u6362\u5faa\u73af\u8282\u3001\u5faa\u73af\u540c\u6784\u3001\u5b57\u7b26\u4e32\u6700\u5c0f\u8868\u793a<\/p>\n
Analysis: <\/h3>\nThere are overall 6 types of segments that connect the sides:<\/p>\n
\n- left-top;<\/li>\n
- top-right;<\/li>\n
- right-bottom;<\/li>\n
- bottom-left;<\/li>\n
- left-right;<\/li>\n
- top-bottom;<\/li>\n<\/ul>\n
If there are both left-right and top-bottom segments, there is no solution. Otherwise there remain only 5 types of segments. Without loss of generality suppose there are no left-right segments. Let\u2019s take a closer look at what should the end picture of the rectangle be:<\/p><\/blockquote>\n
![](\"http:\/\/oi45.tinypic.com\/2dgqbg4.jpg\")
<\/p>\n
All left-top segments should be at the left top corner connecting positions (L,i) and (T,i), otherwise they surely would cross some other segment. Similarly must be positioned top-right, right-bottom, bottom-left segments. Finally, all top-bottom segments should be parallel. We also observe that the number of left-top segments must be equal to the number of right-bottom segments and the number of top-right segments should be equal to the number of bottom-right segments. Thus the important observation: the picture of the end arrangement is unique and can be determined from the input simply by counting the number of segments of each type.<\/p><\/blockquote>\n
\u3002\u3002\u3002\u4ece\u4ee5\u4e0a\u4e3b\u8981\u662f\u5728\u8bf4\u3002\u3002\u5982\u679c\u53ef\u4ee5\u89e3\u9501\u7684\u8bdd\u3002\u3002\u89e3\u9501\u540e\u7684\u56fe\u5f62\u662f\u56fa\u5b9a\u7684\u3002\u3002\u3002<\/p>\n
Next we define a cycle to be the sequence of segments, where the second midpoint of some segment in the cycle is equal to the first midpoint in the next segment in the cycle. In the given example there are two such cycles (but the direction of each cycle actually matters):<\/p><\/blockquote>\n
![](\"http:\/\/oi50.tinypic.com\/2qi73gj.jpg\")
<\/p>\n
Then we observe that the set of the cycles does not change with any permutation by the definition of the cycle. We can make a sketch of the solution: we should find the cycle sets in the given arrangement and in the end arrangement, and compare them for equality.<\/p>\n
At this point we actually find all the cycles in both arrangements. There are only two types of cycles:<\/p>\n
\n- (left-top) (top-right) (right-bottom) (bottom-left);<\/li>\n
- other cycles.<\/li>\n<\/ol>\n
We can easily check whether the sets of first type cycles match, since the length of such cycles is 4. If they match, we rearrange the columns and rows involved to match the end arrangement.
\nHow to compare the remaining cycles. Consider a following example:\n<\/p><\/blockquote>\n
![\"2e0v5gx](\"https:\/\/www.shuizilong.com\/house\/wp-content\/uploads\/2013\/02\/2e0v5gx-1.jpg\")
<\/a><\/p>\nLet the difference in the number of left-top and left-bottom segments be i, and this number plus the number of top-bottom segments s. If we enumerate the midpoints as in the figure, we can see that each top midpoint i is connected to the bottom midpoint (i+a)%b (top-right segments continue as corresponding left-bottom segments). Thus we can describe it as a permutation<\/p><\/blockquote>\n
\\[\\left(\\begin{array}{ccc} 0 & 1 & \\ldots & b-1 \\\\0+a & 1+a & \\ldots & (b-1)+a \\end{array} \\right)\\]<\/p>\n
\uff08\u3002\u3002\u3002\u5b98\u65b9\u9898\u89e3<\/a>\u8fd9\u91cc\u7684\u8bb0\u53f7\u6709\u70b9\u4e71\u3002\u3002\u4e0a\u56fe\u6211\u91cd\u65b0\u6807\u8bb0\u8fc7\u3002\uff09
\n\u3002\u3002\u81f3\u6b64\u5168\u90e8\u90fd\u5728\u96c6\u4e2d\u5206\u6790 cycle \u2014\u2014 \u8fd9\u4e2a rearrange \u8fc7\u7a0b\u7684\u4e0d\u53d8\u91cf\u3002\u3002\u3002\u8fd9\u90e8\u5206\u4e5f\u662f\u8fd9\u4e2a\u9898\u6700\u56f0\u96be\u7684\u5730\u65b9\u3002\uff08\u6211\u8ba4\u4e3a\u3002\u3002
\n\u3002\u3002\u4e00\u5171\u53ea\u6709\u4e24\u7c7b cycle\u3002\u3002 \u7b2c\u4e00\u7c7b cycle \u51fa\u73b0\u5728\u56db\u4e2a\u89d2\u3002\u3002\u957f\u5ea6\u56fa\u5b9a\u4e3a\u3002\u3002\u3002 \u91cd\u6392\u4e4b\u540e\u8ddd\u79bb\u6bcf\u4e2a\u89d2\u7684\u4f4d\u79fb\u4e5f\u53ef\u4ee5\u56fa\u5b9a\u3002\u3002
\n\u3002\u3002\u7b2c\u4e8c\u7c7b cycle \u5219\u5c06\u4f1a\u5f62\u6210\u4e0a\u9762\u8fd9\u4e2a\u7f6e\u6362\u7684\u6240\u6709\u5faa\u73af\u8282\u3002\u3002\u3002<\/p>\nOur cycles correspond to the cycles in this permutation, with top-right segment continuation to left-bottom segment corresponding to the case where permutation cycle element decreases. It is known that the number of such permutations is \\(gcd(a, b)\\( and their length is \\(b\/gcd(a, b)\\(. So all these cycles have the same length. Denote the remaining segment types as some letters (in picture A, B, C). Then not only the length, but the strings describing the cycles are also the same, but can be shifted cyclically (here the direction of the cycles also is important). Besides, we know this string from the correct arrangement cycle. Thus we need to compare all the remaining given arrangement cycle strings to this string, considering cyclic shifts as invariant transformations. For each string this can be done in linear time, for example, using the Knuth-Morris-Pratt algorithm. When we find a cyclical shift for each cycle, we can position its relevant columns and rows according to the end arrangement.<\/p><\/blockquote>\n
\u3002\u3002\u3002<\/p>\n
\u3002\u3002\u7b97\u6cd5\u7684\u6838\u5fc3\u5c31\u662f\u5904\u7406\u51fa\u8fd9\u4e24\u7c7b\u5faa\u73af\u8282\u3002\u3002\u5224\u65ad\u662f\u5426\u5faa\u73af\u540c\u6784\u5373\u53ef\u3002\u3002\uff08\u3002\u3002\u3002\u6ce8\u610f\u8fd8\u8981\u679a\u4e3e\u4e00\u4e0b 2 \u4e2a\u65b9\u5411\u3002\u3002\u3002<\/p>\n
\r\nbool solve() {\r\n REP(i, n) if(!vis[i]){\r\n VI cyc; dfs(i, link, cyc);\r\n if (iscyc1(cyc)) cyc1.PB(cyc);\r\n else cyc2.PB(cyc);\r\n }\r\n return gao1(), gao2();\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n REP_C(i, n = RD(r) + RD(c)){\r\n char s1, s2; RC(s1, s2); int x1 = id(s1, RD()-1), x2 = id(s2, RD()-1);\r\n link[x1] = x2, link[x2] = x1;\r\n }\r\n\r\n if (!solve()) puts("No solution");\r\n else {\r\n REP(i, r) OT(ans_r[i]+1); puts("");\r\n REP(i, c) OT(ans_c[i]+1); puts("");\r\n }\r\n}\r\n<\/pre>\n\u3002\u4e00\u8f6e dfs \u4e4b\u540e\u3002\u3002\u5c31\u53ef\u4ee5\u5f97\u5230\u4e24\u7ec4\u5faa\u73af\u8282\u3002\u3002\u7136\u540e\u5148\u53bb\u5904\u7b2c\u4e00\u7c7b\u5faa\u73af\u8282\u4ea7\u751f\u7684\u89d2\u843d\u3002\u3002\u7136\u540e\u5224\u65ad\u7b2c\u4e8c\u7c7b\u5faa\u73af\u7684\u5408\u6cd5\u6027\u5373\u53ef\u3002\u3002\u3002
\n\u3002\u3002\u5efa\u7acb\u7f16\u53f7\u7cfb\u7edf\u3002\u3002\u9700\u8981\u4e00\u7ec4\u4e92\u9006\u51fd\u6570\u3002\u3002\u3002
\n\u3002pair <==> int<\/p>\n\r\ninline int id(char c, int x) { \/\/ \u7f16\u53f7\r\n if (c=='L') return x;\r\n if (c=='T') return x + r;\r\n if (c=='R') return x + n;\r\n return x + n + r;\r\n}\r\n\r\ninline pair<char, int> di(int x) { \/\/ \u9006\u7f16\u53f7\u3002\u3002\r\n return x < n ? x < r ? MP('L', x) : MP('T', x-r) : x < n + r ? MP('R', x-n) : MP('B', x-n-r);\r\n}\r\n<\/pre>\n\r\n 0 1 2 3 4 \r\n0 0\r\n1 1\r\n2 2\r\n0 1 2 3 4\r\n<\/pre>\n\r\ninline int cp(int x) { \/\/ \u5bf9\u9762\r\n return x < n ? x + n : x - n;\r\n}\r\n<\/pre>\n\u3002\u3002\u8fd9\u6837\u7f16\u53f7\u7684\u8bdd\u5bf9\u9762\u4e5f\u4f1a\u5f88\u5bb9\u6613\u6c42\u3002\u3002<\/p>\n
\r\nvoid gao1(){\r\n REP(i, SZ(cyc1)){\r\n const VI& cyc = cyc1[i];\r\n if (iscyc1(cyc) == 1){\r\n ans_r[i]=di(cyc[0]).se, ans_r[r-1-i]=di(cyc[3]).se;\r\n ans_c[i]=di(cyc[1]).se, ans_c[c-1-i]=di(cyc[5]).se;\r\n }else{\r\n ans_r[r-1-i]=di(cyc[0]).se, ans_r[i]=di(cyc[3]).se;\r\n ans_c[i]=di(cyc[1]).se, ans_c[c-1-i]=di(cyc[5]).se;\r\n }\r\n usd[id('L', i)] = usd[id('L', r-1-i)] = 1;\r\n usd[id('R', i)] = usd[id('R', r-1-i)] = 1;\r\n usd[id('T', i)] = usd[id('T', c-1-i)] = 1;\r\n usd[id('B', i)] = usd[id('B', c-1-i)] = 1;\r\n }\r\n}\r\n<\/pre>\n\u3002\u3002\u7b2c\u4e00\u7c7b\u5faa\u73af\u8282\u53ef\u4ee5\u4efb\u610f\u6253\u4e71\u987a\u5e8f\u3002\u3002\u3002\u4e3b\u8981\u7684\u76ee\u7684\u662f\u7528 usd \u8bb0\u5f55\u5728\u8fd9\u4e2a\u9636\u6bb5\u6316\u53bb\u4e86\u54ea\u4e9b\u70b9\u3002\u3002<\/p>\n
\r\n\r\nvoid gen_dir(){\r\n\r\n VI a1, a2;\r\n\r\n DWN(i, r, 0) if(!usd[i]) a1.PB(i);\r\n REP(i, c) if(!usd[r+i]) a1.PB(r+i);\r\n REP(i, r) if(!usd[n+i]) a1.PB(n+i);\r\n DWN(i, c, 0) if(!usd[n+r+i]) a1.PB(n+r+i);\r\n\r\n REP(i, r) if(!usd[i]) a2.PB(i);\r\n REP(i, c) if(!usd[n+r+i]) a2.PB(n+r+i);\r\n DWN(i, r, 0) if(!usd[n+i]) a2.PB(n+i);\r\n DWN(i, c, 0) if(!usd[r+i]) a2.PB(r+i);\r\n\r\n REP(i, SZ(a1)) dir1[a1[i]] = a1[SZ(a1)-i-1];\r\n REP(i, SZ(a2)) dir2[a2[i]] = a2[SZ(a2)-i-1];\r\n}\r\n\r\nbool gao2(int *dir) {\r\n\r\n CPY(vis, usd); VVI target, start;\r\n\r\n REP(o, SZ(cyc2)){\r\n VI &arr = cyc2[o];\r\n dump(arr, tmp); shift(arr, lex_smallest_head(tmp, SZ(arr)));\r\n start.PB(arr);\r\n }\r\n\r\n REP(i, n) if(!vis[i]){\r\n VI arr; dfs(i, dir, arr);\r\n dump(arr, tmp), shift(arr, lex_smallest_head(tmp, SZ(arr)));\r\n target.PB(arr);\r\n }\r\n\r\n#define n SZ(start)\r\n#define m SZ(start[i])\r\n\r\n if (n != SZ(target)) return 0;\r\n SRT(start), SRT(target); REP(i, n) if(m != SZ(target[i])) return 0;\r\n\r\n REP_2(i, j, n, m){\r\n int s = start[i][j], t = target[i][j]; pair<char, int> ss = di(s), tt = di(t); if (ss.fi != tt.fi) return 0;\r\n tt.se[ss.fi == 'L' || ss.fi == 'R' ? ans_r : ans_c] = ss.se;\r\n }\r\n\r\n#undef n\r\n#undef m\r\n\r\n return 1;\r\n}\r\nbool gao2(){\r\n return gen_dir(), gao2(dir1)||gao2(dir2);\r\n}\r\n<\/pre>\n\u3002\u3002\u3002\u5904\u7406\u7b2c\u4e8c\u7c7b\u5faa\u73af\u8282\u3002\u3002\u5148\u8981\u7528 usd \u6570\u7ec4\u751f\u6210\u4e24\u7ec4\u65b9\u5411\u5e8f\u3002\u3002\uff08\u3002\u3002\u6ce8\u610f\u4e4b\u524d\u7684\u7f16\u53f7\u7cfb\u7edf\u3002\u3002\u8fd9\u4e00\u6b65\u5f88\u5bb9\u6613\u5199\u9519\u3002\u3002
\n\u3002\u3002\u4e4b\u540e\u5224\u65ad\u662f\u5426\u6709\u4e00\u4e2a\u5408\u6cd5\u5373\u53ef\u3002\u3002\u3002\u5224\u65ad\u5408\u6cd5\u7684\u8fc7\u7a0b\u4e3b\u8981\u662f\u5b57\u7b26\u4e32\u7684\u6700\u5c0f\u8868\u793a\u3002\u3002\u7136\u540e\u6328\u4e2a\u6bd4\u8f83\u3002\u3002
\n\u3002\u3002\u3002kelvin<\/font> \u7684\u4ee3\u7801\u3002\u3002<\/a>\u8fd9\u4e00\u6b65\u8fd8\u5148\u5224\u65ad\u4e86\u4e00\u4e0b\u5b57\u7b26\u4e32 hash \u3002\u3002\u4f46\u5b9e\u9645\u610f\u4e49\u4f3c\u4e4e\u4e0d\u5927\u3002\u3002( \u2299 o \u2299 )\u3002\u3002\u3002\uff09\u3002\u3002<\/p>\n\u5b8c\u6574\u4ee3\u7801\u3002\u3002\uff09<\/a><\/p>\nExternal link: <\/h3>\n
Codeforces Round #165 (Div. 1)<\/a>
\nCodeforces Round #165 Tutorial<\/a>
\nhttp:\/\/roosephu.github.com\/2013\/02\/01\/CF-165\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[18],"tags":[114,111,112,75,90,113],"class_list":["post-681","post","type-post","status-publish","format-standard","hentry","category-codeforces","tag-114","tag-111","tag-112","tag-75","tag-90","tag-113"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-aZ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/681","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=681"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/681\/revisions"}],"predecessor-version":[{"id":682,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/681\/revisions\/682"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=681"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=681"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=681"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}