首页 > 其他分享 >题解:AT_abc257_d [ABC257D] Jumping Takahashi 2

题解:AT_abc257_d [ABC257D] Jumping Takahashi 2

时间:2024-09-01 13:25:04浏览次数:19  
标签:题解 LL mid long vis Jumping dfs abc257 check

[ABC257D] Jumping Takahashi 2

博客食用更佳:My blog

大体思路

这题是一道二分题,因为 \(S\) 越大,就越容易满足题目要求,\(S\) 越小,就越难满足题目要求,符合二分的特点。

下面先贴上二分代码。

LL l = 0, r = 1e10;
while (l < r) {
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
}
cout << r;// 二分板子。

check 函数怎么写

因为这题 \(n\) 比较小,所以我们可以在每次 check 时,枚举起点,每次从那个点深搜一遍,然后判断搜索到的点数量是否为 \(n\),若搜到了 \(n\) 个点,直接返回 \(1\),若所有点都没有搜到 \(n\) 个点,返回 \(0\)。

下面是 check 函数代码。

bool check(LL mid) {
	for (LL i = 1; i <= n; i++) {
		memset(vis, 0, sizeof vis);// vis 用来标记是否已访问过。
		cnt = 0;// 用来记录访问了几个点,cnt 和 vis 数组每次都要清空。
		dfs(i, mid);// 搜索。
		if (cnt == n) return 1;
	}
	return 0;
}

dfs 函数怎么写

dfs 传参要传两个参数:当前点和训练次数。每次判断每个点是否之前被访问过,访问过就结束掉,没访问过就把这个点标记为 \(1\),接着枚举下一个点,继续搜索。

下面就是代码。

void dfs(LL u, LL mid) {
	if (vis[u]) return; // 查看是否访问过。
	vis[u] = 1, cnt++;
	for (LL v = 1; v <= n; v++) { // 枚举每个点。
		if (p[u] * mid < abs(x[u] - x[v]) + abs(y[u] - y[v])) continue; // 到不了就 continue。
		dfs(v, mid);
	}
}

Code

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const LL N = 205;
LL n, x[N], y[N], p[N],  cnt, vis[N];
void dfs(LL u, LL mid) {
	if (vis[u]) return;
	vis[u] = 1, cnt++;
	for (LL v = 1; v <= n; v++) {
		if (p[u] * mid < abs(x[u] - x[v]) + abs(y[u] - y[v])) continue;
		dfs(v, mid);
	}
}

bool check(LL mid) {
	for (LL i = 1; i <= n; i++) {
		memset(vis, 0, sizeof vis);
		cnt = 0;
		dfs(i, mid);
		if (cnt == n) return 1;
	}
	return 0;
}

signed main() {
	cin >> n;
	for (LL i = 1; i <= n; i++) cin >> x[i] >> y[i] >> p[i];
	LL l = 0, r = 1e10;
	while (l < r) {
		LL mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r;
	return 0;
}

谨记

一定要开 long long。

题解结束了,有问题大家可以私信我。

标签:题解,LL,mid,long,vis,Jumping,dfs,abc257,check
From: https://www.cnblogs.com/0x3f3f3f3f3f3f/p/18391215

相关文章

  • [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two--记忆化题解
    题目复述:链接跳转:[USACO2.4]两只塔姆沃斯牛TheTamworthTwo-洛谷#[USACO2.4]两只塔姆沃斯牛TheTamworthTwo##题目描述两只牛逃跑到了森林里。FarmerJohn开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和John)。追击在$10\times10$的平面网......
  • [蓝桥杯 2020 省 A1] 超级胶水--题解
    题目再现:链接跳转:[蓝桥杯2020省A1]超级胶水-洛谷#[蓝桥杯2020省A1]超级胶水##题目描述小明有$n$颗石子,按顺序摆成一排,他准备用胶水将这些石子粘在一起。 每颗石子有自己的重量,如果将两颗石子粘在一起,将合并成一颗新的石子,重量是这两颗石子的重量之和。为......
  • [蓝桥杯 2016 省 A] 密码脱落--最长公共子序列题解
    题目复述:题目链接:[蓝桥杯2016省A]密码脱落-洛谷#[蓝桥杯2016省A]密码脱落##题目描述X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D四种植物的种子串成的序列。仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的回文串)。......
  • 「NOI2022 D2T2 冒泡排序」题解
    题意uoj768构造长为\(n\)的序列\(a\),满足\(m\)条限制:\(\min_{j=L_i}^{R_i}\{a_j\}=V_i\),要求逆序对数最少题解21pts暴力先进行一些观察:逆序对只关心相对大小,所以\(\foralla_j\)必然\(\in\{V_i\}\),可以完全离散化经典结论:若\(i<j,a_i>a_j\)且交换后合法,则交换......
  • 【题解】Solution Set - NOIP2024模拟赛4
    【题解】SolutionSet-NOIP2024模拟赛4https://www.becoder.com.cn/contest/5501T2沉默乐团https://www.becoder.com.cn/submission/2593352T3深黯「军团」记录一下考场思路:首先对于长度为\(n\)所有排列,按顺序求出她的逆序对数量。然后找到了规律。后面基于此,写出......
  • abc369 题解
    切了A~F,还挺开心(但是如果上一次把G切了的话,我就上青了QAQ比赛链接:https://atcoder.jp/contests/abc369A-369题意:给定正整数\(a,b\)(\(1\lea,b\le100\)),请问有多少个整数\(x\)满足\(a,b,x\)排序后构成等差数列。思路:观察到\(a,b\)范围很小,直接枚举\(x\)即可。......
  • 题解:洛谷 P10996 【MX-J3-T3】Tuple
    原题链接介绍一种(也许是正解的)卡常做法先说总体思路:对于每个三元组\((x,y,z)\),若有一个\(w\)满足\((x,y,w),(x,z,w),(y,z,w)\)均存在,则找到了一个合法的四元组\((x,y,z,w)\)。\(20\\rm{Pts}\)做法如果暴力搜索,在遍历每一个三元组时,每一次都扫描所有的\(w\in[1,N]\)......
  • 题解:洛谷 P10497 [USACO03Open] Lost Cows
    原题链接思路+算法首先,考虑读入到\(a_i\)时,如果要得到此时的最优解(指所有牛的编号不重不漏地覆盖\([1,i]\)的所有编号),对于第\(i\)头奶牛,因为在它前面有\(a_i\)头奶牛的编号小于它,所以第\(i\)头奶牛的编号应当为\(a_i+1\)。如果有一头新的奶牛\(i+1\)加入到这个......
  • 题解:洛谷 P10878 [JRKSJ R9] 在相思树下 III
    原题链接解析在操作一时,最小值如果在最后一位,其无法更新任何数,会被删除;否则不在最后一位时一定会被其右侧更大的数更新。所以在操作一时,最小值一定会被更新掉。同理,在操作二时,最大值一定会被更新掉。由此,操作一决定了答案的下限,操作二决定了答案的上限。所以可以得出贪心策略......
  • LOJ #6089. 小 Y 的背包计数问题 题解
    Description小Y有一个大小为\(n\)的背包,并且小Y有\(n\)种物品。对于第\(i\)种物品,共有\(i\)个可以使用,并且对于每一个\(i\)物品,体积均为\(i\)。求小Y把该背包装满的方案数为多少,答案对于\(23333333\)取模。定义两种不同的方案为:当且仅当至少存在一种物品的......