「BZOJ1557」GC转移
Description
撞啊撞,撞啊撞,DP终于在规定时间内撞完了所有的石头。轰的一声,一扇厚重的石门上升了,露出一个门,大家激动地冲了进去,却发现是另外一个巨大的迷宫。。。。。。 又经过N轮天翻地覆的巨响之后,DP终究还是把头转昏了,幸好的是他撞完了最后一个迷宫。在DP昏厥之际,也正是谜题解开之际。就在最后的一个小石洞里面,记录了这里N光年前的历史。原来在那个时候,也发生了一次巨大的变动,当时的KD同样是为了维护世界的和平而战死沙场。后来它的朋友们十分的悼念它,所以其中一部分便开始进行对自然法术的研究,经过了漫长的岁月之后,复活圣地终于问世,可惜的是KD的残骸早就不知道丢哪去了。 因为自然的力量过于强大,所以研究者不得不将它封印在地底,经历天地轮回之后,希望它在需要被用到的时候再次被召唤出来,避免悲剧的再次发生。 当知道有复活圣地这种东西存在的时候,大伙都伴随着惊讶和兴奋,立即将KD和其他阵亡战士的GC抬出地面,此时地面早已发生了翻天覆地的变化,战争过后破烂的土地已不复存在,只能看见由光构成的网格状平台覆盖着地面,圣地中心清晰可见。但是自然的力量实在过于强大,导致根本无法靠生物做功而将盒子送至中心,爱因斯坦理论空前乏力,牛顿力学受到极大的挑战。难道只能依靠说明中介绍的控制地来操纵自然力量转移盒子了么,但是它是什么,它在哪,大伙一脸茫然。 话说另外一处,临时组成的寻找F小队还在墓地内四处搜索,却一无所获。而在地面裂开的时候,F就已落入了墓地层下层的地下水系了。此时,F在某处被冲上了岸,碰巧的是,正好冲到了传说中的控制地。F醒来之后,发现四周死寂一片,不得不朝仅有的一处光源靠近。而光源处,除了一个奇怪的控制器以外什么都没有,别无选择,F只能一头雾水地按照控制地的说明进行操作,期望能找到回到地面的方法。 以KD盒子所在的格子为中心,控制地的投光屏上建立了平面直角坐标系,圣地中心在X,Y处。现在的任务就是使用各种咒语,将KD的盒子移动到圣地中心。由于这个控制器年代太久远了,说明上的字被自然所磨损,所以F现在能看清楚的只有X咒语和十咒语。 每念一次咒语,可以选择某坐标格为中心,扩展出一个长度为L的X形状或者十形状,并且顺时针或者逆时针旋转90度,每个格子上的东东会被一起旋转。详细描述如图,红色格子为中心,4个方向扩展出的格子数包括中心格子为长度,箭头表示物品的转移路径。 为了尽快完成任务找到回地面的方法,所以F想知道,至少要念多少个咒语才能完成任务,但是似乎扳蹄子数不出来,所以只好求助于过去世界的你。
Input
第一行一个正整数T,表示一共有T组需要计算的坐标及长度。 接下来T行每行3个整数X、Y、L,表示圣地中心坐标为X,Y,咒语中扩展出的X形状和十形状的长度为L,当然咒语不可能白念,所以L>1。
Output
对于每组输入数据输出一个整数ANS,表示至少要念ANS个咒语才能完成任务。 如果无法完成任务,请输出“Poor F!”
Sample Input
3
12 20 5
14 22 5
0 1 2
12 20 5
14 22 5
0 1 2
Sample Output
4
5
Poor F!
5
Poor F!
HINT
对于10%的数据,X、Y、L的绝对值<=10^2,T<=5;
对于40%的数据,X、Y、L的绝对值<=10^16,T<=100;
对于100%的数据,X、Y、L的绝对值<=10^500,T<=1000;
注意事项:
每个数都没有前导0。
题解
发现x,y奇偶性不同无解
都是奇数就用十咒语先都变为偶数
由于十咒语用两次的话就可以用X咒语代替
那么只要枚举用一次/不用十咒语分别计算答案取最优即可
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 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define inf 100000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; ll x,y,l,ans,t; ll cal(ll x,ll y) { return x/(2*l)+y/(2*l)+(x%(2*l)!=0)+(y%(2*l)!=0); } int main() { T=read(); while(T--) { x=read();y=read();l=read()-1; x=abs(x);y=abs(y); if(x<y)swap(x,y); if((x+y)&1){puts("Poor F!");continue;} bool flag; if(x&1) { t=l;t=min(t,y); if((x-t)&1)t--; x-=t;y-=t; flag=1; } else flag=0; ans=cal(x,y); t=l;t=min(t,y); if(t&1)t--; ans=min(ans,cal(x-t,y-t)+1); printf("%lld\n",ans+flag); } return 0; } |
然后当然要加上高精度,好吧写了近200行高精发现T得停不下来
高精除法写的太丑了。。。此坑待填
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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define rad 10000 #define inf 100000000 #define ll long long using namespace std; int T; char ch[1005]; struct data{ int v[1005],l; data(){ v[1]=0; l=1; } }x,y,l,m,ans; inline void read(data &x){ bool opt; data a; scanf("%s",ch+1); if(ch[1]=='-')opt=1; else opt=0; a.l=strlen(ch+1); if(opt)a.l--; for(int i=1;i<=a.l;i++) a.v[i]=ch[a.l-i+1+opt]-'0'; for(int i=a.l+1;i<=a.l+4;i++) a.v[i]=0; x.l=(a.l-1)/4+1; for(int i=1;i<=x.l;i++) { x.v[i]=0; for(int k=1;k<=4;k++) { x.v[i]=x.v[i]*10+a.v[(i-1)*4+(5-k)]; } } } inline void print(data a){ printf("%d",a.v[a.l]); for(int i=a.l-1;i;i--) printf("%04d",a.v[i]); printf("\n"); } inline bool operator>(data a,data b){ if(a.l>b.l)return 1; if(a.l<b.l)return 0; for(int i=a.l;i;i--) if(a.v[i]>b.v[i])return 1; else if(a.v[i]<b.v[i])return 0; return 0; } data operator*(data a,data b){ data c; for(int i=1;i<=a.l+b.l;i++)c.v[i]=0; for(int i=1;i<=a.l;i++) for(int j=1;j<=b.l;j++) c.v[i+j-1]+=a.v[i]*b.v[j]; for(int i=1;i<=a.l+b.l;i++) { if(c.v[i]>=rad) { c.v[i+1]+=c.v[i]/rad; c.v[i]%=rad; } if(c.v[i])c.l=i; } return c; } data operator+(data a,data b){ if(a.l<b.l)swap(a,b); int t=b.l; for(int i=1;i<=t;i++) a.v[i]+=b.v[i]; for(int i=1;i<=t;i++) if(a.v[i]>=rad) { if(i==a.l) { a.v[i+1]=0; a.l++; } a.v[i+1]+=a.v[i]/rad; t=max(t,i+1); a.v[i]%=rad; } return a; } data operator-(data a,data b){ for(int i=1;i<=b.l;i++) { a.v[i]-=b.v[i]; if(a.v[i]<0) { a.v[i]+=rad; a.v[i+1]--; } } while(!a.v[a.l]&&a.l)a.l--; return a; } inline data operator-(data a,int p){ data b; b.v[1]=p;b.l=1; return a-b; } inline data operator*(data a,int p){ data b; b.v[1]=p;b.l=1; return a*b; } inline data operator+(data a,int p){ data b; b.v[1]=p;b.l=1; return a+b; } inline data operator/(data a,int p){ for(int i=1;i<=a.l;i++) { if(a.v[i]&1)a.v[i-1]+=rad/p; a.v[i]/=p; } while(!a.v[a.l]&&a.l)a.l--; return a; } inline data operator/(data a,data b){ data l,r=a; while(r>l) { data t=r-l; if(t.l==1&&t.v[1]==1)break; data mid=(l+r)/2; if(mid*b>a)r=mid; else l=mid; } if(r*b>a)return l; else return r; } data cal(data x,data y){ data t1,t2,o; t1=x/m,t2=y/m; return t1+t2+(x-t1*m>o)+(y-t2*m>o); } int main(){ scanf("%d",&T); while(T--) { read(x);read(y);read(l);l=(l-1);m=l*2; if(y>x)swap(x,y); int flag; data t; if((x.v[1]+y.v[1])&1){puts("Poor F!");continue;} if(x.v[1]&1) { t=l; if(t>y)t=y; if((x-t).v[1]&1)t=t-1; x=x-t;y=y-t; flag=1; } else flag=0; ans=cal(x,y); t=l; if(t>y)t=y; if(t.v[1]&1)t=t-1; data tmp=cal(x-t,y-t)+1; if(ans>tmp)ans=tmp; print(ans+flag); } return 0; } |
楼主noip多少?
HZWER学长这么强明显是600
540 TAT