Timstamp：2023/07/23 02:40

原本想說寫一寫就去睡了，結果被卡常弄了好久 QQ

這題我自己寫出來的複雜度是 $10^8$ 很危。

一開始想說使用 bfs 的方式，有需要轉移再推進 queue，結果因為 queue 的關係大卡常。

:::spoiler TLE 的程式碼

int ary[10010];
int vis[110][110];
int n,m,k;
pii move(pii now,int dis,int way){
    if(way==1){
        int nx = now.F+dis;
        nx%=n;
        return {nx,now.S};
    }
    if(way==2){
        int nx = now.F-dis;
        nx%=n;
        nx = (nx+n)%n;
        return {nx,now.S};
    }
    if(way==3){
        int nx = now.S+dis;
        nx%=m;
        return {now.F,nx};
    }
    if(way==4){
        int nx = now.S-dis;
        nx%=m;
        nx = (nx+m)%m;
        return {now.F,nx};
    }
    return {0,0};
}
signed main(){
    AC
    cin>>n>>m;
    int x,y,s,t;
    cin>>x>>y>>s>>t;
    cin>>k;
    rep1(i,k)cin>>ary[i];
    queue<pii> q;
    q.push({x,y});
    int cc = 1;
    while(q.size()&&cc<=k){
        int qz = q.size();
        rep1(j,qz){
            pii tp = q.front();
            q.pop();
            for(int i=1;i<=4;i++){
                pii np = move(tp,ary[cc],i);
                if(vis[np.F][np.S]==cc+1){
                    continue;
                }
                else{
                    vis[np.F][np.S] = cc+1;
                    q.push(np);
                }
            }
        }
        cc++;
    }
    if(!vis[s][t]){
        no;
    }
    else{
        yes;
    }
}

:::

後來想說就不用 BFS 了，直接看有沒有被轉移(上一輪有被走過)
結果還是被卡常

:::spoiler TLE again

#define getchar getchar_unlocked
inline void input(int &_x)
{
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
}
int ary[10010];
int vis[2][110][110];
int n,m,k;
inline pii move(pii now,int dis,int way){
    if(way==1){
        int nx = now.F+dis;
        nx%=n;
        return {nx,now.S};
    }
    if(way==2){
        int nx = now.F-dis;
        nx%=n;
        nx = (nx+n)%n;
        return {nx,now.S};
    }
    if(way==3){
        int nx = now.S+dis;
        nx%=m;
        return {now.F,nx};
    }
    if(way==4){
        int nx = now.S-dis;
        nx%=m;
        nx = (nx+m)%m;
        return {now.F,nx};
    }
    return {0,0};
}
signed main(){
    // AC
    // cin>>n>>m;
    input(n),input(m);
    int x,y,s,t;
    // cin>>x>>y>>s>>t;
    input(x),input(y),input(s),input(t);
    // cin>>k;
    input(k);    
    // rep1(i,k)cin>>ary[i];
    rep1(i,k)input(ary[i]);
    vis[1][x][y] = 1;

    for(int cc=1;cc<=k;cc++){
        rep(i,n){
            rep(j,m){
                if(vis[cc%2][i][j]==cc){
                    pii tp = {i,j};
                    for(int c=1;c<=4;c++){
                        pii np = move(tp,ary[cc],c);
                        vis[1-cc%2][np.F][np.S] = cc+1;
                    }
                }
            }
        }
    }
    
    if(vis[1-k%2][s][t]!=k+1){
        no;
    }
    else{
        yes;
    }
}

:::

最後去看了大神的程式碼後，我發現他很多地方都用位元運算取代模運算，還有加減乘除。

於是我把裡面的一些模運算弄掉，用成一樣的做法，結果就AC了!

我自己實驗了一下，因為大概是 $10^8$ 次的模運算，分別繳交了兩次，時間竟然差了五倍!!!
第一次被卡常的經驗 get XD 我也學到教訓了

(接近TLE)

(取代模運算)

:::spoiler AC!

signed main(){
    // AC
    // cin>>n>>m;
    input(n),input(m);
    int x,y,s,t;
    // cin>>x>>y>>s>>t;
    input(x),input(y),input(s),input(t);
    // cin>>k;
    input(k);    
    // rep1(i,k)cin>>ary[i];
    rep1(i,k)input(ary[i]);
    vis[0][x][y] = 1;

    #define add(x,y,n) ( x+y<n?x+y:x+y-n )
    #define del(x,y,n) ( x-y>=0?x-y:x-y+n )
    for(int cc=1;cc<=k;cc++){
        rep(i,n){
            rep(j,m){
                int d1 = ary[cc],d2 = d1%m;
                d1 %= n;
                vis[cc&1][i][j] = vis[(cc-1)&1][add(i,d1,n)][j] |
                            vis[(cc-1)&1][del(i,d1,n)][j] | 
                            vis[(cc-1)&1][i][add(j,d2,m)] | 
                            vis[(cc-1)&1][i][del(j,d2,m)] ;
            }
        }
    }
    
    if(!vis[k&1][s][t]){
        no;
    }
    else{
        yes;
    }
}

:::