2025年4月4日学习记录
单词+算法
单词+算法
考研
背诵了List6这一部分单词。
P1120 小木棍（剪枝）
题意：有一些同样长的小木棍，然后随意砍成几段，直到每段的长都不超过 50。
现在想把小木棍拼接成原来的样子，但是不知道开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
剪枝：设原始木棍长度为m
- 原始木棍长度m一定是所有长度和的因数
- m最小也是现在所有木棍中最长的长度，因此可以从$a_i$的最大值开始枚举
- 对于一个被枚举的$a_i$，若$a_i$不满足要求，则同长度的其他木棍也不满足
- 枚举新木棍时，优先考虑较长的木棍
- 若当前原始木棍的剩余长度等于当前考虑木棍长度，但搜索后不满足要求，则无需考虑更短木棍，直接回溯。（因为短棍拼出当前长度与长棍一致，但短棍更灵活，留到后面更优，长棍不符合要求，则短棍拼接也不可能符合要求）
- 若当前木棍长度就是设定原始木棍长度，搜索后不满足也直接回溯
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2;
int n,a[N],len[N],sum,pre[N],d;
void dfs(int u,int k,int p){
//当前这一只长棍还有u没有拼，
//还有k根长棍没有拼
//当前长棍的最短短棍长度是p
if(u==0){//这一根长棍拼完了
dfs(d,k-1,a[n]);//拼下一根长棍
return ;
}
if(k==0){//所有长棍都拼完了
cout<<d;//这是找到的第一个，也就是最短长度
exit(0);
}
p=min(p,u);//更新最短长度
while(p&&len[p]==0) --p;//如果u不存在相等长度的，找到最接近的
while(p){//pre[1]会=0
if(len[p]){//如果p长度还存在
--len[p];//保存现场
dfs(u-p,k,p);
++len[p];//恢复现场
if((u==p)||(u==d))//如果这都没有exit，证明长度不合适，后面更小的也不合适
return;//剪枝
p=pre[p];//找到更短的长度
}
else//如果p长度不存在
p=pre[p];
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
++len[a[i]];//长度为a[i]的个数
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){//预处理长度为i的上一个长度
if(a[i]!=a[i-1])
pre[a[i]]=a[i-1];
}
for(d=a[n];d*2<=sum;++d){//至少有两根
if((sum%d)==0)//因为sum会由多根同一长度的组成
dfs(d,sum/d,a[n]);
}
cout<<sum;//最终都没有，全部合起来
return 0;
}
迭代加深搜索IDDFS：枚举搜索深度来进行搜索
P1763 埃及分数（IDDFS）
题意：给出一个分子a和分母b组成，分解成一堆互不相同的单位分数（分子为1）。单位分数的数量越少越好，如果数量一样，最小的那个单位分数越大越好（即分母越大越好）。
剪枝我也没看懂，P1763 题解 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 11,INF = 1e7;
int dep;int max_a;
int tmp[N],ans[N];
int a,b,c;
bool flag;
int GCD(const int x,const int y){
return y ? GCD(y, x % y) : x;
}
void dfs(const int a,const int b,const int x){
if(x > dep)
return;
if(a == 1){
tmp[x] = b;
if(!flag || tmp[dep] < ans[dep])
for(int i = 1;i <= dep;i++)
ans[i] = tmp[i];
flag = 1;
return;
}
if(x == dep - 1){
int l = ((b << 2) / (a * a)) + 1,r = min(((max_a << 1)) / a,max_a * max_a / b);
for(int i = l;i <= r;i++){
int delta = a * a * i * i - ((b * i) << 2);
int Sqrt = sqrt(delta);
if(Sqrt * Sqrt != delta || ((a * i - Sqrt) & 1))
continue;
tmp[x] = (a * i - Sqrt) >> 1;tmp[x + 1] = (a * i + Sqrt) >> 1;
if(tmp[x] <= tmp[x - 1] || tmp[x + 1] <= tmp[x])
continue;
if(!flag || tmp[dep] < ans[dep]){
for(int j = 1;j <= dep;j++)
ans[j] = tmp[j];
flag = true;
}
}
return;
}
int l = max((b + a - 1) / a,tmp[x - 1] + 1);
int r = min((((dep - x + 1) * b + a - 1) / a),max_a);
if(flag && r >= ans[dep])
r = ans[dep] - 1;
for(int i = l;i <= r;i++){
tmp[x] = i;
const int A = a * i - b,B = b * i;
const int gcd = GCD(A,B);
dfs(A / gcd,B / gcd,x + 1);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> a >> b;
c = GCD(a,b);
a /= c;b /= c;
tmp[0] = 1;
for(dep = 1;dep <= N - 1;dep++){
ans[dep] = tmp[dep] = INF + 1;
for(max_a = 100000;max_a <= INF;max_a *= 10){
dfs(a,b,1);
if(flag){
for(int i = 1;i <= dep;i++)
cout << ans[i] << ' ';
return 0;
}
}
}
return 0;
}
双向深度优先搜索：数据分为两部分，分别进行DFS
CF525E Anya and Cubes（双向DFS）
题意：给出一个长度为 n 的数组 a ，可以选任意个数组成数组 b ，并在 b 中选出不超过 k 个数，将这不超过 k 个数变成自己的阶乘。最后求数组 b 的各个元素之和为 S 的方案数。
题解：前 $n/2$ 个数一组，后 $n-n/2$ 个数一组，分别DFS。前半组搜索结束时，用Hash记录该状态的方案数，然后对后半部分进行DFS，设搜索结束时状态是选了 i 个阶乘，和为 s ，即为 $(i,s)$，在后半部分搜索结束时，将答案加上 $\sum_{t=0}^{k-i} f[(t,S-s)]$ 即可，$f$ 是前半部分对应方案数。
整体DFS $O(3^n)$，若合并两部分答案复杂度为 $k$，双向DFS $O(k · 3^{n/2})$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3;
int n,t,m;
ll S,ans,a[N];
int b[N];
map<pair<int,ll>,ll> f,g;//存放前半部分数量
ll fact(ll x){//阶乘
ll ret;
for(ret=1;x;ret*=x--)
if((S/ret)<x) return -1;//未看懂
return ret;
}
void check1(){
int cnt=0;//阶乘个数
ll sum=0;//和
for(int i=1;i<=m;i++){
if(b[i]==1) sum+=a[i];//1表示在b中但不会变阶乘
else if(b[i]==2){//2表示在b中会变成阶乘
ll s=fact(a[i]);
if((s==-1)||(++cnt>t)||((s+sum)>S)) return;
//这是加上s后当前和大于S和选择阶乘数限制的情况
sum+=s;
}
}
++f[{cnt,sum}];//累加方案数
++f[{-1,sum}];//标记sum这一和出现过
}
void dfs1(int u){
if(u>m) check1();//到达搜索终点
else{
for(int i=0;i<=2;i++){//枚举每个位置的三进制数
b[u]=i;
dfs1(u+1);
}
}
}
ll qry(int x,ll s){//统计i从0到x,f[{i,s}]的和
//记忆化提高效率
if(g.count({x,s})) return g[{x,s}];
return g[{x,s}]=f[{x,s}]+(x?qry(x-1,s):0);
}
void check2(){
int cnt=0;ll sum=0;
for(int i=m+1;i<=n;i++){//遍历后半部分的数
if(b[i]==1) sum+=a[i];
else if(b[i]==2){
ll s=fact(a[i]);
if((s==-1)||(++cnt>t)||((s+sum)>S)) return;
sum+=s;
}
}
if(f.count({-1,S-sum}))//如果S-sum出现过
ans+=qry(t-cnt,S-sum);//累加答案
}
void dfs2(int u){
if(u>n) check2();//选完了
else{
for(int i=0;i<=2;i++){//枚举状态
b[u]=i;
dfs2(u+1);
}
}
}
int main(){
cin>>n>>t>>S;
for(int i=1;i<=n;i++) cin>>a[i];
m=n/2;
dfs1(1);//前半部分
dfs2(m+1);//后半部分
cout<<ans;
return 0;
}
双向广搜：从两个状态一起开始BFS
P1379 八数码难题
题意：在3*3的棋盘上，有8枚编号棋子，中间为0号空格，棋子可移动到空格中，给出初始布局和目标布局，找到最少步骤移动次数。
题解：每个状态可以映射为一个九位数，双向BFS。还可用A*或IDA*。
#include<bits/stdc++.h>
using namespace std;
int bg,ed=123804765;//开始与结束状态
int a[10];
map<int,int> rec[2];//1表示从结束状态开始的搜索，0是开始状态开始的
queue<pair<int,bool> > Q;
int change(int x,int op){
int p;//0的位置
for(int i=9;i;i--){//9位数变状态
a[i]=x%10,x/=10;
if(a[i]==0) p=i;
}
if(op==1){
if(p<=3) return -1;//边界
swap(a[p],a[p-3]);
}else if(op==2){
if(p>=7) return -1;//边界
swap(a[p],a[p+3]);
}else if(op==3){
if(p%3==1) return -1;//边界
swap(a[p],a[p-1]);
}else if(op==4){
if(p%3==0) return -1;//边界
swap(a[p],a[p+1]);
}
x=0;//变为9位数
for(int i=1;i<=9;i++) x=x*10+a[i];
return x;
}
void check(int x,pair<int,bool> h){
if(x!=-1)
if(rec[h.second^1].count(x)){
//另一个方向的已到达这个状态
cout<<rec[h.second^1][x]+rec[h.second][h.first]+1;
exit(0);
}else{//存入状态
rec[h.second][x]=rec[h.second][h.first]+1;
Q.push({x,h.second});
}
}
int main(){
cin>>bg;
if(bg==ed){
cout<<"0";
return 0;
}
Q.push({bg,0});
Q.push({ed,1});
while(!Q.empty()){//双向BFS
pair<int,bool> h=Q.front();
Q.pop();
int x=change(h.first,1);//0向上
check(x,h);
x=change(h.first,2);//0向下
check(x,h);
x=change(h.first,3);//0向左
check(x,h);
x=change(h.first,4);//0向右
check(x,h);
}
return 0;
}
