hnust_yangyanjun

题解

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

/ 注册

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

Work Group 来自专栏

题意：有一颗n个节点并且以1为根的树，每一个节点有一个权值，你可以选择一些节点组成工作组，工作中中的每一个节点他的子树上的节点在工作组的数目为偶数（不包括自己），求工作组的最大权值为多少（工作组的权值等于工作组中每个节点的权值之和）？思路：树状dpdp[v][0/1]表示第v个节点在满足条件时该子...

树状dp

2021-02-22

1 698

Spy Syndrome 2 来自专栏

题意：描述了一种加密技术，现在将加密后的字符串和字典给出，要你求还原后的字符串。加密方式：①将所有字母改为小写字母②将所单词翻转③将所有空格去掉思路：你可以将字典中的单词按翻转后的结果插入字典树中。然后dfs加密后的字符串从字典树中查找满足的可划分的单词。代码： #include <cst...

dfs 字典树

2021-02-21

2 715

Dima and Salad 来自专栏

题意：给出n个物品的ai和bi的值，求在满足所选物品ai之和除以bi之和等于k时ai之和最大为多少？思路：将每一个物品的ai看成价值，ai-bi*k看成体积，这样题目就变成了所选物品体积为0时价值最大为多少？给体积一开始就加上一个较大的值来解决下标为负的问题，这样就只是一个简单的01背包问题了。 ...

dp

2021-02-10

1 608

Subsequences (hard version) 来自专栏

题意：给出一个长度为n的字符串和一个k，求形成k个不同子串组成的集合至少要删除多少字符？如果无法完成则输出-1. 思路：动态规划：dp[i][j]表示前i个字符组成一个长度为j的不同子串的数目；dp[i][j]=dp[i-1][j] (不加第i个字符)+dp[i-1][j-1] (加第i个字符)+d...

dp

2021-02-10

1 524

Train Hard, Win Easy 来自专栏

题意：有n个参赛者，每个参赛者在做第一题和第二题都有一个罚时，两个人组成一队，每个人负责一题，该队罚时为两人罚时之和（队内会取最优策略），求该参赛者在所有可能的组队中总罚时为多少？思路：我们发现可以按照前一个写第一题，后一个写第二题最优来排序：既：A.a+B.b<A.b+B.a先求该参赛者与...

贪心前缀和

2021-02-10

1 798

Tree Constructer 来自专栏

题意：有一棵n个节点树，请你构造节点数据使图正好为这棵树（节点之间有边仅这二个节点位与等于 -1）。思路：我们可以先黑白染色，因为n<=100,所以一定会有一种颜色少于等于50，所以我们就应该从位上考虑，不然为什么n<=100而不是小于100000呢，又因为只有相邻黑白节点才连接，所以...

构造题

2021-02-06

6 694

和与或来自专栏

题意：有一个长度为N的数组R，求有多少满足条件的序列A使得0 ≤ A[i] ≤ R[i]A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]输出答案对1e9+9取模思路：由于A的N个数和与或结果相等，所以每一位最多存在于这n个数中的其中一个数中。所以可以从高...

数位dp 状压dp

2021-02-02

1 825

[HNOI2012]矿场搭建来自专栏

题意：给出n条边，求该图至少需要设置多少个逃生点才能使无论哪一个点失去，其余点都能至少到达一个逃生点，并求出方案数。思路：考虑点双连通分量：如果该点双连通分量只有一个割点，则需要设一个逃生点，且该点不能是割点（防止唯一的割点失去时其余点无法到达逃生点）。如果该点双连通分量有大于一个割点，则无需设置...

割点点双联通分量

2021-01-29

2 658

魔改森林来自专栏

题意：有一个n行m列的网格图，起点在格点(n+1，1), 终点在(1,m+1),有k个格点是不能走的障碍点。求从起点到终点的路线有多少种？（只能向上或向右）思路：从数据范围看当n,m<=1000时我们可以用动态规划解决：dp[n+1][1]=1;dp[i][j]=dp[i+1][j]+dp[...

容斥组合数

2021-01-26

1 680

[HAOI2006]均分数据来自专栏

题意：将n个数分成m组，求最小均方差？思路：随机打乱数组，然后贪心求结果，取最小值。(double)clock()/CLOCKS_PER_SEC得出程序运行的时间，单位为S。random_shuffle(a+1,a+n+1);打乱数组。贪心策略：前m个数每个数单独为一组，然后将剩余数分给当前最小数...

贪心

2021-01-26

1 632