题意:(英语太垃圾,看翻译,然后越看越懵......,唉,读题真心不易)给定数组 然后取其中 大于 的区间,举个例子 可以得到符合的区间有第二个要求是取的得到的符合的区间里面的第 大加入到 ,例如 ,可以得到 ,最后输出 的第 大的元素,题意就这么多.题解:(这题不会,看别人题解看会的,参考的链接:https://blog.csdn.net/codeswarrior/article/details/82827902)所用到的知识点是,二分和尺取二分:就是每次不断减少现有的一半尺取:首先决定一个尺子的长度,然后把这个尺子不断向后移动对于上述题目,暴力的话,时间复杂度上天是铁定的本题直接面向结果进...

题意: 个数分为两组,然后开始从头遍历,每秒向后+1位,如果从 有小于当前的 时且不是同一组的元素消灭,同时还有个 次操作就是可以在第 秒时,可以使 全部+1,求最后剩余多少个元素题解:暴力,倒着枚举 ,根据这句我们可以先让所有的元素加上相应的数字,如样例所给(最后有点挡住了........)然后不是说前面大于的全部消灭吗?而且分两组的情况,所以我们可以直接找到0和1两组最后出现的位置,取其元素为 ,开始从后向前消灭向前移动的时候如果当前元素大于,那么更新,计数.因为如果前面的数全部小于,那么肯定全部消灭,如果有大于的,那么这一段的全部消灭,更新,而且我们只关心结果,所以记录情况即可,然后要注...

题意:讲n个木棒,变为长度相同的k个木棒,然后问木棒最长长度为多少?题解:二分枚举答案,然后遍历整个数组判断是否可以满足k时间复杂度: #include<bits/stdc++.h> using namespace std; int main() { long long s; int i,t,N,K,M,L,R,T[200005]; scanf("%d%d",&N,&K); R=-1; for(i=0;i<N;i++){scanf("%d",&T[i]);R=max(R,T[i]);} L=1; ...

题意:题解:一看数据范围,肯定是直接输出答案的题上说 那直接写 位置,一共可以写出种,然后我没对于每一种位置进行构串,还剩下 个位置,所以可以构成 种可能.所以 ,加上取模运算和快速幂运算时间负责度: #include<bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9+7; ll quickmod(ll a,ll b,ll m) { ll ans = 1; while(b) { if(b&1) { ...

题意:找到树中距离为偶数的长度的段题解:偶数的长度,即到根节点距离为奇数的两两组合,到根节点为偶数的两两组合,所以搜索全树组合方式时间复杂度:这个好像是个搜索题. #include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF=0x3f3f3f3f; const int maxm=511111; const int maxn=111111; struct EdgeNode { int to; int w; int next; }; struct Node ...

题意:异或,选取任意不重叠的两个区间,使异或结果为0如上述例子,我们可以选取 和 就是满足题意的题解:相同元素异或为0,所以我们找到两个点 ,求与相同答案的个数.(额,这是句废话...)先求解异或前缀和,然后枚举每个位置,统计该位置之前的所有前缀和,即把该位置当作右端点,然后枚举计算右端点之前的所有位,为左端点进行计数,同时当把该位当作右端点计算完之后,并用map存储,把该店当作左端点,逐个枚举右端点,用map查询相同的值,进行计数.比如,当 运算到第一个8的时候,前面有1,2,3的异或值为0,且已经记录,然后当第一个8为右端点运算结束之后,变为左端点是,第一个8和第二个8异或结果为0,并且此...

题意:选取任意一个节点为根节点,求最大流通流量题解:参考第二题所给的遍历方法和换根方法,进行换根即可,只不过换根是式子变为 , 表示第一次搜索的在v节点的值, 表示第v个节点的答案.第二题参考链接:https://blog.nowcoder.net/n/036d85b25e8c4d8aab55351f6d7134cacode: #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; int t,n,hd[N],tot,vis...

题意:求解最小的 ,由于根节点的不同,所以可以改变 值题解:1. 暴力搜索,以每个不同的点进行搜索值时间复杂度: ,超时 2. 以1节点为根节点,遍历全图,并且记录1节点的 值,相邻两个节点的 值,可以相互转化比如已知 求 , 两个节点相邻, 并且 距离1节点距离更近那么, ,其中 表示第 个节点的子节点个数并且包含其本身,那么是否相当于所有非其子节点的节点全部+1,其子节点全部-1时间复杂度: code: #include <bits/stdc++.h> using namespace std; const int N = 1e6+7; list<int&g...

预计写完200+道题,然后实际写了不到100(里面还有水题) 不说了,希望下个20天可以写到200+(不含水题) 然后现在总结:把比较有点东西的题写一下知识点总结 https://ac.nowcoder.com/acm/problem/13889 搜索:枚举每个点进行深搜,然后求解最优答案,额,就硬搜..... https://ac.nowcoder.com/acm/problem/14701 区间dp:第一个接触的区间dp😁,每次枚举区间长度,区间起点,区间终点,然后进行求解 其实只要有起点和区间长度即可......然后假设 为已经求出的答案,并且其长度为每次要不取左边的,要不取右边的时...

题意:输出数组 的中位数懵逼的题解:每次数组 排序...我不知道为什么这个能过,时间复杂度:我怎么算这个时间复杂度也会炸的呀....... //ac code #include<bits/stdc++.h> typedef long long ll; using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int p; cin>>p; while(p--) { int ...

题意:给一颗白色的树,然后进行染色,问最少要多少次可以,把整颗树染成黑色,染色标准是:每个节点都有一个 值, 节点到根的链上（包括节点 与根）所有与节点i距离小于 的点都会变黑.题解:贪心,根据题意可以将树退化成,一条线,如:对于下图,圈内表示,所以我们答案应为2次,可以选择倒数第二个节点,一直到根节点为需要1次,加上最后的剩余的叶子节点,记1次,一共要2次.但是可以把树变为下面这种情况.即 ,然后就是 遍历整个树,以及改变时间复杂度 #include <bits/stdc++.h> using namespace std; const int N = 1e5+100; int...

题意:给一棵树进行染色,并且要保证(x,y)成立,也就是从X节点到y节点的颜色相同题解:因为题目没有对节点进行要求(虽然给定节点的边的关系)此题看上去是一个染色，其实任意两个相同颜色的点对，之间都的一个颜色，那就是一个联通分量全是一个颜色。树，就可以看做是一个点集合，挑哪些点染同一种颜色。显然是DP做法。每一个点跟前一个点的关系只有颜色相同、颜色不同两种，当颜色相同时，该点的方案数等于上一个点方案数，当颜色不同时,只能使用剩余的 种颜色,所以 #include<bits/stdc++.h> using namespace std; typedef long long ll; co...

题意:给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。题解:最先想到的是枚举[L,R]区间内的每一个数,然后求和,即便最快的也要 ,超时我们发现只用写出最高位出现的次数所以下来就是来计算每个 对应的区间比如 那么最后决定答案的是什么?不就是 在范围的倍数的个数如然后呢就是如果每一个都要计算的话,那么时间复杂度为 ,这样接着超时(弥天大雾)举个例子 ,在 的符合的倍数的个数都为 个,所以就可以相当于111*9,然后就可以跳过一部分枚举区间时间复杂度: ...

题意:把图中所有节点分成对点,然后把分成的每对点的距离求和,并且要求和最小题解: 典型的树形结构所以我们考虑的时候,如果当前节点的子节点数为偶数那是否表示,不需要额外添加边如图(图有点丑.....)对于下面的那个节点他有偶数个节点,两两配对即可而对于子节 点有奇数个,那么两两配对,对于小小根还剩余1个子节点,而这个节点配对最好的方法就是和小小根配对,而对于小根的子节点数位偶数,跳过,对于根节点的节点数是奇数,那么它要和自己的某一个子节点结合所以就是搜索全图,如果当前节点的子树节点(子树包括当前节点)为偶数不需要处理,奇数加上当前节点与其根节点的边权时间复杂度 #include<bits...