hdu 5084 HeHe (观察思考题)

题意：

给一个n行n列的矩阵M。这个矩阵M由2n-1数构成。分别是t1,t2,....t(2n-1)。

m个query。每个query形式：ri, ci。

第i个query的答案 ans[i]=E[(ri+ans[i-1])%n ][(ci+ans[i-1])%n] E=M*M

求m个query的答案和。即ans[1]+...ans[m]的答案。

矩阵形式：

t3 t4 t5 t4 t5 t6 t7

t2 t3 t4 t3 t4 t5 t6

t1 t2 t3 t2 t3 t4 t5

　　　　　　　　　　　　　 t1 t2 t3 t4

思路：

直接算M*M，时间复杂度是n^3，会超时。考虑到矩阵具有特殊性，找出规律。

ans[x][y]=t[n+1-x](增)*t[n-1+y](减)+....+a[2n-x]*a[y]

ans[x+1][y+1]=ans[x][y] + 某个东西 - 某个东西 (这里不写出，在记事本上写一下便可观察出)

这样算M*M大约时间复杂度大约是n^2

代码：

int n,m,r,c;

int t[2500];

int ans[1005][1005];

int main(){

   //freopen("test.in","r", stdin);

    while(scanf("%d",&n)!=EOF){

        rep(i,1,2*n-1) scanf("%d",&t[i]);

        mem(ans,0);

        rep(i,1,n) rep(j,1,n){

            if(i-1<1 || j-1<1)

                rep(k,0,n-1) ans[i][j]+=t[n+1-i+k]*t[n-1+j-k];

            else{

                ans[i][j]=ans[i-1][j-1];

                ans[i][j]-=t[2*n-(i-1)]*t[j-1];

                ans[i][j]+=t[n+1-i]*t[n-1+j];

            }

        }

        ll sum=0;

        int ANS;

        scanf("%d",&m);

        scanf("%d%d",&r,&c);  ANS=ans[r+1][c+1];  sum+=ANS;

        rep(i,2,m){

            scanf("%d%d",&r,&c);

            ANS=ans[(r+ANS)%n+1][(c+ANS)%n+1];

            sum+=ANS;

        }

        printf("%I64d\n",sum);

    }

    //fclose(stdin);

}

巴特西

hdu 5084 HeHe (观察思考题)

最新文章

热门文章