题解：P7744 [COCI2011-2012#3] POGODAK

· · 题解

思路

首先考虑暴力，很显然可以手动模拟每一次翻滚，时间复杂度 O(rc)，显然不能通过。

考虑优化骰子横向滚动的情况。

很显然，骰子向一个方向滚过四次以后将会回到原来的状态，因此有 c - c \bmod 4 次滚动可以 O(1) 解决。

至于后面的 c \bmod 4 次滚动，直接模拟即可。

至此，我们已经成功地把原本 O(rc) 的代码优化至 O(r)，可以 AC 此题了！

Tip：注意到题目中 r \times c 已经超过 2^{32}-1 了，所以要开 long long。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,u=1,f=2,r=3,op=1;
long long ans;
void solve(int tp,int len){
    ans+=(len/4)*14;    //批量解决大部分滚动
    len%=4;
    for(int i=1,tmp;i<=len;i++){    //模拟剩下的滚动
        if(tp==1){  //如果是向左滚
            tmp=7-r;
            r=u;
            u=tmp;
        }
        else{   //否则一定是向右滚
            tmp=7-u;
            u=r;
            r=tmp;
        }
        ans+=u;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,tmp;i<=n;i++){
        ans+=u;
        solve(op,m-1);  //注意到上一行已经走了一步了，所以这里是 m-1
        tmp=7-f;f=u;u=tmp;  //模拟骰子向下滚动
        op*=-1; //换方向
    }
    printf("%lld",ans);  
    return 0;
}