2019.11.11&12题解
2019-11-11 16:00:50来源:博客园 阅读 ()
2019.11.11&12题解
Day1
考的不是很好,T1T2没区分度,T3想的太少,考试后期几乎都是在摸鱼,bitset乱搞也不敢打,只拿到了35分,跟前面的差距很大
A. 最大或
标签:
二进制+贪心
题解:
首先x,y中一定有一个是R,考虑L的取值:对于每一位分为x中有没有讨论:
1>有 如果这一位不加以后全加可以>=L则不选,否则选
2>没有 如果这一位选上以后全不加也无法<=R则不选,否则选
因为位数从高到低枚举,所以贪心是正确的
B. 答题
标签:
折半搜索+二分
题解:
2<=n<=40,显然是要折半搜索的,答案满足单调性,可以二分判断,check时复杂度最好是1<<20,而不是2e7的值域
说实话这道题比T1要简单
C. 联合权值·改
标签:
啊啊啊起个标签好蓝啊
题解:
首先证明环的数量是$m*sqrt(m)$的:
考虑最坏情况:一定是一个竞赛图,那么点数就是$sqrt(m)$,环数最多是$m*sqrt(m)$
有了这个性质下面的算法便有了复杂度保证:
1>对于第一问:
把每个点的出边按w[to]降序排序,考虑枚举$ x,y((x,y)\in{edge}),z((x,z)\in{edge}) $
只需要找到第一个不是三元环的z点便可以更新答案,复杂度与枚举到的环有关,而每个环最多会被枚举到3次,所以复杂度是对的
2>对于第二问:
考虑容斥:
用每个点的出点的权值和的平方减去平方的和,
再减去三元环的的情况,我是枚举u,v用bitset求出b[u]&b[v].count()便是有u,v的三元环的个数
原文链接:https://www.cnblogs.com/AthosD/p/11838633.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- Building & Debugging chromium on CLion for Linu 2020-05-19
- 洛谷P1164->小A点菜 2020-05-18
- 表达式·表达式树·表达式求值 2020-04-29
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash