首先题目给出是一棵树 我们可以知道树上两点路径唯一 其次又有一条额外免费的边 所以我们可以这么考虑，x,y之间的路径要么是 在原树上由x到y，要么经过额外免费的边 对于每个询问，取三种情况最小值即可 ll n,m,p; struct node{ int e,next; }edge[maxn]; int head[maxn]; int deep[maxn]; int f[maxn][21]; ll cnt = 0; void addedge(int u,int v){ edge[cnt] = node{v,head[u]}; head[u] = cnt ++; } voi...

这是个结论题，又不是个结论题 —————————————————————————————————————————————————— 显然可以推出来，l,r从高到低前面相同的几位是没有贡献的所以直接异或掉即可ll temp = l^r 最主要的在于如何确定最大值 因为l,r的前几位都被异或掉了，也就是说从当前位开始不一样 那么既然不一样区间就必然包含两个数 假设第pos位不同，只需取2^pos-1与2^pos异或即可 由于区间长度大于等于2，并且有大于等于2^pos的数，也有小于2^pos的数 所以一定可以使得从当前为开始全部是1 Code: int main() { int T;sca...

介绍两种思路，一种被卡掉了注意一下这个异或和是指 所有path(i,j)的异或 首先从一个根出发，算出跟到点x的路径异或为b[x] 那么对于两点的path(i,j)的答案即为：b[x]^b[y]^a[lca] 由于最终答案又是异或 也就是说path(i,j)表示为三个数异或然后在异或 显然对于每一个点而言，要异或其他n-1个点 ，也就是说该点在最终答案中b[i]出现次数是n-1次 所以首先看一下n的奇偶，如果为偶数首先把所有的b[i]异或起来 之后看一下a[u]，a[u]就是作为lca异或的次数 通过dfs计算就可以了，判断奇偶性 Code: /*** keep hungry and calm...

考虑区间dp即可 我们可以发现在左右端点颜色相同的时候越在外面的颜色越早涂是最好的例如：RGR先涂R比先涂G好 根据上述情况 很容易发现 ：当左右端点颜色一致时 只需要扩充即可 不需要在涂色了 因为涂的颜色已经早涂了如果颜色不一致 ，就是区间dp的套路 ，枚举从哪个中间点分开 Code: /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(3) #include <bits/stdc++.h> #define debug(x) cout<<#x<<":"<<x<<...

题目思路 首先注意到这个式子表示的含义即为，所有区间的区间和*区间长度的累加和 把式子拆开: 设a数组的前缀和是fa,b数组的前缀和是fb ( fb(r)-fa(l) )* b_(r-l)  = fa(r)*b_(r-l) - fa(l)*b_(r-l) 所以说我们可以枚举每个点作为左端点的贡献和右端点的贡献 作为左端点的贡献的即为:-fa(i)*fb(n-i) 作为右端点的贡献即为：fa(i)*fb(i) 枚举顺序统计即可: Code: /*** keep hungry and calm&n...

题目链接：https://ac.nowcoder.com/acm/contest/5668/E 题目大意：给出一个序列定义一个序列的权值为： ，其中p一个全排列 问第一小和第二小的序列的权值和 其中对p有要求： 满足并且 并且第一小与第二小的排列任何位置都不相同。 题目思路： 根据 可知： i在全排列中的位置是pi，pi又在第i个位置 所以这个全排列的性质是 每两个元素之间进行了交换 也就说题目所要求的权值转换成为将序列分成N/2组每组的差值的绝对值最小 那么第一小绝对是排序后相邻两元素的差值和(没有一种差值比这小了) 第二小呢？ 第二小会考虑到一些问题，题目中指出第一小与第二小的排列任何位...

题解： 我试图去遍历邻接表（以为是水题），结果T飞了呀——m1e7，随便出点数据就可以卡了。 看一下正解： 用一个数组表示，当前这个点操作了几次，那么就如上图所示，绿色的点操作x次对此次操作的贡献即为2x，蓝色的点为1x。 很显然x的操作次数的贡献为：x的度数+1。 所以显然需要维护邻接点，但是这个邻接点不太好维护，考虑树的性质:一个点的父亲节点有且只有一个。 那么就想到维护 父亲节点。 首先解释一下下面所用到的所有数组： tag[x] ，x节点被操作了几次 ftag[x]，x节点作为被操作节点的父节点的次数 gftag[x]，x节点作为被操做节点爷爷节点的次数 设tag[i]表示第i个节...

链接：https://ac.nowcoder.com/acm/problem/16645 来源：牛客网 题目描述 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下： 1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素； 2.每次取走的各个元素只能是该元素所在行的行首或行尾； 3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 * 2i，其中i表示第i次取数（从1开始编号）； 4.游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序，对于...

题意简化： 首先给出一棵树，其次询问一个点集，求包含这个点集的最小生成树与询问点x的最短距离 题目思路 首先考虑，如何确定这个点集的最小生成树：首先跑一个LCA，找出所有点公共的LCA，那么这个最小生成树的点集根节点(也就可以确定了) 之后就可以考虑这两种情况： 1.如果询问点，不在这个子树内：即绿色为询问点，由红色点生成的生成树可知，是图中三角形的点，显然绿色点不在红色点两点的祖先子树中，由于树上两点路径唯一，那么绿色点要想通过子树的点，就必须经过这个祖先，所以此时就是询问点到LCA的距离 2.如果询问点在子树内，可以考虑如果一个点存在于子树中，那么可以考虑为这个点到公共LCA的路径...

好久没更新牛客的博客了更新一下下 链接：https://ac.nowcoder.com/acm/problem/20242来源：牛客网 [SCOI2005]最大子矩阵时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵 不能相互重叠。输入描述:第一行为n,m,k（1 ≤ n ≤ 100,1 ≤ m ≤ 2,1 ≤ k ≤ 10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超...

链接：https://ac.nowcoder.com/acm/problem/23049 来源：牛客网 华华给月月准备礼物 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也...

这题思路非常巧妙 求有多少个逆序对 不妨转换为求每个逆序对的贡献  每个逆序对的贡献即为 这个逆序对在多少个串中出现 所以总逆序对的个数 ：n*(n-1)/2 对于每个逆序对而言，它可以在:2^(n-2)个子串里出现  所以ans=n*(n-1)/2*2^(n-2) 那肯定Py比较好: n=input(); p = 10**9 + 7 print(n*(n-1)*2**(n-3)%p) 然后T了： 然后C++： /***&nbs...

链接：https://ac.nowcoder.com/acm/problem/14248 来源：牛客网 Treepath 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 输入描述: 第一行一个数n表示点的个数；...

链接：https://ac.nowcoder.com/acm/problem/13249 来源：牛客网 题目描述 一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。 你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。 输入描述: 第一行一个整数n (1 ≤ n ≤ 10^5) 接下来n-1行，每行一个整数，依次为...