备战蓝桥杯---搜索（进阶4）

话不多说，直接看题：

下面是分析：

(a+b)%c=(a%c+b%c)%c;

(a*b)%c=(a%c*b%c)%c;

因此，如果两个长度不一样的值%m为相同值，那就舍弃长的（因为再加1位只不过是原来值*10+那位值，因此他们得出的%m还是同一值）。

因此，我们每次只要BFS最多m-1个值，复杂度为O(k*m*n),其中N为数的位数。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int k,m,vis[10010];
struct node{string s;int yu;
};
queue<node> q;
void bfs(string ss){for(int i=1;i<=k-1;i++){if(vis[i%m]==0){vis[i%m]=1;q.push({to_string(i),i%m});}}while(!q.empty()){node ck=q.front();q.pop();if(ck.yu==0){cout<<ck.s;return;}for(int i=0;i<=k-1;i++){if(vis[(ck.yu*10+i)%m]==1) continue;q.push({ck.s+to_string(i),(ck.yu*10+i)%m});vis[(ck.yu*10+i)%m]=1;}}
}
int main(){cin>>k>>m;bfs("0");
}

接题：

相当于我们要从边界进去一次，并出来一次。

考虑到有a*b个位置可以进，我们可以表示从左上端点开始，可以在边界上动，到了相应的位置再进去即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int a,b,w[10][10],cnt,c[20],kk;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int x,int y,int k){if(k==2&&(x==0||x==a||y==0||y==b)){cnt++;return;}for(int i=0;i<4;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx<0||yy<0||xx>a||yy>b) continue;if(w[xx][yy]==1) continue;w[xx][yy]=1;int k1=k;if(xx!=0&&xx!=a&&yy!=0&&yy!=b&&k==1) k1=2;dfs(xx,yy,k1);w[xx][yy]=0;}return;
}
int main(){cin>>a>>b;if(a==1){cout<<b-1;return 0;}w[0][0]=1;w[1][0]=1;dfs(1,0,1);cout<<cnt;
}

接题（很有意思）：

我们可以得到：每次切割都应该为x/n,y/n的整数倍（否则无法切成相等的，可以画图更直观一点）

然后，切的刀数按照倍数分即可。我们先要选出最大值的最小值，于是我们for切刀，递归求出每一种情况的最大值的最小值（注意，每一个被分的两部分求max,因为他们两个共同组成这一种情况）

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
double x,y;
int n1;
double dfs(double x,double y,int n){if(n==1){return max(x,y)/min(x,y);}double ans=10001;double xx=x/n;double yy=y/n;for(int i=1;i<=n-1;i++){double aa=max(dfs(xx*i,y,i),dfs(x-xx*i,y,n-i));double bb=max(dfs(x,yy*i,i),dfs(x,y-yy*i,n-i));ans=min(ans,aa);ans=min(ans,bb);}return ans;
}
int main(){cin>>x>>y>>n1;printf("%.6lf",dfs(x,y,n1));
}