橫截面圖上的區域

你的任務是模擬洪水災害。
對於給定的橫截面圖，給出淹沒部分的面積。

假設該地區不斷地下雨，而從該地區溢出的水正在落入兩側的海中。例如，對於上面的橫截面圖，雨水將產生洪水，其面積分別為 4、2、1、19 和 9。
輸入
在一行中給出一個字符串，分別用 "/",""和"_" 表示斜坡和平原。例如，上面例子的區域由字符串 “\ \ /// \ _ / \ / \ \ \ \ /_/ \ \ ///_ _ \ \ \ _ \ \ /_ \ /_/” 給出。
輸出
按以下格式輸出：
A
K L1,L2,…,Lk
在第一行，打印出洪水區域的總面積 A。
在第二行，打印出洪水區域的個數 K 和每個區域的面積 Li（從左到右）。
約束
1 ≤ length of the string ≤ 20000

看到這道題，我首先想到我們可以從頭開始，一格一格向後找到開始往下凹的地方，持續跟蹤直到高度與之前持平。然後繼續往後直到又開始下降然後重複之前的過程。。
然後我發現，很容易就會遇到，再也達不到之前開始下降的高度的情況，於是我果斷地放棄這種方案，寫了一個大模擬：
直接構建一個橫截面圖，用 0 代表空氣，1 代表山體，2 代表整格水，3 代表下降的半格水，4 代表上升的半格水
先把山以上的部位全部填滿水，然後重複執行：將左右下方任一方向是空氣的水扔掉，直到再也扔不掉為止，剩下的就是我們的積水
最後用 dfs 找到每一坨水，算出面積
然後我們發現地圖是個二維數組，定義成ditu[MAXN][MAXN]的話會直接爆空間。然後我們考慮到應該不會有一直下降或上升的山所以高度用不到那麼多格，於是嘗試開小第二維。
喜提兩個 TLE

#include <stdio.h>

#define MAXN 20005
#define INF ((int)0x3f3f3f3f)
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) < (b) ? (b) : (a))
int a[MAXN] = {0};
int ditu[MAXN][1005] = {0};//0:empty,1:shan,2:shui,3:downshan,4:upshan
short vis[MAXN][1005] = {0};
int mmjimf[MAXN] = {0};
int newm = 0;

double dfs(int x, int y)
{
    if (vis[x][y])
    {
        return 0.;
    }
    vis[x][y] = 1;

    double value = 0;
    switch (ditu[x][y])
    {
        case 2:
            value = 1;
            break;
        case 3:
        case 4:
            value = 0.5;
            break;
        default:
            return 0;
    }
    if (ditu[x][y] == 2) value += dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1);
    else if (ditu[x][y] == 3)
    {
        value += dfs(x + 1, y)  + dfs(x, y + 1) + dfs(x, y - 1);
        if (ditu[x - 1][y] != 4)
        {
            value += dfs(x - 1, y);
        }
    } else if (ditu[x][y] == 4)
    {
        value += dfs(x - 1, y)  + dfs(x, y + 1) + dfs(x, y - 1);
        if (ditu[x + 1][y] != 3)
        {
            value += dfs(x + 1, y);
        }
    }
    return value;
}

