【Codeforces Round #317Div1 —— A】Lengthening Sticks【数学思维题】

题意：

给出三个木棒的长度为$a$、$b$、$c$，再给出一个长度 $l$ 用来增加三根木棒的长度。三根木棒长度增加之和不能超过$l$，可以为$0$。问有多少种增长方案使得这三根木棒可以拼成一个三角形。$(1\le a,b,c\le 3\ast 10^5,0\le l\le 3\ast 10^5)$

---

思路：

最简单的思路就是令$x$、$y$、$z$分别为$a$、$b$、$c$三根木棒的长度增加值。则 $x+y+z\le l$，然后令 $x+y+z=\text{H}(0\le H\le l)$，枚举 $\text{H}$，计算答案。

比赛时我的思路是正向求解这个问题，然后就可以列出下述的式子。 $$\{\begin{array}{rl}& x+y+z=\text{H}\\ & a+x<b+y+z+c\\ & b+y<a+x+z+c\\ & z+c<a+x+b+y\end{array}$$ 于是问题就变成了一个线性规划问题，要求在线性规划区域中找到有多少个整点。然后就是不断的公式化简和推导，然后成功自闭…

其实推导到这个程度之后就应该及时调整解题方向，线性规划问题的难度是很大的，现在也没有比较好的通用方向进行解决。所以推导到线性规划之后就应该及时调转车头。

于是我们从反向入手，考虑一下容斥的思想。枚举$\text{H}$之后，计算有多少种方案使得木棒无法构成三角形。木棒无法构成三角形主要是因为 最长的木棒长度 $>$ 剩下两个木棒长度相加。因此我们枚举哪一根木棒是最长的木棒。

假如枚举了木棒 $a$ 为最长的木棒，则 $$\{\begin{array}{rl}& x+y+z=\text{H}\\ & a+x>b+y+c+z\end{array}$$ 可以得到 $2\ast x>b+c+\text{H}-a$，可以求出 $x\ge base$，于是只要给$a$分配的长度大于$base$，就一定不可以构成三角形，于是问题转化为 $x+y+z=\text{H}-base$ 有多少种分配方案。

而所有的分配方案数为 $x+y+z=\text{H}$ 的方案数。于是问题转化成了$a+b+c=z$ 有多少种不同的分配方案。

首先考虑 $b+c=z$ 有多少种不同的分配方案数。很明显有 $z+1$ 种分配方案，因此枚举 $a$，可以发现 $a+b+c=z$ 的分配方案数为 $(z+1)+z+(z-1)+...+1=\frac{(z+1)\ast (z+2)}{2}$。当然也可以直接用组合数来求取答案，用隔板法可以得到总方案数为 $C(z+2,2)$，至此本题即可解决。

---

反思：

首先总结一下常见的几个数学思维。 ① 正难则反 —— 容斥思想、反演思想 ② 变量思想 —— 设出未知量再不断进行方程化简，寻找规律

再总结一下此类数学思维题的一些经验。 ① 一道题拿到手上之后，一定要对问题不断进行抽象化简，不断地深入思考，抽丝剥茧，逐层深入，才有可能能够解决这个问题。 ② 要擅长去找到规律，从小例子上找到思路然后放到大例子上进行解决。

一个数学式子记录。 $a+b+c=z，z$ 为常数，一共有 $C(z+2,2)$ 种 <$a,b,c$> 分配方案。

---

代码：

#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define rep(i,a,b) for(int i = a; i <= b; i++) #define LOG1(x1,x2) cout << x1 << ": " << x2 << endl; #define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl; #define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl; typedef long long ll; typedef double db; const int N = 1e5+100; const int M = 1e5+100; const db EPS = 1e-9; using namespace std; int a,b,c,l; ll ans; ll calc(ll a1,ll len){ ll tp = ((a1+a1+len-1ll)*len)/2ll; return tp; } ll solve(int a1,int b1,int c1,int len){ ll tp = ceil((b1+c1+len-a1)/2.0-0.1); tp = max(0ll,tp); len -= tp; // LOG1("len",len); if(len < 0) return 0; ll hp = calc(1,len+1); return max(0ll,hp); } int main() { scanf("%d%d%d%d",&a,&b,&c,&l); rep(i,0,l){ ll tp1 = max(0ll,calc(1,i+1)); // LOG2("i",i,"tp1",tp1); ll tp2 = 0; tp2 += solve(a,b,c,i); // LOG1("tp2",tp2); tp2 += solve(b,a,c,i); // LOG1("tp2",tp2); tp2 += solve(c,a,b,i); // LOG1("tp2",tp2); ans += tp1-tp2; } printf("%lld\n",ans); return 0; }