「10.8」simple「数学」·walk「树上直径」
2024-10-19 10:07:25
A. Simple
本来以为很难,考场瞎推了推好像会了......
想起小凯的诱惑,迷??
首先$n$,$m$,$q$同除$gcd(n,m)$,显然$q$以内的数假如不是$gcd$的倍数,那么一定不能被表示
然后在求新的$q$以内不能被表示的数
因为现在$n$,$m$互质,所以$n\times m$至q的数一定能被表示,我们就把范围缩小到$min(n*m,q)$以内
因为在$n\times m$以内,所以取不同$n$,$m$系数时结果不同
所以就因为$m$很小,直接枚举$m$的系数,最多枚举$n$个数,所以$n\times T$复杂度。
B. Walk
$w\leq 100$打法:
显然将问题转化为当$gcd$为某数时的最大直径,倒着求一边后缀最大值即可,
(听说打$n\times w$的T飞了,然而我打的$n\times w\times w$的没T)
正解:
思路很新颖
将每个边分解出约数,存在$vector$里,然后求出每个约数的最大直径,
注意清空不能全清,
复杂度最坏是$n\times \sqrt{w}$,但应该数据没有卡
最新文章
- <;%@ page contentType=";text/html; charset=utf-8"; language=";java";%>;每一个字符的含义
- 简单的XML操作类
- atitit. java queue 队列体系and自定义基于数据库的队列总结o7t
- 如何在android的mk文件添加依赖已经编译好的库
- JavaScript实现搜索联想功能
- QuickXdev+sublime text打造quick-cocos2d-x开发环境
- Centos6.5网络无法连接问题
- ffmpeg 的tutorial
- 理解和运用javascript中的call及apply
- RAC之常用方法-----新手入门
- Android 学习笔记二 自定义按钮形状 颜色 点击渐变
- string 迭代器
- py库:os、shutil、pathlib
- php微服务框架 PHP-MSF 的容器部署和使用
- Vue-Vue列表渲染v-for
- MySQL与宿主Linux之间交互式执行命令
- shiro 入门
- Centos7安装Wkhtmltopdf -- nodejs将html转pdf
- 微信网页JS分享,微信二次分享无缩略图问题
- Nginx 反向代理时获取用户的真实 IP