题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3962
这个玩意，貌似可以暴力？
预处理出斜着的线上的点有多少，这样在暴力转移的时候，可以做到O(1)
然后就是写代码的事情了，然而写了两个小时了，没写出来QAQ
弃疗………..
—– 2016.9.6 更新 —–
耐着性子码完了代码
为什么觉得线段求交点常数大？
为什么要作死直接分类讨论 (╯‵□′)╯︵┻━┻
#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 1000+9;
int n,m,q,sz,head[N],vout,X,Y;
int mat[N][N],f[2][N][N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}
inline void prework(){
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[0][i][j] = f[0][i-1][j-1] + mat[i][j];
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[1][i][j] = f[1][i+1][j-1] + mat[i][j];
}
inline int pro(int x1, int y1, int x2, int y2, int t) {
int ret = 0;
if (!t) {
x2--; y2--;
if (x1 < 1 || y1 < 1) ret += 0;
else if (x1 <= n && y1 <= m) ret += f[t][x1][y1];
else if (x1 > n) ret += (y1-(x1-n)<=m && y1-(x1-n)>=1)? f[t][n][y1-(x1-n)]: 0;
else ret += (1<=x1-(y1-m) && x1-(y1-m)<=n)? f[t][x1-(y1-m)][m]: 0;
if (x2 < 1 || y2 < 1) ret -= 0;
else if (x2 <= n && y2 <= m) ret -= f[t][x2][y2];
else if (x2 > n) ret -= (y2-(x2-n)<=m && y2-(x2-n)>=1)? f[t][n][y2-(x2-n)]: 0;
else ret -= (1<=x2-(y2-m) && x2-(y2-m)<=n)? f[t][m][2-(y2-m)]: 0;
} else {
x2++; y2--;
if (x1 > n || y1 < 1) ret += 0;
else if (x1 >= 1 && y1 <= m) ret += f[t][x1][y1];
else if (x1 < 1) ret += (y1-(1-x1)>=1 && y1-(1-x1)<=m)? f[t][1][y1-(1-x1)]: 0;
else ret += (x1+(y1-m)>=1 && x1+(y1-m)<=n)? f[t][x1 + (y1 - m)][m]: 0;
if (x2 > n || y2 < 1) ret -= 0;
else if (x2 >= 1 && y2 <= m) ret -= f[t][x2][y2];
else if (x2 < 1) ret -= (y2-(1-x2)>=1 && y2-(1-x2)<=m)? f[t][1][y2 -(1-x2)]: 0;
else ret -= (1<=x2+(y2-m) && x2+(y2-m)<=n)? f[t][x2+(y2-m)][m]: 0;
} return ret;
}
inline void solve(int lim){
vout = 0; X = 1; Y = 1;
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++)
if (i + j > lim + 2) break;
else vout += mat[i][j];
head[1] = vout; int tmp = vout;
for (int j=1;j<=m;j++) {
for (int i=1;i<n;i++) {
tmp += pro(i+lim+1,j,i+1,j-lim,0); // ¨J
tmp -= pro(i,j+lim,i-lim,j,0); // ¨L
tmp += pro(i+1,j+lim,i+lim+1,j,1); // ¨K
tmp -= pro(i-lim,j,i,j-lim,1); // ¨I
if (i + lim + 1 <= n) tmp -= mat[i+lim+1][j];
if (i - lim >= 1) tmp += mat[i-lim][j];
if (tmp > vout) vout = tmp, X = i+1, Y = j;
}
if (j < m) {
tmp = head[j];
tmp += pro(1,j+lim+1,1+lim,j+1,1);//¨K
tmp += pro(1,j+lim+1,1-lim,j+1,0);//¨L
tmp -= pro(1+lim,j,1,j-lim,0);//¨J
tmp -= pro(1-lim,j,1,j-lim,1);//¨I
if (j + lim + 1 <= m) tmp -= mat[1][j+lim+1];
if (j - lim >= 1) tmp += mat[1][j-lim];
if (tmp > vout) vout = tmp, X = 1, Y = j+1;
head[j+1] = tmp;
}
}
}
inline void init(int w){
memset(f,0,sizeof(f));
memset(mat,0,sizeof(mat));
printf("Case %d:\n",w);
}
int main(){
for (int T=1;scanf("%d%d",&n,&m) && n && m;T++) {
init(T); sz = read(); q = read();
for (int i=1,x,y;i<=sz;i++) x = read(), y = read(), mat[x][y]++;
prework();
for (int k=1;k<=q;k++) {
solve(min(m+n,read()));
printf("%d (%d,%d)\n",vout,X,Y);
}
}
return 0;
}
然而DZY告诉我们，这货可以变成正方形？
参见：http://dzy493941464.is-programmer.com/posts/86498.html
仔细想了一想：我们可以通过将整个图旋转45°，然后重新编号，然后就变成了正方形？
然后就是很常规的滑动窗口了？
—– UPD 2016.6.9 —–
坐标旋转的代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2000+9;
int n,k,q,mat[N][N],sta[N],sum[N][N],MX;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
#define SUM(x,y) sum[max(0,min(x,MX))][max(0,min(y,MX))]
inline void solve(int lim) { int vout = 0;
for (int j=1;j<=n;j++) for (int i=1,x,y;i<=n;i++) x = sta[i]-j+1, y = i+j-1,
vout = max(vout, SUM(x+lim,y+lim) + SUM(x-lim-1,y-lim-1) - SUM(x+lim,y-lim-1) - SUM(x-lim-1,y+lim));
printf("%d\n",vout);
}
int main(){
n = read(); k = read(); q = read(); MX = n * 2 - 1;
sta[1] = n; for (int i=2;i<=n;i++) sta[i] = sta[i-1] + 1;
for (int i=n+1;i<=n*2-1;i++) sta[i] = sta[i-1] - 1;
for (int i=k,x,y;i;--i) x = read(), y = read(), mat[sta[x]-y+1][x+y-1] = 1;
for (int j=1;j<=MX;j++) for (int i=1;i<=MX;i++) sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mat[i][j];
for (int i=1;i<=q;i++) solve(read());
return 0;
}
哇塞，居然是沙发？留个名
Ahaa, its fastidious discussion about this piece of writing at this place at this weblog, I have read all that, so now me also commenting at this place.
Thanks very nice blog!
Please let me know if you’re looking for a article
writer for your site. You have some really good articles and I believe I would be a
good asset. If you ever want to take some of the load off, I’d absolutely love to write
some material for your blog in exchange for a link back to mine.
Please blast me an email if interested. Thanks!
I think this is one of the most significant information for me.
And i am glad reading your article. But want to remark on few general things, The web site style is wonderful,
the articles is really nice : D. Good job, cheers
I’ve been browsing online more than 3 hours lately,
but I never found any fascinating article like yours.
It’s beautiful price enough for me. Personally,
if all webmasters and bloggers made excellent content as
you probably did, the web might be much more helpful than ever before.
Hi, i feel that i noticed you visited my web site thus i
came to return the want?.I’m trying to find issues to improve my site!I
assume its ok to make use of a few of your concepts!!
Spot on with this write-up, I actually believe that this website needs far more attention. I’ll probably be returning to see more, thanks for
the information!
Hi there friends, how is everything, and what you would like to say concerning this article, in my view its in fact amazing in support of me.
Excellent post. I was checking continuously this
blog and I’m impressed! Extremely helpful info specifically the last part :
) I care for such info much. I was looking for this certain information for a long time.
Thank you and best of luck.
What a material of un-ambiguity and preserveness of valuable knowledge regarding
unpredicted feelings.
hi!,I really like your writing very a lot! share we be in contact extra approximately your post
on AOL? I need an expert on this space to resolve my problem.
May be that’s you! Looking forward to look you.
A fascinating discussion is definitely worth comment.
I do believe that you ought to publish more about this subject matter, it may not
be a taboo subject but typically people do not speak about such issues.
To the next! All the best!!
Hi would you mind letting me know which webhost you’re utilizing? I’ve loaded your blog in 3 completely different web browsers and I must say this blog loads a lot quicker then most. Can you suggest a good web hosting provider at a fair price? Thanks, I appreciate it!
I used to be suggested this website by way of my cousin. I’m no
longer certain whether or not this post is written by means of him as nobody else know such particular
approximately my difficulty. You’re wonderful! Thanks!
Undeniably imagine that that you said. Your favorite
justification appeared to be at the internet the easiest factor to take note of.
I say to you, I certainly get irked even as other folks consider issues that they plainly don’t realize about.
You controlled to hit the nail upon the top and defined out the entire thing with no need side-effects ,
people could take a signal. Will probably be again to get
more. Thank you
Amazing blog! Is your theme custom made or did you download it from somewhere?
A design like yours with a few simple adjustements would really make my blog shine.
Please let me know where you got your design. Kudos
Hi, all the time i used to check webpage posts here early
in the morning, as i like to find out more and more.
You’ve made some decent points there. I looked on the net for more information about the issue and found most people will go along with your views on this
web site.
What’s up it’s me, I am also visiting this website regularly, this web site is really
nice and the people are actually sharing fastidious thoughts.
Greetings! Very useful advice in this particular article!
It’s the little changes that produce the biggest changes.
Many thanks for sharing!
Hello i am kavin, its my first occasion to commenting anyplace,
when i read this piece of writing i thought i could also make comment due to this brilliant piece of writing.
I read this paragraph completely concerning the comparison of latest and previous technologies, it’s
remarkable article.
Great post. I was checking continuously this blog and I’m impressed!
Very helpful information specifically the last part 🙂 I care for such
info a lot. I was seeking this particular information for a very long time.
Thank you and good luck.
Hurrah! In the end I got a web site from where I be capable of truly get valuable information regarding my study and knowledge.
Thanks for your marvelous posting! I certainly enjoyed reading it, you’re a great author.I will make sure to bookmark your blog and may come back later in life. I want to encourage continue your great work, have a nice weekend!