自动搬运

查看原文

来自洛谷，原作者为

	MY（一名蒟蒻） 你数据结构都用错了，怎么改都是没用的。

搬运于2025-08-24 22:12:48，当前版本为作者最后更新于2020-03-09 21:27:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题一看，第一反应记忆化搜索。看完标签，坚定了信心（但洛谷标签很多时候都是骗人的）。

记忆化搜索的好处：如果搜到以前的便无需再搜，直接返回。对每一个点最多只需找一次。极大的节省了时间。

话不多说上一开始的代码，注释嘛，请您看下去。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int t,x,y,mod,book[10010][10010]; 
int rem(int x,int y)
{
	if(book[x][y] == -1) return -1;
	if(book[x][y]) return book[x][y];
	book[x][y]=-1;
	if(!x) return book[x][y]=1;
	if(!y) return book[x][y]=2;
	int num=(x+y)%mod;
	return book[x][y]=rem(num,(num%mod+y)%mod); 
}
int main()
{
	scanf("%d %d",&t,&mod);
	for(int i=0;i<t;i++) 
	{
		scanf("%d %d",&x,&y); 
		int ans=rem(x,y);
		if(ans == -1) puts("error");
		else if(ans == 1) puts("1");
		else puts("2");
	}
	return 0;
}

为什么煤油注释？因为这个代码连窝本地编译都过不了！

一看数据范围，这样肯定会炸呀！

什么？连int都炸？那怎么办办呢？

作者在深思熟虑一秒钟后，打开了度娘。

原来还有个叫short的东西！！！

short只占用两个字节，而int需要4个。

于是修改代码后就可以愉快地AC啦！

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int t,x,y,mod;//定义
short book[10010][10010]; 
int rem(int x,int y)
{
	if(book[x][y] == -1) return -1;//不行
	if(book[x][y]) return book[x][y];//如果之前搜到过
	book[x][y]=-1;//标记
	if(!x) return book[x][y]=1;//zhouwc赢
	if(!y) return book[x][y]=2;//cbw赢
	int num=(x+y)%mod;//num=处理后的x
    	//(num+y)%mod=处理后的y
	return book[x][y]=rem(num,(num%mod+y)%mod);//记忆化核心
}
int main()
{
	scanf("%d %d",&t,&mod);//读入
	for(int i=0;i<t;i++) 
	{
		scanf("%d %d",&x,&y); 
		int ans=rem(x,y);//搜索
        	//输出
		if(ans == -1) puts("error");
		else if(ans == 1) puts("1");
		else puts("2");
	}
	return 0;
}

话说zhouwc说踏寄几是蒟蒻你信吗？

写题解不易，点个赞好不好嘛。——滚去写作业之前还厚颜无耻要赞的作者