写好模拟的同学可以思考一句话：同一列下落的石子，“基础”的路径是相同的。

假设在x列投下一个石子，其路径如下图所示：

再在x列投下一个石子，若是不考虑上一步停留的石子，那么它会走完这条路径。但事实上，上一路径的末尾处存在一颗石子，所以不妨删除路径的末尾元素，此时路径的末尾位置就是可以放石块的地方，再按照模拟的思路，考虑石子最终的归宿，并更新路径即可。

先贴60分代码有缘人自己改一改(没想到我就是自己的有缘人

标准的O( rn )代码，取最大值必超时(同时回答楼下问题)，留作参考，可以有需要的自己改一改

#include<bits/stdc++.h>
using namespace std;
int r , c , n ;
char a[ 30005 ][ 35 ] ;
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> r >> c ;
    for( int i = 0 ; i <= r + 1 ; i ++ )
    {
        if( i == 0 or i == r + 1 )
        {
            for( int j = 0 ; j <= c + 1 ; j ++ )
            {
                a[ i ][ j ] = 'O' ;
            }
            continue ;
        }
        a[ i ][ 0 ] = a[ i ][ c + 1 ] = 'O' ;
    }
    for( int i = 1 ; i <= r ; i ++ )
    {
        for( int j = 1 ; j <= c ; j ++ )
        {
            cin >> a[ i ][ j ] ;
        }
    }
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        int t1 ;
        cin >> t1 ;
        int nowi = 1 , nowj = t1 ;
        while( 1 )
        {
            if( nowi == r ) break ;
            if( a[ nowi + 1 ][ nowj ] == 'X' ) break ;
            if( a[ nowi + 1 ][ nowj ] == 'O' )
            {
                if( ( a[ nowi + 1 ][ nowj - 1 ] == 'O' or a[ nowi + 1 ][ nowj - 1 ] == 'X' ) and ( a[ nowi + 1 ][ nowj + 1 ] == 'O' or a[ nowi + 1 ][ nowj +  1 ] == 'X' ) ) break ;
                if( a[ nowi + 1 ][ nowj - 1 ] != 'O' and a[ nowi ][ nowj - 1 ] != 'O' and a[ nowi + 1 ][ nowj - 1 ] != 'X' and a[ nowi ][ nowj - 1 ] != 'X' ) nowj -- ;
                else if(a[ nowi + 1 ][ nowj + 1 ] != 'O' and a[ nowi ][ nowj + 1 ] != 'O' and a[ nowi + 1 ][ nowj + 1 ] != 'X' and a[ nowi ][ nowj + 1 ] != 'X' ) nowj ++ ;
                else break ;
            }
            nowi ++ ;
        }
        a[ nowi ][ nowj ] = 'O' ;
    }
    for( int i = 1 ; i <= r ; i ++ )
    {
        for( int j = 1 ; j <= c ; j ++ )
        {
            cout << a[ i ][ j ] ;
        }
        cout << "\n" ;
    }
    return 0;
}

满分做法参考了面条老师的说法，因为最多只有30列，所以即使n取到10^5，我们只需要记录每个点在这一列下落经过的路径，根据路径最后几个点做出路径上的改变可以减少大量重复次数 (也是属于一种剪枝优化吧大概，但是因为c最大30所以绝大多数重复都被剪掉了)

首先就是模拟部分，和上面大同小异，但是写成函数形式并记录完整路径

函数设计
nowi表示当前横坐标
nowj表示当前纵坐标
nowjd表示这是从第几列落下来的石头,记录路径时候会用到
然后就是模拟部分，值得注意的是需要注意扣细节
    比如题目说左侧和左下方，不要仅仅理解为左下方了，这样会导致出错

void down( int nowi , int nowj , int nowjd )
{
    while( 1 )
    {
        if( nowi == r ) break ;
        if( a[ nowi + 1 ][ nowj ] == 'X' ) break ;
        if( a[ nowi + 1 ][ nowj ] == 'O' )
        {
            if( ( a[ nowi + 1 ][ nowj - 1 ] == 'O' or a[ nowi + 1 ][ nowj - 1 ] == 'X' ) and ( a[ nowi + 1 ][ nowj + 1 ] == 'O' or a[ nowi + 1 ][ nowj +  1 ] == 'X' ) ) break ;
            if( a[ nowi + 1 ][ nowj - 1 ] != 'O' and a[ nowi ][ nowj - 1 ] != 'O' and a[ nowi + 1 ][ nowj - 1 ] != 'X' and a[ nowi ][ nowj - 1 ] != 'X' )
            {
                nowj -- , nowi ++ ;
                vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
                continue ;
            }
            else if(a[ nowi + 1 ][ nowj + 1 ] != 'O' and a[ nowi ][ nowj + 1 ] != 'O' and a[ nowi + 1 ][ nowj + 1 ] != 'X' and a[ nowi ][ nowj + 1 ] != 'X' )
            {
                nowj ++ , nowi ++ ;
                vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
                continue ;
            }
            else break ;
        }
        nowi ++ ;
        vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
    }
    a[ nowi ][ nowj ] = 'O' ;
    vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
}

然后就是根据路径剪枝部分，这部分我选择放在主函数中进行

这部分的注意事项就是注意别在空栈的时候对栈执行除.empty()和.push()以外的任何操作，否则肯定会内存错误爆RTE
然后就是当栈里没有保存你的路径的时候就要完整执行一遍下落过程代码存储路径，以后就可以直接用这个路径来优化了
为什么要执行多次pop:因为有可能路径上有多个已经定住的石块了需要把它们都出栈

