2020-5-16CF反思ZHK's blog-

CF凉了是显然的，不然也不会写这篇反思了。

开题很快
$AC$

AC 了
$A$

A 和
$B$

B。

到了
$C$

C 的时候定睛一看

Like any unknown mathematician, Yuri has favourite numbers:
$A, B, C$

A,B,C and
$D$

D, where
$A≤B≤C≤D$

A≤B≤C≤D. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides
$x, y$

x,y and
$z$

z exist, such that
$A≤x≤B≤y≤C≤z≤D$

A≤x≤B≤y≤C≤z≤D holds?

Yuri is preparing problems for a new contest now, so he is very busy. That’s why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.

这段英文还是挺好懂的，就是说一个三角形三条边分别为
$x,y,z$

x,y,z，有如下限制

$Ale x le B le yle C le zle D$

A≤x≤B≤y≤C≤z≤D

显然等于

$A le x leq B\ B le y leq C\ C le z leq D$

A≤x≤BB≤y≤CC≤z≤D

我们知道三角形要满足
$2$

2 边之和大于第
$3$

3 边的。

所以
$x +y >z$

x+y>z

我的做法是枚举
$x+y$

x+y，答案显然
$=$

=
$x,y$

x,y 取值方案数
$times$

×
$z$

z 的取值方案数

对于
$x,y$

x,y 的取值方案数

我猛然想到《组合数学》上的内容，那是不久前刚学的所以现在十分记忆犹新，这种东西，我之前只手算过，压根儿也没有想过有朝一日要用程序算出来。

回到题目

设
$x+y=k$

x+y=k

则

$x+y=k\ Aleq xleq B\ Bleq yleq C$

x+y=kA≤x≤BB≤y≤C

我们去化解

$x+y=k-A-B\ 0leq xleq B-A\ 0leq yleq C-B$

x+y=k−A−B0≤x≤B−A0≤y≤C−B

直接套无限多重集的多重集合的结论

设
$n=k-A-B,X=B-A,Y=C-B$

n=k−A−B,X=B−A,Y=C−B

$begin{pmatrix} n+2-1 \ n end{pmatrix}+ begin{pmatrix} n-A-1+2-1 \ n-A-1 end{pmatrix}+ begin{pmatrix} n-B-1+2-1 \ n-B-1 end{pmatrix}+ begin{pmatrix} n-A-B-2+2-1 \ n-A-B-2 end{pmatrix}$

(n+2−1n​)+(n−A−1+2−1n−A−1​)+(n−B−1+2−1n−B−1​)+(n−A−B−2+2−1n−A−B−2​)
我们来捋一捋

$begin{pmatrix} n+1 \ n end{pmatrix}+ begin{pmatrix} n-A \ n-A-1 end{pmatrix}+ begin{pmatrix} n-B \ n-B-1 end{pmatrix}+ begin{pmatrix} n-A-B-1 \ n-A-B-2 end{pmatrix}$

(n+1n​)+(n−An−A−1​)+(n−Bn−B−1​)+(n−A−B−1n−A−B−2​)

然后这个东西巨难调，好不容易过了
$3$

3 个样例自信满满地去交得到的确实
$WA$

WA 声一片。

这个题目的数据挺好造的，于是，我自信满满地打了个对拍，拍了几组发现了几个小问题逐一化解之后又交，又
$WA$

WA。

时间就像哗啦啦的小溪总是在不经意间悄无声息地流走了。时间所剩无几，但我也一直在努力。

之后突然发现这
$4$

4 个组合数可以直接求，于是有改了改代码，还是
$WA$

WA。

最后时刻，我把暴力一交发现暴力也
$WA$

WA 了，我绝望了。

此时的我排名已来到了
$5000+$

5000+ 名，
$D$

D、
$E$

E 和
$F$

F都没有碰过，但也不敢碰了，不停的死磕
$C$

C。

带到倒计时种那苍白而又孤独的
$00:00$

00:00 的到来，无助的我也叹了叹气。

窗外一片黑灯瞎火，只有房间还闪烁着些许亮光，
$textsf{textbf{textcolor{black}{w}textcolor{red}{33z8kqrqk8zzzx33}}}$

w33z8kqrqk8zzzx33 怒切
$A$

A、
$B$

B、
$C$

C 和
$E$

E，更给孤独的我的心头埋上了一片阴霾。

风扇还在不停地转动，我为什么就不能在继续呢？

我开始了艰难而又漫长地调题，我在静思中梳理，在思索中奋斗，在 May/16/2020 22:52 我
$AC$

AC 了，我的心犹如初生的旭日般明亮，
$AC$

AC 的代码和比赛最后一次提交的代码仅仅有一处不同，而正是这一处让我的分数悄然无息而又微妙地发生了变化。

回首再去看看对拍的代码

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; template<typename T>inline void read(T &FF) {  T RR = 1; FF = 0; char CH = getchar(); for (; !isdigit(CH); CH = getchar())if (CH == '-')RR = -1; for (; isdigit(CH); CH = getchar())FF = (FF << 1) + (FF << 3) + (CH ^ 48);  FF *= RR; } template<typename T>inline void write(T FF) { if (FF < 0) { putchar('-');   FF *= -1; } if (FF > 9)write(FF / 10); putchar(FF % 10 + 48); } template<typename T>inline void writen(T FF) { write(FF); puts(""); } ll C(ll m, ll n) { if (n == 0)return 1; if (m <= 0 || n <= 0)return 0;  ll ans = 1; for (ll i = 0; i < n; i++)ans *= m - i; for (ll i = 1; i <= n; i++)ans /= i; return ans; } ll work(ll i, ll l, ll r) { return min(i - l + 1, r - l + 1); } ll xxx(ll a,ll b,ll c,ll d){  ll ans = 0; for (ll i = c + 1; i <= b + c; i++) {   ll x = b - a, y = c - b;   ll m = i - a - b;   ll n = m + 1 - max((m - x), (ll)0) - max((m - y), (ll)0) + max((m - x - y), (ll)0);   ans += max(n, (ll)0) * max((ll)0, work(i - 1, c, d)); } return ans; } ll xx(ll a,ll b,ll c,ll d){  ll ans=0; for(int x=a;x<=b;x++){ for(int y=b;y<=c;y++){    ans+=max((ll)0,work(x+y-1,c,d)); } }return ans; } int main() { srand(time(NULL)); while(1){   ll a=1+rand()%20,b=a+rand()%20,c=b+rand()%20,d=c+rand()%20; if(xx(a,b,c,d)!=xxx(a,b,c,d)){    cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;    cout<<xx(a,b,c,d)<<" "<<xxx(a,b,c,d); return 0; } } return 0; } 

悲楚也会变得快乐。

$textsf{textbf{textcolor{black}{w}textcolor{red}{33z8kqrqk8zzzx33}}}$

w33z8kqrqk8zzzx33 的做法比我的做法简单的多，但我的方法就是我的方法。

$textsf{textbf{textcolor{black}{h}textcolor{red}{zw}}}$

hzw 大佬说过：

自己选择的路跪着也要走完

OI比赛似乎注定是无情的，在坚强的意志品质的同时，几分理性同样是不可或缺的，
$D$

D、
$E$

E 和
$F$

F 我明天再调qwq