CF976B Lara Croft and the New Game 题解

wwwidk1234 · 2023-07-26 11:13:09 · 题解

洛谷题目传送门

CodeForces 题目传送门

更好的阅读体验？

题目简介

这是一道很考验思维的数学题。

题意

一个 n \times m 的矩阵，从左上角 (1,1) 出发，从上走到下之后按照蛇形方式走到终点 (1,2)。给定一个步数 k，求走 k 步之后的坐标。

分析

通过数据量 2\le n,m \le 10^9,0\le k \le n \cdot m 得知模拟小人走的路径是不可以的。因此，我们考虑常数时间复杂度的数学算法。

分析一下，可以得知小人走的路径分为两部分：从左上角走到左下角和从左下角走到终点两部分。

第一部分

走一步时，小人在 (2,1)；走两步时，小人在 (3,1)……走 k(k<n) 步时，小人在 (k+1,1)。

所以我们可以得到第一部分的代码：

if(k<n) cout<<k+1<<" "<<1<<endl;

第二部分

第二部分的路径可以分为两种情况：从左往右走和从右往左走。设 k_1=k-n，那么 k_1 即为第二部分走的步数。

通过分析 k_1 我们可以得到一个规律：

• 当 \left \lfloor \dfrac{k_1}{m-1} \right \rfloor 为偶数时，即为从左往右走，此时小人的坐标为 (n-\dfrac{k_1}{m-1},k_1 \bmod (m-1)+2)

• 当 \left \lfloor \dfrac{k_1}{m-1} \right \rfloor 为奇数时，即为从右往左走，此时小人的坐标为 (n-\dfrac{k_1}{m-1},m-k_1 \bmod (m-1))

于是我们可以得到第二部分的代码：

long long k1=k-n;
if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl;
else cout<<n-k1/(m-1)<<" "<<k1%(m-1)+2<<endl;

完整代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    long long n,m,k;
    cin>>n>>m>>k;
    if(k<n) cout<<k+1<<" "<<1<<endl;
    else
    {
        long long k1=k-n;
        if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl;
        else cout<<n-k1/(m-1)<<" "<<k1%(m-1)+2<<endl;
    }
    return 0;
}

最后提醒：注意数据范围，此题需要开 long long！