题目链接 https://qduoj.com/problem/22 题目大意 n个节点的一棵树，先确定一个节点，问与其直接相连的节点的个数，与其隔一个节点相连的节点的个数，与其隔两个节点相连节点的个数……；输入：t组数据；每组数据n，k分别代表n个城市，k是基准城市序号；n-1行道路，输入u，v，相连城市的序号。输出：每组数据的第一行先输出全部城市被遍历需要几次，再以此输出每天遍历的城市个数。 解题思路 一眼过去直接bfs。加个统计就行，其实这个统计也不是特别好想。还是讲讲代码吧。 AC代码 #include<bits/stdc++.h> using namespace std; ...

题目链接 https://www.dotcpp.com/oj/problem1837.html 题目大意 输入两个数，m，n分别代表A的数量和B的数量；构建一个人塔，要求A脚底下的两个字母必须是A和A或者B和B，即脚底两个字母相同，B脚底下的两个字母必须是A和B或者B和A，即脚底两个字母不相同；输出能排列出的种类数量。 解题思路 我的思路比较直白（傻），二进制枚举，枚举最底下一行的排列状态。最底下一行的排列状态确定后，上面的排列状态也就确定了，所以，只要统计构建的人塔中A和B的数量是否与输入相同，相同的话种类数+1。什么是二进制枚举？以本题为例，每一个位置要么放A要么放B，这和二进制有点像啊，...

题目链接 https://ac.nowcoder.com/acm/problem/15172 题目大意 矩阵由0，1构成，n行n列；m次询问，操作数为1时，对某个坐标处的数值翻转，即0变1，1变0；操作数为2时，求一个坐标为子矩阵左上角坐标，另一个坐标为子矩阵右上角坐标的子矩阵和并输出。 解题思路 我的思路: 二维数组a，表示每个灯泡的状态；二维数组c，为树状数组。a[i][j]表示第i行第j个灯泡的状态，c[i][j]表示第i行所处的树状数组，举例：c[1]表示第一行树状数组首地址，也就是每行有独立的树状数组存储。 AC代码 #include<bits/stdc++.h> usi...

逆序对 百度百科定义：设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。 逆序对解法 方法一：冒泡排序 对原序列进行冒泡排序，统计交换次数，得到的交换次数=逆序对数。时间复杂度高，不推荐。 方法二：归并排序 题目链接 典型例题 讲解 归并讲解递归这东西，难者不会会者不难，理解之后再写会好写点，但是小细节上还会有点小错。这不是我主要想讲的内容，所以直接挂链接了。 AC代码 /...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1166 AC代码 #include<bits/stdc++.h> using namespace std; const int N=5e4+10; int c[N],a[N]; int n; int lowbit(int x){ return x&(-x); } int getsum(int x){ int ans=0; while(x>0){ ans+=c[x]; x-=lowbit(x); } re...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1556 解题思路 方法一：差分与前缀和 差分与前缀和 这应该是入门学的吧。为了回忆回忆加深一下印象，再稍微写一下。区间[a,b]全部+1，就让存差值的数组c在a位置+1，b+1的位置-1。c[i]=第i个数的值-第i-1个数的值。输出i位置的值，求i位置的前缀和就行了。 AC代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int ball[N]; int n; int main(){ whil...

离散化讲解 大佬讲解离散化 离散化例题 例1 题目链接 例1：Cinema（来自cf） 题目大意 （我说详细点，你就不用翻译了）n个人，每个人会一种语言；m部电影，每部电影的声音语言和字幕语言都不一样。若某人只能听懂，那么此人将非常满意；若某人只能看懂，那么他将勉强满意。输入：输入n，表示人的个数输入n个数，代表不同语言的序号输入m，表示电影个数输入m个数，代表每部电影的声音语言输入m个数，代表每部电影的字幕语言输出：一部电影的序号，此电影让尽可能多的人非常满意，若非常满意的人数相同，那么就再让尽可能多的人勉强满意，若都相同，那么输出任意一个满足条件的即可。 解题思路 大佬给出了板子了，...

