文章目录
洛谷练习题
P1019 单词接龙
对n个单词进行接龙，以第n+1个字符为开头，前后不能存在包含关系。
接龙中，重叠部分，只出现一次。每个单词可以用2次。
求接龙的最长长度
思路
要求最长，所以要保证重叠部分最小，以及通过搜索比较，找到最长的接龙方式。
三个函数
主函数：输入
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 数的划分
将一个数字n分解为k 个正整数，（115，511算一种方案），问一共几种方案
思路
为了防止重复，所以在选择数的时候，按照非递减的顺序。
也就是在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最大值2127-1，超过1030,可以过这个题的数据
问题二
当数字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';
}
