ACwing98 分形之城分形图

2021-01-28 21:16

阅读：478

标签：www bsp 题意 printf 就是 ace sqrt c++ ++

网址：https://www.acwing.com/problem/content/100/

题意：

说着太复杂了，直接看原网页吧$QAQ$。

题解：

首先我们先推一下公式，就是这个点，在高一级图中的另外三个子图的对应位置应该怎么表示出来。首先在$n-1$级图中$2^{2n-2}$个房子，我们将其编号成$0$到$2^{2n-2}-1$，然后$n$级图中的$m$号房子$n-1$级图的房子整除就知道了房子在哪个$n-1$级图中。取模则知道了对应于这个$n-1$级图的哪个房子，然后继续递归直到一级图上，回溯时加上这个图上的点对应于$n-1$级图的偏移量，最后计算出欧氏距离即可。

偏移量：设在$n-1$级图的坐标是$(x,y)$，$n-1$级图长度为$len$，则：

如果在$n$级图中的$1$号图，则实际坐标为$(y,x)$。

如果在$n$级图中的$1$号图，则实际坐标为$(x,y+len)$。

如果在$n$级图中的$1$号图，则实际坐标为$(x+len,y+len)$。

如果在$n$级图中的$1$号图，则实际坐标为$(len×2-y-1,len-x-1)$。

AC代码：

#include 
using namespace std;
typedef long long ll;
pair calc(int n, ll m)
{
	if (n == 0)
		return make_pair(0, 0);
	ll len = 1ll & a, pair& b)
{
	return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		ll s, d;
		scanf("%d%lld%lld", &n, &s, &d);
		auto p1 = calc(n, s - 1), p2 = calc(n, d - 1);
		double dis = dist(p1, p2);
		printf("%0.0f\n", dis * 10);
	}
	return 0;
}

ACwing98 分形之城分形图

标签：www bsp 题意 printf 就是 ace sqrt c++ ++

原文地址：https://www.cnblogs.com/Aya-Uchida/p/11873436.html

上一篇：AcWing 9. 分组背包问题

下一篇：009.Kubernetes二进制部署kube-apiserver

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：ACwing98 分形之城分形图
文章链接：http://soscw.com/index.php/essay/48407.html

亲，登录后才可以留言！

ACwing98 分形之城分形图

题意：

题解：

评论

热门文章

推荐文章

最新文章

置顶文章

ACwing98 分形之城 分形图

题意：

题解：

评论

热门文章

推荐文章

最新文章

置顶文章

ACwing98 分形之城分形图