wweiyiのblog

【解题报告】洛谷P6189 跑步 题目链接 https://www.luogu.com.cn/problem/P6189 思路 发现相当于给一个数字 nnn ，问你有多少种方法能使得一个不递减序列的和为 nnn 这实际上是一个分拆数的模板题目 根据OIES，这个分拆数的伪代码是 123456789>def A000041(n): if n == 0: return 1 S = 0; J = n-1; k = 2 while 0 <= J: T = A000041(J) S = S+T if is_odd(k//2) else S-T J -= k if is_odd(k) else k//2 k += 1 return S 然后我们就把它翻译成C++就好了 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <cstdio>#include <algorith...

【解题报告】洛谷P6852 Mex 题目链接 https://www.luogu.com.cn/problem/P6852 思路 要求构造一个序列 我们发现，对于一个区间 [l,r][l,r][l,r] 的 mexmexmex 为 valvalval ，[0,val−1][0,val-1][0,val−1] 必须都出现在这个区间中，并且 valvalval 不能出现在这个区间中 所以我们对于某个值 val=0val=0val=0 可以变成这个 valvalval 必须出现的 一个区间，和不能出现的很多区间 val≠0val \not =0val=0 可以变成一个必须出现的区间和不能出现的区间，实际上就是把不能出现的区间并起来，剩下的就是能出现的区间了 所以我们从小到大填入一个数字 valvalval ,每次在 valvalval 必须出现的区间中随便选一个点填进去 然后我们用一个集合来维护可以选择的点，每次用二分确定还能选择符合要求的数字，且必须在区间的左端点，然后再判断它是不是在不能出现的区间里面，如果不在的话，填进去，否则不填进去，然后找不在这个区间只能的能填进去...

【解题报告】洛谷P7726 天体探测仪 思路 对于排列中的一个数字 iii ，设以 iii 为区间最小值的最长的区间是 [li,ri][l_i,r_i][li​,ri​] 首先考虑：如果已知 li,ril_i,r_ili​,ri​ ，如何求出来 iii 的具体位置 设 leni=ri−li+1len_i=r_i-l_i+1leni​=ri​−li​+1 则对于某个 j≤lenij \le len_ij≤leni​ 这段区间里面就一共有 leni−j+1len_i-j+1leni​−j+1 个长度为 jjj 的子区间，如果所有长度为 jjj 的区间中都包括 iii ，那么 iii 在 SjS_jSj​ 中就应该出现了 leni−j+1len_i-j+1leni​−j+1 次，反之，它在这个集合中的出现次数小于 leni−j+1len_i-j+1leni​−j+1 次 因此，我们可以找到最大的 jjj 使得 iii 在 SjS_jSj​ 中出现的次数 ≤leni−j+1\le len_i-j+1≤leni​−j+1 次，那么 iii 到区间边界的距离就是 jjj ,也就是说，iii ...

【解题报告】洛谷P1021 邮票面值设计 题目链接 https://www.luogu.com.cn/problem/P1021 思路 这道题目，首先要用固定的邮票数量和固定的种类表示出最大的数目以内的所有数字 所以我们就对其进行分析 首先1肯定要选，然后呢？ 我们发现这个时候从1到n都能表示出来了，然后呢？ 我们从1到n枚举选择第二种邮票，然后以此类推 直到找到可以表示总共最大的为止 这个时候呢我们就要用动态规划 我们记录一个 f[i]f[i]f[i] 表示选到了第 iii 张邮票，选多少个选到了这里 然后我们就进行动态规划就可以了 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string&g...

