首页 > 其他分享 >优秀的树 - 题解(数学)

优秀的树 - 题解(数学)

时间:2024-08-02 19:39:02浏览次数:15  
标签:10 结点 题解 优秀 long 测试用例 数学

优秀的树

时间限制:C/C++ 2000MS,其他语言 4000MS
内存限制:C/C++ 256MB,其他语言 512MB

描述

给定一棵树,其所有边权重均为 \(1\),定义 \(f(u)=Σ_v dis(u,v)\),v 表示树上的所有结点,\(dis(u,v)\) 表示结点 \(u\) 和 \(v\) 的简单路径的长度。
一棵树被称为“优秀”,当且仅当存在两个结点 \(u\) 和 \(v\) 满足 \(f(u)−f(v)=x\)。
给定 \(x\),求满足 “存在两个结点 \(u\) 和 \(v\) 满足 \(f(u)−f(v)=x\)” 成立的树最少有多少个结点。

输入描述

输入有多组测试用例,第一行包含一个整数 \(t(1≤t≤10^5\)) ,表示接下来有 \(t\) 组测试用例。
每一个测试用例包含一个整数 \(x(1≤x≤10^{18}\))。

输出描述

对每一个测试用例,输出一个整数,表示能满足条件被称为 “优秀” 的树结点最少为多少。
可以证明答案总是存在的。

用例输入 1

3
2
3
114514

用例输出 1

4
5
678

提示

\(1≤t≤10^5\)
\(1≤x≤10^18\)

代码

#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		long long x; scanf("%lld",&x);
		long long k=sqrtl(x);
		if(k*k==x) printf("%lld\n",(k<<1)+1);
		else if(x<=k*(k+1) && !(x&1)) printf("%lld\n",(k<<1)+2);
		else printf("%lld\n",(k<<1)+3);
	}
	return 0;
}

标签:10,结点,题解,优秀,long,测试用例,数学
From: https://www.cnblogs.com/jerrycyx/p/18339485

相关文章

  • 【题解】走路
    I题意简述从原点出发,一步只能向右走、向上走或向左走。恰好走\(N\)步且不经过已走的点共有多少种走法?多组数据,每行输入一个数\(N\)。对于每一组测试数据,每行输出一个数,答案对\(12345\)取模。对于100%的数据,保证\(1\leqN\leq1000\)。时间限制\(1\text{s}\),空......
  • 树(tree) - 题解(带权并查集)
    树(tree)时间限制:C/C++2000MS,其他语言4000MS内存限制:C/C++256MB,其他语言512MB描述给定一个\(n\)个结点,\(n−1\)条边的有根树。第\(i\)条边可以用(\(a_i,b_i\))来描述,它表示连接结点\(a_i\)和结点\(b_i\)的一条边,其中结点\(a_i\)是结点\(b_i\)的父节点。......
  • 青少年编程与数学 01-008 在网页上完成计算 01课题、数学课程的性质
    青少年编程与数学01-008在网页上完成计算01课题、数学课程的性质课题要求一、课程性质二、数学的本质三、数学的社会功能四、数学教育的重要性五、数学教育的目标六、数学教育的特性七、连贯性和实践性连贯性(Coherence)实践性(Practicality)八、个性化进度与节奏九、数......
  • Luogu P5005 中国象棋 - 摆上马 / Luogu P8756 国际象棋 题解 [ 蓝 ] [ 状压 dp ] [
    国际象棋:模板棋盘状压。摆上马:需要点思维的棋盘状压,相比上一道题加了“蹩马脚”的设定。Easy_version:国际象棋概述一下此类棋盘问题的思路:用二进制数表示出棋盘上某一行的状态。用位运算预处理出合法的单行状态,以及需要用到的一些东西。用位运算判断前一行或者前几行能否......
  • Luogu P3959 宝藏 题解 [ 紫 ] [ 状压 dp ] [ 二项式定理 ]
    宝藏:一个对着蓝书代码调都能调两个小时的大毒瘤,但是思路还是很值得借鉴的,有普通状压和三进制状压两种做法,或者暴搜剪枝也可以(这里不介绍暴搜剪枝做法)。普通状压做法观察到\(n\le12\),首先想到状压。但考虑到普通的状压不太行,因为\(K\)这个数算在代价里,会导致这个dp有后效......
  • BZOJ2839/LG10596 集合计数 题解(二项式反演+扩展欧拉定理)
    题目大意:一个有\(N\)个元素的集合有\(2^N\)个不同子集(包含空集),现在要在这\(2^N\)个集合中取出若干集合(至少一个),使得它们的交集的元素个数为\(K\),求取法的方案数,答案模\(10^9+7\)。为表述方便,不妨设这\(i\)个元素分别为\(1\simn\)。前置知识:二项式反演。考虑设\(g(......
  • 如何架构优秀的Go后端REST API服务
    如何架构优秀的Go后端RESTAPI服务原创 K8sCat 源自开发者 2024年07月01日18:12 广东源自开发者专注于提供关于Go语言的实用教程、案例分析、最新趋势,以及云原生技术的深度解析和实践经验分享。283篇原创内容公众号REST(RepresentationalStateTransfe......
  • 题解:CF1537E2 Erase and Extend (Hard Version)
    CF1537E2EraseandExtend题解分析通过观察题目,可以证明结果一定是由多次前缀复制得来的。题目要求你进行删和复制的操作,与其交替着操作,不如直接先删到最优的前缀再进行复制。现在就是要找最优的前缀。从头一位一位往后遍历。用\(l\)来存储目前最优前缀的长度,第\(i\)位......
  • 题解:CF1301B Motarack's Birthday
    CF1301DTimetoRun题解思维题。分析把一个格子视作一个点,每个点的度数都是偶数,所以这是一张欧拉图。而需要走遍整个方格图,可以证明只要\(k\)不超过\(4nm-2n-2m\)就一定有解。很明显存在很多种方案,这里我用的方案是:从左上角出发,向右走\(m-1\)步到头,再向左走\(m-1\)......
  • 题解:CF634A Island Puzzle
    CF634AIslandPuzzle题解分析由于我们仅能移动\(0\),所以其它数字的相对顺序较原来应该是不变的,所以我们从环中删除\(0\)再判断相对位置即可。还有需要注意的是本题是一个环,找到末尾需要用取模操作回到开头继续比较。示例代码#include<bits/stdc++.h>usingnamespacest......