首页 > 其他分享 >1.29

1.29

时间:2023-01-31 21:48:26浏览次数:57  
标签:frac log text 异或 1.29 即可 Graph

ABC287Ex - Directed Graph and Query

顺序枚举点,记 \(a_{i,j}\) 表示从 \(i\) 点出发能否到达 \(j\) ,从初始对于每条边 \((u_i,v_i)\) ,有 \(a_{u_i,v_i}=1\) ,然后跑 \(\text{floyd}\) 即可,\(\text{bitset}\) 优化一下即可做到 \(O(\frac{n^3}{64})\) 。

ABC286G - Unique Walk

将不在 \(S\) 里的边加上缩点判欧拉回路即可。

ABC286Ex - Don't Swim

将起点、终点跟多边形的每一个点放在以其跑凸包,如果两个点都在凸包内,就是两边取个 \(\min\) ,否则就是两点直线距离。

CF1777E. Edge Reverse

考虑如果缩完强联通分量之后,只存在一个无入度的点的话,就符合条件。直接二分答案,每次判定就是将边权小于二分值的边加上反向边,跑 \(\text{tarjan}\) 即可,时间复杂度 \(O((n+m) \log w)\) 。

CF1777F. Comfortably Numb

此题直接考虑以每个点为左端点的区间并不好做。由于所求有一个 \(\max\) ,我们可以直接通过枚举区间的最大值来解决。这个可以使用笛卡尔树。注意异或的性质,区间 \([l,r]\) 异或和可以转化成 \(r\) 的前缀异或和异或上 \(l-1\) 的前缀异或和。

因此我们对于笛卡尔树上的每一个节点, 用 \(\text{0-1 Trie}\) 维护这个节点子树内所有点的前缀异或和,向父节点合并更新的时候启发式合并就行了。时间复杂度 \(O(n \log n \log w)\) 。

CF1780E. Josuke and Complete Graph

如果小于等于 \(l\) 的 \(a\) 在 \([l,r]\) 的子图中出现,那么等价于:

\[\left \lfloor \frac{r}{a} \right \rfloor-\left \lfloor \frac{l-1}{a} \right \rfloor \geq 2 \]

对于后者由于 \(l \leq 10^9\) 不同的取值只有 \(\sqrt{10^9}\) 种,直接数论分块就可以做了。

CF1780F. Three Chairs

考虑容斥,先让答案是 \(n \choose 3\) ,然后去除掉所有的以 \(a(a>1)\) 为公约数的不合法的方案数,容斥系数是 \(\mu(a)\) 。

CF1780G. Delicious Dessert

\(\text{SAM}\) 板子题,预处理出 \(1-n\) 所有数的约数即可。

CF1790G. Tokens on Graph

只考虑可行的点跑最短路,然后在看某个出发点边上可行点数量,如果有连续两个点在边上就可以走无限次。

标签:frac,log,text,异或,1.29,即可,Graph
From: https://www.cnblogs.com/oscaryangzj/p/17080850.html

相关文章

  • 上周热点回顾(1.23-1.29)
    热点随笔:· C#中检查null的语法糖,非常实用 (王者天涯)· ChatGPT开发实战 (哥不是小萝莉)· 不过是享受了互联网的十年红利期而已。 (why技术)· ORM哪家强?java,c#,p......
  • 1.29 vp Educational Codeforces Round 142 (Rated for Div. 2)
    A-GamingForces题意有n只怪兽,每个怪的血量是\(a_i\),有两种操作:1.直接消灭这只怪2.消灭两只血量为1的怪问最少需要多少次操作可以将怪全部杀死思路可以想到,操作二......
  • 闲话 23.1.29
    闲话感觉我现在得先提升自己的specify水平(这题我少说用了七八张草稿纸(只算写了主要过程的好题!loj:LightNovelOJ不要越级做题。——大师APJifengc今日推歌:1/6......
  • 1.29数论课笔记
    o.O一、\(O(\sqrt{n})\)判断质数枚举\(\left[2,\sqrt{n}\right]\)中的数,判断是否能整除\(n\),如果都没有则返回\(true\)。为什么不用枚举\(\sqrt{n}\)以上的数:......
  • 【2022.11.29】windows server安装hyper-v
    在已经安装好的winserver2022上打好驱动,这个如果缺的话,可以在网上寻找就好了有个重要的核显驱动在因特尔官网英特尔®显卡–Windows*DCH驱动程序(intel.cn)激活WI......
  • 2022.11.29 vjudge构造、思路题
    WeightingaTree构造切入点:调整总结:图上的题,可以先考虑树上的做法。(尤其是构造题)首先我们要知道这种“点与跟他连着的所有边的关系”什么的题的套路就是找生成树。-......
  • 11.29小记
    会议号:795-775-9627首先是逝去的NOIP。我没想到NOIP2022倒在了我前面。总结就是题整体不难,但是有病。最有病的就是random_shuffle题目顺序。我觉得最优开题顺序......
  • 11.29
    今日内容1.SQL注入问题2.视图3.触发器4.事务5.存储过程6.函数7.流程控制8.索引相关概念9.索引数据结构10.慢查询优化11.联合索引全文索引12.插入数据13.更新......
  • 2022.11.29 No.4
    重庆最近要降温了,感谢东哥的京东,我的生活物资才不至于花冤枉钱去买学校“合作”的本地商城的衣物。昨天的数据还没出,前天新增近万,但是学校居然说要恢复线下了。不是......