【题解】UVA10161 Ant on a Chessboard

_Qingyu1123_ · 2025-01-09 22:46:29 · 题解

【题解】UVA10161 Ant on a Chessboard

题目意思

有一只蚂蚁从原点 (1,1) 出发，先向上方移动一格，然后再向下走一个格子，之后，它再向右走一个格子，然后向上走两个格子，再向左走两个格子。总而言之，它行走的路径就是像蛇一样。

思路

首先这是一道找规律题，其实就和蛇形矩阵差不多，画了一个图，发现对角线上的数字的公差是等差数列，公式为 a_n = n \times (n-1) +1。

所以先要给的 n 开平方并向上取整，判断 n 为奇数还是偶数。

这个蛇形矩阵有以下规律：

• 奇数行与列：

  行： 从左到右到此行对角线上的数字依次递减。

  列： 从对角线上数字开始从上到下依次递减。

• 偶数行与列：

  行：从左到右到此行对角线上的数字依次递增。

  列：从对角线上数字开始从上到下依次递增。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int d=sqrt(n);
        if((d*d)!=n)
            d++;
          //等价于向上取整
        int x=d*(d-1)+1;
          //x为对角线上的数字
        if(d%2!=0)
        //奇数  行：left->right top->bottom 递减
        {
            if(n>=x)
                cout<<d-(n-x)<<" "<<d<<endl;
            else
                cout<<d<<" "<<d-(x-n)<<endl;
        }
        else
       //偶数  行：left->right top->bottom 递增
        { 
            if(n<=x)
                cout<<d-(x-n)<<" "<<dia<<endl;
            else
                cout<<d<<" "<<d-(n-x)<<endl;
        }
 return 0;
}

ac 记录。