題目描述

由于晨晨還沒有研究出核心算法，在游戲中總是被明明擊敗。晨晨拿出了殺手锏進行反擊，精心設(shè)計了一個大型取數(shù)字求位置的難題：N*N( N是奇數(shù))個地磚，每個上面寫有一個編號，這些編號正好是1到N平方。她把這些地磚按次序從中間開始螺旋的鋪墊在地上，形成一個N*N的正方形。N=5時如下圖：

每塊地磚的位置用行列編號表示。左上的地磚位置為第一行第一列，右下的地磚位置為第N行第N列。上圖中編號3的地磚在第2行第3列。

如果一塊地磚在X行Y列，則位置編碼為X*N+Y。例如：上圖中編號是1的地址位置編碼是：5*3+3 = 18；編號是5的地址位置編碼是：5*3+4 = 19。

晨晨要明明計算，從數(shù)A的位置編碼是什么。比如：N=5，A=6,為： 24

每次提問前，晨晨想知道正確的答案，請編程計算出位置編碼。

輸入

第一行：1個奇數(shù)N。
第二行：1個整數(shù)A。（0<A<=N*N）

輸出

?一個整數(shù)，表示編號A地磚的位置編碼。

樣例輸入?

5 20

樣例輸出?

28

提示

數(shù)據(jù)范圍：80%數(shù)據(jù)0<N<1000; 100%數(shù)據(jù)0<N<100000.

---

題目大意：給出一個奇數(shù)n，按照要求構(gòu)造上述矩陣，然后求出某個編號對應(yīng)的序號，序號=x*n+y

題目分析：首先這個題目給的m最大到了1e5，明擺著就是不讓暴力打表然后一個一個找，看了一眼就感覺這個題目感覺很難，因為第一反應(yīng)是數(shù)學(xué)推公式的題，然后就陷入了思維定式之中，一直在用序號和對應(yīng)的坐標(biāo)找映射關(guān)系，但最后還是失敗了。。于是我又仔細(xì)觀察了一下這個題目的矩陣，發(fā)現(xiàn)它構(gòu)造起來實際上是一層一層構(gòu)造的，可以理解為從中間往外擴，也可以理解為從外往中間縮，每一個環(huán)我們可以看成單獨的一層，每一層的值都是連續(xù)的，并且范圍也是可以求出來的，而且起點也都是左上角的那一格，這樣一來我們就可以直接套遞歸解決了，線性查找當(dāng)前所要查詢的值屬于哪一層，找到的話求出坐標(biāo)，回溯的時候維護好坐標(biāo)即可，這里我是分四種情況求的目標(biāo)坐標(biāo)，大概是這樣的四個區(qū)間：

?分類討論一下即可

注意一下，這個題目會爆int，所以所有數(shù)據(jù)都用longlong就ok了，還有遞歸在層數(shù)等于1的時候記得特判一下就沒問題了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5;void dfs(LL &x,LL &y,LL pos,LL step) {LL l=(step-2)*(step-2);LL r=step*step;if(step==1){x=y=1;return;}if(pos>l&&pos<=r){if(l<pos&&pos<=l+(step-1))//第一種情況{x=1;y=pos-l;}else if(l+(step-1)<pos&&pos<=l+2*(step-1))//第二種情況{y=step;x=pos-(l+(step-1));}else if(l+2*(step-1)<pos&&pos<=l+3*(step-1))//第三種情況{x=step;y=step-(pos-(l+2*(step-1)))+1;}else//第四種情況{y=1;x=step-(pos-(l+3*(step-1)))+1;}return;}else{dfs(x,y,pos,step-2);x++,y++;return;} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);LL n,a;cin>>n>>a;LL x,y;dfs(x,y,a,n);printf("%lld\n",x*n+y);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - 位置(模拟+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。