「10.29」数列(exgxd)·数对(线段树优化DP)·最小距离(最短路,树上直径思想)
2024-09-07 05:25:39
好久没碰到这么友好乱搞的题了....
A. 数列
考察的是exgcd的相关知识，最后的答案直接O(1)求即可
B. 数对
本来以为是原题，然后仔细看了看发现不是，发现不会只好乱搞骗分了
事实上直接按$a+b$为第一关键字，然后就是原题了.....
C. 最小距离
事实上这道题的思路还是不错的，考场上联想树上直径问题于是想到了
观察数据范围，我们好像只能跑一遍最短路
那么如何在一遍中求出$p$个点的距离，可以记录一个$pre_{i},dis_{i}$分别表示i节点到任意源点的最短距离，和源点是谁
然后我们对于路径的某一个点他被更新时顺便更新他的路径两端
我们关心的问题时这样做能否将全部源点更新，和是否能将最短路更新出
对于是否全部更新因为每个节点都会被扫到，所以最短路径上的点一定会被除起点以外的其他节点更新
对于是否是最短路，因为对于每一个源点的最短路径都是可以更新的拐点，对于每个拐点，已经记录过了从其他点来的
最小距离，所以是正确的
上述可能纯属考场意淫。。
最新文章
- Main()
- 关于WEB Service&WCF&WebApi实现身份验证之WCF篇（1）
- checkbox属性checked="checked"通过js已设置，但是不勾选
- 如何打印出lua里table的内容
- 【jQuery基础学习】11 jQuery性能简单优化
- javascript原生dom操作方法
- 转：Order&Shipping Transactions Status Summary
- css在各浏览器中的兼容问题
- Python使用SMTP发送邮件[HTML格式、送带附件]
- JNI-使用RegisterNatives注册本地方法
- C# 数据结构 基础 论述
- Cocos2d-x3.0 捕Android菜单键和返回键
- 【安卓开发】Android系统中Parcelable和Serializable的区别
- KnockoutJS知识规整目录
- 关于while read line 循环中变量作用域的问题
- fillder--信息面板显示请求耗时列
- socket 编程中。 服务端用到多线程
- Luogu P3327 [SDOI2015]约数个数和
- vuex操作
- java第四节 类的继承/抽象/接口/多态性