2010-1082
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题意大致是：有N*M格子组成矩形，有K个格子需要从边界出发找一条直线的路让军队进入。从四条边界出发分别有四条，但是只有最短的一条或并列最短的几条是有效的。同时两条路如果相交，只有较短的一条路是有效。
可以考虑把矩形分成东西南北四块，显然根据条件，西块的格子可以从西线进入，南北同理。有一些格子到两边或更多边距离相等的会在不同的块上分别出现。如正中心的格子四块上都有，于是到某格的路线数可以用格子出现的次数表示。
如下图，由相交路线只取最短可知：当西块的某格A出现，与其同一Y坐标，正东方向的西块格子B必须从西块消失，因为A的存在，B格无法从西线进入。可以在西块把待占格子按Y坐标排序，Y坐标相等的只取X坐标最小的，其余全都去掉。
[[Image(au.jpg)]]
东南北块同样处理。南北按X坐标排序，X坐标相等取离边界最近的格子（南块取Y坐标最大，北块取Y坐标最小）。然后统计东西南北四块格子i的出现次数a,,i,,，结果[[Image(http://icpc.watashi.ws/cgi-bin/mathtex.cgi?ans=\prod{a_i})]]。因为结果最大可以到2^10000^左右，需要大数运算处理。
{{{
#!cpp
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
struct point
{
int x,y;
bool type[4];
point()
{
type[0]=type[1]=type[2]=type[3]=false;
}
void output()
{
printf("%d-%d ",x,y);
}
};
struct bignum
{
int c,n[1000];
void mul(int p)
{
int i;
if (p==1) return;
for (i=0;i<c;i++)
n[i]*=p;
for (i=0;i<c;i++)
if (n[i]>10000)
{
n[i+1]+=n[i]/10000;
n[i]%=10000;
}
if (n[c]>0) c++;
}
void output()
{
int i;
printf("%d",n[c-1]);
for (i=c-2;i>=0;i--)
{
if (n[i]<1000) printf("0");
if (n[i]<100) printf("0");
if (n[i]<10) printf("0");
printf("%d",n[i]);
}
printf("\n");
}
void clear()
{
memset(n,0,sizeof(n));
c=1; n[0]=1;
}
};
vector <int> vp[4];
point p[11000];
int m,n,k,rp,ri;
void build(int ii)
{
point pt=p[ii];
int t,i,j;
int d[4],o[4];
d[0]=pt.y; o[0]=0;
d[1]=n-pt.x+1; o[1]=1;
d[2]=m-pt.y+1; o[2]=2;
d[3]=pt.x; o[3]=3;
for (i=0;i<4-1;i++)
for (j=i+1;j<4;j++)
{
if (d[j]<d[i])
{
t=d[i]; d[i]=d[j]; d[j]=t;
t=o[i]; o[i]=o[j]; o[j]=t;
}
}
(vp[o[0]]).push_back(ii);p[ii].type[o[0]]=true;
if (d[1]==d[0]) {
p[ii].type[o[1]]=true;
vp[o[1]].push_back(ii);
}
if (d[2]==d[0]) {p[ii].type[o[2]]=true; vp[o[2]].push_back(ii);}
if (d[3]==d[0]) {p[ii].type[o[3]]=true; vp[o[3]].push_back(ii);}
}
int cmp0(const int a,const int b) //North
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->x-p2->x;
if (ret==0) ret=p1->y-p2->y;
return ret<0;
}
int cmp1(const int a,const int b) //East
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->y-p2->y;
if (ret==0) ret=p2->x-p1->x;
return ret<0;
}
int cmp2(const int a,const int b) //South
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->x-p2->x;
if (ret==0) ret=p2->y-p1->y;
return ret<0;
}
int cmp3(const int a,const int b) //West
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->y-p2->y;
if (ret==0) ret=p1->x-p2->x;
return ret<0;
}
void output()
{
int i,j;
for (i=0;i<4;i++)
{
for (j=0;j<(int)vp[i].size();j++)
{
p[vp[i][j]].output();
}
printf("\n");
}
}
int main()
{
bignum ans;
int x,y,i;
scanf("%d",&rp);
for (ri=0;ri<rp;ri++)
{
memset(p,0,sizeof(p));
ans.clear();
for (i=0;i<4;i++) vp[i].clear();
point t;
scanf("%d%d",&n,&m);
scanf("%d",&k);
for (i=0;i<k;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
build(i);
}
sort(vp[0].begin(),vp[0].end(),cmp0);
sort(vp[1].begin(),vp[1].end(),cmp1);
sort(vp[2].begin(),vp[2].end(),cmp2);
sort(vp[3].begin(),vp[3].end(),cmp3);
x=y=0;
for (i=0;i<(int)vp[0].size();i++)
{
point *pt=&p[vp[0][i]];
if (pt->x>x) x=pt->x; else pt->type[0]=false;
}
x=y=0;
for (i=0;i<(int)vp[1].size();i++)
{
point *pt=&p[vp[1][i]];
if (pt->y>y) y=pt->y; else pt->type[1]=false;
}
x=y=0;
for (i=0;i<(int)vp[2].size();i++)
{
point *pt=&p[vp[2][i]];
if (pt->x>x) x=pt->x; else pt->type[2]=false;
}
x=y=0;
for (i=0;i<(int)vp[3].size();i++)
{
point *pt=&p[vp[3][i]];
if (pt->y>y) y=pt->y; else pt->type[3]=false;
}
for (i=0;i<k;i++)
{
int j,c=0;
for (j=0;j<4;j++)
if (p[i].type[j]) c++;
if (c==0) break;
ans.mul(c);
}
if (i==k) ans.output(); else printf("0\n");
}
return 0;
}
}}}
by pxhdg题意大致是：有N*M格子组成矩形，有K个格子需要从边界出发找一条直线的路让军队进入。从四条边界出发分别有四条，但是只有最短的一条或并列最短的几条是有效的。同时两条路如果相交，只有较短的一条路是有效。
可以考虑把矩形分成东西南北四块，显然根据条件，西块的格子可以从西线进入，南北同理。有一些格子到两边或更多边距离相等的会在不同的块上分别出现。如正中心的格子四块上都有，于是到某格的路线数可以用格子出现的次数表示。
如下图，由相交路线只取最短可知：当西块的某格A出现，与其同一Y坐标，正东方向的西块格子B必须从西块消失，因为A的存在，B格无法从西线进入。可以在西块把待占格子按Y坐标排序，Y坐标相等的只取X坐标最小的，其余全都去掉。
东南北块同样处理。南北按X坐标排序，X坐标相等取离边界最近的格子（南块取Y坐标最大，北块取Y坐标最小）。然后统计东西南北四块格子i的出现次数ai，结果。因为结果最大可以到210000左右，需要大数运算处理。
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
struct point
{
int x,y;
bool type[4];
point()
{
type[0]=type[1]=type[2]=type[3]=false;
}
void output()
{
printf("%d-%d ",x,y);
}
};
struct bignum
{
int c,n[1000];
void mul(int p)
{
int i;
if (p==1) return;
for (i=0;i<c;i++)
n[i]*=p;
for (i=0;i<c;i++)
if (n[i]>10000)
{
n[i+1]+=n[i]/10000;
n[i]%=10000;
}
if (n[c]>0) c++;
}
void output()
{
int i;
printf("%d",n[c-1]);
for (i=c-2;i>=0;i--)
{
if (n[i]<1000) printf("0");
if (n[i]<100) printf("0");
if (n[i]<10) printf("0");
printf("%d",n[i]);
}
printf("\n");
}
void clear()
{
memset(n,0,sizeof(n));
c=1; n[0]=1;
}
};
vector <int> vp[4];
point p[11000];
int m,n,k,rp,ri;
void build(int ii)
{
point pt=p[ii];
int t,i,j;
int d[4],o[4];
d[0]=pt.y; o[0]=0;
d[1]=n-pt.x+1; o[1]=1;
d[2]=m-pt.y+1; o[2]=2;
d[3]=pt.x; o[3]=3;
for (i=0;i<4-1;i++)
for (j=i+1;j<4;j++)
{
if (d[j]<d[i])
{
t=d[i]; d[i]=d[j]; d[j]=t;
t=o[i]; o[i]=o[j]; o[j]=t;
}
}
(vp[o[0]]).push_back(ii);p[ii].type[o[0]]=true;
if (d[1]==d[0]) {
p[ii].type[o[1]]=true;
vp[o[1]].push_back(ii);
}
if (d[2]==d[0]) {p[ii].type[o[2]]=true; vp[o[2]].push_back(ii);}
if (d[3]==d[0]) {p[ii].type[o[3]]=true; vp[o[3]].push_back(ii);}
}
int cmp0(const int a,const int b) //North
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->x-p2->x;
if (ret==0) ret=p1->y-p2->y;
return ret<0;
}
int cmp1(const int a,const int b) //East
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->y-p2->y;
if (ret==0) ret=p2->x-p1->x;
return ret<0;
}
int cmp2(const int a,const int b) //South
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->x-p2->x;
if (ret==0) ret=p2->y-p1->y;
return ret<0;
}
int cmp3(const int a,const int b) //West
{
point *p1=&p[a];
point *p2=&p[b];
int ret=p1->y-p2->y;
if (ret==0) ret=p1->x-p2->x;
return ret<0;
}
void output()
{
int i,j;
for (i=0;i<4;i++)
{
for (j=0;j<(int)vp[i].size();j++)
{
p[vp[i][j]].output();
}
printf("\n");
}
}
int main()
{
bignum ans;
int x,y,i;
scanf("%d",&rp);
for (ri=0;ri<rp;ri++)
{
memset(p,0,sizeof(p));
ans.clear();
for (i=0;i<4;i++) vp[i].clear();
point t;
scanf("%d%d",&n,&m);
scanf("%d",&k);
for (i=0;i<k;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
build(i);
}
sort(vp[0].begin(),vp[0].end(),cmp0);
sort(vp[1].begin(),vp[1].end(),cmp1);
sort(vp[2].begin(),vp[2].end(),cmp2);
sort(vp[3].begin(),vp[3].end(),cmp3);
x=y=0;
for (i=0;i<(int)vp[0].size();i++)
{
point *pt=&p[vp[0][i]];
if (pt->x>x) x=pt->x; else pt->type[0]=false;
}
x=y=0;
for (i=0;i<(int)vp[1].size();i++)
{
point *pt=&p[vp[1][i]];
if (pt->y>y) y=pt->y; else pt->type[1]=false;
}
x=y=0;
for (i=0;i<(int)vp[2].size();i++)
{
point *pt=&p[vp[2][i]];
if (pt->x>x) x=pt->x; else pt->type[2]=false;
}
x=y=0;
for (i=0;i<(int)vp[3].size();i++)
{
point *pt=&p[vp[3][i]];
if (pt->y>y) y=pt->y; else pt->type[3]=false;
}
for (i=0;i<k;i++)
{
int j,c=0;
for (j=0;j<4;j++)
if (p[i].type[j]) c++;
if (c==0) break;
ans.mul(c);
}
if (i==k) ans.output(); else printf("0\n");
}
return 0;
}
by pxhdg
附加文件
- au.jpg by pxhdg