题目链接：https://ac.nowcoder.com/acm/contest/5673/E
题意
数$n$的拆分，要求最大值与最小值相差为2，且相邻两个数之间相差小于1，$f[i]$表示拆分的个数。 有T组测试，每组给出l和r，求出$\sum_{i=l}^rf[i]$。
思路
首先知道$n$是由三个连续自然数之和相加组成的，当然，这三个自然数的个数是不知道的，那么就是求$$f[i]=a*l+b*(l+1)+c*(l+2)（a，b，c\ge q1）$$
方法一
根据标程给的题解，它是枚举$l$，所以这三个数为$l,l+1,l+2$，表示为$l,mid,r$，我们知道两个$mid$可以拆成$l和r$，所以当有$m$个$mid$的时候，就有$(m-1)/2$中拆法，例如：（下面三个数字分别为$l，mid和r的个数$） $m=5：有2种拆法$ $1，2，1$ $2，0，2$ $m=8：有3种拆法$ $1，5，1$ $2，3，2$ $3，1，3$
为什么$mid$可以等于0，因为之前$m-1$,这个1就是$mid$。 为什么$l和r$不可以等于0，这样的话就不保证$a,c\ge q1$。
这样枚举$l$的过程中，再分别枚举$m$的个数，再枚举往左加$l$的个数和往右加$r$的个数，最后再做个前缀和答案就出来了，不过问题就是$l\leq100$，标程说枚举会比较慢（是非常慢），所以要用dp优化，不过我也不会就咕咕咕了，然后就有了第二种方法。
! #### 方法二 应该也算枚举，不过是很巧妙的枚举。我也是看别人的博客才稍微懂一点点点点的。 这里应用了差分的思想。 最后是一阶差分+隔项差分。 参考大佬的博客： [大佬1](https://blog.csdn.net/zhangchizc/article/details/107784622?utm\_medium=distribute.pc\_relevant.none-task-blog-baidulandingword-2&spm=1001.2101.3001.4242) [大佬2](https://blog.csdn.net/zhangchizc/article/details/107784622?utm\_medium=distribute.pc\_relevant.none-task-blog-baidulandingword-2&spm=1001.2101.3001.4242 “大佬2”) [大佬3](https://www.cnblogs.com/rair/p/13430729.html) 关于差分，可以参考：[https://blog.csdn.net/qq\_44786250/article/details/100056975\](https://blog.csdn.net/qq\_44786250/article/details/100056975) 一阶差分就是后一项减去前一项$d[i] = a[i]-a[i-1]$。 隔项差分就是后一项的后一项减去前一项$d[i] =a[i]-a[i-2]$。 然后回到本题。 我们先把式子改变一下。 $m=b1+b2+b3$ $n=a*b1+(a+1)*b2+(a+2)*b3=a*(b1+b2+b3)+b2+2b3=am+b2+2b3$ 具体细节请看上面三个大佬的博客。 最后我们得出来： $f[am+3]++，f[(a+1)m+1]–，f[(a+1)m+2]–，f[(a+2)m]++$ 这里一定要看图解，不然真的很昏。 只要我们枚举$a和m$之后，然后对上述位置进行加减操作，最后在隔项差分、一阶差分求出原数组，最后在前缀和得出答案。 ## Code ```c++ ##include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pdd; ##define INF 0x7f7f7f ##define mem(a, b) memset(a , b , sizeof(a)) ##define FOR(i, x, n) for(int i = x;i <= n; i++) // const ll mod = 1e9 + 7; // const int maxn = 1e5 + 10; // const double eps = 1e-6; const int N = 1e5 + 10; ll f[N * 2]; ll F[N * 2]; void Init() { for(int m = 3;m < N; m++) { for(int a = 1;a * m < N; a++) { f[a * m + 3]++; f[(a + 1) * m + 1]–; f[(a + 1) * m + 2]–; f[(a + 2) * m]++; } } for(int i = 3;i < N; i++) f[i] += f[i - 2]; for(int i = 2;i < N; i++) f[i] += f[i - 1]; for(int i = 1;i < N; i++) F[i] = F[i - 1] + f[i]; } void solve() { Init(); int Case = 1; int T; cin >> T; while(T–) { int l, r; cin >> l >> r; cout << “Case ##” << Case++ << “: “ << F[r] - F[l - 1] << endl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ##ifdef ACM_LOCAL freopen(“in.txt”, “r”, stdin); freopen(“out.txt”, “w”, stdout); solve(); ##else solve(); ##endif return 0; } ``` ## 反思 **比赛再也不在一题上花5个小时了，呜呜呜~~~**
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/08/05/2020-nowcoder-shujia-8-e/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！