题目大意：
长度为 n ，含有 m 个 1 的 01串含有 1 的子串个数 最多是多少
思路：
既然是要求含有 1 的子串个数要最多，也就是要让含有 0 的子串个数要最少
长度为 n 的字符串它的子串总个数是 n * (n + 1) / 2
我们考虑全为0的子串个数
我们有m个1，相当于有m+1的空隙可以用来放0。那么显然我们把这n-m个0匀着放到这m+1个空隙，可以使得每个0的部分尽可能短，进而使得全为0的子串尽可能少。
所以每个空隙放 a = (n-m)/(m+1) 因为不能整除，所有有 b = (n-m) % (m+1)个空隙实际上还要再多一个0。
如果每个空隙都放a = (n-m)/(m+1)个，那么显然每个空隙产生 a * (a + 1) / 2，一共产生(m + 1) * a * (a + 1) / 2 个全为0的子串。但是有b个空隙实际上还有一个0，所以还要在多产生b * (a+1)个串。
#include <iostream> #include <algorithm> #include <string> #include <string.h> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <math.h> #include <cstdio> #include <iomanip> #include <time.h> #include <bitset> #include <cmath> #define LL long long #define INF 0x3f3f3f3f #define ls nod<<1 #define rs (nod<<1)+1 const double eps = 1e-10; const int maxn = 1e5 + 10; const LL mod = 1e9 + 7; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; int main() { int T; cin >> T; while (T--) { int n,m; cin >> n >> m; LL tot = 1ll*n*(n+1)/2; LL a = (n-m)/(m+1); LL b = (n-m)%(m+1); cout << tot-a*(a+1)/2*(m+1)-(a+1)*b << endl; } return 0; }
原文：https://www.cnblogs.com/-Ackerman/p/12325761.html