⊙__⊙

题解

/ 注册

全部文章 / 题解（共23篇）

Removal

这是一道经典dp 的题目！题目意思大致就是: 给出一个序列，问你任意删除m个字符，有不同种方案？每个数字的范围在k之内。我们可以设 dp[i][j] 表示前i个元素删除j个元素后的方案数很容易推出dp方程: dp[i][j]=dp[i-1][j-1]+dp[i-1][j]意思就是 ...

2020-04-27

3 861

边的染色

题外话: 这题开始并没有什么思路,第二天参考并学习了雨神的思路和写法。感谢雨神大大和清楚姐^-^ &nbs...

2020-04-23

2 1046

K-th Number

本弱由于把题目看错，k和m看反了，导致样例一直推不出，还有怀疑题目错误的**行为。先说下题目意思，给出一个A数组，问所有区间长度大于等于k中，取第k大的数，然后放进B数组中，最后在B数组中在求第m大的数。分析: 首先暴力去做，1e5的数据量那是妥妥的T了，我们可以先对答案进行二分，然后反向去满...

2020-04-21

0 564

糖糖别胡说，我真的不是签到题目

首先感谢 PDSU----18计一-----周宁，我是看了这位大佬的解题，然后获取了一些思路。题目意思：第i个糖糖会有bi的能力值，然后他父亲能够在第i秒把1-i位置的b能力值都加1. 第i个糖糖在第i秒能干掉前面比他能力值小的人,并且是不用小组的，同一小组是不能干的。小组最多就2组。思路...

2020-04-20

3 848

华华给月月准备礼物

题意: 给出若干个木棍长度，你可以对每个木棍进行切割。比如有5个木棍，长度分别是4 4 4 5 3 你可以一次切长度为2的，那么4能切2刀，5能切2刀，3只能切一刀。总数加起来ans=2+2+2+2+1=9 题目问的就是一次切w刀，能使的ans>K.(K由题目给出),算出max(w) 数...

2020-04-16

0 497

逆序对

题意:给出一个长度为n的“01”串，问:统计所有01串的逆序对总数分析：首先对于逆序对，满足设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。只有当出现 1 0 这种样子串，才会对结果造成影响，所以先从n个中选出2个。剩下n-2个数就有2^(n-2)种...

2020-04-16

0 594

Treepath

题意:树中长度路径为偶数的路径数，不能重复分析：首先树中点x到点y的距离 =dep[x]+dep[y]-2*dep[LCA(x,y)] 首先可以发现，2*dep[LCA(x,y)]对奇偶性无影响那么就剩下dep[x]和dep[y] 所以我们只需要求出深度为奇数的个数和偶数的个数然后奇偶性...

2020-04-14

0 493

Accumulation Degree

题目意思:给出一个无向图,n个顶点,n-1条边。每条边有权值w,表示流量。流量:本来我实在没理解题目样例的解释,后来问了一位大佬的解,秒懂了.其实边权可以理解成水管的粗细,水能流多少。比如1->4-3 首先1->4可以通过13的水,由于4->3水管只有5的大小,所以1-4-3...

2020-04-14

3 906

NC201400 树学（换根做法）

链接：https://ac.nowcoder.com/acm/problem/201400 题意: 给出连通图，由n个点和n-1条边构成，在树上选择一个结点作为根，使得以这个结点为根的所有结点的深度和最小。默认根的深度为0 样例：41 21 31 4 很显然以1为根,depth=1+1+1=3 是最...

2020-04-13

6 1067

Shortest Path

把n个城市分成n/2对，这样n/2对城市之间的长度之和最小。保证n是均分样例一：我们最小的分法是1-2,2-3，答案是5+6=11 其他分法均比这个要大样例二：我们选择的是1-3,2-4,5-6 合计5+(3+9)+(10+4)=31 我可以发现，选择2个城市，尽可能要不重复，如果出现交...

2020-04-02

0 767