PAT 1103 Integer Factorization (30分) dfs(可行性剪枝+最有性剪枝)附数据生成器和对拍程序 Apare_xzc
PAT 1103 Integer Factorization (30分)
dfs+剪枝
附数据生成器和对拍程序
题目链接：
1103 Integer Factorization(30分)
题面：
题意：
输入为3个正整数N, K, P, 现在要将 N 分解成 K 个数的 P 次方之和，要求这K个数组成的数列是非递增的数列。
如果没有满足的拆分方案，输出一行“Impossilbe”, 如果有多组拆分方案，输出K个的和最大的方案，如果仍有多组方案，输出字典序最大的方案。
数据范围：
1 <= N <= 400
1 <= K <= N
2 <= P <= 7
(N,K,P 为正整数)
样例：
Sample Input 1
169 5 2
Sample Output 1
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
Sample Input 2
169 167 3
Sample Output 2
Impossible
分析与思路：
因为是把正整数拆分成K个正整数的P次方之和，可能会有凑不出来的情况。那么我们如何知道凑不出来呢？
我们先分析边界条件，如果K个数都取最小值1, 还比N大，那一定无解。但是题目条件已经保证了K<=N, 所以我们并不能直接判断出Impossible的情况。所以我们只能搜索，如果搜不到可行解，那么就是无解。
我们不妨做一个简单的思考，如果K个数一样大，那么一定是最优解（想想为什么）
题目要求输出K个数之和最大的可行解，如果和相同，输出字典序最大的式子。所以我们不妨按字典序从大到小进行搜索，如果sum_of_k比之前的可行解大，再更新答案
由于是非递增的数列，所以我们在搜索的时候，只要先确定第一个数的大小。那么第一个数的上界和下界怎么确定呢？
我们可以分析一下，如果后面的K-1个数都去最大值，即都和第一个数一样，他们的P次方和还是小于N, 这样肯定是无解，所以我们的下界down要满足 down^p * K >= N , 循环或者二分即可以找到最大的下界； 如果后面的K-1个数都取最小值，即都取1，他们的P次方之和还是小于N, 可定也无解。所以上届up要满足up^p + K - 1 <= N, 可以二分找到up的最小值。于是我们确定了第一个数的上届up和下界down.
接下来我们就可以开始搜索了。搜索的时候，我们自然还是要从往小填数来保证字典序最大的需要，填数的上届和下界的计算方法同第一个数。
关于剪枝, 我们可以进行可行性剪枝和最有性剪枝：
- 可行性剪枝:
如果后面都放最大值都凑不够N, 就剪掉
如果后面都放1都比N大，也剪掉 - 最优性剪枝：
如果后面都放最大值，最后K个数的和还是小于当前的最大和，也剪掉
这样搜索的效率就会比较高
我的AC代码(15ms)
#include <bits/stdc++.h>
using namespace std;
int Pow[21][8]; //Pow[x][j]中存储的是x^j
long long a[21]; //a[i]表示Pow[i][p]
int N,k,p; //题目输入，待分解的正整数N,要拆分成K个数的p次方之和
int ans[405]; //搜索中用于存储拆分方案的数组
int res[405]; //用于记录最终答案的数组
int MaxSum; //拆分后x1,x2,x3...xk最大的和
bool flag; //标记是否搜到了可行的拆分方案
void dfs(int index,int pos,int remain,int tmpSum)
{ //
if(pos==k+1) //说明搜到了一种可行的拆分方案
{
flag = true; //标记搜到了解
if(tmpSum>MaxSum) //更新最大的和
{ //因为是按字典序从大往小遍历的，所以
//tmpSum==MaxSum并不需要更新答案
MaxSum = tmpSum; //更新K个数的最大和，并记录答案
for(int i=1;i<=k;++i) res[i] = ans[i];
}
return;
}
ans[pos] = index; //第pos个数是index
tmpSum += index; //当前pos个数的总和为tmpSum
remain -= a[index]; //remain代表N减去之前Pos个数的p次方和剩余
///可行性剪枝：
if(1ll*(k-pos)*a[1]>remain) return;
//后面从第pos个到第K个数都放1也会使最后最后的p次方之和大于N
if(1ll*(k-pos)*a[index]<remain) return; //
//后面从第pos个到第K个数都放index^p也会使最后最后的p次方之和大于N
///最优性剪枝：
if(1ll*(k-pos)*index+tmpSum<MaxSum) return;
////后面从第pos个到第K个数都放index^p得到的K个数的和也小于之前搜到的最大值
for(int t=index;t>=1;--t)
{//从index往1遍历，保证了字典序大的先搜索
dfs(t,pos+1,remain,tmpSum);
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out2.txt","w",stdout);
//因为p>=2,N<=400,所以填的数最大为sqrt(400)=20
for(int i=1;i<=20;++i) //预处理1-20的2-7次方
Pow[i][0] = 1;
for(int i=1;i<=20;++i)
for(int j=1;j<=7;++j)
Pow[i][j] = Pow[i][j-1]*i;
while(scanf("%d%d%d",&N,&k,&p)!=EOF)
{ //多组输入
// printf("%d %d %d\n",N,k,p); //用于调试
map<int,int> mp; //mp中存放1-20的p次方
for(int i=1;i<=20;++i)
a[i] = Pow[i][p],mp[a[i]]++;
if(N%k==0&&mp.count(N/k)) //注意判断键的存在性要用count
//打codeforces的时候吃过两次亏，用[]访问直接MLE
{ //K个数都相同和一定最大
int y = N/k; //存在x使得x^p * K = N
int x = lower_bound(a,a+21,y)-a; //二分查找确定x的值
//输出答案，行末无空格
printf("%d = %d^%d",N,x,p);
for(int i=2;i<=k;++i)
printf(" + %d^%d",x,p);
puts("");
continue;
}
MaxSum = 0;
//up和down是第一位的上界和下界
int up = 0; //a[up] <= N-K+1的最大值
int down = 0; //a[down]*K>=n;的最小值
for(int i=1;i<=20;++i)
if(a[i]<=N-k+1) up = i;
for(int i=1;i<=20;++i)
{
if(a[i]*k>=N)
{
down = i;break;
}
}
flag = false;
for(int st=up;st>=down;--st)
{
dfs(st,1,N,0);
}
if(!flag) puts("Impossible");
else
{
printf("%d = %d^%d",N,res[1],p);
for(int i=2;i<=k;++i)
printf(" + %d^%d",res[i],p);
puts("");
}
}
return 0;
}
数据生成器：
由于这道题N,K,P范围都不大，所以我们可以穷尽所有的合法输入。只要保证：
1 <= N <= 400
1 <= K <= N
2 <= P <= 7
(N,K,P 为正整数)
即可，所以数据生成也非常好写，只需要三个for加文件输出即可
数据生成器代码
CreateDate.cpp
//Create Date.cpp
//Author xzc
//2020.1.31
#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("in.txt","w",stdout);
for(int N=1;N<=400;++N)
{
for(int k=1;k<=N;++k)
{
for(int p=2;p<=7;++p)
cout<<N<<" "<<k<<" "<<p<<endl;
}
}
return 0;
}
运行完CreateDate.cpp之后，我们得到一个较大的输入文件in.txt, 可以用notepad++或者其它文本编辑器打开来查看
生成标准答案：
因为这个题也没什么其它的更稳妥，更暴力的方法生成答案，所以，我们可以用已经AC了的正确代码来计算出 (400+1)*400/2*6 = 481200组N,P,K的输入的解
我用我的AC代码，改成多组输入，然后用freopen()输入输出重定向，得到了所有输入的解，用时119秒
可以得到一个更大的输出文件，由于为了对排方便，我在每个样例的答案前一行都输出了N,K,P的值。输出文件out.txt的内容展示如下：
对拍程序：judge.cpp
比较输出文件和标准答案的异同，如果不同，得到相应的输入和错误输出，并且统计出错的个数。
因为我进行了比较好的剪枝，所以程序跑得飞快，119秒就跑完了481200组输入的数据，但是你的程序如果没有剪枝，或者cin,cout，或者滥用STL，或者该二分查找的非要for遍历等等，可能根本不能在可以接受的时间内跑完所有的合法输入，所以，我们人性化一点儿，没有直接比较两个文件到文件尾，我们设置了比较的行数。
#include <bits/stdc++.h>
using namespace std;
string ask1,res1,ask2,res2;
int main()
{
ifstream Ans("out.txt"); //标程生成的标准答案
ifstream Out("MyOut.txt"); //你的输出
// freopen("Judge_result.txt","w",stdout);
int cnt = 0;
for(int i=1;i<=962400;i+=2)
{
getline(Ans,ask1);
getline(Ans,res1);
getline(Out,ask2);
getline(Out,res2);
if(res1!=res2)
{
cout<<ask1<<endl;
cout<<"ans is: "<<res1<<endl;
cout<<"Myout is: "<<res2<<endl;
cout<<endl;
++cnt;
}
}
Ans.close();
Out.close();
if(cnt==0) cout<<"AC"<<endl;
else cout<<"cnt = "<<cnt<<endl;
return 0;
}
评测结果显示：
同程旅行工作强度 19人发布
