题解：P14308 【MX-S8-T1】斐波那契螺旋

询问值小于等于

10^{18}

，数量级在

f_{90}

附近。而每个正方形的起始结点，终止结点都可以推导。

T

最大在

10^6

，加输入输出优化，每次查询遍历预处理好的正方形信息，符合条件输出，可以通过此题。

推导方法：对

(i-2)\bmod 4

进行分类讨论。这些是易得的，代码中

(fx,fy)

是正方形左下角的坐标，

(tx,ty)

是正方形右上角的坐标，

f_i

即为边长。实现逻辑也很简单，不再过多阐述。

CPP

#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void solve() {
	
}

struct Rectangle {
	ll fx, fy, tx, ty;
}fib[101];


main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	fib[1] = {-1, 0, 0, 1};
	fib[2] = {-1, -1, 0, 0};
	rep(i, 3, 92) {
		if ((i - 2) % 4 == 1) {
			fib[i].ty = fib[i - 2].ty;
			fib[i].fx = fib[i - 1].tx;
			fib[i].fy = fib[i - 1].fy;
			fib[i].tx = fib[i].fx + fib[i].ty - fib[i].fy;
		}
		if ((i - 2) % 4 == 2) {
			fib[i].fx = fib[i - 2].fx;
			fib[i].fy = fib[i - 1].ty;
			fib[i].tx = fib[i - 1].tx;
			fib[i].ty = fib[i].fy + fib[i].tx - fib[i].fx;
		}
		if ((i - 2) % 4 == 3) {
			fib[i].fy = fib[i - 2].fy;
			fib[i].tx = fib[i - 1].fx;
			fib[i].ty = fib[i - 1].ty;
			fib[i].fx = fib[i].tx - (fib[i].ty - fib[i].fy);
		}
		if ((i - 2) % 4 == 0) {
			fib[i].fx = fib[i - 1].fx;
			fib[i].tx = fib[i - 2].tx;
			fib[i].ty = fib[i - 1].fy;
			fib[i].fy = fib[i].ty - (fib[i].tx - fib[i].fx);
		}
	}
	int T;
	cin >> T;
	while (T--) {
		ll x, y;
		cin >> x >> y;
		rep(i, 1, 92) {
			if (fib[i].fx <= x && x <= fib[i].tx && fib[i].fy <= y && y <= fib[i].ty) {
				ll ans = fib[i].tx - fib[i].fx;
				cout << ans << '\n';
				break;
			}
		}
	}
//	int t; cin >> t; while (t--) solve();
	return 0;
}

题解：P14308 【MX-S8-T1】斐波那契螺旋

文章操作

相关推荐

评论

题解：P14308 【MX-S8-T1】斐波那契螺旋