10.16 模拟赛
10.16 模拟赛T1首先,对于全0或者全1可以手推或者打表发现是卡特兰数。 假设从0切换到1或者1切换到0,一定有$ai \leq b_i \leq b{i + 1} \leq a_{i + 1}$ 相当于一定把前$i$个位置填完了才会开始填$i + 1$个位置。 所以直接乘起来就好了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565 ...
阅读更多
10.15模拟赛
10.15 模拟赛原题场。 A 石子暑假,概率与期望ppt中的经典例题的一道题。。 考虑令$x_i$表示第$i$堆石头在第几次被取。那么有 $x_1 = \sum_i{ [x_i \leq x_1] } = 1 + \sum_i{[x_i < x_1]}$ 两边同时套一个期望,由期望的线性性 $E(x_i) = 1 + \sum_iE([x_i < x_1]) = 1 + \sum_i{P([x_i < x_1])}$ 然后求的就是第$i$堆石头比第一堆石头先取的概率。 这个可 ...
阅读更多
10.14模拟赛
10.14 模拟赛抱歉咕了一天,前一天晚自习搞oj去了。 A 序列开始看错题了1h20分钟。。。。一场爆炸。。 枚举开头是0还是1,就已经确定了每个数字到哪里(这个贪心显然) 然后我们考虑怎样让字典序变小,我们注意到只有同往一个方向走,且可以第一次的可以覆盖第二次的起点的时候可以任意交换。可以拿一个set或者pq维护一下。 真的毒瘤。。 12345678910111213141516171819202122232425262728293031323334353637383940414243444 ...
阅读更多
10.12 模拟赛
10.12 模拟赛T1首先有一个显然可以得到的结论,每次减去最大值一定最优。 只会最无脑的做法。。每次减去最大值,复杂度$O(n)$,虽然减了一些枝但还是显然过不去 其实感觉60分做法就很有意思了。 对于$n \leq 10^{12}$ 考虑分开考虑前六位和后六位,这个时候前六位的变化只有$O(\sqrt n)$次。 考虑当前六位的最大值为某一个值时,后六位分别需要多少次才可以变成负数,以及会变成多少 复杂度是$O(\sqrt n)$ 对于$n \leq 10^{18}$ 也是一个挺奇妙的搞法吧 ...
阅读更多
Peaks Gym 100365H
Peaks ( Gym 100365H )这题nk做法还挺正常的。。后面那个循环就很恶心了 考虑 dp[i][j] 表示长度为i的排列,恰好有k个峰的方案数量。 然后转移就是把 i 插入 i-1 的排列。 i显然是i-1的排列里面最大的数,然后插入就只有两种情况: 插入在峰的左右,由于峰不可能相邻,所以可以插入在 2j 个位置 插入在爬山的时候,那么峰的数量+1 $dp[i][j] = 2j\times dp[i-1][j] + ( i - 2(j - 1) )dp[i-1][j-1]$ 其 ...
阅读更多
手写Bitset优化
一种优化方法,具体例子可以看这里 这里只是存一下手写Bitset的板子 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091struct Bitset{ unsigned a[1600]; voi ...
阅读更多
Sums gym100753M
Sums gym100753M同余最短路模板,然而这个东西貌似也可以做去年D1T2 首先我们选择一个模数作为基准,然后剩下的这样连边: 对于一个面值为 x 的硬币 ,当前在 u 这个点(感性理解一下吧) u + x < Mod 这种情况直接从u向 u + x 连一条长度为0的边,表示我们在 0 * M + (u + x) 的时候就已经可以凑出了 u + x > Mod 这种情况下可以 u 向 ( u + x ) mod Mod 连一条长度为1的边,表示通过x的硬币至少在 1 * ...
阅读更多
Break up CF700C
Break upCF700C 首先考虑只能删一条边的做法,我们可以找出所有的桥,然后随便跑一条 S 到 T 路径,如果这条路径上有桥就说明可以,否则不行 发现这个做法其实是 O(M) 的 那么可以先随便找一条 N 到 M 的路径,分别尝试删这条路径上的边再套上面做法就好了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606 ...
阅读更多
Cycling City CF521E
Cycling City毒瘤题 首先建dfs树,由于是个无向图所有返祖边都是连向祖先的。 判是否有解其实很简单,只要图不是一个仙人掌就有解了。 仙人掌有关可以看这个博客 但是这道题由于要输出路径成功变成了一个一个顶俩的题。。。。。 通过判仙人掌我们确认了一个点,它连向自己父亲的路径至少被两个边所覆盖。 然后我们可以从这个点开始深搜,找到这两个返祖,注意是返向这个点祖先的路径。 于是有起点就是这两个路径下端的lca,终点就是这两个路径上端点最深的一个(画图很好看出来的) 然后有哪些路径就显然了。。 ...
阅读更多
Unique Path AGC 038 D
Unique PathAGC 038 D 考虑如果两个点之间只能有一个边它们就把它们缩起来,那么最后缩起来的每一块都只能是一棵树。 如果两个点之间必须不止一个边,并且在一个连通块,显然无解。 首先把所有树给连好,现在的可用的边的数量只有$m - n + c$了。 然后两个连通块之间如果有超过一条边,连通块内部的点显然不只一条路径了。 其他情况,如果我们给连通块连边的时候每个连通块都只一直用一个点来往外连,就可以保证所有连通块都满足要求。 如果不存在两个点之间不只一个边的情况 那么只要可用的边的 ...
阅读更多