dilingtian

分类

题解(18)

/ 注册

全部文章（共17篇）

题解 | #小A的柱状图#

本题是找一个最大面积的矩形，图形是不能变换的，所以我们只需要先确定左右区间，再得到本区间的最小高度便可得到面积。我们可以通过栈的特点，确定第i个位置上的左端点和右端点，高度为h[i]。h[i]。h[i]。当我们遍历到第i个位置时，我们以h[i]h[i]h[i]为矩形高度，对于左右端点而言，增加高度...

栈前缀和

2022-11-06

1 384

题解 | #小A买彩票#

这是一个计算概率的问题，最直接的做法是将满足条件的情况数算出，除以所有情况。观察到本题的数据nnn只有30，所以所有情况最多只有4304^{30}430种，即260<2642^{60}<2^{64}260<264。方法一：时间复杂度（N5N^5N5）题意中说只有四种牌，我们进行...

动态规划暴力

2022-11-04

1 471

题解 | #乌龟棋#

本题不可以采用dfs爆搜，极其容易TLE，因为时间复杂度大致为:4M4^M4M,而M的大小为120，即使在运算过程中达不到4M4^M4M，但是也远远大于10710^7107，所以我们应该使用动态规划。题目中说只有四种牌，这个是可以利用的条件。我们dp的状态表示每张牌已经使用了多少张，我们根据使用的牌...

动态规划

2022-11-03

1 381

题解 | #Forsaken喜欢数论#

欧拉筛题解欧拉筛欧拉筛法可以在线性的时间复杂度里筛出N以内的所有质数 vector<long long> oula(long long n) { vector<long long> prime; vector<bool> vis(n + 1...

欧拉筛数学

2022-11-03

1 417

题解 | #装货物#

有 n 件货物，第i件重wiw_iwi吨，另有 x 个集装箱，每个集装箱可以装重量不超过 W 吨的货物。货物不能分拆，请判断这 x 个集装箱能否装下所有货物。 n的数据很小，所以可以考虑爆搜 AC代码 #include <bits/stdc++.h> using namespace...

dfs

2022-11-02

1 478

题解 | #区间权值#

求解:∑l=1n∑r=lnwr−l+1∗∑i=lrai\sum_{l=1} ^n \sum_{r=l} ^n w_{r-l+1}*\sum_{i=l} ^ra_i∑l=1n∑r=lnwr−l+1∗∑i=lrai 定义：si=∑j=1iaj,sumi=∑j=1isjs_i=\sum_{j=1...

数学

2022-11-02

1 424

题解 | #Paint Box#

快速幂排列组合容斥原理及二项式反演题解快速幂对于一个数的次幂，如:2102^{10}210。最常规的计算方法是将2乘以10次，时间复杂度为：O(NNN)。如果我们将它写成二进制:2101022^{{1010}_2}210102，很自然的可以分解成2100022^{{1000}_2}2...

C++ 数学计数排序组合数学

2022-11-02

2 558