洛谷同题 其实大佬们的题解本菜鸡都看不懂，在这里给出另一种形而上的理解，以及期待能有更加完备的数学解释：为什么负净收益序列中可以单纯对收益b排序。 只有上面的问题比较复杂。 首先对序列的净收益排序，赚的先打（让资本达到峰值），亏的后打。 然后既然都是赚的，那么就先打简单的，刷小怪，这样随着应对的挑战在上升，资本也在上升，这一步的贪心非常好理解。 那么重头戏来了，对于亏损的怪，迟早也都要打，那么选取什么样的策略呢？ 对于负收益序列，能不能采用对c从大到小排列（降序）或者对a降序呢？毕竟资本在持续减少，先啃硬骨头也就是a大的看起来也有点道理。 想一个简单的的案例： 7 2 5 2 4 3初始7血，...

结构体数组写法更好，不需要每次都更新，检索到无法剪到的地方更新即可。 考虑对布条排序，右端优先比左端优先更好，因为贪心肯定是在尽可能最右的地方剪，剪不到的地方就说明一刀无法满足，需要进行下一个区间判断了。 我不知道我有没有说清楚，如果没懂可以再留言问我。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; const ll mod = 1e9 + 7; struct p { ll L, R;//左边和右边 } a[N]; bool cmp(p a, p ...

二维前缀和，思路是建一个二维数组表示从炸到所能收获的value之和。 然后就一个一个比过去就好了。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e3 + 7; const ll mod = 1e9 + 7; inline ll read() { ll s = 0, f = 1; char ch; do { ch = getchar(); if (ch == '-') f = -1; } while (ch < 48 || ch > 57); whil...

一道水题，一开始还想写一个从最高位逐位比对的cmp…… 真是被秀到 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; string a[N]; bool cmp(string a, string b) { return a + b > b + a; } int main() { int n;cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; sort(a, a + n...

一道水题，但是在编码的时候居然卡住了，收集了一些写法，还满有趣的。 我自己的 vector #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; const ll mod = 1e9 + 7; inline ll read() { ll s = 0, f = 1; char ch; do { ch = getchar(); if (ch == '-') f = -1; } while (ch < 48 || ch > 57); while (c...

没什么可说的，记录一下写法，以及long double这种精度 引用自兰子大佬  很容易发现左边是一个单调增的函数，所以二分求解即可。值得注意的是如果用double可能出现tle的情况（实测double精度有问题，导致后面无限不动）。解决方法有两种，一种是换long double，另外一种是进行足够多次二分即可（例如1000次二分），可以避免tle的出现。  青竹大佬的 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7, mod = 1e9 + 7; const double eps = 1...

其实兰子大佬的题解已经很好很清楚了，我写这个只是为了方便我自己看。  想了很久按位计算贡献是什么意思。 套路就在于按位统计 int c[100]={0}; for(int i = 1; i <= n; i++) { long long x,b=0; scanf("%lld", &x); while(x) c[b++] += x & 1, x >>= 1; } 这样就可以统计出来每一位1的个数，那么就是每一位0的个数。 这一位三元异或和为1的情况只有或者。 然后对这两种情况累加一下，乘上对应的位数就好了。 #include <bits/stdc++.h&g...

本题考察栈这一数据结构，可使用STL或直接用数组模拟。 直接用数组模拟码量更小。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5 + 7; const ll mod = 1e9 + 7; char s[N]; char st[N]; int main(){ cin>>s; int n=strlen(s),p=1; st[0]=s[0]; for(int i=1;i<n;++i){ if(s[i]==st[p-1])p--; else st[p+...

贪心，每个数字只用一次，从前往后扫一遍即可。 想复杂了，最简单的就是最好的。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll T, a; cin >> T; while (T--) { cin >> a; ll cnt = 0; for (ll i = 1; i <= a; ++i) if (a % i == 0) a /= i, ++cnt; cout << cnt << endl; } return 0; ...

使用游标的左边和游标的右边，用两个变量记录，成功配合前缀和完成对区间的分离。 #include <bits/stdc++.h> using namespace std; long long a[200001]; int main() { int T, n, k; cin >> T; while (T--) { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1]; long long maxx = -1e18, ans = -1e18;...

题目表述不是特别好而且数据没有给全，比如m的数据规模没有给出。 正向的时间复杂度是 后缀数组+差分 实际上影响因子只有最末敌对最大点，也即：如果一个人后面没有比他更大的另一个队伍的人，那么他一定能活下来。 故从后往前看只需要不断锚定最大的点，逐步更新计数即可。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 1e6 + 7; const int N = 50005; int a[N], b[N], v[N], mx[2], c; int main() { ll n, ...

分析 考虑对 质因数分解，并将提取成的最简形式。如果要满足，对于任意一个而言，化简后都带有。 于是问题被转化成能被表示为多少种个数的和，其中可以有。 也即个苹果放在个篮子里有多少种放法。 此处可用dp解， 表示个苹果放在个篮子里方法总数。 转移方程为 应牛友要求详细解释一下： 把5个苹果放进2个篮子里，我们已经知道了五个苹果放进一个篮子里有多少种方法，那么现在多出来了一个篮子，考虑篮子不空的情况，先把所有的篮子都放一个苹果，然后再加上3个苹果放进两个篮子里的方案数量。 也就是说对于， 是空了篮子的方案，是一个篮子都不空的方案。无论空多少个篮子呢，都包含在里面：这里是类似递归的理解，空一个篮子里...

和校门口的树是一样的。只不过校门口的树数据太水了。 对于，前缀和 + 差分可以满足需求，再大就需要离散化，这个离散化还是稍有难度的（暂时先不写了 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e8 + 7; const ll mod = 1e9 + 7; inline ll read() { ll s = 0, f = 1; char ch; do { ch = getchar(); if (ch == '-') f = -1; } while (ch < ...

题目大意  在起点为a，终点为b的滑道上，有两个长度为t小滑块随机滑动（可重叠） ，问它们重叠的概率。 分析 a,b是无用信息，设 ，当特别大，超过时，第二个滑块无处可放，必定重叠。   对于一般情况，另外分析：我们把二者的数轴分离，即建立平面直角坐标系，设为小滑块甲的起始坐标，为小滑块乙的起始坐标。 当二者重叠时，满足 ，即建立如下坐标系，完成线性规划。   知可行域内面积为整个正方形面积减去两个三角形面积，即，概率。 即解。 solution #include <bits/stdc++.h> using namespace std; const double eps = 1e-...