2020/11/12 Day 2 笔记
今天N老师因为要监考，所以布置了一堆AcWing的题目（9道）T89~T98。因本蒟蒻的水平实在太低，并不会做T98“分形之城”，所以今天就分享一下其他几道题的做题经验。
步入正题——（89,90,95题的题解我已经发在昨天的blog上了）
- 最短Hamilton路径
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数n。
接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
1≤n≤20
0≤a[i,j]≤107
输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18
解析：我第一次看到这道题是崩溃的（因为并不知道hamilton路怎么写），但是从网上查到了hamilton路的方法：
其实这是一道旅行商问题，NP问题（显然我并不知道怎么写），但是发现有的做法使用了状态压缩DP并且写起来很简单。
主要的想法是：从一个点出发，有若干种走法，每走一步都进行比较，并且只选取最短的路径，用每一步的最优解来达到全局最优。所以就是一道很简单的DP题目，状态转移方程：
设i为方案，j为抵达的点，就有：
f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]
下面贴代码：
#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<20;
int n;
int f[M][N];
int weight[N][N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>weight[i][j];
}
}
memset(f,0x3f,sizeof(f));
f[1][0]=0;
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
{
if((i>>j)&1)
{
for(int k=0;k<n;k++)
{
if((i-(1<<j)>>k)&1)
{
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[j][k]);
}
}
}
}
}
cout<<f[(1<<n)-1][n-1]<<endl;
return 0;
}- 递归实现指数型枚举
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
这是一个递归部分的板子题，直接DFS+递归就能做出来。递归的作用就是进行判重，并且要对三个状态进行分析：第一个：最大的数字，第二个：当前搜索到的数字，第三个：一共需要搜索多少个数字。
贴代码：
#include<bits/stdc++.h>
using namespace std;
int n;
void dfs(int x,int now)
{
if(x>n) return;
if(x==n)
{
for(int i=1;i<=n;i++)
if(now>>(i-1)&1)
cout<<i<<" ";
puts("");
}
dfs(x+1,now<<1|1);
dfs(x+1,now<<1);
}
int main()
{
cin>>n;
dfs(0,0);
return 0;
}- 递归实现组合型枚举
从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。
数据范围 n>0 , 0≤m≤n , n+(n−m)≤25
输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
分析：这道题的做法和上一道题很相似，进行DFS，用回溯算法就可以写出来，但是要注意只输出m个的情况。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
void dfs(int x,int now,int date)
{
if(x>n||date+(n-x+1)<m) return;
if(date==m)
{
for(int i=1;i<=n;i++)
if(now>>(i-1)&1)
cout<<i<<" ";
puts("");
return;
}
dfs(x+1,now+(1<<x),date+1);
dfs(x+1,now,date);
}
int main()
{
cin>>n>>m;
dfs(0,0,0);
return 0;
}- 递归实现排列型枚举
把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围 1≤n≤9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
分析:这道题还有一个名字叫全排列，思路还是很相似，依然要用vis数组判重，用DFS深搜就可以出正解了。
代码：
#include<bits/stdc++.h>
using namespace std;
int order[20],n;
bool vis[20];
void cal(int k)
{
if(k==n+1)
{
for(int i=1;i<=n;i++)
cout<<order[i]<<" ";
puts("");
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
order[k]=i;
vis[i]=1;
cal(k+1);
vis[i]=0;
order[k]=0;
}
}
int main()
{
cin>>n;
cal(1);
return 0;
}- 奇怪的汉诺塔
汉诺塔问题，条件如下：
1、这里有A、B、C和D四座塔。
2、这里有n个圆盘，n的数量是恒定的。
3、每个圆盘的尺寸都不相同。
4、所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸从塔顶到塔底逐渐增大。
5、我们需要将所有的圆盘都从塔A转移到塔D上。
6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。
请你求出将所有圆盘从塔A移动到塔D，所需的最小移动次数是多少。
输入格式
没有输入
输出格式
对于每一个整数n(1≤n≤12),输出一个满足条件的最小移动次数，每个结果占一行。
输入样例：
没有输入
输出样例：
参考输出格式
解析：本来的汉诺塔的递推方程是：d[i]=d[i-1]*2+1（不会真有人不知道吧？不会吧，不会吧）
但是还需要进行的递归是以塔的数目为基础进行计算，每次都去掉一个塔，求剩余塔的解法，状态转移方程是：
f[i]=min(f[i],f[j]*2+d[n-j]);
代码：
#include<bits/stdc++.h>
using namespace std;
int d[21],f[21],i,j;
int main()
{
for(i=1;i<=12;i++)
d[i]=2*d[i-1]+1;
memset(f,0x3f,sizeof(f));
f[0]=0;
for(i=1;i<=12;i++)
for(j=0;j<i;j++)
f[i]=min(f[i],f[j]+f[j]+d[i-j]);
for(i=1;i<=12;i++)
cout<<f[i]<<endl;
return 0;
}- 约数之和
假设现在有两个自然数A和B，S是AB的所有约数之和。
请你求出S mod 9901的值是多少。
输入格式
在一行中输入用空格隔开的两个整数A和B。
输出格式
输出一个整数，代表S mod 9901的值。
数据范围
0≤A,B≤5×107
输入样例：
2 3
输出样例：
15
注意: A和B不会同时为0。
解析：
先来ctrl+v一段数学类分析：
质因数分解，就是将一个数分解成为 p1c1×p2c2×…×pncnp1c1×p2c2×…×pncn 比如说24=23×3124=23×31
唯一分解定律，就是字面意思
约数和公式，如下文所示
AB=(1+p11+p12+.....+p1B∗c1)×(1+p22+.....+pnB×c2AB=(1+p11+p12+.....+p1B∗c1)×(1+p22+.....+pnB×c2) sum(p,c)=1+p+p2+…+pcsum(p,c)=1+p+p2+…+pc
然后呢我们可以通过分类以及乘法中的提取公因式法，将sum函数中c为奇数的公式和sum函数中c为偶数的公式推出。
快速幂写法：
int fast(int a,int b)
{
int ans=1;
a%=mod;
while(b)
{
if (b&1)
ans=ans%mod*a;
a=a%mod*a%mod;
b>>=1;
}
return ans;
}求和写法：
long long sum(int p,int c)
{
if (c==0)
return 1;
if(c&1)//奇数
return ((1+fast(p,(c+1)>>1))*sum(p,(c-1)>>1))%mod;
else//偶数
return ((1+fast(p,c>>1))*sum(p,(c>>1)-1)+fast(p,c))%mod;
}完整代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define mod 9901
int a,b;
int fast(int a,int b)
{
int ans=1;
a%=mod;
while(b)
{
if (b&1)
ans=ans%mod*a;
a=a%mod*a%mod;
b>>=1;
}
return ans;
}
long long sum(int p,int c)
{
if (c==0)
return 1;
if(c&1)
return ((1+fast(p,(c+1)>>1))*sum(p,(c-1)>>1))%mod;
else
return ((1+fast(p,c>>1))*sum(p,(c>>1)-1)+fast(p,c))%mod;
}
int main()
{
cin>>a>>b;
int ans=1;
for (int i=2;i<=a;i++)
{
int s=0;
while(a%i==0)
{
s++;
a/=i;
}
if (s)
ans=ans*sum(i,s*b)%mod;
}
if (a==0)
cout<<0<<endl;
else
cout<<ans<<endl;
return 0;
}