bitset优化+滚动优化dp ----- 2021牛客多校第8场 F Robot

题目大意:

就是给你一个大小为 n ∗ m n*m n∗m的矩阵，里面有障碍物，每次询问给你一个机器人，以及机器人的起始位置，问你这个机器人能否从起点到终点
机器人有3种类型

1. 只能往右走
2. 只能往下走
3. 可以往右走也可以往下走
   q ∈ [ 1 , 5 e 5 ] , n , m ∈ [ 1 , 500 ] q\in[1,5e5],n,m\in[1,500] q∈[1,5e5],n,m∈[1,500]

---

解题思路：

首先我们知道这个询问超级多！！
我一开始就想到bitset去优化但是，空间开不够！！
比赛大概剩半小时的终于想到了正解，但是对bitset的操作复杂度不熟悉以为不可行就被hack了！！

1. 就是我们知道询问次数很多，图很小， 那么我们可以离线处理，每次把询问的点存到对应位置去！那么我们就可以只遍历图一次就把所以的询问给处理了！
2. e g : 有 从 ( 1 , 1 ) 点 出 去 到 ( 2 , 2 ) 或 者 ( 3 , 6 ) eg:有从(1,1)点出去到(2,2)或者(3,6) eg:有从(1,1)点出去到(2,2)或者(3,6)那么我们就把 q [ ( 2 , 2 ) ] . p u s h _ b a c k ( ( 1 , 1 ) ) q[(2,2)].push\_back((1,1)) q[(2,2)].push_back((1,1))和 q [ ( 3 , 6 ) ] . p u s h _ b a c k ( ( 1 , 1 ) ) q[(3,6)].push\_back((1,1)) q[(3,6)].push_back((1,1))
3. 对于每个点我们就看看可达它的点有哪些？
4. 就是用bitset去dp了对于可以到达的点的位置bit设置为1，直接 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ( G [ i − 1 ] [ j ] = = ′ 0 ′ ) ( 或 运 算 ) d p [ i ] [ j − 1 ] ( G [ i ] [ j − 1 ] = = ′ 0 ′ ) dp[i][j] = dp[i-1][j](G[i-1][j]=='0') (或运算) dp[i][j-1](G[i][j-1]=='0') dp[i][j]=dp[i−1][j](G[i−1][j]==′0′)(或运算)dp[i][j−1](G[i][j−1]==′0′)
5. 但是空间不够，那么直接滚动就好了
6. b i t s e t < 500 ∗ 500 > d p [ 2 ] [ 500 ] bitset<500*500> dp[2][500] bitset<500∗500>dp[2][500]

---

AC代码：

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 500010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
   x = 0;char ch = getchar();ll f = 1;
   while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
   while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
   read(first);
   read(args...);
}

int n, m;
char G[505][505];
bitset<505*505> dp[2][505];
vector <PII> q[505*505];
int summ[505][505];
int sumn[505][505];
int ans[maxn];

inline int getid(int x, int y) {
   return (x - 1) * m + y;    
}

int main() {
    IOS;
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
       cin >> (G[i] + 1);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j++)
            sumn[i][j] = sumn[i-1][j] + (G[i][j]=='1'),
            summ[i][j] = summ[i][j-1] + (G[i][j]=='1');
    int qs;
    cin >> qs;
    for(int i = 1; i <= qs; ++ i) {
       int type, bex, bey, tagx, tagy;
       cin >> type >> bex >> bey >> tagx >> tagy;
       if(type == 1) ans[i] = (bey == tagy) && (bex <= tagx) && (sumn[bex-1][bey]-sumn[tagx][tagy] == 0);
       else if(type == 2)  ans[i] = (bex == tagx) && (bey <= tagy) && (summ[bex][bey-1] - summ[tagx][tagy] == 0);//,puts("???");
       else q[getid(tagx,tagy)].push_back({getid(bex,bey),i}); 
    }
    for(int i = 1; i <= n; ++ i)
       for(int j = 1; j <= m; ++ j)
         if(G[i][j] == '0') {
             if (G[i-1][j] == '0') dp[i&1][j] = dp[(i&1)^1][j];
             else dp[i&1][j].reset();
             
             if(G[i][j-1] == '0')
               dp[i&1][j] |= dp[(i&1)][j-1];
             
             dp[i&1][j].set(getid(i,j));
             
             for(auto it : q[getid(i,j)]) {
                 int idx = it.second;
                 int ver = it.first;
                 if(dp[i&1][j][ver]) ans[idx] = 1;
             }
         } else dp[i&1][j].reset();

    for(int i = 1; i <= qs; ++ i)
       if(ans[i]) puts("yes");
       else puts("no");
}