BZOJ 4558 方

Link

什么鬼题,做完了整个人都方了。。 正方形可以斜着!可以斜着!可以斜着! # Solution 容斥自不必说。。。 考虑“太难了”的问题,\(K=0\)怎么做? 对于每个正方形,不管它怎么斜,肯定对应着唯一一个正好套着它的、与坐标轴平行的正方形,称之为框架(Framework)。每个边长为\(len\)的框架,肯定包含着恰好\(len\)个以它为框架的正方形。所以只要枚举每种长度的框架有几个,就可以得到答案。 那么剩下的,对应着正方形上有几个被删除的点,就有四种情况。 至少删除二三四个的情况,一个\(O(n^2)\)枚举,都很好说。 只剩下经过至少一个被删除的点的情况。 \(O(n)\)地枚举必然被删除的那个点,剩下的问题就是统计有多少个正方形以这个点为一个角。 然后,由于一个正方形有唯一的框架;一个框架上每个点只是一个正方形的角。所以,以一个点为角的正方形数==经过这个点的框架数 然后问题转化成求经过一个点的、与坐标轴平行的正方形数。 可以把平面分成四个形如阴影的部分,然后把四部分答案相加,再把重合部分的减一下。 现在问题转化为 经过一个数轴上定点,并且处于一段固定长度的区间内,且有边长限制的正方形个数。 先考虑简化的版本:如果没有固定长度的限制怎么做? 显然,枚举每种长度,并且在数轴上滑一滑,可以得到总和为\(2+3+4+...+(h+1)\)(\(h\)为边长限制) 现在考虑超出数轴边界的。只考虑超出左边界的,右边界差不多。 只有边长超过\(p-1\)的才会超出数轴边界,边长为\(p\),会被截去\(1\)个。边长为\(p+1\),会被截去\(2\)个。求出有多少种边长超出了限制,就可以用求和公式计算对答案的贡献了。 # Code

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include "lucida"
typedef unsigned long long qword;
const int MAXN=2000+11,MAXL=1e6+11,P=1e8+7;
const double eps=1e-6;
double fcmp(const double &x) {
return -eps<x && x<eps?0:(x<0?-1:1);
}
using std::fill;
using std::min;
int64 Sum(int64 n) {
return (n*(n+1)/2)%P;
}
template <class T>
qword Hash(const T &x) {
return x;
}
namespace hashset {
struct Node {
qword key;
Node *pre;
Node(qword key,Node *pre):key(key),pre(pre) {}
void *operator new(size_t) {
static Node *Me=alloc(Node,MAXN);
return Me++;
}
};
template <class T,int Modu>
struct HashSet {
Node **id;
HashSet() {
id=alloc(Node*,Modu);
memset(id,0,Modu*sizeof(Node*));
}
void Insert(const T &x) {
qword hcode=Hash(x);
int bucket=hcode%Modu;
id[bucket]=new Node(hcode,id[bucket]);
}
bool Find(const T &x) {
qword hcode=Hash(x);
for(Node *p=id[hcode%Modu];p;p=p->pre) {
if(p->key==hcode) {
return 1;
}
}
return 0;
}
};
}using hashset::HashSet;
int n,m;
struct point {
int x,y;
point() {}
point(int x,int y):x(x),y(y) {}
bool inside() {
return 1<=x && x<=n && 1<=y && y<=m;
}
friend point operator +(const point &a,const point &b) {
return point(a.x+b.x,a.y+b.y);
}
friend point operator -(const point &a,const point &b) {
return point(a.x-b.x,a.y-b.y);
}
};
typedef point vector;
template <>
qword Hash<point>(const point &p) {
return ((qword)p.x-1)*(1e6+1)+p.y;
}
vector Rotate(const vector &a,const int &dir) {
return vector(-a.y*dir,a.x*dir);
}
point p[MAXN];
HashSet<point,99929> set;
int64 All() {
int64 res=0;
for(int64 i=1,ei=min(n,m);i<=ei;++i) {
(res+=i*(n-i)*(m-i))%=P;
}
return res;
}
int64 SquareCount(int64 p,int64 l,int64 h) {
chkmn(h,l-1);
int64 res=(Sum(h+1)-1),c;
res-=(c=h-p+1)>0?Sum(c):0;
res-=(c=p+h-l)>0?Sum(c):0;
return res%P;
}
int64 CoverCount(point p) {
int64 res=SquareCount(p.y,m,n-p.x)
+SquareCount(p.x,n,m-p.y)
+SquareCount(p.y,m,p.x-1)
+SquareCount(p.x,n,p.y-1)
-min(n-p.x,p.y-1)
-min(p.y-1,p.x-1)
-min(p.x-1,m-p.y)
-min(m-p.y,n-p.x);
return res%P;
}
int Check(point a,point b,int dir) {
int res=-1;point c(0,0),d(0,0);
if(dir) {
c=a+Rotate(b-a,dir),d=b+Rotate(a-b,-dir);
} else {
vector normal=Rotate(b-a,1);
double cx=(a.x+b.x)/2.0,cy=(a.y+b.y)/2.0;
double dx=normal.x/2.0,dy=normal.y/2.0;
c=point(cx-dx+0.5,cy-dy+0.5),d=point(cx+dx+0.5,cy+dy+0.5);
if(fcmp(c.x-(cx-dx)) || fcmp(c.y-(cy-dy))) {//判合法!!
c=point(0,0);
}
if(fcmp(d.x-(cx+dx)) || fcmp(d.y-(cy+dy))) {
d=point(0,0);
}
}
if(c.inside() && d.inside()) {
res++;
res+=set.Find(c);
res+=set.Find(d);
}
return res;
}
int main() {
freopen("input","r",stdin);
int K;is>>n>>m>>K;++n,++m;
for(int i=1;i<=K;++i) {
is>>p[i].x>>p[i].y;
p[i].x++,p[i].y++;
set.Insert(p[i]);
}
int64 res[5]={0,0,0,0,0};
res[0]=All();
for(int i=1;i<=K;++i) {
(res[1]+=CoverCount(p[i]))%=P;
for(int j=1;j<=K;++j) if(i!=j) {
for(int d=-1;d<=1;++d) {
int dr=Check(p[i],p[j],d);
res[2]+=dr>-1;
res[3]+=dr>0?dr:0;
res[4]+=dr==2;
}
}
}
int64 Ans=((res[0]-res[1]+res[2]/2-res[3]/6+res[4]/12)%P+P)%P;
os<<Ans<<'\n';
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利