搜索 ---- 练习题（洛谷）

洛谷练习题

P1019 单词接龙

思路

要求最长，所以要保证重叠部分最小，以及通过搜索比较，找到最长的接龙方式。

三个函数

主函数：输入

dfs : 更新字符串，长度，进行dfs搜索

link :计算两个字符串最小重叠部分

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
string str[25];
int lenth=0,v[25],n;
int link(string str1,string str2)
{fir(i,1,min(str1.size(),str2.size())-1) //重叠部分最小1，最大时lenth-1{int f=0;fir(j,0,i-1){if(str1[str1.size()-i+j]!=str2[j])f=1;}if(f==0) return i;//配对，退出返回最小重叠部分}return 0;
}
void dfs(string strnow,int lenthnow)
{lenth=max(lenthnow,lenth);//更新最大长度fir(i,0,n-1){if(v[i]>=2) continue;//使用两次了int len=link(strnow,str[i]);if(len>0){v[i]++;dfs(str[i],lenthnow+str[i].size()-len);//调用新的末尾字符串及此时长度，向下搜v[i]--;//还原}}
}
signed main()
{IOScin>>n;fir(i,0,n)cin>>str[i];dfs(' '+str[n],1);//因为初始是单个字母，重叠部分是lenth-1,1-1=0,为了能在link里接第一个字符,加‘ ’cout<<lenth<<'\n';return 0;
}

P1025 数的划分

思路

为了防止重复，所以在选择数的时候，按照非递减的顺序。

也就是在dfs搜索选择下一个数时，从上一个数字的大小开始。

dfs 中调用三个参量，一个是num将要选择的数字大小（也就是上个数字的大小）,一个是sum此时已选数字的和，另一个是count已经选了几个数字。

在循环选择是，进行一次剪枝，由于数字是非递减的，已选数字sum+此时选的 i 乘 未选的数量 >n, 就可以直接退出了

代码

 int ans=0,n,k;
void dfs(int num,int sum,int count)
{if(count==k){if(sum==n) ans++;return;}for(int i=num;sum+i*(k-count)<=n;i++)dfs(i,sum+i,count+1);
}
signed main()
{IOScin>>n>>k;dfs(1,0,0);cout<<ans<<'\n';
}

P1037 产生数

输入数字n,最长29位，有K 种规则。

k行，每行两个数字x,y，表示可以x可以变化为y。

求 可以产生多少种数（包括本身）

思路

A这一题需要解决两个问题

n 数字较大，需要高精乘

计算出某个数字可以变化成几种

对于问题一

___int128最大值2^{127-1，超过10}30,可以过这个题的数据

问题二

当数字1可以变为2，而2可以变成3，此时1也可以变成 3 。有点弗洛伊德算法的感觉，每个数都作为中间节点，遍历一遍。所以写三个循环，最外层是中间节点。

这两个问题解决就可以写代码了。将n各个位上可以变化的次数累乘就可以了

多亏了zcb.

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int> 
map<PII,int> mp;
string n,s;
int k,num[10],x,y;
void to_s(__int128 m)
{while(m){s+=m%10+'0';m/=10;}
}
signed main()
{IOScin>>n>>k;while(k--){cin>>x>>y;mp[{x,y}]=1;}fir(i,0,9)fir(j,0,9)fir(k,0,9){if(mp[{j,i}]&&mp[{i,k}])mp[{j,k}]=1;}fir(i,0,9){mp[{i,i}]=1;fir(j,0,9)if(mp[{i,j}]==1)num[i]++;}__int128 ans=1;fir(i,0,n.size()-1)ans*=num[n[i]-'0'];to_s(ans);reverse(s.begin(),s.end());cout<<s<<'\n';}

P1406 方格填数

输入一个数字n,再输入n*n个数字。排列成一个字典序最小的矩阵。且每行每列，两条对角线上的数字和，均相等。

思路

字典序最小

现在数字排序，从前往后选择插入矩阵，第一个满足条件的就是答案

和均相等

通过dfs,遍历每一种组合方式，中间不断判断，最后输出满足要求的

剪枝

