传送门
正难则反。
考虑计算两人相遇的方案数。
先正反跑一遍最短路计数。
然后对于一条在最短路上的边(u,v)(u,v)(u,v)，如果(dis(s,u)*2<total&&dis(v,t)*2<total)说明两人可以在这条边上面相遇。
如果对于一个点从起点到它的距离刚好是最短路的一半也可以在这个点相遇。
代码
2018.11.05 NOIP模拟 规避（最短路计数）的更多相关文章
-
2018.11.05 NOIP模拟 相交（dfs序+bit）
传送门 又TMTMTM考原题真是服. 考虑到两条路径相交一定满足某一条的lcalcalca在另外一条路径上面. 于是分开统计有多少个lcalcalca在当前路径上面以及有多少个路径经过了当前的lcal ...
-
2018.11.05 NOIP模拟 列队（差分约束）
传送门 直接建边跑差分约束就可以了. 代码
-
2018.11.03 NOIP模拟 图（bfs/最短路）
传送门 显然如果AAA到BBB或者CCC到DDD走的不是最短路一定是有一段路径重合了,于是可以O(n2)bfsO(n^2)bfsO(n2)bfs出两点之间的最短距离然后枚举两个点作为重合的端点来更新答 ...
-
2018.11.08 NOIP模拟 班车（倍增+dfs+bit）
传送门 对于每个点离线处理出向上走2i2^i2i班车到的最上面的点. 然后每个询问(u,v)(u,v)(u,v)先把(u,v)(u,v)(u,v)倍增到刚好走不到lcalcalca的情况(有一个点如果 ...
-
2018.11.08 NOIP模拟 水管（简单构造）
传送门 仔细读题会发现只要所有点点权之和等于0一定有解. 如何构造? 直接当做树来构造就行了,非树边都赋值成0就行. 代码
-
2018.11.08 NOIP模拟 景点（倍增+矩阵快速幂优化dp）
传送门 首先按照题意构造出转移矩阵. 然后可以矩阵快速幂求出答案. 但是直接做是O(n3qlogm)O(n^3qlogm)O(n3qlogm)的会TTT掉. 观察要求的东西发现我们只关系一行的答案. ...
-
2018.11.07 NOIP模拟 异或（数位dp）
传送门 对于每个二进制位单独考虑贡献. 然后对于两种情况分别统计. 对于第二种要用类似数位dpdpdp的方法来计算贡献. 代码
-
2018.11.07 NOIP模拟 分糖果（贪心）
传送门 考虑 n = 2 时的情况:假定两个人分别为(a, b),(c, d),则当且仅当min(a,d) ≤ min(b,c)时,把(a, b)放在前面更优,否则把(c, d)放在前面更优 然后把n ...
-
2018.11.07 NOIP模拟 数独（模拟）
传送门 sbsbsb签到题. 读题时间比写题时间长系列. 写一个checkcheckcheck函数来检验当前时间段第(i,j)(i,j)(i,j)号格子能否放入kkk就行了. 代码
随机推荐
-
Businessworks的设计思想
Businessworks的设计思想基于一下三篇ATA: <从Eclipse平台看交易平台化>,强调微内核和扩展机制实现 <Google Guice平台模块化开发的果汁>,讨论 ...
-
HDU 1498 50 years, 50 colors (行列匹配+最小顶点覆盖）
题目:点击打开链接 题意:每个格子有不同颜色的气球用不同数字表示,每次可选某一行 或某一列来戳气球.每个人有K次机会.求最后哪些气球不能在 k次机会内 ...
-
ubuntu下搭建nginx+mysql+php-fpm站点
概述 Nginx ("engine x") 是一个高性能的 HTTP 和 反向代理 服务器,也是一个 IMAP/POP3/SMTP 代理服务器. nginx的优势在于能以低内存高 ...
-
linux文件系统下的特殊权限
SUID, SGID, Sticky 1 权限 r, w, x user, group, other 2 安全上下文 前提:进程有属主和属组:文件有属主和属组: (1) 任何一个可执行程序文件能不能启 ...
-
【转载】[ORACLE]详解not in与not exists的区别与用法
在网上搜了下关于oracle中not exists和not in性能的比较,发现没有描述的太全面的,可能是问题太简单了,达人们都不屑于解释吧.于是自己花了点时间,试图把这个问题简单描述清楚,其实归根结 ...
-
编程题：利用for循环打印 9*9 表?
利用for循环打印 9*9 表? 1*1=1 1*2=2 2*2=4 1*3=3 2*3=6 3*3=9 1*4=4 2*4=8 3*4=12 4*4=16 1*5=5 2*5=10 ...
-
spring mvc+redis实现微信小程序登录
本文将详细的介绍微信小程序的登录流程以及在ssm框架下如何实现小程序用户登录 登录流程概要 主要的登录流程可以参考官方提供的一张流程图: 1.微信前台页面: 在微信版本更新之后,提高了安全机制,我们需 ...
-
cocos creator主程入门教程（八）—— 代码结构
五邑隐侠,本名关健昌,10年游戏生涯,现隐居五邑.本系列文章以TypeScript为介绍语言. 这一篇简单介绍下代码结构,清晰的代码结构更有利于团队对项目的理解和维护. 1.前面我们介绍了一系列基础功 ...
-
C. Multi-Subject Competition 思维+前缀和+填表加减复杂度（复杂度计算错误）
题意: 给出n个学生 m类题目 每个人会做s[i]类的题 并且做这个题的能力为r[i] 组成一个竞赛队 要求可以选择一些题目 在竞赛队中 擅长每一个题目的 人数要均等 求max(sigma(r[ ...
-
使用requests库提交multipart/form-data 格式的请求
前言: Requests是用Python语言编写,基于urllib,采用Apache2 Licensed开源协议的HTTP库.它比urllib更加方便,可以节约我们大量的工作,完全满足HTTP测试需求 ...