题目链接题目大意：有n个学科需要考试，每门学科有mi种复习材料，每个材料需要花费v天来阅读，得到w的分数，每门课得分上限为100分。你还有t天的复习时间，最多可以挂p门课的前提下最多可以的多少分。总体思路：对每门课的所有复习材料做01背包，f[i][j]表示第i门课花费j天最多可以获得多少分数，每一门课f[i][j]看作一组物品，每组物品至多是能选一个，再做一个分组背包。g[i][j][k]表示前i门课，在挂j门课的前提下，第k天最多可以的多少分。这里i这一维不可以省略，因为我们最后全为负无穷表示挂科数超过P输出-1。 #include<bits/stdc++.h> using n...

题目链接题目大意：树初始每个节点也有颜***r>总体思路：题目是在每一棵子树整体做一个修改，所以我们就没有必要用树剖来写了。直接通过一边DFS来的到整棵树DFS序列，于是我们就将问题在一棵子树上进行操作转化为在一段连续的区间经行操作，这时候我们就可以用线段树来维护区间信息了。我们可以注意到所有颜色的种类是有60种，所有我们可以用状态压缩来表示一棵树不同颜色的状态。每一中颜色存在为1，对应状态long long的一位。区间合并我们用|运算就可以了，注意每次更新是将前一次的颜色覆盖掉，所以lazy和sum表示也会直接被覆盖掉。总之看见状态数比较小就可以考虑用状压来表示状态。代码实现： #in...

题目链接题目大意：总体思路：f[k][i]表示第i层楼选择的是K的最小代价最终的一段段连续的0区间加上连续1区间，0和1连续区间循环。如果[l, r]区间放乒乓球桌那么l-1和r+1就必须是游泳池。显然我们就不需要考虑去打乒乓球的人的贡献，因为他们自己所在的楼层就有其想要的设施；拥有的人分为两段贡献1~ (l+ r)>>1去l-1位置，(l+ r)>>1|1~r去r+1的位置。于是我们状态转移的时候就枚举以 ii 为右端点的极大连续段。转移方程就为cost为[l, r]区间另一类运动爱好者对答案的贡献。注意l=1&&r=n是不合法的状态要特判掉，因为题目...

题目链接题目大意：已知一棵包含 N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：1、 x y z，表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。2、 x y，表示求树从 x 到 y 结点最短路径上所有节点的值之和。3、 x z，表示将以 x 为根节点的子树内所有节点值都加上 z。4、 x 表示求以 x 为根节点的子树内所有节点值之和。 #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,r,p; int ch,x,y,z; int a[100005...

题目链接题目大意：总体思路：二维差分数组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、在二维矩阵进行修改操作，就是在二维差分数组上进行操作：d[x1][y1] += c;d[x1][y2+1] -=c;d[x2+1][y1] -=c;d[x2+1][y2+1] += c;2、在二维矩阵进行查询操作s[i][j]为二维差分数组的前缀和的前缀和（也就是矩阵的前缀和），求(x1,y1)和(x2,y2)的矩阵和=s[x2][y2]-...

题目链接题目大意：给一段数，进行三种操作1、将一段区间所有数减去ai&-ai2、将一段区间所有数加上2^k<= ai <2^(k+1)3、区间和总体思路：求区间和可以直接用普通线段树来维护，但是操作1和2都不是线段树支持的区间操作。对于操作1，我们可以采取直接暴力更新，但是我们会发现一个数减去一定次数的lowbit就会变为0，在0上进行更新操作是没有意义的，所以定义一个falg=1表示这段区间所有数都为0，那么这段区间就不用被更新了。对于操作2，我们发现每次加上2^k,其实就是将最高位乘以2，所以我们可以将一个数分为高位和低位两部分来处理。每次更新操作2，其实将区间高位整体...

题目链接题目大意：  总体思路：这题是动态的区间修改和区间求和，毫无疑问要用到线段树进行操作。但是普通的线段树无法进行区间异或操作。通常遇见异或问题一般两种思路。1、做异或前缀和。2、就是拆位。01Trie就是这种思想的一个体现。我们可以发现异或运算的两个性质：1、 0、1异或0，原来的数保持不变2、 0、1异或1，原来的数翻转于是这题可以用20棵线段树分别维护每一个位置上的数。这样就变成了维护一个01串，操作就是区间异或0和1，区间询问1的个数，这是个经典的区间翻转问题。后面差不多就是一个裸的线段树了，注意细节就可以了。 #include<bits/stdc++.h> using...

题目链接题目大意：输入：5 50 0 0 0 01 21 33 43 51 1 31 3 71 4 51 5 62 1输出：599 总体思路：因为是对一棵子树整体进行操作+k,所以我们可以用DFS序列将一棵树转化为一个序列，然后再在序列中用线段树来进行区间操作。线段树维护平方和也是老套路了。代码实现： #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=23333; ll n,q; ll a[100005];//记录每个点的初始值 //int b[100005]; ll df...

