本文共 2345 字，大约阅读时间需要 7 分钟。

昨天做了蓝桥杯的时候，发现自己对于记忆优化搜索甚是不熟悉，所以今天随便找了几个基础题做做，顺便写下两片题解，顺便用了一下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 161 21 41 102 32 54 34 54 86 57 67 98 59 810 610 710 9

输出：

9

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

#include 
   
    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<
    
     <
    
   

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 101 3

输出样例

error

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

#include 
   
    using namespace std;short rem[10010][10010];  //开short为了防止mleint 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<
    
     <
    
   

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

转载地址：https://blog.csdn.net/xxxxxiao123/article/details/104878802 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！