hnust_yangyanjun

题解

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

/ 注册

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

[SCOI2009]生日礼物

题意：有一个有n个彩珠、m种彩珠的彩带，使每一种彩珠都包含的最小长度是多少？思路：离散+尺取法代码： #include <bits/stdc++.h> typedef long long ll; using namespace std; const ll inf=99824435...

离散尺取法

2020-08-27

1 625

[SCOI2010]游戏

题意：你有n件装备，每件装备有两个属性，每件装备只能用一次，你打boss时属性只能从1开始连续用装备攻击，求你的最大攻击次数。思路：二分图匹配问题，属性与物品编号连边，从1开始匹配，用匈牙利算法，冲突时进行改变。代码： #include <bits/stdc++.h> typedef...

2020-08-27

1 723

Mr. Kitayuta, the Treasure Hunter

题意：有一个由30001个小岛组成的群岛，编号为0-30000，一字排开，首先从0岛跳的d岛，然后每一次跳的距离与上一次的距离绝对值等于小于1，有些岛有宝石。思路：dp:ma[i]表示i岛的宝石数目。dp[i][j]表示跳到i时跳的距离为250-j+d时收集的最大宝石数。初始化dp[d][250]...

dp

2020-08-27

1 554

树学

题意：给你一颗树，你选择一个节点当根，求所有点的深度和最少为多少？思路：树状dp+换根一开始随便选一个点当根计算结果。dp[i]表示以i为根的子树节点的深度和。se[i]表示以i为根的子树的节点数目。换根：dp[v]=dp[u]+n-2*se[v];(v为u的子节点，根从u转向v时，以v为根的子树...

树状结构换根

2020-08-22

1 590

Accumulation Degree

题意：给予你一棵n个节点的树，每一条边有一个容量，你选择一个节点当根，求从根节点到叶子节点的流量的最大值。思路：树状dp+换根：flow[i]为以i为子树i到子树叶子节点的流量最大值。ans[i]表示以i为根节点时的答案。flow[u]= min(flow[v],cost(u,v))(v为u的子节...

换根树状dp

2020-08-22

1 784

选课

题意：你有n门课程，你可以选择m门课选修，有的课程有先修课，每一门课程都有学分，求你可获得的最大学分为多少？思路：树状dp没先修课的与0节点连接，有先修课的与先修课连接，这样就是0节点为根的一棵树了。dp[i][j]表示以i节点为根的子树且选择了i时共选择j门课程的最大学分，这样就满足了先修课的条...

树状dp

2020-08-22

6 554

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 775

旅游

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

树状数组

2020-08-21

1 441

黑白树

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

贪心树状结构

2020-08-21

1 803

装货物

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

dfs

2020-08-21

1 665