hnust_yangyanjun

分类

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

/ 注册

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

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

Rinne Loves Data Structure

题意：告诉你有n个整数，按顺序构建一棵二叉查找树，既树中每一个节点满足左儿子小于节点，右儿子大于节点。求每次插入一个整数后树中每一个节点深度之和？思路：学过二叉查找树的都知道插入操作最坏情况为O(n^2)（链状时），所以模拟肯定过不了。仔细观察二叉查找树，再分析下插入时进行的操作，我们可以发现对于...

二叉查找树

2020-07-28

0 645

Binary Vector

题意：随机n个n维01向量，询问这个n个向量线性无关的概率？思路：观察样例，我们发现f(i)初始为1，分子开始乘1，分母乘2，然后每次乘前一次乘的2倍+1，分母每次乘前一次的二倍。由于n<=2*10^7,所以我们打表。我们先打出f(i)的表，f(1)=1/2的逆元ans[1]=5000000...

数学

2020-07-27

3 553

Easy Construction

题意：给你两个整数n和k。求你用 1~ n构造一个存在 1~n 长度的连续子列都能加起来之和取模n等于k，如果不能，输出-1. 思路：我们可以知道长度为n时的子列只有一个，和为n * (n+1)/2 ,所以当(n * (n+1)/2)%m=k时才有解。当n为偶数时，1+（n-1）=n、2+（n-2)...

2020-07-27

3 527

Combination of Physics and Maths

题意：给你一个n*m的矩阵，求矩阵的子矩阵最大压强为多少，压力F为子矩阵所有元素之和，受力面积为子矩阵最后一行的元素之和？思路：由于我们只要求最大压力，所以我们根据公式求每一列的子列的最大压力即可。代码： #include <iostream> #include <cstdio...

数学

2020-07-27

1 582

小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 576

[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