hnust_yangyanjun

题解

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

/ 注册

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

小A的柱状图

题意：给你一个柱状图，有n根柱子，给予你每根的宽度和高度，求柱状图的最大矩形面积？思路：单调栈，维护一个单调递增的栈，维护高度和左边界。当h[i]>栈顶元素的高度时入栈，左边界不变。当h[i]<栈顶元素的高度时，栈顶元素出栈，并计算以该栈顶元素高度为一条边的矩形最大面积（既（右边界-左...

2020-07-27

1 569

区间权值

题意：给你一个a数组和一个w数组，定义请你求的值? 思路：由于n<=5 * 10^5,所以暴力肯定是不行的，所以我们可以按暴力求法列出式子看是否能优化。当n=5时，结果=f(1,1)+f(1,2)+f(1,3)+f(1,4)+f(1,5)+f(2,2)+f(2,3)+f(2,4)+f(2,5...

数学

2020-07-26

1 676

[SCOI2008]着色方案

题意：给你n种染料，每种染料可以使用Ci次，同一种染料不能连续使用，求用完所有染料的方案数为多少种？思路：纯动态规划，我们用dp[a][b][c][d][e][last]描述一个还可以使用一次的染料为a种，还可以使用两次的染料为b种，.....,可以使用五次的染料为f种时上一次染色为使用还可以使用...

dp

2020-07-26

1 521

[ZJOI2006]BOWL 碗的叠放

题目：给与你n只碗，每只碗上宽下窄，告诉你上下半径和高度，请你求出n只碗叠放的高度最小为多少？思路：由于n<=9,所以可以直接枚举碗的顺序，求高度。我们可以对两只碗不同情况的叠加情况（从边的斜率和上下半径考虑）进行分析，维护下底高度。代码： #include <bits/stdc++...

数学

2020-07-22

1 577

[SCOI2009]生日快乐

题意：将一块x*y的蛋糕切n-1刀分成n块面积相同的小蛋糕，每次切只能平行于边将一块切成二块。求N块蛋糕的长边与短边的比值的最大值最小为多少？思路：我们发现n<=10,而且每次切只能平行于边将一块切成二块，而且每一块面积相同，所以我们可以用dfs枚举每一种切法。平行于y边切：可以切成(i *...

dfs

2020-07-21

1 888

[SCOI2007]压缩

题意：给与一个长度不超过50的字符串，它可以按下列方式压缩：M是开始，R是重复从前一个M开始的字符串。求字符串压缩后的最短长度。思路：区间dp:dp[i][j][0/1]:dp[i][j][0]表示从i到j这段字符串中没有有M、dp[i][j][1]表示从i到j这段字符串中可以出现M的最少字符数。...

dp

2020-07-21

1 674

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