一道非常好的题目题目链接题目大意：输入：5 11 2 3 4 51 5 3输出：3 总体思路：这题用 离线+树状数组 来写最简单。我们可以发现每一次查询会有两个变量，一个是区间左右的整体，另一个是K值。所以我们可以固定其中一个值来求另一个值。 方法一：在保证当前所有数都是小于等于K的情况下询问区间[l, r]有多少个数。我们先将ai和K从小到大排序，将ai对应的位置加1，每次查询区间[l, r]有多少个数小于等于K，只需要查区间[l-1, r]存在的数的个数。代码实现： #include<bits/stdc++.h> using namespace std; int n,q; in...

题目链接题目描述：  思路分析：DP[i][j]表示将初始位置为K的电脑进行第i次操作后当前位置为j的最小不执行命令次数。这题的DP方程是真的巧妙，因为我们考虑的是初始位置为K的电脑最终放在j位置的最小不执行次数，所以每一个交换命令意味着，1、这一层交换不执行，坏电脑在X位置的最小并不执行次数就是就在上一层状态x不执行次数加一，2、执行就是坏电脑在Y的位置移到了X位置，所以坏电脑在X位置的最小不执行次数就等于上一层坏电脑在Y位置的最小不移动次数（第一次见这样的状态转移方式记录一下）。因为每一层只交换命令的x,y，其他位置不变所以时间复杂度为O（m). 题目代码： #include<bit...

题目链接题目描述：题目大意：一个僵尸在一个N*M的矩阵里面初始位置为（1，1），它只能向有或向下走，且矩阵中有些点有土豆雷它无法走到这个点，求僵尸能够走到的所有点的个数。 思路分析：通过题目意思分析我们可以知道，知道一个将能走到一个点，当且仅当它的上面的点或左边的点至少有一个能走到，那么僵尸才能走到这个点（矩阵外的点看作是不能走的点）。第一行是一个特殊情况，因为题目保证（1，1）点是可以达到的，所以我们设边界（0，1）也是可以到达的。所以我们可以根据上一层的状态来确定下一层，能够到达的点。在每一层中我们找到连续无土豆雷点区间，在上一层中我们找到相同区间中第一个可以到达点的下标（对应当前层），从...

题目链接题目大意：有一串0，1组成的序列，每次A会询问B,l-r一段区间总含有1的个数是偶数还是奇数。B会回答是奇数还是偶数，但是B可能会撒谎。比如：B曾经回答过1-3中有奇数个1，4-6中有偶数个1，但是后面问B，l-r中有1的个数是奇数还是偶数，B回答是偶数，这与前面的回答相矛盾，所以B说谎了。题目要求出前1~k个数是正确的，求K是多少。 输入：输入N表示01串的长度，M表示的询问次数，接下来M行，每行输入两个数a,b和even/odd,a,b表示区间的左右端点，even表示偶数，odd表示奇数。输出:K.1、带权并查集总体思路：我们可以用一个sum数组来记录前i个有偶数个1还是有奇数个1...

题目链接题目大意：给一根无根树，让你求以各个节点为起始点，每个节点到达的最大距离。输入：输入N表示节点个数，接下来N-1行从2开始，每行输入两个数x1,x2,x1表示第I个节点所连的节点编号，x2表示这条边的权值。输出：输出每个节点能到达的最大距离。 具体思路：如图所示计算一个节点所能到达的最大距离包括两部分：1、以这个节点为根的树所能到达的最大距离，也就是篮圈部分。2、这个节点父节点为根的树出去蓝色部分所能达到的最大距离+父节点与这个节点相连的边的权值。这两者取最大值。所以我们定义int f[10005][0];表示以x为根节点的和他相连的所有子树的最长距离中的最长值+x根节点到相邻点的距离...

题目链接题目大意：给一段数列，从第二个数开始给出，第I个数之前比I小的数的个数，让你计算序列每个数具体的值。（序列值在1——N之间，且不重复）。输入：N表示序列个数，后面N-1行表示从二开始第I个数之前比I小的数的个数。输出：输出序列每个数具体的值。思路分析：我们要确定序列第I个数的具体数值，就需要I前面和后面比他小的的数的数量，例如：以他小的数有X个，他这个数本身就是X+1。但是计算后面比他小的数的个数不好计算，所以我们可以从后开始计算。样例输入：51210从后面开始第一个数0，所以最后一个数序列中第0+1小的数，第二个数1，那么倒数第二个数就是第1+1小的数（注意这里需要将序列中前面1~n...