还有需要注意的就是别钻牛角尖不然就像我一样九小时就做一道题

for( int i = 1 ; i <= n ; i ++ )
{
    if( vis[ b[ i ] ].empty() )
    {
        down( 1 , b[ i ] , b[ i ] ) ; 
    }
    else
    {
        while( !vis[ b[ i ] ].empty() )
        {
        	XoY t2 = vis[ b[ i ] ].top() ;
        	if( a[ t2.x ][ t2.y ] != 'O' ) break ;
        	vis[ b[ i ] ].pop() ;
		}
        if( !vis[ b[ i ] ].empty() ) 
        {
            XoY t2 = vis[ b[ i ] ].top() ;
            down( t2.x , t2.y , b[ i ] ) ;
        }
        else
        {
            down( 1 , b[ i ] , b[ i ] ) ;
        }
    }
}

其余注意输出和一份能让自己看得赏心悦目的代码(?

完整代码见下

#include<bits/stdc++.h>
using namespace std;
struct XoY
{
    int x ; int y ;
};
int r , c , n , b[ 100001 ] ;
char a[ 30005 ][ 35 ] ;
stack<XoY> vis[ 35 ] ;
void down( int nowi , int nowj , int nowjd )
{
    while( 1 )
    {
        if( nowi == r ) break ;
        if( a[ nowi + 1 ][ nowj ] == 'X' ) break ;
        if( a[ nowi + 1 ][ nowj ] == 'O' )
        {
            if( ( a[ nowi + 1 ][ nowj - 1 ] == 'O' or a[ nowi + 1 ][ nowj - 1 ] == 'X' ) and ( a[ nowi + 1 ][ nowj + 1 ] == 'O' or a[ nowi + 1 ][ nowj +  1 ] == 'X' ) ) break ;
            if( a[ nowi + 1 ][ nowj - 1 ] != 'O' and a[ nowi ][ nowj - 1 ] != 'O' and a[ nowi + 1 ][ nowj - 1 ] != 'X' and a[ nowi ][ nowj - 1 ] != 'X' )
            {
                nowj -- , nowi ++ ;
                vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
                continue ;
            }
            else if(a[ nowi + 1 ][ nowj + 1 ] != 'O' and a[ nowi ][ nowj + 1 ] != 'O' and a[ nowi + 1 ][ nowj + 1 ] != 'X' and a[ nowi ][ nowj + 1 ] != 'X' )
            {
                nowj ++ , nowi ++ ;
                vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
                continue ;
            }
            else break ;
        }
        nowi ++ ;
        vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
    }
    a[ nowi ][ nowj ] = 'O' ;
    vis[ nowjd ].push( ( XoY ){ nowi , nowj } ) ;
}
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> r >> c ;
    for( int i = 0 ; i <= r + 1 ; i ++ )
    {
        if( i == 0 or i == r + 1 )
        {
            for( int j = 0 ; j <= c + 1 ; j ++ )
            {
                a[ i ][ j ] = 'O' ;
            }
            continue ;
        }
        a[ i ][ 0 ] = a[ i ][ c + 1 ] = 'O' ;
    }
    for( int i = 1 ; i <= r ; i ++ )
    {
        for( int j = 1 ; j <= c ; j ++ )
        {
            cin >> a[ i ][ j ] ;
        }
    }
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        cin >> b[ i ] ;
    }
    for( int i = 1 ; i <= n ; i ++ )
    {
        if( vis[ b[ i ] ].empty() )
        {
            down( 1 , b[ i ] , b[ i ] ) ; 
        }
        else
        {
            while( !vis[ b[ i ] ].empty() )
            {
            	XoY t2 = vis[ b[ i ] ].top() ;
            	if( a[ t2.x ][ t2.y ] != 'O' ) break ;
            	vis[ b[ i ] ].pop() ;
			}
            if( !vis[ b[ i ] ].empty() ) 
            {
                XoY t2 = vis[ b[ i ] ].top() ;
                down( t2.x , t2.y , b[ i ] ) ;
            }
            else
            {
                down( 1 , b[ i ] , b[ i ] ) ;
            }
        }
    }
    for( int i = 1 ; i <= r ; i ++ )
    {
        for( int j = 1 ; j <= c ; j ++ )
        {
            cout << a[ i ][ j ] ;
        }
        cout << "\n" ;
    }
    return 0;
}

我这个没有问题啊。。。咋说超时就超时了？？？

#include <bits/stdc++.h>
using namespace std;
int r, c, n;
int x, y;
char m[30005][35];
int main()
{
    scanf("%d%d", &r, &c);
    for (int i = 1; i <= r; i++)
        scanf("%s", &m[i][1]);
    scanf("%d", &n);
    while (n--)
    {
        x = 1;
        scanf("%d", &y);
        while (m[x + 1][y] != 'X' && x < r)
        {
            if (m[x + 1][y] == 'O')
            {
                if (y - 1 >= 1 && m[x + 1][y - 1] == '.')
                    x++, y--;
                else if (y + 1 <= c && m[x + 1][y + 1] == '.')
                    x++, y++;
                else if (y - 1 >= 1 && m[x][y - 1] == '.')
                    y--;
                else if (y + 1 <= c && m[x][y + 1] == '.')
                    y++;
                else
                    break;
            }
            else
                x++;
        }
        m[x][y] = 'O';
    }
    for (int i = 1; i <= r; i++)
    {
        for (int j = 1; j <= c; j++)
            printf("%c", m[i][j]);
        printf("\n");
    }
    return 0;
}