首页 > 其他分享 >2023.8.9 做题记录

2023.8.9 做题记录

时间:2023-08-09 22:13:13浏览次数:37  
标签:度数 题意 记录 复盘 偶数 2023.8 root 节点

CF20C


题意:输出 \(1\sim n\) 的最短路路径。
分析:直接裸 bfs 记录松弛操作的上一个点即可。
复盘:不需要复盘。

CF840B


题意:给出若干条边,对于每个点给出 \(d_i=0/1/-1\),若 \(d_i=1\) 则表示该点度数为奇数,若 \(d_i=0\) 则表示该点度数为偶数,若 \(d_i=-1\) 则表示该点度数无限制,请你在给出的边中选出几条边,使由这些边构成的图一定联通。
分析:考虑到每次加一条边会使得总度数增加 \(2\),因此,图的总度数一定是偶数,因此若总度数为奇数且不含 \(-1\)(\(-1\) 可以随时调整总度数)则无解。
现考虑有解的情况,可以对原图构造一个生成树,在生成树上由下到上,根据子节点的现有度数决定是否与他的父节点连边,对于不是根节点的 \(-1\) 节点当偶数节点考虑。
考虑这样构造的正确性:

  • 若 \(d_{root}=-1\),显然可行。
  • 若 \(d_{root}\neq -1\),由于 \(root\) 的所有子树一定符合条件,因此目前总度数一定是偶数,所以若 \(root\) 还要向上连边,那么肯定总度数是奇数,本来就无解。

复盘:明天补。

CF1000E


题意:给出 \(n\) 个点,\(m\) 条边的无向图,保证图联通。求图上经过最多桥的路径。
分析:比较板,用 tarjan 求出无向图的所有桥,然后将边双的点缩成一个点,这时候图一定是一棵树,两次 dfs 跑树的直径即可。
复盘:比较经典,比赛应该不会出这种板子,这题可以巩固一下对桥的理解。

标签:度数,题意,记录,复盘,偶数,2023.8,root,节点
From: https://www.cnblogs.com/mirrork/p/17618124.html

相关文章

  • 2023.8.9 练习
    ARC063E首先树是二分图。二分图同侧的点奇偶性必须相同,异侧必须不同。排掉不合法之后。然后我们处理出若只考虑子树,一个点的取值范围。若一个点没法取值,也排掉。然后从根开始构造即可。ARC062F牛题。首先求点双。若不在点双里面的边,贡献是\(K\).考虑一个点双,若这个点双......
  • 2023.8.89周三:输入带空格的字符串
    1.#include<string>strings;getline(cin,s);2.#include<cstring>#include<stdio.h>chara[1024];gets(a);intlen=strlen(a);//得到数组的实际长度//!!!!!!!!!!!!!!注:cin和getline不能连着用,中间需要加一个cin.ignore;......
  • 记录shell脚本漫漫长路one(很基础)
    背景: 实现进程唤醒的一个小需求编程开始:进程探测配置编排唤醒操作一、基础用法if用法:if[command];then符合该条件执行的语句elif[command];then符合该条件执行的语句else符合该条件执行的语句fi例子:不等于空(以下只是简单示例if用法,里边的变量不要强求和较真)i......
  • 记录--使用 JS 实现基本的截图功能
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助思路分析在开始动手之前,分析一下整个功能的实现过程:根据图片大小创建canvas1画布,并将原图片直接定位在canvas1上;在画布上添加一个蒙层,以区分当前canvas图像是被裁剪的原图像;在蒙层上方,对裁剪区域(鼠......
  • 波形记录系统的搭建-基于Tektronix示波器
     波形测试系统的搭建目标需求:能自动捕获波形并上传至PC机,目标波形1Khz,脉宽50us进度:已实现所需硬件:Tekronix示波器TDS2002B(毕竟NI的PXI示波器太贵了),PC机软件:示波器驱动、SingleExpress、DIAdem 安装驱动、软件,连接PC机,使用LABVIEW检查是否能检索到TDS2002B SingleExpre......
  • Ubuntu gitlab 磁盘扩容记录
    使用vgdisplay命令查看剩余LVM卷组信息,利用lvextend命令进行扩容,最后使用resize2fs命令直接执行vgdisplaylvresize-l+100%FREE/dev/mapper/ubuntu--vg-ubuntu--lv//按百分比扩容resize2fs/dev/mapper/ubuntu--vg-ubuntu--lv引用:https://www.cnblogs.com/gcc2020/p/......
  • Leetcode刷题记录本
    Leetcode刷题记录本ID:1点击查看代码暴力破解法classSolution(object):deftwoSum(self,nums,target):""":typenums:List[int]:typetarget:int:rtype:List[int]""" #暴力破解法fori......
  • oracle物理映射记录
    流程oracle数据库oracle数据库[root@node-3oracle]#lsu01u01-01u01-02[root@node-3oracle]#pwd/root/fileData/bpm/oracle[root@node-3oracle]#u01为从31521导出的数据库数据u01-01对应31522易捷测试环境u01-02对应315238287环境......
  • 记录mysql排序字段有重复值,分页数据错乱问题
    引用http://vsalw.com/9768.html记录mysql排序字段有重复值,分页数据错乱问题,下面2个sql除了分页limit外,其他都一样,但是第三页的结果却包含部分第二页的数据。SELECT id, show_flag, sort, vote_title, img_url, max_option_count, vote_option_type, begin_time, ......
  • MyBatis Generator 学习记录
    目录参考资料什么是MyBatisGenerator?运行MyBatisGenerator方式mavenplugin方式java代码方式参考资料官方文档什么是MyBatisGenerator?MyBatisGenerator是MyBatis代码生成工具。运行MyBatisGenerator方式命令行antmaven运行java代码运行eclipse......