YYHSOI模拟赛题解（T6围栏问题）

题目描述

在一片草原上，有n只兔子无忧无虑地生活着。这片草原可以划分成m×m的方阵。每个方格内最多有一只兔子。

一位饲养员负责喂养这些兔子。为了方便，她需要用篱笆建造最多k座围栏，将草原上的兔子全部围起来。

围栏需要满足以下条件：

（1）必须沿着网格线建造；

（2）每座围栏是一个不与自身重叠或相交的封闭回路；

（3）各座围栏之间互相不重叠、不相交；

（4）一座围栏不能被围在另一座围栏里面。

请你帮助饲养员计算一下围栏总长度的最小值。

输入

输入文件名为fence.in

输入第1行为三个整数m，k，n。

接下来n行每行为一对正整数x，y，表示第x行第y列的方格中有一只兔子。

输出

输出文件名为fence.out

输出仅1行，为一个正整数，表示围栏总长度的最小值。

样例输入

【输入输出样例1】

fence.in

6 1 4

1 3

4 2

4 4

6 4

fence.out

样例输出

【输入输出样例2】

fence.in

6 2 4

1 3

4 2

4 4

6 4

fence.out

【数据范围】

对于10%的数据，k=1；

对于10%~30%的数据，k=2；

对于30%~60%的数据，n≤10；

对于100%的数据，1≤k≤n≤16，m≤1,000。

这道题题解表示可以用Dancing Links X做，但是我不会。

但是我们会看到这个数据范围只有16，那么我们对于每一只兔子，我们都可以暴力枚举它是自己建一个围栏，还是使用之前的围栏。当然我们还可以求证出一些非常奇妙的东西。比如说：矩形去围一定是最优的，就算你不用矩形去围，我们也可以将它化成一个周长相同，但是面积更大的矩形。这样子还可以围更多的兔子何乐而不为呢？

当我们决定要自建一个栅栏时，灰常的简单。如果我们要插入一个围栏怎么办？同样灰常的简单，我们将这个围栏拆了，加入这个点后重新建一遍围栏就行了。

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 struct node
 10 {
 11     long long X,Y;    
 12 };
 13 
 14 int N;
 15 long long L,R;
 16 long long RR[1000005];
 17 node a[1000005];
 18 long long s[1000005];
 19 long long AnsA,AnsB;
 20 
 21 void gbsort1(int l,int r)
 22 {
 23     int mid=(l+r)/2;
 24     if (l == r) return;
 25     gbsort1(l,mid);
 26     gbsort1(mid+1,r);
 27     int head1=l;
 28     int tail1=mid;
 29     int head2=mid+1;
 30     int tail2=r;
 31     int len=head1-1;
 32     while (head1 <= tail1 && head2 <= tail2)
 33     {
 34         if (a[head1].X < a[head2].X)
 35         {
 36             RR[++len]=a[head1].X;
 37             head1++;
 38         }
 39         else if (a[head1].X >= a[head2].X)
 40         {
 41             RR[++len]=a[head2].X;
 42             head2++;
 43             AnsA+=(tail1-head1+1);
 44         }
 45     }
 46     while (head1 <= tail1)
 47     {
 48         RR[++len]=a[head1].X;
 49         head1++;
 50     }
 51     while (head2 <= tail2)
 52     {
 53         RR[++len]=a[head2].X;
 54         head2++;
 55     }
 56     for (int i=l; i<=r; i++)
 57     {
 58         a[i].X=RR[i];
 59     }
 60 }
 61 
 62 void gbsort2(int l,int r)
 63 {
 64     int mid=(l+r)/2;
 65     if (l == r) return;
 66     gbsort2(l,mid);
 67     gbsort2(mid+1,r);
 68     int head1=l;
 69     int tail1=mid;
 70     int head2=mid+1;
 71     int tail2=r;
 72     int len=head1-1;
 73     while (head1 <= tail1 && head2 <= tail2)
 74     {
 75         if (a[head1].Y <= a[head2].Y)
 76         {
 77             RR[++len]=a[head1].Y;
 78             head1++;
 79         }
 80         else if (a[head1].Y > a[head2].Y)
 81         {
 82             RR[++len]=a[head2].Y;
 83             head2++;
 84             AnsB+=(tail1-head1+1);
 85         }
 86     }
 87     while (head1 <= tail1)
 88     {
 89         RR[++len]=a[head1].Y;
 90         head1++;
 91     }
 92     while (head2 <= tail2)
 93     {
 94         RR[++len]=a[head2].Y;
 95         head2++;
 96     }
 97     for (int i=l; i<=r; i++)
 98     {
 99         a[i].Y=RR[i];
100     }
101 }
102 
103 long long gcd(long long a,long long b)
104 {
105     if (b == 0) return a;
106     else return gcd(b,a % b);
107 }
108 
109 int main()
110 {
111     scanf("%d%lld%lld",&N,&L,&R);
112     for (int i=1; i<=N; i++)
113     {
114         int X;
115         scanf("%d",&X);
116         s[i]=s[i-1]+X;
117         a[i].X=L * i - s[i];
118         a[i].Y=R * i - s[i];
119     }
120     AnsA=0; AnsB=0;
121     gbsort1(0,N);
122     gbsort2(0,N);
123     //printf("%lld %lld\n",AnsA,AnsB);想· 
124     long long Tmp=(long long) N;
125     Tmp=Tmp * (Tmp + 1) / 2;
126     long long Ans=AnsA-AnsB;
127     if (Ans == Tmp)
128     {
129         printf("1\n");
130     }
131     else if (Ans == 0)
132     {
133         printf("0\n");
134     }
135     else
136     {
137         long long D=gcd(Ans,Tmp);
138         printf("%lld/%lld\n",Ans/D,Tmp/D);
139     }
140     return 0;
141 }

Show My Ugly Code