ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

bzoj4316: 小C的独立集

bzoj4316: 小C的独立集链接 bzoj 思路不是环的边==没有上司的舞会。其他的，把环拿出来,考虑与深度最小的点u的交界处的点选不选，进行两次dp更新f[u] 代码 #include <bits/stdc++.h> using namespace std; co...

圆方树仙人掌 DP

2019-05-31

0 567

bzoj1023: [SHOI2008]cactus仙人掌图

1023: [SHOI2008]cactus仙人掌图链接 bzoj 思路仙人掌求两点间最短路最大。姑且叫他仙人掌的直径。 f[u]表示u为端点的最长的最短路当他是圆圆边，和树上一样dp转移。圆方边，取出环了进行别的dp。转化成带权的环上更新两端距离的最短路的最大值，单调队列。最后...

仙人掌圆方树 DP

2019-05-31

0 574

[SDOI2019]热闹又尴尬的聚会构造,贪心

[SDOI2019]热闹又尴尬的聚会链接 luogu loj 思路第一问贪心？的从小到大删除入度最小的点，入度是动态的，打个标记。当然不是最大独立集。第二问第一问的顺序选独立集，不行就不要。选出来的一定是满足不等式的。每次最多删除p+1个，独立集个数是\(\lceil \frac{...

贪心构造

2019-05-15

0 511

SDOI2019快速查询

链接 vijos 思路虽然询问1e7，但他询问很有意思，所以最多修改1e5个。先把他们修改的点缩小到1e5之内并没有什么影响。然后维护mul和add。不修改很好弄，修改的点可以弄点式子加加减减弄出来，逆元线性推也是可以的。总的复杂度\(O(qlogq+tq+mod)\) 总结我考...

木得标签

2019-05-07

0 479

SDOI 二轮垫底鸡

SDOI 二轮垫底鸡 day0 准备爆零没啥好准备考试的，12.00出发，试机敲抄个ntt，在宾馆不知道颓啥。 day1 爆零爬山 T1noip的题目也放到省选上。第一档线段树？肯定不写，直接上100吧。万万没想到，我的码力居然如此的差劲，三个小时都没写出来。之后一小时就去看T2,T...

游记

2019-05-07

0 554

[SDOI2018]物理实验 set，扫描线，旋转坐标系

[SDOI2018]物理实验 set，扫描线，旋转坐标系链接 loj 思路先将导轨移到原点，然后旋转坐标系，参考博客。然后分线段，每段的贡献(三角函数值)求出来，用自己喜欢的平衡树，我选set。显然答案的一端是小线段的端点。然后扫描线求出最大的ans。代码 #include ...

平面几何 set 旋转坐标系

2019-05-04

1 597

bzoj [SDOI2014]数表莫比乌斯反演 BIT

bzoj [SDOI2014]数表莫比乌斯反演 BIT 链接 bzoj luogu loj 思路 \[ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}a*[f[gcd(i,j)]<=a] \] \[ f[]可以O(n)预处理出来 \] \[ ...

莫比乌斯函数莫比乌斯反演树状数组线性筛

2019-05-04

0 611

友链

脑子不好使，记不住人名，欢迎评论加友链 3 .txt skh 明年今日 GTBA 没有博客的wwc 2 大头 xmex lwl scx ikka cyh 1 很多小号的gzy yyh wxy axma 菜鸡dsr 1 mjt zzzzx lgj->...

友链

2019-05-04

0 462

P3327 [SDOI2015]约数个数和莫比乌斯反演

P3327 [SDOI2015]约数个数和莫比乌斯反演链接 luogu 思路第一个式子我也不会，luogu有个证明，自己感悟吧。 \[d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)==1]\] \[\sum\limits_{i=1}...

莫比乌斯反演莫比乌斯函数

2019-05-03

0 549

3495: PA2010 Riddle 2-sat 前缀优化

3495: PA2010 Riddle 2-sat 前缀优化链接 bzoj 思路不想说啥了，看hwim的吧，我去睡觉了zZ。代码 /************************************************************** Problem:...

2-sat 前缀优化

2019-05-02

0 544