自动搬运

查看原文

来自洛谷，原作者为

	MassPoint 我要蓝钩

搬运于2025-08-24 22:32:42，当前版本为作者最后更新于2024-12-07 19:25:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首先考虑暴力，很显然可以手动模拟每一次翻滚，时间复杂度 $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;
}