题目链接 https://www.qduoj.com/problem/80 题目大意 n个节点，相连节点距离为1，顺序输出每个节点距离其他节点的距离之和。举个例子：假如构造的树是这样的，因为要按照节点序号输出，所以我们先以1号节点为根节点。那输出的结果应该为 15 //15 = (9->1 = 1) + (6->1 = 1) + (5->1 = 2) + (3->1 = 2) + (4->1 = 2) + (8->1 = 2) + (2->1 = 2) + (7->1 = 3) 25 //25 = (6->2 = 1) + (8->2...

题目链接 https://www.qduoj.com/problem/93 题目大意 判断是否能将一组数平均分成两份。 解题思路 一看到这个题感觉好像做过，但还是没做出来。我成功的当成贪心去算了，wa不停。正解是01背包恰好装满：找个sum/2的背包，sum为数和。每件物品的是每个数，每个数的值既是体积大小，又是自身价值。最后只要看dp[sum/2]是否等于sum/2就行，这意味着sum/2大小的背包装下了价值为sum/2的东西。对应到本题而言，意味着存在一组数的和正好为sum/2。 错误的贪心代码（我的） #include<bits/stdc++.h> using namespa...

题目链接 https://ac.nowcoder.com/acm/problem/204870 题目大意 t组数据输入，n个关系，每个关系包括三个数a，b两个人，c=1表示二者互为好朋友，c=0表示二者互为敌人，遵循朋友的朋友就是朋友的原则，问这组数据是否自相矛盾，（如果两个人既是友好的又是不友好的则视为相互矛盾的），不矛盾输出YES，矛盾输出NO。 题目分析 一打眼过去，并查集吧。因为有“朋友的朋友就是朋友”，显然是连通区域。（不会并查集的可以看一下 并查集例题及讲解链接 ）并查集有了，但是发现总人数是1e9个人，实际给出的关系只有1e6个，这就说明…………要离散化！如何离散化呢？对我这种小...

题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1232 题目大意 多组样例输入，n座城市，m条路，问最少需要修多少条路能使全部城市相互可达。本质：求图的连通分支数。 解题思路 思路很明确，就是划分块，相互连通的属于同一块，最后数数多少块输出。难点在于如何存储块？出来吧！并查集！ 大神讲解，绝了！我就稍微总结一下：核心代码 int find(int x){//查找x的掌门 int r=x;//委托 r 去找掌门 while(r!=fa[r]){//如果r的上级不是r自己（也就是说找到的大侠他不是掌门） r=fa[r]...

dfs序简介 dfs序一般用于树状结构中，如图： 图中红色序号为每个点对应的dfs序序号，黑色序号为每个点默认的序号，我称之为节点序序号（下文同）可见，dfs序如其名，dfs序序号是按照dfs顺序标记的，所以说给每个节点安排上dfs序序号也很简单，只要dfs的时候顺便标上就行了，dfs第多少次就给dfs到的点标为多少。 代码模板 代码如下： //vector<int> node[N]; //int in[N],out[N]; int Time = 0; //时间戳 void dfs(int now,int fa){ in[now]=++Time; num[Tim...

前言 大佬们都说是经典题型，但对我这种小白来说，这题确实挺难挺不错的，思考了好久才差不多弄明白。下面我会详细的讲解一下。 题目链接 https://ac.nowcoder.com/acm/contest/5158/I 题目大意 一棵树，n个节点，m次操作，k为根节点；输入n个正整数，表示第i个数的权值；输入n-1对数，为节点，表示两者之间有边；输入m个组数，每组代表一次操作：1 node add ：表示将节点 node 的权值加上 add //加数2 node ：表示求 node 节点的子树上所有节点的和（包括 node 节点本身） //输出 解题思路 我没想出是这个方法。我的...

题目链接 https://ac.nowcoder.com/acm/contest/5158/J 题目分析 意思很简单，给出每个城市的价值，求任意俩城市价值差值的平方和。看到数据你就应该明白，不能暴力啊，这样比较简单的要求自然会想到公式变形。暴力时间复杂度:O(n*(n-1)/2) 解题思路 先枚举写一下：（单纯的去括号） 把所有的ai^2合并一下： 把所有的-2aiaj合并一下： 得到最终变形结果： 过程实现 第一部分求和比较简单；第二部分减法部分的求和，通过前缀和实现。遍历ai，ai*后面区间的总和就行了，而后面区间总和用前缀和做差求得。 AC代码 #include<b...