三笠.阿克曼

分类

并查集(1) 思维题题解(2) 搜索题解(1) 数位DP(1) 数论(1) 树形DP题解(2) 树状数组和线段树题解(10) 线性DP(3)

/ 注册

全部文章（共18篇）

I love exam 01背包+分组背包

题目链接题目大意：有n个学科需要考试，每门学科有mi种复习材料，每个材料需要花费v天来阅读，得到w的分数，每门课得分上限为100分。你还有t天的复习时间，最多可以挂p门课的前提下最多可以的多少分。总体思路：对每门课的所有复习材料做01背包，f[i][j]表示第i门课花费j天最多可以获得多少分数，每一...

背包问题

2021-08-25

1 581

CF620E New Year Tree (线段树+状压）

题目链接题目大意：树初始每个节点也有颜***r>总体思路：题目是在每一棵子树整体做一个修改，所以我们就没有必要用树剖来写了。直接通过一边DFS来的到整棵树DFS序列，于是我们就将问题在一棵子树上进行操作转化为在一段连续的区间经行操作，这时候我们就可以用线段树来维护区间信息了。我们可以注意到所有...

线段树状态压缩

2021-08-15

1 478

UVA12991 Game Rooms (线性DP数列分段问题）

题目链接题目大意：总体思路：f[k][i]表示第i层楼选择的是K的最小代价最终的一段段连续的0区间加上连续1区间，0和1连续区间循环。如果[l, r]区间放乒乓球桌那么l-1和r+1就必须是游泳池。显然我们就不需要考虑去打乒乓球的人的贡献，因为他们自己所在的楼层就有其想要的设施；拥有的人分为两段贡献...

线性DP

2021-08-15

1 710

洛谷P3384 【模板】轻重链剖分/树链剖分+线段树

题目链接题目大意：已知一棵包含 N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：1、 x y z，表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。2、 x y，表示求树从 x 到 y 结点最短路径上所有节点的值之和。3、 x z，表示将以 x 为根节点的子树内所有...

树剖线段树

2021-08-14

1 536

P4514 上帝造题的七分钟（二维树状数组）

题目链接题目大意：总体思路：二维差分数组d[i][j]等于a[i][j]和a[i-1][j]+a[i][j-1]-a[i-1][j-1]的差=a[i][j]-(a[i-1][j]+a[i][j-1])+a[i-1][j-1](可以根据二维前缀和来理解）。1、在二维矩阵进行修改操作，就是在二维差分数组...

树状数组

2021-08-13

1 531

Counting Stars HDU 7059（线段树）

题目链接题目大意：给一段数，进行三种操作1、将一段区间所有数减去ai&-ai2、将一段区间所有数加上2^k<= ai <2^(k+1)3、区间和总体思路：求区间和可以直接用普通线段树来维护，但是操作1和2都不是线段树支持的区间操作。对于操作1，我们可以采取直接暴力更新，但是我们会...

线段树

2021-08-13

1 537

CF242E XOR on Segment （拆位线段树）

题目链接题目大意：总体思路：这题是动态的区间修改和区间求和，毫无疑问要用到线段树进行操作。但是普通的线段树无法进行区间异或操作。通常遇见异或问题一般两种思路。1、做异或前缀和。2、就是拆位。01Trie就是这种思想的一个体现。我们可以发现异或运算的两个性质：1、 0、1异或0，原来的数保持不变...

线段树

2021-08-08

1 741

牛客小白月赛9 D、书上求和（DFS序+线段树）

题目链接题目大意：输入：5 50 0 0 0 01 21 33 43 51 1 31 3 71 4 51 5 62 1输出：599 总体思路：因为是对一棵子树整体进行操作+k,所以我们可以用DFS序列将一棵树转化为一个序列，然后再在序列中用线段树来进行区间操作。线段树维护平方和也是老套路了。代码实现...

线段树

2021-08-04

1 508

牛客小白月赛9 E、换个角度思考（离线+树状数组）

一道非常好的题目题目链接题目大意：输入：5 11 2 3 4 51 5 3输出：3 总体思路：这题用离线+树状数组来写最简单。我们可以发现每一次查询会有两个变量，一个是区间左右的整体，另一个是K值。所以我们可以固定其中一个值来求另一个值。方法一：在保证当前所有数都是小于等于K的情况下询问区间[...

离线树状数组

2021-08-04

1 504

鸽子（线性DP）

题目链接题目描述：思路分析：DP[i][j]表示将初始位置为K的电脑进行第i次操作后当前位置为j的最小不执行命令次数。这题的DP方程是真的巧妙，因为我们考虑的是初始位置为K的电脑最终放在j位置的最小不执行次数，所以每一个交换命令意味着，1、这一层交换不执行，坏电脑在X位置的最小并不执行次数就是就...

线性DP

2021-08-02

1 509