首页 > 其他分享 >有趣的构造题

有趣的构造题

时间:2023-05-02 12:11:37浏览次数:31  
标签:输出 询问 独立 构造 选取 对数 有趣 times

前言:这篇题单里放了一些个人认为很有用/新奇的构造题,这些是我第一次见比较难想出来题,建议想不出来先看下思路。

CF1198C

题意

给一个无向简单图,\(3\times n\) 个点, \(m\)条边,请找大小为 \(n\) 的点独立集或边独立集。输出点独立集、边独立集均可,或输出无解。输出方案的同时需输出具体选择了哪 \(n\) 个点/边,任意方案均可。

\(\sum n \leq 10^5,\sum m \leq 5\times 10^5\)

题解

先说解法:贪心地选取边独立集,如果选取的边集边数不小于 \(n\) 条,则输出边独立集。否则选择非边集中边上的点。

证明:

选边独立集的不用多说,贪心的选取,感性理解一下就是贪心地选完之后一定不会出现两条未被覆盖的点相邻的情况,选到的边的数量是否最多并不重要,因为下文还有关于选取点独立集。

当选取到的边的数量不足 \(n\) 条时,则选取点独立集。因为选完边独立集后一定不会出现两条未被覆盖的点相邻的情况,除去边上的点好还剩 \(3\times n-2\times w\)(\(w\) 是边的数量)。当 \(w<n\),\(3\times n-2\times w\) 一定大于 \(n\)。所以从剩下的点里任意选取 \(n\) 即可满足条件,并且一定不会出现无解的情况。

P9219

题意

这是一道 IO 交互题。

有一个长为 \(n\) 的正整数序列,其中有一个特殊数是其他任意数的两倍及一上。你每次可以询问两个数的差,你需要在 \(\lfloor \frac n 2\rfloor +2\) 次询问中找出这个特殊数。

题解

一个重要结论:特殊数与任意数的差一定比除了特殊数外任意两个数的差要大。

可以自行推导以上结论,一个原因是序列中最小为 \(1\)。

只需先将序列中 \(\lfloor \frac n 2\rfloor\) 对数询问一遍,确定出特殊数可能在的一对数。若 \(n\) 为偶数,则将这对数与这对数与另外的一个数分别询问差,若 \(n\) 是奇数则与先前没有问到的数询问差。在这三对数的差中较小的差所对应的两个数即不是答案。

标签:输出,询问,独立,构造,选取,对数,有趣,times
From: https://www.cnblogs.com/lyz09-blog/p/interesting-structure-problem.html

相关文章

  • 有趣的插入排序
    原文点此跳转什么是插入排序(insertionSort)?在数组中从左到右依次取一个数出来,然后把它放到合适的位置。从思想上可以分为有序区和无序区,有序区在左边代表已经排列好的元素。算法步骤默认左边第一个元素已经在有序区了在无序区取一个数出来(第二个元素)遍历有序区元素,把取出来的元素放......
  • 10分钟搞定!C++类中构造函数和析构函数的完全指南
    一、初步认识构造函数1.什么是构造函数?要了解构造函数就要先了解一下,类的6个默认成员函数,如下图:构造函数:构造函数是一个特殊的成员函数,名字与类名相同,创建类类型对象时由编译器自动调用,以保证每个数据成员都有一个合适的初始值,并且在对象整个生命周期内只调用一次。通俗一点来......
  • 一些有趣的题目 - 1
    \(1.\)如图所示,一硬杆\(AB\)竖立靠在墙角,受外力作用下滑,顶部与底部始终接触墙面和地面,直至完全倒下.若杆长为\(L\),粗细不计,求杆扫过的图形的面积以及围成此图形的一段曲线的函数解析式.\(\large\calMy\Solve:\)设在杆下滑时的某一时刻,杆上端\(A\)位于\((0,y_o)......
  • Java根据Integer数组(有null值)递归构造二叉树
    二叉树:publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.l......
  • GitHub 上有趣、入门级的开源项目HelloGitHub 升级版的 MiniGPT-4 搞定基于图片的文
    GitHub上有趣、入门级的开源项目HelloGitHub  https://github.com/521xueweihan/HelloGitHubhttps://github.com/521xueweihan/HelloGitHub/blob/master/content/HelloGitHub61.md 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等,涵盖多种编程语言Python......
  • 构造函数和析构函数
    1.概念引入在说明构造函数和析构函数的概念之前,首先看一个例子下面这段代码是栈经典的应用场景括号匹配如图,栈必须先初始化,然后在每一个returnfalse之前都需要销毁栈,不然就会内存泄漏这样很繁琐,而且有些时候很容易忘记写,所以在C++中添加默认的成员函数,构造函数和......
  • c++中的构造函数
    C++中的构造函数可以分为一下几种:默认构造函数初始化构造函数(有参数)拷贝构造函数移动构造函数(move和右值引用)委托构造函数转换构造函数#include<iostream>usingnamespacestd;classStudent{public:Student(){//默认构造函数,没有参数this->age=20......
  • C++中关于默认构造函数(Default Constructor)
    读<<深度探索C++对象模型>>,第二章介绍了默认构造函数,自觉知识点虽基础但是很是被忽略,故作此文记录.关于基础概念不做介绍,先看代码#include<stdio.h>#include<string>classSample{public:intintVal;};classFoo{public:Foo(inta=1000):int......
  • Codeforces Round 866 (Div. 1) C. The Fox and the Complete Tree Traversal (构造)
    传送门题目大意:  给定一个有n个点的树,我们可以任意选择一个点作为起点,这个点可以跳到跟自己距离为1或者距离为2的点,已经到达的点不能再到达(最终必须回到起点),询问是否存在一种方案可以从一个点出发经过所有的点最终再回到这个点来。  输入一个整数n。紧接着输入n-1条边。大......
  • Codeforces Round 847 (Div. 3) G.Tokens on Graph (构造)
    传送门题目大意  给定一个无向图,我们定义图中有四种点,一种是黑色的点表示终点,并且黑色的点始终是1号点,一种是红色的点,一种是灰色的点,最后一种就是没有颜色的点。  游戏规则:我们必须移动任意一个灰色的点到相邻的点上,如果灰色的点移动到了红色的点上,那么我们可以移动其他灰......