日本人的比赛
C:如果两个数差了大于1无解，否则分类讨论
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100010, mod = 1000000007; int n, m; ll a[N]; ll power(ll x, ll t) { ll ret = 1; for(; t; t >>= 1, x = x * x % mod) if(t & 1) ret = ret * x % mod; return ret; } int main() { scanf("%d%d", &n, &m); if(n < m) swap(n, m); if(n - m != 1 && n - m != 0) { puts("0"); return 0; } a[0] = 1; for(int i = 1; i <= n + 1; ++i) a[i] = a[i - 1] * (ll)i % mod; if(n == m) printf("%lld ", 2ll * a[n] % mod * a[m] % mod); else printf("%lld ", a[n] % mod * a[m] % mod); return 0; }
D:分别按xy排序，然后分别把相邻的差放进去做最小生成树。因为如果三个点xaxbxc,xa<xb<xc,那么连xa->xb->xc肯定比xa->xc优，也就是说连相邻的肯定最优。因为这n-1条边能构成最小生成树，而且是自己维度最优的，所以只要和最小的y比较就行了，肯定会有解，而且是最优的，因为我们不可能会去用其他的边。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100010; struct edge { int u, v; ll w; edge(int u, int v, ll w) : u (u), v (v), w (w) {} }; struct data { ll x, y; int id; } a[N]; int n; int fa[N]; ll ans; vector<edge> e; bool cp(edge x, edge y) { return x.w < y.w; } bool cp1(data x, data y) { return x.x < y.x; } bool cp2(data x, data y) { return x.y < y.y; } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) fa[i] = i; for(int i = 1; i <= n; ++i) { scanf("%lld%lld", &a[i].x, &a[i].y); a[i].id = i; } sort(a + 1, a + n + 1, cp1); for(int i = 2; i <= n; ++i) e.push_back(edge(a[i].id, a[i - 1].id, a[i].x - a[i - 1].x)); sort(a + 1, a + n + 1, cp2); for(int i = 2; i <= n; ++i) e.push_back(edge(a[i].id, a[i - 1].id, a[i].y - a[i - 1].y)); sort(e.begin(), e.end(), cp); for(int i = 0; i < e.size(); ++i) { if(find(e[i].u) == find(e[i].v)) continue; ans += e[i].w; fa[find(e[i].u)] = find(e[i].v); } printf("%lld ", ans); return 0; }
E：并没有AC，不知道哪里错了。
结论：不全在边框上的整数互相之间肯定能连起来。
只要考虑的是在边框上的点，防止出现ijij的情况，于是用一个栈从顺时针加入，如果加入的点和栈顶是同一种数字，那么弹出，否则加入，最后看栈是否为空。
wa
#include<bits/stdc++.h> using namespace std; const int N = 100010; struct data { int x, y, id; }; int n, r, c, top; vector<data> v[4]; data st[N]; bool cp1(data x, data y) { return x.x < y.x; } bool cp2(data x, data y) { return x.x > y.x; } bool cp3(data x, data y) { return x.y < y.y; } bool cp4(data x, data y) { return x.y > y.y; } int main() { scanf("%d%d%d", &r, &c, &n); for(int i = 1; i <= n; ++i) { data a, b; scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y); a.id = b.id = i; if((a.x == 0 || a.x == c || a.y == 0 || a.y == r) && (b.x == 0 || b.x == c || b.y == 0 || b.y == r)) { if(a.x == 0) v[0].push_back(a); else if(a.y == r) v[1].push_back(a); else if(a.x == c) v[2].push_back(a); else if(a.y == 0) v[3].push_back(a); if(b.x == 0) v[0].push_back(b); else if(b.y == r) v[1].push_back(b); else if(b.x == c) v[2].push_back(b); else if(b.y == 0) v[3].push_back(b); } } sort(v[0].begin(), v[0].end(), cp3); sort(v[1].begin(), v[1].end(), cp1); sort(v[2].begin(), v[2].end(), cp4); sort(v[3].begin(), v[3].end(), cp2); st[0].id = 0; for(int i = 0; i < 4; ++i) for(int j = 0; j < v[i].size(); ++j) { data x = v[i][j]; // printf("x.id=%d x.x=%d x.y=%d ", x.id, x.x, x.y); if(x.id == st[top].id) --top; else st[++top] = x; } puts(top == 0 ? "YES" : "NO"); return 0; }