int main(void)
{
    char c = getchar();
    int newp = 1;
    int zvdi = INF, zvgc = -INF;
    while (c == '/' || c == '\\' || c == '_')
    {
        ++newp;
        switch (c)
        {
            case '/':
                a[newp] = a[newp - 1] + 1;
                break;
            case '\\':
                a[newp] = a[newp - 1] - 1;
                break;
            case '_':
                a[newp] = a[newp - 1];
                break;
        }
        if (a[newp] < zvdi)
        {
            zvdi = a[newp];
        }

        c = getchar();
    }
    for (int i = 1; i <= newp; ++i)
    {
        a[i] += (-zvdi + 1);
        if (a[i] > zvgc)
        {
            zvgc = a[i];
        }
    }

    for (int i = 1; i < newp; ++i)
    {
        int low = min(a[i], a[i + 1]);
        int high = max(a[i], a[i + 1]);
        for (int j = 1; j <= zvgc; ++j)
        {
            if (j <= low)
            {
                ditu[i][j] = 1;
            } else if (j >= low && j <= high)
            {
                if (low != high)
                {
                    if (a[i] > a[i + 1]) ditu[i][j] = 3;
                    else ditu[i][j] = 4;
                } else
                {
                    ditu[i][j] = 2;
                }

            } else if (j > high)
            {
                ditu[i][j] = 2;
            }
        }
    }
    int vcdc = 0;
    do
    {
        vcdc = 0;
        for (int j = zvgc; j >= 1; --j)
        {
            for (int i = 1; i < newp; ++i)
            {
                if (ditu[i][j] == 2 || ditu[i][j] == 3 || ditu[i][j] == 4)
                {
                    if (!((ditu[i - 1][j] || ditu[i][j] == 3) && (ditu[i + 1][j] || ditu[i][j] == 4) && ditu[i][j - 1]))
                    {
                        ++vcdc;
                        ditu[i][j] = 0;
                    }
                }
            }
        }
    } while (vcdc);
    double mmji = 0;
    for (int j = zvgc; j >= 1; --j)
    {
        for (int i = 1; i < newp; ++i)
        {
            switch (ditu[i][j])
            {
                case 2:
                    mmji += 1;
                    break;
                case 3:
                case 4:
                    mmji += 0.5;
                    break;
            }
        }
    }
    printf("%.0lf\n", mmji);
    for (int i = 1; i < newp; ++i)
    {
        for (int j = zvgc; j >= 1; --j)
        {
            if (!vis[i][j])
            {
                double ans = dfs(i, j);
                if (ans) mmjimf[++newm] = ans;
            }
        }
    }

    printf("%d ", newm);
    for (int i = 1; i <= newm; ++i)
    {
        printf("%d ", mmjimf[i]);
    }
    return 0;
}

遇到嚴重超時 TLE，我內心十分悲痛，打開了必應，搜索全網，搜到了一个題解。這個題解告訴我們

由淹沒區域可以想到 ‘\’ 與 '/' 的配對。
此題比較特別的是如何組成一整個被水淹沒的區間？答案是將所有配對的區間中相互包含的區間合併。
如何合併呢？可以知道大區間所包含的小區間必定比大區間先入棧，則可以依此合併。
如何計算橫截面積？所有配對的‘\’與 '/' 之間形成的橫截面都為梯形或三角形，把問題分解為多個小問題來解答。

我看完大受啟發，決定按此思路寫一寫。寫了一段後發現，這哪裡用得到棧，好像只需要加加減減就可以了。
這時我發現，只要我把最開始的做法變得更暴力一點，從每一個起點出發，如果再也達不到之前開始下降的高度，就扔掉這個起點，換下一个起點。這樣做不僅不會浪費太多空間，而且比大模擬快很多，順利 AC。

#include <stdio.h>

#define MAXN 20005

char sgn[MAXN] = {0};
double ans[MAXN] = {0};
double tot = 0;
int news = 0;
int newa = 0;

int main()
{
    int h = 0;
    char t = getchar();
    while (t == '/' || t == '\\' || t == '_')
    {
        sgn[++news] = t;
        t = getchar();
    }
    int i = 1;
    while (i <= news)
    {
        double sum = .5, hi = 1;
        if (sgn[i] != '\\')
        {
            ++i;
            continue;
        }
        int st = 1;
        int j;
        for (j = i + 1; j <= news && st > 0; ++j)
        {
            if (sgn[j] == '\\')
            {
                ++st;
                ++hi;
                sum += (hi - .5);
            } else if (sgn[j] == '/')
            {
                --st;
                --hi;
                sum += (hi + .5);
            } else
            {
                sum += hi;
            }
        }
        if (st == 0)
        {
            i = j;
            ans[++newa] = sum;
            tot += sum;
        } else
        {
            ++i;
        }
    }

    printf("%.0lf\n%d ", tot, newa);
    for (int i = 1; i <= newa; ++i)
    {
        printf("%.0lf ", ans[i]);
    }
    return 0;
}

復健之路進行中～～