题解 P5635 【【CSGRound1】天下第一】
这题一看，第一反应记忆化搜索。看完标签，坚定了信心（但洛谷标签很多时候都是骗人的）。
记忆化搜索的好处：如果搜到以前的便无需再搜，直接返回。对每一个点最多只需找一次。极大的节省了时间。
话不多说上一开始的代码，注释嘛，请您看下去。
#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说踏寄几是蒟蒻你信吗？