尊龙游戏旗舰厅官网
收集整理的这篇文章主要介绍了
sicily 1694. spiral
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
训练的题目
模拟题，蛇形矩阵，保证是n*n的矩阵，并且n是奇数 ， 在矩阵中填数，从最中心开始填，逆时针转圈，1,2,3…………n*n。输入n，表示矩阵的大小，输入一个数字m，找出m在矩阵的哪行哪列
其实这个蛇形矩阵可以分为一圈一圈来看，要找m，可以先确定它在哪一圈
每一圈都值的范围是 [ k^2 1 , (k 2)*(k 2) ] ，其中k是奇数
看一圈的四个角，
右上角最大： max = (k 2)*(k 2)
左上角次之： max - (k 2) 1
左下角再次： max - 2*(k 2) 2
右下角 ： max - 3*(k 2) 3
所以可以以这4个值作为一个范围，将这个圈分成4份，叫做 上行 ， 左列 ， 下行 ， 右列
这4分里面的数字是连续的，要在里面找一个值，直接扫描即可
代码写得不是很好，后来没修改了
#include
#include
#define max 32768typedef long long ll;
ll nn[max 10];
ll pos,n;void init()
{memset(nn,0,sizeof(nn));for(ll i=1; i<=max 6; i =2)nn[i] = i*i;
}ll search(ll p)
{for(ll i=1; ; i =2)if(nn[i] < p && p <= nn[i 2])return i;return -1;
}int main()
{init();int t;scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&pos);if(pos == 1){printf("%lld %lld\n",(n 1)/2 , (n 1)/2);continue;}ll m = search(pos);ll max = (m 2)*(m 2);ll q = (m 1)/2;//【 m*m 1 , (m 2)*(m 2) 】//找到在第q圈
ll r , c;ll k;ll temp;if(pos <= max && pos > max-(m 2) 1) //上行
{r = (n 1)/2 - q;c = (n 1)/2 q;temp = max;for(k=c; ;k--,temp--)if(temp == pos)break;printf("%lld %lld\n",r,k);}else if(pos <= max-(m 2) 1 && pos > max-2*(m 2) 2 ) //左列
{c = (n 1)/2 - q;r = (n 1)/2 - q;temp = max-(m 2) 1;for(k=r; ;k ,temp--)if(temp == pos)break;printf("%lld %lld\n",k,c);}else if(pos <= max-2*(m 2) 2 && pos > max-3*(m 2) 3 ) //下行
{r = (n 1)/2 q;c = (n 1)/2 - q;temp = max-2*(m 2) 2;for(k=c; ;k ,temp--)if(temp == pos)break;printf("%lld %lld\n",r,k);}else if( pos <= max-3*(m 2) 3 && pos > max-4*(m 2) 4)//右列
{c = (n 1)/2 q;r = (n 1)/2 q;temp = max-3*(m 2) 3;for(k=r; ;k--,temp--)if(temp == pos)break;printf("%lld %lld\n",k,c);}}return 0;
}
总结
以上是尊龙游戏旗舰厅官网为你收集整理的sicily 1694. spiral的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得尊龙游戏旗舰厅官网网站内容还不错，欢迎将尊龙游戏旗舰厅官网推荐给好友。
