ComplexPug

未归档

做题记录(1)

/ 注册

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

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 564

[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 520

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 513

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 411

bzoj 2527: [Poi2011]Meteors

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

整体二分

2019-02-15

0 512

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

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

莫比乌斯函数二分容斥

2019-02-14

0 595

GCD与莫比乌斯反演的勾当

目录机房最后一个学懵逼钨丝的人题目一题目 bzoj1101 机房最后一个学懵逼钨丝的人题目一链接题目没找到求\(\sum_{1}^{n}\sum_{1}^{m}gcd(i,j)\)...

莫比乌斯反演

2019-02-14

0 577

2870: 最长道路tree

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2870 思路先把树转化为二叉树再链分治 %%yyb 代码 #include <iostream> #include <algorithm> #include...

链分治

2019-02-13

0 569

bzoj2152: 聪聪可可点分治

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2152 luogu爆搜都能过，总时间超过100ms就是写错了思路直接mod上面跑点分治就行了，又是模板代码 #include <cstdio> #include &l...

点分治

2019-02-12

0 525

3545: [ONTAK2010]Peaks 平衡树，最小生成树

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3545 离线询问，按照权值排个序就是在克鲁斯卡尔时候维护个treap，到时候挨个查询一下就好了 nb的gzy说要要在线才是呢，nb 代码 /********************...

最小生成树 fhqtreap

2019-02-12

0 494