atcoder 076

日本人的比赛

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\n", 2ll * a[n] % mod * a[m] % mod);elseprintf("%lld\n", a[n] % mod * a[m] % mod);return 0; } View Code

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\n", ans);return 0; } View Code

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\n", x.id, x.x, x.y);if(x.id == st[top].id) --top;elsest[++top] = x;}puts(top == 0 ? "YES" : "NO");return 0; } View Code

 

转载于:https://www.cnblogs.com/19992147orz/p/7076421.html

总结

以上是生活随笔为你收集整理的atcoder 076的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。