记忆优化搜索（简单题）（洛谷P3183 [HAOI2016]食物链 ）（ P5635 【CSGRound1】天下第一 ）

昨天做了蓝桥杯的时候，发现自己对于记忆优化搜索甚是不熟悉，所以今天随便找了几个基础题做做，顺便写下两片题解，顺便用了一下devc++敲的代码，发现没有代码补全真的可以说是灰常难受了。。。
洛谷P3183 [HAOI2016]食物链 ：
题目描述
如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3…am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链
输入格式
第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）1<=N<=100000 0<=m<=200000题目保证答案不会爆 int
输出格式
一个整数即食物网中的食物链条数
输入：

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

输出：

9

题解：这个题可能稍稍的用到了图论里面的少许内容，主要是运用了链向式前向星存图+拓扑排序，可以简单地理解为从入度为零的点到出度为零的点一共有几条，这样的话当一个链特别长的时候，我们会发现一个点可能会重复的出现在好几个链当中，那么如果不记忆的话，这个点之前的所有情况我们要反复的去搜索，这样会浪费掉很多时间，所以将他记录下来是一个不错的解决方法。

#include <bits/stdc++.h>
using namespace std;
struct{
	int to,next;
}a[200010];
int head[200010];
int rem[200010];
int in[100010];
int out[100010];
int cnt=0;
void add(int u,int v){  //链向式前向星存图
	a[++cnt].to=v;
	a[cnt].next=head[u];
	head[u]=cnt;
}
int dfs(int x){
	if(rem[x]) return rem[x];  //如果这个点之前的情况已经被记录过了，那么就直接调用之前统计的情况
	int ans=0;
	if(out[x]==0) return 1;  //找到出口，情况+1
	for(int i=head[x]; i;i=a[i].next){
		ans+=dfs(a[i].to);  //从这个点通向其他路
	}
	rem[x]=ans;  //记录
	return ans;  //返回总数目
}
int ans=0;
int main() {
	
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		in[y]++;
		out[x]++;
	}
	for(int i=1;i<=m;i++){
		if(in[i]==0&&out[i]!=0){//我们要遍历每个入读为0的点，并且单个点不为一条食物链
			ans+=dfs(i);
		}
	}
	cout<<ans<<endl;
	return 0;
}

P5635 【CSGRound1】天下第一
题目描述：
游戏是这样的:
给定两个数x, y,与-个模数Mod.
cbw拥有数x, zhouwc拥有数y。
第一个回合: x= (x + y)%Mod.
第二个回合: y= (x + y)%Mod.
第三个回合: x= (x + y)%Mod.
第四个回合: y= (x + y)%Mod.
以此类推…
如果x先到0,则cbw胜利。如果y先到0,则zhouwc胜利。如果x,y都不能到0,则为平局。
cbw为了捍卫自己主席的尊严，想要提前知道游戏的结果，并且可以趁机动点手脚，所以他希望你来告诉他结果。
输入格式：
有多组数据。
第一行: T和Mod表示-共有T组数据且模数都为Mod.
以下T行，行两个数x, Y。
输出格式：
共T行
1表示cbw获胜, 2表示zhouwc获胜，error 示平局。
输入样例：

1 10
1 3

输出样例

error

题解：这里记忆化的关键就是可能会重复出现某两个数记录的原因有两个，一是为了判断是否error，二是因为有多组数据，我们可以减少其中的计算量。

#include <bits/stdc++.h>
using namespace std;
short rem[10010][10010];  //开short为了防止mle
int t,mod;
int dfs(int x,int y){
	if(rem[x][y]) return rem[x][y];
	if(rem[x][y]==-1)  return 3;  //！！一定要注意这个要放在上一行的下面！
	rem[x][y]=-1;   //标记这两个数已经走过一次了
	if(x==0)  return rem[x][y]=1;
	if(y==0)  return rem[x][y]=2;
	return rem[x][y]=dfs((x+y)%mod,((x+y)%mod+y)%mod);
}

int main() {
	
	cin>>t>>mod;
	while(t--){
		int x,y;
		cin>>x>>y;
		int ans=dfs(x,y);
		if(ans==1) cout<<ans<<endl;
		else if(ans==2)  cout<<ans<<endl;
		else   cout<<"error"<<endl;
	}	
	return 0;
}

**devc++真的是用不惯 **