牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共9篇）

图论杂题

矩阵游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1059 刚开始以为只要每行每列都存在一个1，就是可行的解，然后发现可以被yxm简单的数据hack掉： 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 正解是...

图论二分图树上差分桶线段树 wqs二分

2019-07-16

0 386

奇袭 CodeForces 526F Pudding Monsters 题解

考场上没有认真审题，没有看到该题目的特殊之处：保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样的。于是无论如何也想不到复杂度小于$O(n^3)$的算法，只好打一个二维前缀和草草了事。所以还是要仔细审题。 $O(n^2)$算法：因为每行上只有一个军队，...

分治桶

2019-07-16

0 341

模拟17 题解

A. 入阵曲求每一行的前缀和，枚举左右端点，O(n)扫下去，顺便更新桶。维护栈清空桶中的内容。 B. 将军令 k=1，小胖守皇宫弱化版。与小胖守皇宫比较，发现特殊性质：点没有权值。考虑贪心。每次找出深度最深的点，点亮它的k级父亲。 1.点...

差分 dp 贪心桶

2019-08-11

0 821

模拟23 题解

A. mine 设dp(i,0/1/2/3,0/1)表示前i位，且第i位填入0/1/2/炸弹的方案数。当第i位填入1的时候，需要关注炸弹在1的左侧或者右侧，故加半维表示炸弹在1的哪一侧，当i为不为1，最后一维无意义。简单转移。 B. water 第一眼：直接考虑临...

dp 最小生成树莫比乌斯函数桶容斥

2019-08-16

0 407

模拟38 题解

A. 金显然是问gcd是否为1 高精取模 B. 斯诺(snow) 考虑问题的逆问题。有多少区间是不合法的。显然一个区间，最多在考虑一种颜色的情况下不合法，所以不用容斥。推一下不合法条件的式子，然后发现要求一个前缀和。树状数组就一个log了。发现每次查询...

wqs二分 dp 桶

2019-09-07

0 354

模拟37 题解

A. 简单的区间看到这种题，一眼就是枚举最值，则确定左右区间，统计跨最值点的答案。维护前缀和后缀和就完了。于是自然地想到用个主席树，还是枚举小的区间，复杂度$O(nlog^2n)$。复杂度证明见模拟31 C.English 正确的算法一定无法避免枚举小区间，已经带了一个log， ...

启发式合并单调栈 ST表桶分治组合计数 dp

2019-09-06

0 502

模拟63 题解

A. Median 线性筛完质数，就会发现给的时间已经快没了。所以只能$O(n)$求$n-k$个中位数？不会做，所以打权值线段树。在权值线段树上二分找第k大值，可以做到$O(nlogn)$。打$zkw$线段树，比传统线段树快一倍，然而并没有什么用，仍然T70。题中确实给出了一些...

dp 桶贪心

2019-10-07

0 407

模拟79 题解

A. 树发现问题是树上对祖先链维护单调栈，然后分别二分权值和深度。因为已经做过一个类似的题，直接维护一个基于倍增进行二分的链栈（或者叫可持久化单调栈？）就完了。 B. 环 circle 一个结论是：在竞赛图中，要么不存在环，要么存在的最小环为三元环。虽然想不到，...

单调栈图论桶结论题

2019-10-20

0 365

模拟95 题解

A. 简单计算发现向下整除会损失一些贡献，然后就无法直接用等差数列考虑。如果不计损失，那么答案是一个等差数列求和。可以考虑损失的是什么，即$\sum \limits_{i=1}^{p}i*q\ mod\ p$。这个式子就很好，不妨设$gcd(p,q)=1$，因为$gcd$不为1的情况...

贪心桶

2019-10-31

0 338