思路解析 一道二分答案的水题 此类问题我们无法直接求得问题解的题，都可以采用二分逼近答案的方法 code #include <iostream> #include <cmath> #include <cstdio> #include <cstring> using namespace std; #define MAXN 10005 double arr[MAXN]; int n, k; int check(double x) { int cnt = 0; for (i…
解题思路 惯例素数打表 以 10! 为例: 10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 如何计算含有多少个素因子 2 呢？ 我们可以看出: 每隔 2 个数便包含一个素因子 2; 每隔 4 个数便包含一个素因子 2; 每隔 8 个数便包含一个素因子 2; 所以包含含素因子 2 的个数为: \frac {n} {2} + \frac {n} {4} + \frac {n} {8} + \frac {n} {2^{[log_{2}n]}} 其他素因子求法同理 code #in…
解题思路 多重背包 思路 我们可能无法直接算出能组成多少种面额，我们可以先判断是否能组成该种面值，再统计个数 动态转移方程 dp[i][j] 表示前 i 种钱币组成 j 面值有多少种 v[i] 表示第 i 种钱币的面值 dp[i][j] = \begin{cases} dp[i][j],&\text {dp[i][j - v[i]]= 0} \end{cases} code #include<iostream> #include<cstring> #include<cstdio>…
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define MAXN 1000005 struct Node { int s, e; bool operator< (const Node &a) { if (a.e == e) return s < a.s; return e < a.e; } } arr[MAXN]; int main()…
题目链接 https://www.luogu.org/problem/P1823 题目描述 N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。 写一个程序计算出有多少对人可以互相看见。 思路解析 明显的单调栈，很天真的踩了坑 只要两个人中间没有比他们高的，就可以互相看见，这样我们就可以维护一个递减的队列 注意一群身高一样还站在一起的坏孩子，坑。。。 code #include &…
