Atcoder训练记录

弱菜再来挖个坑QAQ坑好多人好懒我还打个毛OI(摔

我已经补了4

ARC058

[problem C] 直接暴力枚举做就行了

[problem B] 考虑把合法路径拆成两段,从(1,1)(H-A,i),再从(H-A+1,i)(H,W),直接计数即可,时间复杂度O(n\log n)


AGC018

[problem A] 两个数相减得绝对值一定是两个数的GCD的倍数,

[problem B] 考虑答案具有二分性,我们二分答案,然后每个数优先选第一喜好的课,然后考虑是否有课GG,有的话就把选了这门课的往后推,推不了就显然是false。

[problem C] 把人按照A_{i}-B_{i}排序,这样满足A_{i}-B_{i}\leq A_{j}-B_{j},移项得A_{i}+B_{j}\leq A_{j}+B_{i},也就是证明给史努比银币的一定全都在给他金币的前面。这样枚举下断开点,多余的全都归给铜币即可。


ARC078

[problem C] 子集和dp

[problem D] 考虑黑白染来染去一定会在某个点相遇,而所有的点,黑先到给黑,白先到给白,然后比较下就行了。正确性显然,搞个BFS即可。

[problem E] 首先我们用1,10,100...去试这个数的位数,如果试到1e11还没有N,就证明,数一定是我们试的数中的某一个,大力做就行了。不然的话,我们二分答案的值,把答案*10就一定可以直接比较出来。

[problem F] f(s,t)表示只用s中的点,构造出一条且仅有这一条从1t的路径的最小需要删的边权之和。一种转移情况是,枚举t能到达的点x,删掉其他点到x的所有边的边权。第二种情况是,枚举不与s相交的任意一个子集y,考虑删掉s中除了t以外,所有点到y中的点之间的边权。我想了下第二种情况,发现他这样做的原因实际上是为了保证不会让s中的点通过y中的点,再绕回s中的点,或者直接从y中的点到达t。但是这样很可能会多删掉一些边,但这个我们不关心,为什么?因为第一种情况会在以后把这个失误给矫正过来。


ARC079

[problem F] 考虑是一棵基环树,边上的权值大力固定一个点即可。由于是个弱连通图所以时间复杂度可以保证。


ARC080

[problem E] 考虑第一个数一定是偶数位,第二个数一定是奇数位(下标从0开始),然后就可以用区间裂解的trick,区间最小值用ST表做即可。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注