首页 > 其他分享 >CF1003E Tree Constructing

CF1003E Tree Constructing

时间:2023-10-20 15:44:25浏览次数:36  
标签:typedef Constructing int dis Tree long CF1003E include define

很trivial的构造题

首先上来判掉一些显然无解的情况,然后考虑既然最后直径长为\(d\)那么不妨先搞一条长度为\(d\)的链来

考虑在链上接一些点使得直径不会变长,对于链上的某个点,它最多能接上的链的长度就是它到两个端点距离的最小值

不妨设计递归函数求解,设solve(x,dis,lim)表示在\(x\)点,最多能接长为\(dis\)的链,\(x\)这个点还能接上\(lim\)个点

最后看下把能加的位置都加完是否用完了\(n\)个点即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=400005;
int n,d,k,idx; vector <pi> ans;
inline void solve(int now,CI dis,CI lim)
{
	if (dis==0) return; for (RI i=1;i<=lim;++i)
	if (idx<n) ans.push_back(pi(now,++idx)),solve(idx,dis-1,k-1); else break;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; if (scanf("%d%d%d",&n,&d,&k),d>n-1) return puts("NO"),0;
	if (k==1&&d>1) return puts("NO"),0;
	for (i=1;i<=d;++i) ans.push_back(pi(i,i+1)); idx=d+1;
	for (i=2;i<=d;++i) if (idx<n) solve(i,min(i-1,d+1-i),k-2);
	if (idx<n) return puts("NO"),0; puts("YES");
	for (auto [x,y]:ans) printf("%d %d\n",x,y);
	return 0;
}

标签:typedef,Constructing,int,dis,Tree,long,CF1003E,include,define
From: https://www.cnblogs.com/cjjsb/p/17777257.html

相关文章

  • CF723F st-Spanning Tree
    小清新贪心+分类讨论,因为边的数组开小了WA了好久……首先我们贪心地选出不包含\(s,t\)的边,用这些边尽量地将除了\(s,t\)外的\(n-2\)个点连通接下来考虑每个连通块,由于题目保证图初始连通,因此只有三种情况,即要么其中仅有和\(s\)相连的边;仅有和\(t\)相连的边;或者同时有向\(s,t\)连......
  • [ABC207F] Tree Patrolling 题解
    [ABC207F]TreePatrolling弱智DP题,设\(f(i,j,0/1/2)\)表示在点\(i\),子树中有\(j\)个点被覆盖,且\(i\)点自身状态是未被覆盖/被自身覆盖/被某个儿子覆盖,然后树上背包更新就行了。代码:#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintmo......
  • AT_tdpc_tree 木 题解
    木弱智DP题,直接设\(f_i\)表示\(i\)子树内染色的方案数,然后每次合并一个点与它的儿子即可(具体而言,因为儿子间独立,所以方案数就是二项式系数)。需要注意的是因为第一条边可以在任意位置,所以要以每个点为根各DP一次。但是这样每条边会被算两次,所以乘以2的逆元即可。时间......
  • 哈夫曼树Huffman tree
    哈夫曼树Huffmantree一句话解释,哈夫曼树将一个softmax的多分类问题转换成了多个logistic的二分类问题以连续词袋模型(CBOW)为例,输入多个词向量,输出层则输出最可能的w,最简的实现自然是softmax,但为了计算难度,使用哈夫曼树简化计算pwp^wpw为从根节点到词汇w叶子节点对应的路径......
  • Huffman Tree in C
    ////main.c//HuffmanTree////Createdbystevexiaohuzhaoon2023/10/18.//#include<stdio.h>#include<stdlib.h>//定义一个HuffmanTree的节点structHTNode{//表示权值intweight;//定义一个左节点和右节点指针structHTNode*l......
  • [题解] CF1790E - XOR Tree
    CF1790E-XORTree题意给定一颗无根树,在可以改变任意一个点的点权操作基础上,让树上任意简单路径的异或和不为\(0\),问最少需要多少次操作。思路假设某个点为根,设\(pre_x\)为\(x\)点到根的树上前缀异或和,\(a_x\)为\(x\)的点权,则\(x\)和\(y\)之间简单路径的异或和......
  • WPF控件ItemsControl、ListBox、ListView、DataGrid、TreeView、TabControl用法及区别
    1.ItemsControltemsControl是WPF中最基本的控件之一,用于显示一个数据项集合。它允许按照自定义方式呈现任何类型的对象,可以在其中使用不同的布局和面板来展示数据。ItemsControl非常灵活,可以满足各种需求。以下是一个简单的ItemsControl的XAML示例,它使用StackPanel作为布局容器,......
  • CF1873F Money Trees
    CF1873FMoneyTrees双指针好题,但是我用的队列(考虑先找出所有极长的、满足任意一个数都能被它后面的那个数整除的连续段。显然这个操作可以在\(\mathcal{O}(n)\)的时间复杂度内完成。求出每个极长连续段的答案,取\(\max\)即为最终答案。那么现在的问题就是求一个数列中,满......
  • Binary Tree Postorder Traversal
    SourceGivenabinarytree,returnthepostordertraversalofitsnodes'values.ExampleGivenbinarytree{1,#,2,3},1\2/3return[3,2,1].ChallengeCanyoudoitwithoutrecursion?题解1-递归首先使用递归便于理解。C++-Tra......
  • btree 与 b+tree 的区别
    btree:1.关键字和记录放在一起     2.越靠近根节点的记录查询速度越快b+tree:1.非叶子节点中只有关键字和指向下一个节点的索引,记录只放在叶子节点中      2.查询都需要从根节点走到叶子节点,叶子节点还要进行关键字的比较,每个记录的查询时间基本相同......