【解题报告】洛谷P1419 寻找段落 题目链接 https://www.luogu.com.cn/problem/P1419 思路 这道题目我们首先可以想暴力，我们暴力的时候记录一个前缀和 时间复杂度 O(n2)O(n^2)O(n2) 然后我们考虑优化 我们要找到的是一个最大的平均区间，我们发现，区间长度越小，实际上，得到最大的平均值越大的概率越高，所以我们可以设置一个时间，然后在快要超时的时候直接退出，返回一个暂时的最优解，虽然时间复杂度没改变，还是能通过这一道题目 但是我们当然要正统方法 通过前面的分析可以知道，我们可以二分一个区间的平均值，然后判断这个平均值能不能达到，如果可以达到的话则试更大的平均值，反之，试更小的平均值 然后二分之内的判断函数实际上就是要找是否存在一个序列，使得这个序列的和大于 000 我们可以使用单调队列来维护是否存在这样一个连续的序列 总共的时间复杂度 O(nlogn)O(nlogn)O(nlogn) 123456789101112131415161718192021222324252627282930313233343536373839404142...

【解题报告】洛谷P1410 子序列 题目链接 https://www.luogu.com.cn/problem/P1410 思路 我们考虑动态规划 设 f[i]f[i]f[i] 表示到 iii 的最长的递减的长度 发现，如果 f[i]f[i]f[i]​ 大于 222 的话，这个序列就不成立 反之，这个序列成立 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;int n;int main(){ while(cin>>n) { int a[2005],f[2005]; bool flag=false; for(int i=0;i<n;i++) { cin>>a[i]; f...

【解题报告】洛谷P1725 琪露诺 题目链接 https://www.luogu.com.cn/problem/P1725 思路 这道题目首先一看就要用动态规划 我们设 f[i]f[i]f[i] 表示走到 iii 这个位置可以得到的最大的冰冻指数 并可以简单地得到状态转移方程 f[j]=max{f[i]}+a[i],i+l≤j≤min(i+r,n)f[j]=max\{f[i]\}+a[i],i+l \le j \le min(i+r,n)f[j]=max{f[i]}+a[i],i+l≤j≤min(i+r,n) 然后我们打下去就可以得到60pts了 1234567891011121314151617181920212223242526272829#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cstring>#define int long longusing namespace std;const int...

【解题报告】洛谷P3467 PLA-Postering 题目链接 https://www.luogu.com.cn/problem/P3467 思路 这道题目我开始理解错了 我理解的是从侧边看过去，也就是建筑物东西延伸，我从东西看，然后我想的是从左边单调栈一次，右边单调栈一次 但是题目的意思是从南北看过去，然后贴海报 啊喂，有房子把海报直接贴在家门口的吗草 所以我们直接用一个单调栈维护一下就好了，我们维护一个单调递减的单调栈，特别地，如果两个相邻的高度一样的话，我们所需要的海报数量减一，因为两个建筑可以直接共用一张海报 12345678910111213141516171819202122232425262728293031#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;const int maxn=250005;int n,ans;int d[ma...

【解题报告】CF939E 题目链接 http://codeforces.com/problemset/problem/939/E 思路 贪心 这道题目发现，要选的数字的最大值的减去选的数字平均值最大，我们可以yy出来我们每次加入的新的数字都要加进去（因为单调递增地加入数字 然后我们从前面加数字，然后加的数字如果能使平均数更小，那我们即一直加下去，否则我们不加，这样贪心就行了 证明不太会 然后要开long long 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;long long T,s[500005];long long len,ans,tot;int main(){ cin>>T; while(T--) {...

【解题报告】洛谷P4653 [CEOI2017]Sure Bet 题目链接 https://www.luogu.com.cn/problem/P4653 思路 我们首先观察样例，发现，我们选的都是各组权值比较大的灯泡 所以，我们有一个思想，就是贪心，我们将两个序列从大到小排序 然后，我们对于每个序列设置一个指针，表示某个序列选到哪里了 然后我们根据实际情况进行移动 如果第一个序列产生的收益大于第二个的收益了，这个时候再取第一个序列已经没用了，因为我们最小值这个时候是不变的，我们就要让第二个序列向后拓展一个，增大第二个的收益 反之亦是如此 当然，我们要设置一个访问数组记录是否某个权值已经被加过了 PS：双指针好难懂啊qaq 123456789101112131415161718192021222324252627282930313233343536373839#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <st...