首页 > 其他分享 >Gym-101915D 题解

Gym-101915D 题解

时间:2024-03-10 16:34:10浏览次数:25  
标签:le 20 题解 Gym 右部点 101915D

D

给定一张图,分为左右各 \(P\) 个点,左右各自内部是一个完全图,左右之间有 \(m\) 条边。求这个图的最大团。\(P\le 20,m\le P^2\)。

对于每个右部点,求出一个长度为 \(20\) 的二进制数,第 \(i\) 位是 \(1\) 表示它与左部第 \(i\) 点有连边。

枚举右部点的子集 \(S\),将它们的二进制数按位与起来,\(1\) 的个数 + \(|S|\) 就是这个子集的答案。

复杂度 \(O(2^PP)\)。

标签:le,20,题解,Gym,右部点,101915D
From: https://www.cnblogs.com/FLY-lai/p/18064323

相关文章

  • Acwing166 数独题解 - DFS剪枝优化
    166.数独-AcWing题库题意数独是一种传统益智游戏,你需要把一个9×9的数独补充完整,使得数独中每行、每列、每个3×3的九宫格内数字1∼9均恰好出现一次。请编写一个程序填写数独。思路搜索+剪枝(优化搜索顺序、位运算)优化搜索顺序:很明显,我们肯定是从当前能填合法......
  • [ABC219E] Moat 题解
    [ABC219E]Moat题解思路解析一眼看到输入数据只有\(4\)行\(4\)列,直接想到状压枚举。可以直接枚举所有护城河所包含起来的格子,判断是否连通以及判断是否包含住了所有村庄。判断连通我选择用洪水填充,随便选一个包含着的格子,若可以通过当前格移动到所有被包含格就说明连通。以......
  • ABC344G 题解
    ABC344G题解给定平面上\(n\)个点和\(q\)条直线,问对于每条线,有多少点在它上方。形式化的,对于直线\(y=ax+b\)统计有多少点\((x,y)\)满足\(y\geax+b\),即\(-ax+y\geb\)。故我们可以将所有点按照\(-ax+y\)排序,从而利用二分简单的得出结果。但是我们显然不可能暴力进......
  • 洛谷 P1099 题解
    洛谷P1099【NOIP2007提高组】树网的核题意简述给定一棵带边权无根树和一个正整数\(s\)。在这棵树的任意直径上截取一段长度不超过\(s\)的路径\(F\),使离\(F\)最远的点到\(F\)的距离最小,求出这个距离。思路记\(\delta(a,b)\)为\(a,b\)之间的路径。对于任意......
  • abc344_D - String Bags 题解
    一个月没有碰oi,感觉水平已经退化到负的了。来复健一下。D-StringBagslink题意:给你\(n\)组字符串组,按\(1\)~\(n\)的顺序,对于每组字符串组,可从中至多选一个字符串。求能否用所选串按顺序拼接成指定串,以及选取字符串的最小个数。然后读完题发现是个\(01\)背包;对于第......
  • AT_abc344_e 题解
    本文同步发表于洛谷。赌狗天天输的一集。赛时各种【数据删除】原因导致没做出来。大意给你一个长度为\(N\)的序列\(A=(A_1,\ldots,A_N)\)。保证\(A\)中的元素是不同的。你要处理\(Q\)个操作。每个操作是以下两种类型之一:1xy:在\(A\)中元素\(x\)后面紧接着插入......
  • AT_abc344_d 题解
    赌狗天天输的一集。大意你最开始有一个空字符串\(S\)。你还有编号为\(1,2,\dots,N\)的袋子,每个袋子都包含一些字符串。袋子\(i\)包含\(A_i\)个字符串\(S_{i,1},S_{i,2},\dots,S_{i,A_i}\)。对\(i=1,2,\dots,N\)重复以下步骤仅一次(这里原题没有讲清楚):......
  • P10238 [yLCPC2024] F. PANDORA PARADOXXX 题解
    分析考虑时光倒流。对于需要合并的两个连通块\(x,y\),其合并之后的最远点对距离一定是合并之前的两组点对中产生的。在合并的时候枚举点对,取距离最大值即可。由于我们是倒着来的,所有连通块的最远点对距离最大值不减,所以能直接在合并之后取最大值。维护连通块用并查集即可。复杂......
  • P10237 [yLCPC2024] E. Latent Kindom 题解
    分析一眼了非最优解。考虑二分答案。对于二分出来的中位数\(x\),到\(a_i\)和\(a_j\)里边又去二分。得到两个序列中不超过\(x\)的数的数量。若这个数量\(cnt\ge\lceil\frac{len_{i}+len_{j}}{2}\rceil\),则\(x\)可能成为中位数,然后继续二分即可。把序列离散化,复杂度......
  • [ABC219F] Cleaning Robot 题解
    [ABC219F]CleaningRobot题解思路解析要点:将整个图拆分成每一轮的每一个点单独考虑贡献。首先看到\(k\le10^{12}\)发现不能直接枚举\(k\)轮,于是开始找每一轮的规律。首先可以知道,如果操作固定,那么起点和路径上每一个点以及终点的相对位置不会改变。也就是说每一轮的起......