每排列一行，就先判断一下这一行

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
int n,a[30],ans[6][6],v[30],st;
void dfs(int x,int y,int k) //x,y表示矩阵坐标
{ans[x][y]=a[k];if(y==n){int sum=0;fir(i,1,n)sum+=ans[x][i];if(sum!=st)return;}if(x==n&&y==n){int sum1=0,sum2=0,sum3=0,sum4=0;fir(i,1,n){    sum1=0,sum2=0;fir(j,1,n){sum1+=ans[i][j];sum2+=ans[j][i];}if(sum1!=st||sum2!=st)return;sum3+=ans[i][i];sum4+=ans[i][n-i+1];}if(sum3!=st||sum4!=st)return ;cout<<st<<'\n';fir(i,1,n){fir(j,1,n)cout<<ans[i][j]<<" ";cout<<'\n';}exit(0);}fir(i,1,n*n){if(v[i]==0){if(y+1<=n){v[i]=1;dfs(x,y+1,i);v[i]=0;}else{v[i]=1;dfs(x+1,1,i);v[i]=0; }}}
}
signed main()
{IOScin>>n;int sum=0;fir(i,1,n*n){cin>>a[i];sum+=a[i];}st=sum/n;//求出每行...和值sort(a+1,a+n*n+1);//!!!fir(i,1,n*n){v[i]=1;dfs(1,1,i);   //遍历每一个数作为开端v[i]=0;}}

P2392 kkksc03考前临时抱佛脚

有四行数字，每行内，两个数字可以同时进行，问这四行全完成需要多长时间

思路

这个题用dp，可以很好解决。

由于数据范围较小，可以作为一个搜索题去写。

用 L,R，表示左右脑，在搜索中，L+a[c]放到左脑递归，也可R+a[c]递归。全部搜索完，累加最小值

因为l,r会进行**l-=a[c]**还原，所以不需要作为形参调入函数，可以直接作为全局变量。

搜索完return不能忘

不需要将数字全部输入，存储。输入一行，就计算一行

代码（搜索）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
int  n[5],s[25],l,r,mi=0x3f3f3f3f,ans;
void dfs(int c,int y) //x,y表示矩阵坐标
{if(c>n[y]){mi=min(mi,max(l,r));return ;//不能忘}l+=s[c];dfs(c+1,y);l-=s[c];r+=s[c];dfs(c+1,y);r-=s[c];
}
signed main()
{IOScin>>n[1]>>n[2]>>n[3]>>n[4];fir(i,1,4){l=r=0;mi=0x3f3f3f3f;fir(j,1,n[i])cin>>s[j];dfs(1,i);ans+=mi;}cout<<ans;
}

代码（dp）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define fir_(i,a,b) for(int i=a;i>=b;i--)
signed main()
{int n[5],s[25],dp[1500],ans=0;fir(i,1,4)cin>>n[i];fir(i,1,4){int sum=0;fir(j,1,n[i]){cin>>s[j];sum+=s[j];}fir(j,1,n[i]){fir_(k,sum/2,s[j])  //背包最大为总时间的一半{dp[k]=max(dp[k],dp[k-s[j]]+s[j]);//大小为k,除去s[j]的空间最大容量+s[j]}}ans=ans+sum-dp[sum/2];fir(i,1,sum)dp[i]=0;}cout<<ans<<'\n';
}

B 3624 猫粮规划

第一行，三个正整数 n, l, r。

第二行，n个正整数，表示每一份食物含有的能量 w[i]。

输出一个整数，表示选择数字在区间内方案数。

思路

和上题相似，一个数有两种可能。dfs非常简洁，不过要加一个剪枝，不然会T。

如果ans>r，不需要向下搜，直接返回

代码

int w[25],ans=0,sum=0,n,l,r;
void dfs(int k)
{if(k==n+1){if(ans<=r&&ans>=l)sum++;return;}if(ans>=r)//剪枝{if(ans==r)sum++;return;}ans+=w[k];dfs(k+1);ans-=w[k];dfs(k+1);
}
signed main()
{IOScin>>n>>l>>r;fir(i,1,n)cin>>w[i];dfs(1);cout<<sum<<'\n';
}