AtCoder Regular Contest 076(C/D)

C - Reconciled?

首先容易发现给定的2个数,如果要没有相同的动物相邻,那么肯定$n$,$m$的差要$\leq 2$,所以特判此情况;此外考虑插空法,那么答案就是$n! \times C(m-n+1,2) \times m!$。

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
const int mo=1e9+7;
typedef long long ll;
ll n,m;
ll getstep(ll n)
{
ll res=1;
for(ll i=1;i<=n;i++) res=(res*i)%mo;
return res;
}
ll geta(int n,int m)
{
ll res=1;
for(ll i=n-m+1;i<=n;i++) res=(res*i)%mo;
return res;
}
int main()
{
scanf("%lld%lld",&n,&m);
if(abs(n-m)>=2) printf("0\n");
else{
if(m<n) swap(n,m);
if(m-n==1)
printf("%lld\n",((getstep(n)%mo)*(getstep(m)%mo))%mo);
else
printf("%lld\n",((getstep(n)%mo)*(getstep(m)%mo)%mo)*2%mo);
}
return 0;
}

D - Built?

考试的时候因为一些奇怪的记忆写错了生成树,结果超时得很惨QWQ,然后考完试才改对…(我太菜了QWQ)

考虑这个图,由于加的全为无向边,所以这图最终应该是一个生成树。我们考虑加边,由于生成树时需要不断取出最小得边,并且恰好连点数-1条这么多的样子,由于边不可能在$n\leq 100000$的情况下全部存下,所以我们考虑只找到最小的一些边。

两点间距离$d=min(|a−c|,|b−d|)$,所以我们先按照$x$轴递增次序排序,相邻点加边,可以得到一些最小的、基于$x$坐标差的边;再按$y$排序的话,就可以得到一些最小的、基于$y$坐标差的边。最小的边一定是这些,而这些边的条数肯定大于$n-1$,所以可以生成树。

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
const int maxn=100000+5;
typedef long long ll;
struct point{int x,y,id;};
point p[maxn];
int n;
struct edge{int from,to,cost;};
vector<edge> pool;
int myabs(int x){return x<0?-x:x;}
bool cmppp(edge a,edge b){
return a.cost<b.cost;
}
bool cmp1(point a,point b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(point a,point b){
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
struct ge{int to,cost;};
struct cmpp{
bool operator()(edge a,edge b){
return a.cost>b.cost;
}
};
vector<ge> g[maxn];
int f[maxn],rnk[maxn];
int getf(int x){
return f[x]==x?f[x]:f[x]=getf(f[x]);
}
void merge(int u,int v)
{
int fu=getf(u),fv=getf(v);
if(fu==fv) return;
else{
if(rnk[fu]>rnk[fv]){
rnk[fu]+=rnk[fv];rnk[fv]=0;
f[fv]=fu;
}else{
rnk[fv]+=rnk[fu];rnk[fu]=0;
f[fu]=fv;
}
}
}
vector<edge> egs;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {p[i].id=i;scanf("%d%d",&p[i].x,&p[i].y);}
sort(p+1,p+1+n,cmp1);
for(int i=1;i<n;i++){
egs.push_back((edge){p[i].id,p[i+1].id,min(myabs(p[i].x-p[i+1].x),myabs(p[i].y-p[i+1].y))});
}
sort(p+1,p+1+n,cmp2);
for(int i=1;i<n;i++){
egs.push_back((edge){p[i].id,p[i+1].id,min(myabs(p[i].x-p[i+1].x),myabs(p[i].y-p[i+1].y))});
}
bool has=true;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++) rnk[i]=1;
ll ans=0;
sort(egs.begin(),egs.end(),cmppp);
int lev=n-1;
for(int i=0;i<egs.size();i++)
{
edge now=egs[i];
if(getf(now.from)!=getf(now.to))
{lev--;merge(now.from,now.to);ans+=now.cost;}
if(lev==0) break;
}
printf("%lld\n",ans);
return 0;
}