• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Educational Codeforces Round 115 (Rated for Div. 2) E – Staircases (dp)

开发技术 开发技术 8小时前 3次浏览

E. Stairc++ases

  • 题意:一张(n)x(m)的图,有两种楼梯形,(L)(7)形,即向下向右和向右向下这样无限重复,单点和横着的两个点和竖着的两个点也算,有(q)个询问,每次将每个点的权值异或(1),如果某个点的值为(0),那么这个点就不能用,再询问贡献。

  • 题解:在纸上手玩几个例子,发现某个点改变后,最多只有(3n-2)个格子被影响,因为路径是该点所在的左斜对角线。先不考虑修改的情况,最初答案很容易计算,设(dp[0/1][i][j])表示第((i,j))个点,从上面/左边转移过来的贡献,那么有:(dp[0][i][j]+=dp[1][i-1][j],dp[1][i][j]+=dp[0][i][j-1]),因为单点也有贡献,所以dp数组初始化为(1),但注意计算贡献的时候单点的贡献算了两次,所以(ans+=dp[0][i][j]+dp[1][i][j]-1).再根据上面的结论,每次修改我们可以直接枚举左斜对角线修改,复杂度为(O(n*q)).

  • 代码

    #include <bits/stdc++.h>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    #define rep(a,b,c) for(int a=b;a<=c;++a)
    #define per(a,b,c) for(int a=b;a>=c;--a)
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
    
    int n,m,q;
    int x,y;
    int a[1005][1005];         
    int dp[2][1005][1005]; //0:vertical 1:horizontal
    
    int main() {
        scanf("%d %d %d",&n,&m,&q);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                dp[0][i][j]=dp[1][i][j]=1;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                dp[0][i][j]+=dp[1][i-1][j];
                dp[1][i][j]+=dp[0][i][j-1];
                ans+=dp[0][i][j]+dp[1][i][j]-1;
                a[i][j]=1;
            }
        }
        
        while(q--){
            scanf("%d %d",&x,&y);
            a[x][y]^=1;
            if(a[x][y]){
                dp[0][x][y]=1+dp[1][x-1][y];
                dp[1][x][y]=1+dp[0][x][y-1];
                ans+=dp[0][x][y]+dp[1][x][y]-1;
            }
            else{
                ans-=(dp[0][x][y]+dp[1][x][y]-1);
                dp[0][x][y]=dp[1][x][y]=0;
            }
            for(;x<=n && y<=m;x++,y++){
                if(x<n){
                    ans-=dp[0][x+1][y];
                    dp[0][x+1][y]=a[x+1][y]*(1+dp[1][x][y]);
                    ans+=dp[0][x+1][y];
                }
                if(y<m){
                    ans-=dp[1][x][y+1];
                    dp[1][x][y+1]=a[x][y+1]*(1+dp[0][x][y]);
                    ans+=dp[1][x][y+1];
                }
                if(x<n && y<m){
                    ans-=(dp[0][x+1][y+1]+dp[1][x+1][y+1]-1);
                    dp[0][x+1][y+1]=a[x+1][y+1]*(1+dp[1][x][y+1]);
                    dp[1][x+1][y+1]=a[x+1][y+1]*(1+dp[0][x+1][y]);
                    ans+=(dp[0][x+1][y+1]+dp[1][x+1][y+1]-1);
                }
            }
            printf("%lldn",ans);
        }
        
        return 0;
    }
    

喜欢 (0)