CCPC-2020 黑龙江省赛——1012.Let’s Get Married

题意

• 在二维平面中，坐标原点是 $0$，从原点开始，按照 $上、右、下、左$ 的顺序进行 $bfs$，每个位置的值依次递增。
• 定义两种操作：
  • 1 id ： 输出平面中值为id的坐标(相对于上一次操作的坐标)
  • 2 x y ： 输出此坐标(相对于原点(0,0))的值

题解

• 按照 $BFS$ 序动手画一下就看得出来规律了

• 其实还是蛮简单的

• 数字是每一层填满了再进入下一层

• 每一层的最大数是在当前层最左端的数字

• 每一层的填充规律为：从最上面开始，以此右左右左跳跃式递增，抵达最右端之后，从右向左，递增填充当前层。

• 不难发现，对于第 $i$ 层： 最小数：$2(i?1)(i)+1$，最大数：$2(i)(i+1)$，最右端：$2(i^2)$

• 然后随便搞一搞就可以出来了 (;-_-)????

• 注意每一次操作后都要记录坐标，最后输出的答案是基于上一次操作的坐标的相对位置

  ---

• 求坐标的时候需要确定层数，设层数为 $t$，目标值为 $s$，则需要确定一个 $t$ 使其满足：$2(t?1)(t)<s<=2(t)(t+1)$ 。

• 这里在比赛的时候发现二分就可以过，就没有按解方程做。

• 但 …(??ˇ?ˇ??)…

• 二分写傻了……

• 虽然最后魔改之后可以得到正解，但是也发现了最基础的东西理解的还是不到位。8说了，撸二分去了，嘤~

  --------------------------------------------------------------------华丽的分割线---------------------------------------------------------------------

9.28日晚5点更：
二分（目标值），返回所在层数t

int solve(ll s) {
    int l = 0, r = (int)1e8;while (l < r) {
    int mid = r - (r - l) / 2;ll tmp = 2LL * mid * (mid - 1);if (tmp < s) {
    l = mid;}else {
    r = mid - 1;}}return l;
}

由于题目还没开放，所以没有测试。但是本地测试 $[0,1e8]$范围内都是正解。
虽然基本上可能大概差不多这样是对的，但是还是有很多关于二分原理不懂的地方。
开闭区间、初值设置、循环条件、mid取值方式、子区间选取范围、返回l还是r等等问题。

AC-Code

// 码子太丑了，懒得粘了