首页 > 其他分享 >2023.7.21 课上速记

2023.7.21 课上速记

时间:2023-07-21 14:34:03浏览次数:49  
标签:le 21 最小 课上 2023.7 权值

ExaWizards 2019 F

没记到,淦。

CF773D

有一个 $n$ 个点的完全图,每两个点之间有一条长度为 $w_{i,j}$ 的无向边。

构造以 t 为根的生成树,使得树上每个节点到根最短边的长度和最小。

对于每个 \(t\) 求答案。

\(n \le 2000\)。


把所有边减去最小的权值,设最小的边的一端为 x,于是转化成求 x 到 t 一条链的权值。

又可以发现,一定可以构造出一种最优情况,使链上的点从与最小边相连的点到 e 是 依次递增的。

这个结论可以用反证法证明:

如果链上有一条递减的边,那么把这条边放到链的起始位置答案肯定不劣,

因为前面较大的边并不会对链上的代价作出任何贡献.

由于链上的边权依次递增,每条边都只会作出一次贡献,相当于是一条 路径.

所以我们从与最小边相连的点 s 出发跑一遍最短路就可以计算得到。

跑 dj 松弛即可。

CF843D

给定一个有向图,q 次操作

  • 询问 1 到 t 的最短路
  • 将一些边的边权+1

\(n,m\le 10^5, q\le 2000, \sum|s_i|\le 10^6\)


标签:le,21,最小,课上,2023.7,权值
From: https://www.cnblogs.com/eggome/p/17571257.html

相关文章

  • 学习生理基础 | 记忆的四个环节1——识记 | 2023年7月21日
    小虾米原创作品,转载请注明出处:https://www.cnblogs.com/shrimp-can/p/17570988.html 我们都想高效学习,但如何实现呢?网络上充斥着各种记忆、学习的技巧,能给予我们很大的帮助。但我始终认为,要做好一件事,须得“顺势而为”。那对于学习,什么是这个“势”呢?我认为便是人学习的生理......
  • LECTOR 621阅读器用于料盘读码和筛选调试实例
    第一部分:现场需求/问题描述 客户样品为卷料盘,料盘上有一张白色标签和一个粉色标签,白色标签上有4个一维码及一个二维码(QR码),粉色标签上有一个一维码 客户要求静态读取粉色标签上一维码和白色标签QR码,客户要求在没有粉色标签的时候输出二维码,在有粉色标签的情况下既输......
  • 7.21
    首先先将之前出问题的kali虚拟机重新安装了一遍,再将之前作品赛中未来得及收尾的日志系统进行收尾并检查是否还有遗漏。由于忙着期末考已经有很长一段时间没有深入学习Java,剩余时间决定先将Java语言基础知识过一遍,然后试着寻找几篇文章尝试入门计算机网络。......
  • 2023.7.20
    今天学了ctfwiki上ret2dlresolve的stage4。刚开始看到那个exp,给我看傻了。有种熟悉感,但是这种熟悉感来自于我刚开始学PartailRELRO的时候,因为嫌ctfwiki里的六个阶段太麻烦就去找博客看,结果被exp里的各种看不懂作用的代码劝退了。今天看的是伪造符号表项的代码,又看到了那种看不懂......
  • 网课记录2023.7.20
    视频BV1q54y1q79w首先是今日教训,scanf使用时忘了取地址,折腾了半个多钟才发现scanf("%d",&a);然后文件还莫名其妙地丢失了,幸好之前上传了github下面是正式内容转义字符与\配合导致原本的意思改变目前经常使用的有\n表示换行\t表示水平制表符其余目前未在日常使用中见到ps:如果要在字......
  • 2023.7.20 周四:稀疏数组
    1importjava.sql.SQLOutput;2importjava.util.Arrays;3importjava.util.Scanner;4//稀疏数组5publicclasstest{6publicstaticvoidmain(String[]args){7//首先创建一个11*11的二维数组0:没有棋子1:白棋2:黑棋8int[][]a......
  • Luogu 6821 PA2012 Tanie linie
    这里只讲加强版,这是严格弱化。结论是贪心。每次取出最大和连续子段,目前答案加上这个子段和,然后再把这个子段取反(相反数T),然后求整个过程答案的最大值。考虑费用流模型。对于\(i\len\),\(S\toi\)连边,\(i\toT\)连边,流量为\(1\)费用为\(0\);\(i\toi+1\)连边,流量为\(1\)费......
  • CF1821F Timber
    考虑如何判断一个方案是合法的,很容易想到贪心,从左到右考虑第\(i\)棵树:如果这棵树能向左倒即\([x_i-k,x_i]\)没有被占据,就向左倒。否则向右倒。显然向左倒对之前已经倒下的树没有影响,而对后面的树来讲,这棵树向左倒能留下尽量多的空间,所以优先向左倒一定不劣。所以考虑一......
  • 2023.7.20 环形子数组的最大和
    求子数组最大和可以用dp解决,所以环形子数组也可以用dp解决。最简单的就是破环成链,将原数组再复制一遍然后接到尾端,然后对每个起点做一次求子数组最大和dp。但是由于n的范围较大,这样做的时间复杂度是\(n^2\),会超时。所以必须想办法优化。根据这张图,我们可以把子数组分为二种情......
  • 上班摸鱼刷算法-Java-hot100-[21]合并两个有序链表
    //将一个链表插入到另一个链表中classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){if(list1==null){returnlist2;}if(list2==null){returnlist1;}retur......