36 条题解
-
3T2017 LV 7 @ 2018-05-23 20:09:25
思路:
1、判断(x,y)在哪一层。
2、算出该层的最左上角的数字(该层最小的一个数字;作为该层开头)
和它下面一个数字(该层最大的一个数字;作为该层结尾)。
3、判断(x,y)在右上半部分还是左下半部分。
4、从开头或者是结尾,加上或是减去这个点到开头或结尾的长度。
#include<iostream>
#include<cmath>
using namespace std;
int n,x,y,c,s,e=0,t=0,N;
int main(){
cin>>n>>y>>x;
c=min(x,y);c=min(c,(n-x+1));c=min(c,(n-y+1));
N=n;
for(int i=1;i<=c;i++){
e=e+4*(N-1);
N=N-2;
}
s=e-4*(n-2*c+1)+1;
if(n%2==1&&c==(n+1)/2){
s=n*n;e=n*n;
}
if(x>=y){
cout<<(s+(x-c)+(y-c))<<endl;
}else{
cout<<(e-(x-c)-(y-1-c))<<endl;
}
return 0;
} -
12021-02-25 12:34:01@
#include<bits/stdc++.h> using namespace std; int n,m,p,q,ans,sum; int work(int n,int i,int j) { if(i==1) { return j; } else if(j==n)return n+i-1; else if(i==n)return 3*n-2-j+1; else if(j==1)return 4 * n - 4 - i + 2; return work(n - 2, i - 1, j - 1) + 4 * (n - 1); } int main() { cin>>n>>p>>q; cout<<work(n,p,q); }
-
12018-05-23 20:07:00@
找规律嘛,水题水题
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<queue> #include<vector> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int ans=0; int x,y,luyan=1; int n,dx,dy; int main(){ //freopen("playground.in","r",stdin); //freopen("playground.out","w",stdout); cin>>n>>dx>>dy; if(dx>n/2) y=n-dx+1; else y=dx; if(dy>n/2) { x=n-dy+1; } else { x=dy; } int m=min(x,y); for(int k=1;k<=m-1;k++) { luyan+=4*(n-1); n=n-2; } int x1=dx-m+1,yy1=dy-m+1; if(x1==1) { cout<<luyan+yy1-1; //fclose(stdin); //fclose(stdout); return 0; } if(yy1==1){ cout<<luyan+4*(n-1)-1-x1+2; //fclose(stdin); //fclose(stdout); return 0; } if(yy1>x1){ cout<<luyan+n-1+x1-1; //fclose(stdin); //fclose(stdout); return 0; } if(x1>yy1) { cout<<luyan+4*(n-1)-1-n+2-yy1+1; //fclose(stdin); //fclose(stdout); return 0; } if(x1==yy1) { cout<<luyan+(n-1)+(n-2)+1; //fclose(stdin); //fclose(stdout); return 0; } //fclose(stdin); //fclose(stdout); return 0; }
-
12016-11-06 19:55:53@
展♂开即可
```c++
#include <iostream>
#include <algorithm>
using namespace std;int main()
{
int n, x, y;
int i, j, k;cin >> n >> x >> y;
for(i = 1, j = n, k = 0;x != i && x != j && y != i && y != j;i ++, j --)
k += (j - i) * 4;if(x == i)
cout << k + 1 + y - i;
else if(x == j)
cout << k + (j - i) * 3 + 1 - y + i;
else if(y == i)
cout << k + (j - i) * 3 + 1 - x + j;
else if(y == j)
cout << k + j - 2 * i + 1 + x;
cout << endl;return 0;
}
``` -
12015-04-23 20:05:15@
好吧,秒杀AC了- -这题目考的TM的是浆糊啊- -做题前想的好好的思路写着写着就乱了。醉了- -5分钟写好调试用了好久好久。自抽。
那么由我来发一份完整的题解给各位。
这道题乍看之下非常棘手。但是其实数据还是很水的。我们一开始可能认为啊。这道题有什么数学公式,实际上仔细去思考发现不可能有数学公式可以推出来(如果有,那么几行代码就能解决,把这种题目放在普及组比较难的题目里是绝对不可能的。)因此我们思路应该转到怎么枚举出答案。
枚举方法很多,楼下很多人看代码似乎跟我的想法很像,我有3 4个思路,不过觉得这个比较好实现就用了这个,其实也是差不多的。我这个代码的时间复杂度最坏情况是(4*30000)左右,很明显已经足够秒杀此题,也就懒得优化了,直接去数一圈了。我以为有个点会过100MS,呵呵,数据水到100都不用- -
那么怎么去写呢?很简单
我们发现这个矩阵由一圈一圈组成。什么是一圈一圈,就是这个
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
这个算是一圈。我们不难推出,一圈上增加的数就是大圈(1)减去小圈(2)各位对照N=4的样例。因此要是我们知道我们求的点在哪一圈,就可以快速把它外围的圈瞬间求出来,之后只要在循环做一圈就OK,如果i,j找到了就是答案,找不到就ans+1就可以得到答案了。
那么怎么知道这货在第几圈?我们用变量num存它在第几圈。拿i举例,n=5时候,j=1或5答案只会在第一圈,2或4的时候答案就可能在第1或2圈,i同理。我们可以画画图想一想。发现有个很牛叉的结论。
比如i在最多只能在3圈,j最多可以在2圈,那么答案必在少的这个上。即我们求的点在第2圈的某个点上
因此num=min(i,j,n-i+1,n-j+1)
这个结论我不好讲。听不懂的话只能靠意会。各位要可以自己动手或者想下吧。。然后我们num-1.把前几圈的值用上面的那个公式直接算好。就跟我程序里一样。
然后就在4个for,走一圈就行了。主要4个角。不要数重复了。详细看我程序。还要注意一些特殊情况能不能考虑到。
然后轻松AC。
###pascal code
program P1913;
uses math;
var n,i,j,a,b,num,ans,k:longint;
procedure pd;
begin
if (a=i) and (j=b) then begin write(ans); halt; end;
end;begin//main
read(n,i,j); ans:=0;
num:=min(i,j); num:=min(num,n-i+1); num:=min(num,n-j+1); dec(num); //找到num
if n=1 then begin write('1'); halt; end; //特判,保险
for k:=num downto 1 do ans:=ans+(n-2*k+2)*(n-2*k+2)-(n-2*k)*(n-2*k); //计算前num-1圈的值
inc(num); //答案肯定在第num圈
a:=num; b:=num; //从起点准备枚举
if (a=i) and (j=b) then begin write(ans+1); halt; end; //特判,刚好在起点。
for b:=num to n-num+1 do //从左到右
begin
inc(ans); pd;
end;for a:=num+1 to n-num+1 do //从上到下
begin
inc(ans); pd;
end;for b:=b-1 downto num do //右到左
begin
inc(ans); pd;
end;for a:=a-1 downto num do //下到上
begin
inc(ans); pd;
end;write('yes,you can AC it'); //反正也输不出来,拿出来激励人
end. -
02021-06-12 16:47:31@
模拟大法
#include<stdio.h> int n,x,y; int min(int n1,int n2){ if(n1<n2)return n1; else return n2; } int solve(){ scanf("%d%d%d",&n,&x,&y); int layer=min(x,n+1-x);//确定层,n方阵,如n=7,x=5就是第二层 layer=min(layer,min(y,n+1-y)); int num=0,side=n-1; for(int i=1;i<layer;i++,side-=2){ int layer_total; if(side==0)layer_total=1; else layer_total=side*4;//当前层一圈总个数 num+=layer_total; } num++; int nx=layer,ny=layer; if(nx==x && ny==y)return num; for(int i=1;i<=side;i++){ ny++;num++;//y列向右递增 if(nx==x && ny==y)return num; } for(int i=1;i<=side;i++){ nx++;num++;//x行向下递增 if(nx==x && ny==y)return num; } for(int i=1;i<=side;i++){ ny--;num++;//y列向左递增 if(nx==x && ny==y)return num; } for(int i=0;i<side;i++){ nx--;num++;//x行向上递增 if(nx==x && ny==y)return num; } return -1; } int main(){ int res=solve();printf("%d",res); return 0; } ```
-
02018-11-03 22:26:40@
Water!!
#include<cstdio> int read() { int a=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-f; c=getchar(); } while(c>='0'&&c<='9') a=a*10+c-'0',c=getchar(); return a*f; }///读入优化不解释 int n=read(),i=read(),j=read(),x=1,y=1,num=1,h=n,l=n,h1=1,l1=2;///l1第一次只能走到2了 int main() { while(y!=i||x!=j) { if(y==i)///如果是这一排 { printf("%d",num+j-x);///之前走的步数加上还需要走的步数 return 0; } num+=h-x;///加上这一排需要走的步数 x=h--;///x为当前可以走到的地方,之后这个地方就不可以走了 if(x==j)///如果是这一列 { printf("%d",num+i-y);///之前走的步数加上还需要走的步数 return 0; } num+=l-y;///加上这一列需要走的步数 y=l--;///y为当前可以走到的地方,之后这个地方就不可以走了 if(y==i)///如果是这一排 { printf("%d",num+x-j);///之前走的步数加上还需要走的步数 return 0; } num+=x-h1;///加上这一排需要走的步数 x=h1++;///x为当前可以走到的地方,之后这个地方就不可以走了 if(x==j)///如果是这一列 { printf("%d",num+y-i);///之前走的步数加上还需要走的步数 return 0; } num+=y-l1;///加上这一列需要走的步数 y=l1++;///y为当前可以走到的地方,之后这个地方就不可以走了 } printf("%d",num); }
-
02018-07-20 16:18:11@
#include <iostream>
using namespace std;
int main()
{
int n,x,y;
cin>>n>>x>>y;
int l=min(min(x,n+1-x),min(y,n+1-y));
int begin=4*(l-1)*(n-2*l+2)+4*(l-1)*(l-1)+1;
if(l==x)
cout<<begin+y-l<<endl;
else if(l==n-x+1)
cout<<begin+3*(n-2*l+1)-y+l<<endl;
else if(l==y)
cout<<begin+4*(n-2*l+1)+l-x<<endl;
else
cout<<begin+n-2*l+x-l+1<<endl;
return 0;
} -
02018-07-20 16:09:48@
这题有多弱智呢?
估计连学过小奥的四年级小学生都能说出解题流程#include <iostream>
using namespace std;
int main()
{
int n,x,y;
cin>>n>>x>>y;
int l=min(min(x,n+1-x),min(y,n+1-y));
int begin=4*(l-1)*(n-2*l+2)+4*(l-1)*(l-1)+1;
if(l==x)
cout<<begin+y-l<<endl;
else if(l==n-x+1)
cout<<begin+3*(n-2*l+1)-y+l<<endl;
else if(l==y)
cout<<begin+4*(n-2*l+1)+l-x<<endl;
else
cout<<begin+n-2*l+x-l+1<<endl;
return 0;
} -
02018-06-07 18:45:30@
#include <iostream> using namespace std; int n,a,b,nowx,nowy,lowx=1,lowy=1,num=0; void solve(int n){ int x=1,y=1,x1=n,y1=n,turn=1,i,line=n; while(true){ if(x!=a&&y!=b&&x1!=a&&y1!=b){ num+=line*4-4; x++;y++;x1--;y1--; line-=2; nowx--;nowy--; lowx++;lowy++; } else if(x==a||y==b||x1==a||y1==b){ while(i++){ if(turn==1) { if(x==a&&y==b) {cout<<num+1<<endl;return;} else { if(y<nowy) {y++;num++;} else if(y==nowy) turn=2; } } else if(turn==2) { if(x==a&&y==b) {cout<<num+1<<endl;return;} else { if(x<nowx) {x++;num++;} else if(x==nowx) turn=3; } } else if(turn==3) { if(x==a&&y==b) {cout<<num+1<<endl;return;} else { if(y>lowy) {y--;num++;} else if(y==lowy) { turn=4;lowy++;lowx++; } } } else if(turn==4) { if(x==a&&y==b) {cout<<num+1<<endl;return;} else { if(x>lowx) {num++;x--;} else if(x==lowx) { turn=1;nowx--;nowy--; } } } } } } } int main() { cin>>n>>a>>b; nowx=nowy=n; solve(n); return 0; }
暴力计算某坐标数值,优化版。
-
02018-05-18 21:39:58@
观察一下规律,跟着数字增长的方向走,不难发现:
如果是第 1 行,那么第 j 列的数字就是 j ;
如果是第 n 列,那么第 i 行的数字就是 n + i - 1;
后两条规律有点难找,但是不要放弃,继续观察:
如果是第 n 行,那么第 j 列的数字就是 3*n-2-j+1
如果是第 1 列,那么第 i 行的数字就是 4*n-4-i+2
如果对于上述推导过程不是很理解,不妨打开 Excel,自己画图观察。
推导完公式,剩下的就简单多了。不难想出一个递归解法:把螺旋矩阵一层一层地剖开,看看目标位置在哪一层,然后加上这一层最左上角的数字
(4*(n-1)),即为要求的数字。上代码:
#include<bits/stdc++.h>using namespace std;
int work(int n, int i, int j) {
if (i == 1)
return j;
if (j == n)
return n + i - 1;
if (i == n)
return 3 * n - 2 - j + 1;
if (j == 1)
return 4 * n - 4 - i + 2;
return work(n - 2, i - 1, j - 1) + 4 * (n - 1);
}int main()
{
int m,x,y;
cin>>m>>x>>y;
cout<<work(m,x,y);
return 0;
} -
02018-04-22 22:44:44@
从1开始暴力计算到某一数据的坐标。
#include <iostream> using namespace std; int n,a,b,nowx,nowy,lowx=1,lowy=1,num=0; void solve(int n) { int x=1,y=1,turn=1,i; for(i=0;;i++) { if(turn==1) { if(x==a&&y==b) {cout<<num+1<<endl;break;} else { if(y<nowy) {y++;num++;} else if(y==nowy) turn=2; } } else if(turn==2) { if(x==a&&y==b) {cout<<num+1<<endl;break;} else { if(x<nowx) {x++;num++;} else if(x==nowx) turn=3; } } else if(turn==3) { if(x==a&&y==b) {cout<<num+1<<endl;break;} else { if(y>lowy) {y--;num++;} else if(y==lowy) { turn=4;lowy++;lowx++; } } } else if(turn==4) { if(x==a&&y==b) {cout<<num+1<<endl;break;} else { if(x>lowx) {num++;x--;} else if(x==lowx) { turn=1;nowx--;nowy--; } } } } } int main() { cin>>n>>a>>b; nowx=nowy=n; solve(n); return 0; }
-
02018-03-18 20:07:57@
#include<iostream>
using namespace std;
int min1(int a,int b){
return a<b?a:b;
}
int min2(int a,int b,int c,int d){
return min1(min1(a,b),min1(c,d));
}
int main(){
int n,i,j,abc=0,sum=0;
cin>>n>>i>>j;
int x=n/2;
int temp=min2(i-1,j-1,n-i,n-j);
for(int i1=n;;i1=i1-2){
sum+=4*i1-4;abc++;
if(abc==temp) break;
}
if(i<=j) sum+=(i+j-2*temp-1);
else sum+=(2*n-2*temp-i-j-1+2*n-4*temp);
cout<<sum;
return 0;
}//努力看能看懂的 -
02017-06-06 16:24:30@
/* 不用数组的暴力模拟,时间能过,主要是绕过了数组太大的问题 */ #include <bits/stdc++.h> using namespace std; int main() { int size, row, col; int count = 1; int i = 1, j = 1; cin >> size >> row >> col; int up = 2, left = 1, down = size, right = size; while(count < size * size) { while(j < right) { if(i == row && j == col) { cout << count << endl; return 0; } j++; count++; } right--; while(i < down) { if(i == row && j == col) { cout << count << endl; return 0; } i++; count++; } down--; while(j > left) { if(i == row && j == col) { cout << count << endl; return 0; } j--; count++; } left++; while(i > up) { if(i == row && j == col) { cout << count << endl; return 0; } i--; count++; } up++; } cout << count << endl; return 0; }
-
02017-01-31 09:43:45@
你们 为什么 可以写那么短,我写了快一百行了....
Var
n,x,y:longint;Procedure zx(a,b,h,l,k:longint);
Var
i,q,s:longint;Begin
if (x=h) and (y=l) then
begin
writeln(a);
exit;
end;
s:=a; q:=l;
for i:=s to s+k-2 do
if x=h then
begin
if y=q then
begin
writeln(i);
exit;
end;
inc(q);
end
else
break;
s:=s+k-1; q:=h;
for i:=s to s+k-2 do
if y=l+k-1 then
begin
if x=q then
begin
writeln(i);
exit;
end;
inc(q);
end
else
break;
s:=s+k-1; q:=l+k-1;
for i:=s to s+k-2 do
if x=h+k-1 then
begin
if y=q then
begin
writeln(i);
exit;
end;
dec(q);
end
else
break;
s:=s+k-1; q:=h+k-1;
for i:=s to s+k-2 do
if y=l then
begin
if x=q then
begin
writeln(i);
exit;
end;
dec(q);
end
else
break;
End;Procedure dfs(h,l,i,j,k:longint);
Var
ch:boolean;
Begin
if k<0 then
k:=1;
ch:=false;
if (x=h+k-1) and (y>=l) and (y<=l+k-1) then
ch:=true;
if (x=h) and (y>=l) and (y<=l+k-1) then
ch:=true;
if (x>=h) and (x<=h+k-1) and (y=l+k-1) then
ch:=true;
if (x>=h) and (x<=h+k-1) and (y=l) then
ch:=true;
if ch then
begin
zx(i,j,h,l,k);
exit;
end
else
dfs(h+1,l+1,j+1,j+2*(k-2)+2*(k-4),k-2);
End;Begin
readln(n,x,y);
dfs(1,1,1,2*n+2*(n-2),n);
readln;
End. -
02017-01-21 07:52:27@
var
n,i,j,q:longint;
ans:int64;
function min(a,b:longint):longint;
begin
if a<b then exit(a);exit(b);
end;
begin
readln(n,i,j);
q:=min(i,min(j,min(n-i+1,n-j+1)));
if i<=j then
ans:=4*n*q-4*q*q+6*q-4*n-3+i+j
else
ans:=4*n*q-4*q*q+2*q+1-i-j;
writeln(ans);
end. -
02016-10-02 15:41:59@
深搜,从外圈一层层拨♂开
用数学推导出处于边界的数值,
若不在边界则深搜至下一圈。
```pascal
program Rectangle;
var n,i,j:longint;procedure Getlost(lol:longint);
begin
writeln(lol);
halt;
end;procedure Diehere(c,x,y,n:longint);
begin
if not((x=1)or(x=n)or(y=1)or(y=n)) then Diehere(c+4*n-4,x-1,y-1,n-2);
if x=1 then Getlost(c+y-1);
if x=n then Getlost(c+3*n-2-y);
if y=1 then Getlost(c+4*n-x-3);
if y=n then Getlost(c+n+x-2);
end;begin
readln(n,i,j);
Diehere(1,i,j,n);
end.
``` -
02016-08-28 17:42:22@
疯狂地模拟。。。。。。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,im,jm,i=1,j=1,ls,lx,lz,ly,dir;
long int ans=1;
bool epo=false;
int main()
{
scanf("%d%d%d",&n,&im,&jm);
ls=1;
lx=n;
lz=1;
ly=n;
dir=2;
while(1)
{
if(dir==1&&j==jm) {ans+=i-im;break;}
if(dir==2&&i==im) {ans+=jm-j;break;}
if(dir==3&&j==jm) {ans+=im-i;break;}
if(dir==4&&i==im) {ans+=j-jm;break;}
if(dir==1) {ans+=lx-ls;lx--;i=ls;dir=2;continue;}
if(dir==2)
{
ans+=ly-lz;
if(epo==false) epo=true;
else lz++;
j=ly;
dir=3;
continue;
}
if(dir==3) {ans+=lx-ls;ls++;i=lx;dir=4;continue;}
if(dir==4) {ans+=ly-lz;ly--;j=lz;dir=1;}
}
printf("%ld\n",ans);
return 0;
} -
02016-08-05 18:09:47@
如果在最外圈则特判,否则转化为在内圈找,坐标相应变化即可。
```
#include <iostream>
#include <cstdio>
using namespace std;int num(int beg, int n, int i, int j)
{
if (i == 1) return beg+j-1;
if (j == n) return beg+n+i-2;
if (i == n) return beg+n+n-2+n-j;
if (j == 1) return beg+n+n+n-3+n-i;
return num(beg+4*(n-1), n-2, i-1, j-1);
}int main()
{
int n, i, j;
cin >> n >> i >> j;
cout << num(1, n, i, j) << endl;
return 0;
}
``` -
02016-07-12 16:16:34@
还用发题解吗?
信息
- ID
- 1913
- 难度
- 5
- 分类
- (无)
- 标签
- 递交数
- 2027
- 已通过
- 624
- 通过率
- 31%
- 被复制
- 16
- 上传者