hnust_yangyanjun

分类

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

/ 注册

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

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

Tree

题意：给与一棵n个节点的树，求每个点的连通点集的数量？思路：树形结构+换根dp[i]表示以i为根且包括i的这棵子树连通点集的数量。ans[i]表示包括i的连通点集的数量，既结果。父节点u与子节点v：dp[u]= (dp[v]+1) * dp[u];（v为u的子节点）换根时:ans[v]=((ans...

树形结构换根

2020-08-22

5 763

旅游

题意：有一棵n个节点的树，第一天你在s点住宿，每一天你可以浏览与它距离不超过1的节点，你不能住宿在你已经浏览过的节点，求你最多住宿几天？思路：树状dp，以s节点为根。dp[i][1/0]表示在i为根的子树中是否在i节点住宿的最大住宿次数。如果u是父节点，v是子节点。dp[u][1]= dp[v][...

树状数组

2020-08-21

1 427

黑白树

题意：有一颗n个节点的树，每个节点有一个权值k[i]，一开始树上节点全是白色的，你可以选择一个白色的节点进行染色，使该节点到根节点路径上的点距离该节点小于k[i]的节点染成黑色。求使该树所有节点变黑的最少操作次数。思路：树形结构+贪心由于染色的节点在你选择的节点和根之间，所以叶子节点你一定会选择，...

贪心树状结构

2020-08-21

1 788

装货物

题意：有n件货物，每件货物有一个重量，我们有x个承重为w的箱子，求是否能全部装上？思路：dfs暴搜：先将货物重量从大到小排序，这样可以降低解空间。dfs时箱子使用个数不超过当前物品数，因为超过没有意义。代码： #include <bits/stdc++.h> typedef long...

dfs

2020-08-21

1 644

华华和月月种树

题意：一开始被给予一棵只有一个编号为0、权值为0的根节点的树，有M个操作，每个操作为以下三种之一：操作1：输入格式为1 i 表示给i节点加个权值为0的子节点，编号为当前最大编号+1。操作2：输入格式为2 i a 表示给i为根的子树所有节点的权值加a。操作3：输入格式为3 i 表示输出i节点的权值。 ...

dfs 树状数组

2020-08-21

1 666

地斗主

题意：给你一个4 * n的矩阵，让你用1 * 2的矩阵填满，求有多少种方法？思路：n=1时有1种n=2时有5种n=3时有11种n=4时有36种由官方题解可知dp[i]=dp[i-1]+5d[i-2]+dp[i-3]-dp[i-4].所以我们可以用矩阵快速幂求结果。为了防止产生负数，所以-1可以等价...

矩阵快速幂

2020-08-14

1 1230

双栈排序

题意：给你一个长度为n的序列，你是否能用两个栈用以下操作进行排序？操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列不能输出0，能则输出最小字...

模拟

2020-08-13

0 693

追债之旅

题意：有n个城市，小明再1号城市，它的欠债人在n号城市，城市之间有道路连接，不过需要交路费，而且欠债人每天都会花费一些钱，每天你只能走一条道路从一个城市到另一个城市，求你最少的花费（路费+欠债人花费）为多少？思路：最短路的变形题，多了个欠债人每天的花费。用val[i][j]表示第i天在第j个城市的...

最短路

2020-08-13

1 598

蓝魔法师

题意：给与一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。思路：树形dp：从叶子节点向根转移，dp[i][j]表示以i为根的树删边时i处于的连通块大小为j的方案数。sum...

树状dp

2020-08-12

2 817

矩阵消除游戏

题意：有一个n*m的矩阵，你可以进行k回合的游戏，每一回合将矩阵的一行或者一列的值置零并将分数加上。求你最后最多能得多少分？思路：由于消除行对列有影响，所以不能简单的贪心，但你n和m小于15，所以我可以枚举消除列的状态，然后对每一种合理状态再对行进行贪心操作，然后取最大分数值。代码： #incl...

枚举贪心

2020-08-10

1 867