ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

P2860 [USACO06JAN]冗余路径Redundant Paths tarjan

题目链接 https://www.luogu.org/problemnew/show/P2860 思路缩点，之后就成了个树一般的东西了然后（叶子节点+1）/2就是答案，好像贪心的样子，lmc好像讲过诶 cpp #include <iostream> #include <c...

tarjan 树

2019-02-18

0 616

4514: [Sdoi2016]数字配对费用流

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=4514 思路 EK直接贪心做 <0的时候加上剩余返回二分图a->b的时候把b->a也连接上最后除2 整除和贪心可只知道它是对的代码 #include <...

费用流二分贪心

2019-02-18

0 483

P4137 Rmq Problem / mex

目录链接思路线段树莫队链接 https://www.luogu.org/problemnew/show/P4137 思路做了好几次，每次都得想一会，再记录一下可持久化权值线段树区间出现存最小的下标然后线段树上二...

莫队可持久化线段树卡常

2019-02-18

0 522

SP10707 COT2 - Count on a tree II 莫队

链接 https://vjudge.net/problem/SPOJ-COT2 https://www.luogu.org/problemnew/show/SP10707 思路 dfs欧拉序转化为普通莫队（并不算树上莫队，不过也可做) 好神仙啊，原来欧拉序是可以求任意两点的点，不过要加lca。...

莫队 dfs序

2019-02-16

0 559

4819: [Sdoi2017]新生舞会分数规划

题目 https://www.lydsy.com/JudgeOnline/problem.php?id=4819 思路分数规划的模板题？(好菜呀) 假如n=3吧(懒得写很长的式子) \(c=\frac{a_1+a_2+a_3}{b_1+b_2+b_3}\) 我们先二分一下，变为判定性问题 c...

网络流二分答案分数规划

2019-02-16

0 568

[Sdoi2017]序列计数矩阵优化dp

题目 https://www.lydsy.com/JudgeOnline/problem.php?id=4818 思路先考虑没有质数限制 dp是在同余系下的，所以\(f[i][j]\)表示前i个点，和为j的方案数转移就是\(f[i][j]=f[i-1][k]+g[(j-k)\%p]\) g...

DP 矩阵快速幂

2019-02-16

0 526

SDOI2017相关分析线段树

题目 https://loj.ac/problem/2005 思路 \[ \sum_{L}^{R}{(x_i-x)^{2}} \] \[ \sum_{L}^{R}{(x_i^2-2*x_i*x+x^{2})} \] \[ \sum_{L}^{R}{x_i^2}-2*x*\sum_{L}^{...

线段树

2019-02-15

0 516

loj SDOI2017数字表格

目录太才了注意，错误代码太才了 \(\prod \limits_{i=1}^{n}\prod\limits_{j=1}^{m}f[gcd(i,j)]\) \(\prod\limits_{k=1}^{n}f[k]^{\sum\limi...

莫比乌斯反演

2019-02-15

0 413

bzoj 2527: [Poi2011]Meteors

昨天写了一晚，越写复杂度越感觉不对，早上一想果然是假的。 (这里n,m,k我就不区分了) 首先一个城市的询问可以很容易的二分 check用树状数组维护区间(区间修改，单点查询的那种) 一次是\(O(nlog^2n)\) n次就是\(O(n^2log^2n)\) 但是我们check的时候都...

整体二分

2019-02-15

0 517

BZOJ2440: [中山市选2011]完全平方数

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2440 题解二分，转化为判定1到x内的无平方因子的数的个数 (范围自己二分着试) 然后容斥含0个平方因子-含1个平方因子+含有两个平方因子~~~~ 于是观察一下上面那个式子，再联想mo...

莫比乌斯函数二分容斥

2019-02-14

0 600