ovo的憨憨题解

这题毫无疑问是递归ovo

先上代码：

变量解释

t：t组案例

tot：记录排法种数

red，gre：记录红灯，绿灯个数

color：记录上一个灯的颜色

首先是对输入数据的处理，如果不处理则TLEqwq

根据题意，红灯后必放绿灯

所以， 1.当红灯=绿灯时，排序方式只有“红绿红绿红绿...红绿”一种，直接输出 1；

            2.当红灯>绿灯时，一定没有合理的排序方式，输出0；

            3.当红灯<绿灯时，用递归统计种数

然后是递归的处理

由于红灯后面必须放一个绿灯，所以递归顺序可以从后往前排，则首位必须是绿灯

有三种情况可以终止判断，减少时间

1.红灯=0，则后面只能排y个绿灯，无论如何排序都只算一种，tot++后退出；

2.绿灯=0，红灯>1，因为红灯后必排绿灯，所以此解不合法，直接退出

2.绿灯=0，红灯=1且前一个是绿灯，则红灯可以摆进去，tot++；

最后就是注意一下排红灯的时候要保证前一个不是红灯，这里我用了一个color记录颜色

如果有不足的地方希望大佬补充qwq

ovo大佬tql

那么迭代版也就是组合数C(n,m)

n为红灯，m为绿灯

由于红灯只能放在绿灯前，所以绿灯前的m个位置挑n个出来放红灯就是最终的答案

%%%%%%%%%%%%%%大佬ovo

这题好像是个阶乘？

我试了 这题用阶乘会爆  ！500000 6位数不断相乘很容易爆