首页 > 其他分享 >2000-2500板刷

2000-2500板刷

时间:2024-03-11 11:55:38浏览次数:17  
标签:状态 路径 板刷 状压 2000 2500

20240311

CF1929E *2300

题意: 一棵树, k 条简单路径, 想让这 k 条简单路径中都有至少一条边被染色, 问最少染色多少条边能满足这个条件, k 不大于 20

题解: k 很小, 考虑状压. 每一条边能影响的路径最多是 k 条, 可以用状态来表示每一条边影响的简单路径, 然后状态相同的边随便选一条就行, 效果是一样的, 那么会出现多少种不同的状态呢?  可以用虚树来考虑, 最多只会有 O(k) 种状态, 然后就是经典状压 dp 了.

 

标签:状态,路径,板刷,状压,2000,2500
From: https://www.cnblogs.com/Leonard7/p/18065773

相关文章

  • 3月板刷ARC记录
    ARC058F考虑背包,记\(f_{i,j}\)表示考虑前\(i\)个串,取出长为\(j\)的最小串。由于涉及字典序比较,时间复杂度为\(\mathcalO(nk^2)\)。字典序比较不同于计算式比较,找到\(LCP\)后第一位即可得出结果。考虑仅保留能转移到\(f_{n,k}\)的\(f_{i,j}\)。对于\(f_{i,j1},f......
  • 洛谷题单指南-搜索-P1019 [NOIP2000 提高组] 单词接龙
    原题链接:https://www.luogu.com.cn/problem/P1019题意解读:要计算接龙能得到的最长字符串,可以通过DFS暴搜所有可能的接龙方案解题思路:DFS的关键在于两个判断:1、下一个单词是否可以和上一个单词接龙,最短公共长度是多少(只需要看两个单词的最短公共长度,这样能保证接龙更长)2、单词......
  • mssql排序order by42000报错解决
    原文链接:https://blog.csdn.net/wang1qqqq/article/details/122961882在mssql查询中,如果子查询中使用orderby,会出现报错:[42000][Microsoft][ODBCDriver17forSQLServer][SQLServer]除非另外还指定了TOP、OFFSET或FORXML,否则,ORDERBY子句在视图、内联函数、派生表、子......
  • linux基本知识汇总1(基础命令) 20000字汇总
    linux版本号主版本号.次版本号.修正次数2.6.30--次版本号为偶数:稳定版奇数:测试版$$$$命令选项查看方式1.内建命令(help)格式:help+内建命令####help命令//命令使用说明2.外部命令(–help)一般是Linux命令自带的帮助信息,并不是所有命令都自带这个......
  • P9997 [Ynoi2000] pmpkmp
    我永远喜欢数据结构。lxl大毒瘤!开写到AC耗时\(5\)天的大毒瘤题,期间学习了神仙@云浅知处的思路。他修改部分的代码也帮助我找到锅AC,膜拜云浅!本题是CF1045JMoonwalkchallenge的加强版,码量超过\(6\text{KB}\),作为一名对读者负责人的笔者,我在此必须郑重警告:\[\color{re......
  • Codeforces(1500板刷)
    目录写在前面1.A.DidWeGetEverythingCovered?(构造、思维)题目链接题意题解代码总结2F.Greetings(离散化+树状数组)题目链接题意题解代码总结写在前面开始板刷1500了,主要是最近卡1300-1400上不去,发现cf很多思维题要不是想不到,要不就是签的慢,被读题卡了心态就巨难受,一下就......
  • 速度高达2000MB/s!雷克沙发布SL600移动SSD:1TB版本650元
    雷克沙近日发布了ProfessionalSL600移动固态硬盘,采用了USB3.2Gen2x2技术,读写速度高达2000MB/s。外观上该移动固态硬盘采用了喷砂工艺,材质为耐用铝制外壳可防止碰撞和跌落,兼具高速传输、耐用性和可靠性,足以满足用户各种场景下的使用需求,确保复杂场景使用无忧。在速度上,读写速......
  • foobar2000 v2.1.2 汉化版
    新春佳节,送上一份新年礼物,祝您在新的一年里,万事如意,心想事成,身体健康,事业有成,财源广进,家庭和睦,笑容常开,好运连连。   foobar2000v2.1.2汉化版-----------------------【软件截图】----------------------     -----------------------【软件介绍】--------......
  • 飞腾S2500为啥这么弱
    飞腾S2500为啥这么弱背景前段时间有项目反馈飞腾机器的环境下产品非常慢不仅仅是启动慢,运行慢,干啥都慢。所以想总结一下为啥飞腾CPU性能如此的不好可能有失偏颇。希望飞腾能越做越好飞腾的历史飞腾是中国电子旗下国产CPU团队设计开发的产品但是飞腾CPU最早是国防科......
  • Vision Pro 5 月将在中国区发售;全球科技大厂 1 月已裁员 32000 人丨RTE 开发者日报 Vo
      开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑......