C 小球下落_牛客博客

C 小球下落

想要代码量少，思维量一定要大。
这个题可以用 $dfs$ 爆搜，~~但我太菜了写不出来~~ ，比赛时写了个 $bfs$ 只得了30分。赛后看了眼大佬们的代码，才发现是真的巧妙。

首先核心思想是贪心。反向输入图形，把第 $n$ 行当作第 $1$ 行，现在的目标就是尽可能的去让球去填满上面的空。但是，有三种情况是会封死路的

xx
.x
x.
x.
.x

所以要分区。所以现在问题就转化成了，让球去尽量往上填这一分区的空。

先给出代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n , r , f , Q[N << 1];
long long ans=0;
char a[N][5];

int main()
{
    scanf("%d", &n);
    for(int i = n; i >= 1;i--) scanf("%s", a[i]);
    for(int i = 1; i <= n;i++)
    {
        if(a[i][0] != 'x') Q[r++] = i;
        if(a[i][1] != 'x') Q[r++] = i;
        if(a[i][0] == 'o') ans += i - Q[f++];
        if(a[i][1] == 'o') ans += i - Q[f++];
        if((a[i][0]=='x'&&a[i][1]=='x')||(a[i][0]=='x'&&a[i+1][1]=='x')||(a[i+1][0]=='x'&&a[i][1]=='x')) r = f = 0;
    }
    printf("%lld\n", ans);
    return 0;
}

一一解释变量。

$Q$ 数组下标是递增的，代表目前除了x的个数； $Q$ 数组的值代表这个不是x的字符是第几行的。
顺着下来，上去的球就也相当于点了。

$r$ 就是下标。

  if(a[i][0] != 'x') Q[r++] = i;
  if(a[i][1] != 'x') Q[r++] = i;

$f$ 为全部空位（包括点和已经上去的球）已被球占用了的个数，也同样作为 $Q$ 的下标。
```
  if(a[i][0] == 'o') ans += i - Q[f++];
  if(a[i][1] == 'o') ans += i - Q[f++];
```
$ans$ 加上当前行减去目前存在空位最上面的行， $f$ 继续自增。
最后，就是当出现三种拦路的情况，直接让 $r,f$ 都清 $0$ 即可。相当于就是开辟了个新的分区，啥都清 $0$ 了。