[2022ICPC南京]Stop, Yesterday Please No More

题目链接

题意

• 在$n\times m$$n×m$的矩阵上，每个格子上都有一只袋鼠
• 同时，题目给出了包含U,D,L,R四个字符的操作序列，分别对应上、下、左和右。对于操作序列中的每个字母，所有的袋鼠会向对应方向移动一格，边界上的袋鼠会消失。
• 同时，矩阵上有一个坑，袋鼠如果掉进坑里也会消失。
• 在操作后，剩余了$k$$k$只袋鼠，希望求出合法的坑的位置的个数。

思路

• 如果没有井，那么袋鼠最后会剩下一个矩形，或者什么也不剩。
• 设上述矩形的面积为$r$$r$
• 运动是相对的，袋鼠相对井在运动，井也在相对袋鼠运动。
• 所以，在网格上反向绘制出井的运动轨迹。
• 轨迹与矩形相交，就是坑掉的袋鼠的数量$\delta$$\delta$。
• 当$\delta +k=r$$\delta+k=r$时，该位置是合法的。
• 可以通过二维前缀和来求交集。

代码

​x
#include <iostream>
#include <string.h>
using namespace std ;

int readInt () ;

#define maxlen 1000060
#define maxn 1050

int n , m , len , rem ;
char s[maxlen] ;

class Point {

    public :
        int x , y ;

        Point (int x = 0, int y = 0) {
            this->x = x ;
            this->y = y ;
        }

        void show (char sp = '\n') {
            printf ("(%d,%d)%c" , x  , y , sp) ;
        }
};

Point operator + ( Point p1 ,  Point p2) {
    return Point (p1.x + p2.x , p1.y + p2.y) ;
}
Point operator - (Point p1 , Point p2) {
    return Point (p1.x - p2.x , p1.y - p2.y) ;
}

Point getdlt (char c) {

    if (c == 'U') return Point (-1 , 0) ;
    if (c == 'D') return Point (+1 , 0) ;
    if (c == 'L') return Point (0 , -1) ;
    if (c == 'R') return Point (0 , +1) ;

    return Point (0 ,0 ) ;
}

int a[maxn<<1][maxn<<1] ;

int get (int x1 , int y1 , int x2 , int y2) {

    return a[x2][y2] - a[x2][y1 - 1] -a[x1 - 1][y2] + a[x1 - 1][y1 - 1] ;
    //return a[x2][y2] - a[x1-1][y1-1] ;//+ a[x1-1][y2] + a[x2][y1-1] ;
}
void solve () {
    n = readInt () , m = readInt () , rem = readInt () ;
    scanf ("%s" , s + 1) ;
    len = strlen (s + 1) ;

//    puts (s + 1 ) ;

    Point lu (1 , 1) , rd (n , m) ;
    Point d(0 ,0) ;

    for (int i = 1 ; i <= len ; ++ i) {
        Point now = getdlt (s[i]) ;

        d = d + now ;
//      d.show() ;

        if (d.x < 0) lu.x = max (lu.x , -d.x + 1) ;
        if (d.x > 0) rd.x = min (rd.x , -d.x + n) ;

        if (d.y < 0) lu.y = max (lu.y , -d.y + 1) ;
        if (d.y > 0) rd.y = min (rd.y , -d.y + m) ;
    }

    if (lu.x > rd.x || lu.y > rd.y) {

        if (rem == 0) {
            printf ("%d\n" , n * m) ;
        } else {
            printf ("0\n") ;
        }


        return ;
    }
//  lu.show() ;
//  rd.show() ;

    Point rec_size = rd - lu + Point (1 , 1);
    Point rec_rd = lu - Point (1 , 1),
          rec_lu = lu - Point (n , m);

//  rec_size.show () ;
//  d.show() ;


    d = Point (1 ,1) - rec_lu ;

    rec_lu = d + rec_lu ;
    rec_rd = d + rec_rd ;

//    d.show() ;
//    rec_lu.show() ;
//    rec_rd.show() ;
//    puts ("-----") ;

    Point RD = rec_rd + rec_size - Point (1 , 1) ;
//cout << '#' << endl;
#define N RD.x
#define M RD.y

//cout << N <<' ' << M << endl;
    for (int i = 1 ; i <= N ; ++ i) {
        for (int j = 1 ; j <= M ; ++ j) {
            a[i][j] = 0 ;
        }
    }

//cout << '#' <<endl;
    Point pos = d ;

    a[pos.x][pos.y] = 1 ;
    for (int i = 1 ; i <= len ; ++ i ) {
        Point now = getdlt (s[i]) ;
        now.x = -now.x ;
        now.y = -now.y;

        pos = pos + now ;

        a[pos.x][pos.y] = 1 ;
    }

    for (int i = 1 ; i <= N ; ++ i) {
        for (int j = 1 ; j <= M ; ++ j) {
            a[i][j] = a[i][j] + a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] ;

//            cout << a[i][j] <<' ' ;
        }
//        cout << endl;
    }

    int ans = 0 ;
//  cout << get (3 , 4 , 5 , 6) << endl;

//int ans = 0 ;


    for (int i = 1 ; i <= N ; ++ i) {

        if (i + rec_size.x - 1 > N) break ;
        for (int j = 1 ; j <= M ; ++ j) {
            if (j + rec_size.y - 1 > M) break ;

            int now = get (i , j , rec_size.x + i - 1 , rec_size.y + j -1) ;

            if (now == rec_size.x * rec_size.y - rem) {
                ++ ans;
            }
        }
    }

    printf ("%d\n" , ans) ;

}


int main () {

//    freopen ("data.txt" , "r" , stdin) ;
//    freopen ("my.out" , "w" , stdout) ;
    int T = readInt () ;
    while (T -- ) {

//      cout << T << endl;
        solve () ;
    }

    return 0 ;
}

int readInt () {
    int x = 0 ;
    char c = getchar () ;
    while (c > '9' || c < '0') c = getchar () ;
    while (c >='0' && c <='9') {
        x =x  * 10 + c - '0' ;
        c = getchar () ;
    }
    return x ;
}

回到上级目录