hnust_yangyanjun

分类

大数加法(1) 尺取法(1) 面经(4) 题解(119)

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

kingdom

题意：有一棵节点数为n的树，每一个子节点向父节点传送消息时，如果以父节点为根的子树中该节点为根的子树中节点数最多，则该节点花费为父节点的花费，否则为父节点花费+1.求所有节点一层一层向根节点传送消息的花费之和尽量大时的花费为多少？思路：这题我们可以用dp解决，我们求的是n个节点树的最大花费...

dp

2020-07-19

1 567

点权和

题意：给予一颗树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和（与点x树上距离<=1的所有点点权之和）.如果是第i次操作，这次操作结果为ans,则这个结果的值加上i * ans，结果模19260817。思路：设数组f1[]记录该点本身修改...

2020-07-16

3 763

Color

题意：给与一个二分图，给边染色，连接同一端点的边的颜色不能相同，求最少用多少种颜色才能完成染色？思路：二分图最大匹配的匈牙利算法，对一条边进行染色，设一个端点最小可染的颜色为x，另一个端点最小可染的颜色为x.①x==y,该边染成x.②x<y,将该边强行染成x，最小可染颜色为y的点显然已经有了...

2020-07-16

3 730

矩阵取数游戏

题意：给出一个n*m的矩阵，每一次取数从每一行中取一个数，每行取数的得分为每行所取数a[i][j] * ,k表示第几次取，且每次取数只能取头或者尾。求取完后的得分最大值？思路：我们可以发现每一行的取数只与当前行有关，所以该题相当于求n次数组中取数得分之和。我们可以区间dp解决。每一次不断增加区间...

__int128 dp

2020-07-14

1 994

Alliances

题目：有n个城市，有(n-1)条道路，每条路连接两个城市，城市和道路构成了一棵n个节点的树。有k个帮派，每个帮派占领ci个城市。帮派集合称为联盟，他们控制的城市为他们占领的城市和所占领的城市二二之间的城市。有q个询问，每个询问给出一个首都和一个联盟，求首都距离联盟所控制的城市最近的距离？思路：在树...

dfs 二分 LCA

2020-07-11

1 701

平衡二叉树

题意：在一棵每一个节点的左右子树高度差小于d的n高度的树上，求出节点的左右子树节点差的最大值？思路：是左子树的节点尽可能多，所以左子树为满二叉树。右子树的节点尽可能少，所以右子树高度为n-d-1。n高度的右子树节点个数=n-1高度的右子树节点个数+（n-d-1）高度的右子树节点个数+1。（将一棵树...

dfs

2020-07-10

0 734

最短路

题目：给一个连通图，每次询问两点间最短路。每条边的长度都是1。思路：看数据范围我们就知道普通的最短路是无法在规定的时间爬完的，所以我们盯上了长度为1，和m<n+100。如果是一颗树，我们可以用Lca求最短路，每一次查询为O(log(n))。我们已知这是一个连通图，所以我们可以用并查集生成最小...

最短路并查集 LCA

2020-07-08

0 684

[SCOI2005]最大子矩阵

题意：在一个n*m的矩阵中选择k个子矩阵，这k个子矩阵互不相交，求这k个子矩阵分值最大为多少？思路：dpdp[k][i][j]为在第一列前i个，第二列前j个，选择k个矩阵的最大值。分析我们动态所加的一个元素参与结果的情况。既枚举所加元素在第一列前i个，第二列前j个中所有矩阵加上在该矩阵外选（k-1...

dp

2020-06-12

0 543

小A与小B

题意：小A与小B被困在一个n*m的迷宫中，'.'为可通过，'#'为障碍不可通过，'C'为小A初始位置，'D'为小B初始位置。小A可以上下左右左上左下右上右下8个方向移动，而小B只能上下左右移动，不过小B能一秒移动二次，而小A只能一秒移动一次。求小A与小B最早什么时候相遇？不能相遇只输出NO. 思路：...

bfs

2020-06-10

0 526

[CQOI2010]扑克牌

题意：有n种牌，每种牌有ci张，还有m张万能的joker牌，每一套牌可以用一张joker牌代替任意一张牌，求最多能组成多少套牌？思路：二分求最大值，因为能组成k套牌则必能组成（k-1）套牌。是否能组成k套牌，首先我们最多用min（m,k）张万能牌，用万能牌补数目少于k的牌，最后看万能牌是否够用。 ...

二分

2020-06-10

0 569