ComplexPug

分类

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

/ 注册

全部文章（共277篇）

cf1173 D. Nauuo and Circle

链接 [cf]http://codeforces.com/contest/1175/problem/F) 思路当1在1的位置做dp[i]为i的子树所有的方案。一条性质是i的子树所占圆上的位置一定一段连续的。那\(f[i]\)的方案就是$(son[i]+(i!=1))!\prod\limi...

DP

2019-06-09

0 610

bzoj3745: [Coci2015]Norma 分治，单调队列

链接 bzoj 思路首先\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=i}^{j}max(a_k)\)可以用单调队列求解。参见? 求解此题目，我们分治。计算\([l,mid]\)对\([mid+1,r]\)的贡献。我们...

分治前缀优化单调队列

2019-06-09

0 612

bzoj1176: [Balkan2007]Mokia cdq

链接 bzoj 思路 cdq入门题，拆成4个矩阵，然后cdq。代码 /************************************************************** Problem: 1176 User: gryz2016 Langu...

cdq

2019-06-09

0 517

luoguP3964 [TJOI2013]松鼠聚会

链接 luogu 思路切比雪夫距离有max，不好优化。但是我们能转化成曼哈顿距离，只需要 \((x,y)变成(\frac{x+y}{2},\frac{x-y}{2})\) 相反的曼哈顿距离转切比雪夫距离 \((x,y)=>(x+y,x-y)\) 详情见attack 剩下的就是sort...

2019-06-06

0 507

bzoj 2716: [Violet 3]天使玩偶

bzoj 2716: [Violet 3]天使玩偶链接 bzoj 思路 80s的评测交了五六发、、、貌似卡评测了只讨论在左下角的点，cdq分支求出。然后剩下的用坐标对称啥的再来三遍。不过每次还原这样是会T的。对x排序，然后搞就过了，（我也不知道，不过还是40s左右） KD-tree...

cdq 树状数组

2019-06-06

0 476

cf1175 D\E

链接成功带wxy掉分、、全程0输出 D E D 题意把序列分成连续k段，f(i)表示i这个在第几段 \(\sum\limits_{i=1}^{n}a_i*f(i)\)最大思路想象成从k层积木依次递减先把积木搭满，也就是\(sum_n*k\) 然后考虑删除积木，删除k-1个最小的前...

CF

2019-06-06

0 524

luoguP3374 【模板】树状数组 1 cdq

链接 luogu 思路可耐我连cdq都不会，Orz 陈丹琦代码 #include <bits/stdc++.h> using namespace std; const int N = 5e5 + 7; int read() { int x = 0, f = 1; c...

cdq

2019-06-05

0 539

bzoj1935: [Shoi2007]Tree 园丁的烦恼lowbit 离散化

链接 bzoj 最好不要去luogu，数据太水思路一个询问转化成四个矩阵，求起点\((0,0)到(x,y)\)的矩阵离线处理，离散化掉y，x不用离散。一行一行的求，每次处理完一行之后下一行的贡献直接叠加到当前。用lowbit统计错误离散化小心点，是y-1不是y 代码 #i...

树状数组离散化

2019-06-05

0 566

# [SDOI2019]移动金币阶梯博弈 dp

[SDOI移动金币链接 vijos 思路阶梯博弈，dp统计. 参见wxyww 代码 #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 7, mod = 1e9 + 9; int read()...

DP 博弈论

2019-06-04

0 682

P1501 [国家集训队]Tree II LCT

链接 luogu 思路简单题代码 #include <bits/stdc++.h> #define ls c[x][0] #define rs c[x][1] using namespace std; const int N = 1e5 + 7, mod = 51061; ...

LCT

2019-06-02

0 537