首页 > 其他分享 >2023.8.4 杂题

2023.8.4 杂题

时间:2023-08-04 21:56:11浏览次数:45  
标签:度数 一个点 log 建图 删成 自环 2023.8 杂题

1.P5344 【XR-1】逛森林

先用并查集维护连通性。
考虑如何建立传送门:
如果使用树剖,强行线段树优化建图,那么空间开销过大,已经有 2 只 \(\log\)。
考虑使用倍增优化建图,对于一个点向上 \(2^k\) 的祖先的形成链都建一个点,模仿 LCA 的过程建边,空间是 1 只 \(\log\).
如果我们模仿 ST 表,那么就没有 \(\log\) 了。
即可通过此题。(码量过大)

2.P4350 [CERC2015] Export Estimate

离线。首先先将边权排序,然后从大到小加边,即可避免删除操作。
我们考虑什么点会被删掉。
1.度数为 0
2.度数为 2 且最后不删成自环。

这是因为如果有一个纯粹的环(所有点度数为 2),这样的话最后只能删成自环。
但是如果有一个点连向外面,整个环都会被删掉,因为总有点度数为 2。
那么最后点的数量是 \(n-度数为0的点-度数为2的点+纯粹的环\)

标签:度数,一个点,log,建图,删成,自环,2023.8,杂题
From: https://www.cnblogs.com/Simon-Gao/p/17607122.html

相关文章

  • 暑假集训D11 2023.8.4 补题
    题意给定一个数组\(a\).询问区间\([l,r]\)是否可以分成\(k\)段,每一段的和都是\(2\)的倍数(偶数)考虑前缀和\(sum\),如果\(sum[i]-sum[j-1]\)是偶数,那么\([j,i]\)一定是\(1\)个合法的区间.因此对于询问\(l,r\),可以统计前缀和的值为偶数的个数,......
  • 2023.8.2
    考完科三临时决定去海边啦十二点半睡四点半起来!!但是居然起得来在学校上课肯定是起不来的但是为了玩是肯定起得来的哈哈哈准备玩两天,第一天先去了白沙湾赶海,但是只抓住了很多寄居蟹和小螃蟹晚上的日落很好看!......
  • 2023.8.4 周五:MySQL相关命令
    1#展示数据库2showdatabases;34#创建数据库5creatdatabase+db1(数据库名称);67#如果创建同样名字的数据库,会报错,可以选择另一条判断语句;8creatdatabaseifnotexistsdb1;910#删除数据库11dropdatabasedb1(数据库名称);1213#如果删......
  • 暑假集训D10 2023.8.3 补题
    D.DnDDice给出分别有不同个数的\(4,6,8,12,20\)面骰子,\(k\)面骰子的每个面的点数分别是\(1~k\).问用上所有骰子能组合出来的情况的概率从大到小排序,如果有相同的可能性的情况,按任意顺序即可.\(\operatorname{Solution}\)可以将骰子两两合并,合并后的骰子大小为\([m......
  • 2023.8.3
    早上起来买了17号的火车票18号早上就能到学校,时间过去好快啊不到两个星期就回去了,明天打算回去老家再玩玩,这边太无聊了,下午看了看新出的动漫,技术炸裂,真的是国产之光,晚上一如既往地写了会儿pta看了会儿java就睡了。......
  • 2023.8.3
    今天去看了花式栈溢出的stackpivoting,前面没怎么卡壳,倒是后面exp里payload的最后最后两部分汇编指令搞卡壳了,刚开始用本就没正式学过所以一知半解的汇编知识去分析,结果没分析出来,反而越分析越迷惑,无奈之下去查几个汇编指令的详细执行流程(如jmp,ret,leave),中间还又去找博客详细了解......
  • 2023.8.3 训练
    A有一个01矩阵,求最少取反若干矩阵,使得存在一条由左上到右下仅为0的路径,且只能向下向右走。设\(f(i,j,0/1)\)表示走到\((i.j)\),且那个点为0/1的最小值。用\(f(i-1,j),f(i,j-1)\)更新\(f(i,j)\)即可。B[AGC010C]Cleaning有一棵树,每次可以选择连接两个叶子的路......
  • 2023.8.3
    学习java中的类面向对象与面向过程面向过程:强调的是功能行为,以函数为最小单位,考虑怎么做。面向对象:强调具备了功能的对象,以类/对象为最小单位类与对象的关系类:对一类事物的描述,是抽象的、概念上的定义对象:是实际存在的该类事物的每个个体,因而也称为实例(instance)面向对象......
  • 2023.8.3 周四:SQL
    1#SQL语句可以单行或者多行书写,以分号结尾2#MySql数据库的SQL不区分大小写,关键字建议使用大写3#注释:4#单行注释:--注释内容或者#注释内容(MySQL特有)5#多行注释:/*注释内容*/67/*8DDL:操作数据库,表等;9DML:对表中的数据进行增删改;10DQL:对表中......
  • 2023.8.2 翻转卡片游戏
    坑点注意:x不能与任意一张卡片的正面数字相同,包括自己。因此如果一张卡片正反面数字相同,必然不可能是x。暴力由于\(n\leq1000\),因此\(n^2\)暴力是可以过的。遍历每一个\(nums[i]\),判断其正反面是否相同,相同则跳过,不相同则进一步检验。分为两种情况,一是取\(fronts[i]\),另一种是......