【BZOJ1072】排列(搜索)
搜索 排列
2023-09-11 14:14:41 时间
【BZOJ1072】排列(搜索)
题面
题解
算下复杂度,如果用\(next\_permutation\)
那就是\(10!\times 10\times 15\),复杂度不太对
那好办啊,把\(next\_permutation\)改成搜索不就完了。。
#include<iostream>
#include<cstring>
using namespace std;
char ch[15];
int a[10],d,ans,n;
void dfs(int x,int r)
{
if(x==n+1){ans+=r==0;return;}
for(int i=0;i<=9;++i)
if(a[i])--a[i],dfs(x+1,(r*10+i)%d),++a[i];
}
int main()
{
ios::sync_with_stdio(false);
int T;cin>>T;
while(T--)
{
cin>>(ch+1)>>d;ans=0;n=strlen(ch+1);
for(int i=n;i;--i)++a[ch[i]-48];
dfs(1,0);cout<<ans<<endl;
a[0]=a[1]=a[2]=a[3]=a[4]=a[5]=a[6]=a[7]=a[8]=a[9]=0;
}
return 0;
}
相关文章
- PHP文件查找器,搜索本地文件
- nyist oj 19 擅长排列的小明(dfs搜索+STL)
- 编程算法 - 二叉搜索树 与 双向链表 代码(C++)
- 【BZOJ4325】NOIP2015 斗地主 搜索+剪枝
- C#,深度优先搜索(DFS)、广度优先搜索(BFS)算法的源代码与数据可视化
- 谷歌发布美国语音搜索使用习惯报告
- 何不 Ack?Grep, Ack, Ag的搜索效率对比
- UVa 1629 Cake slicing (记忆化搜索)
- Python 3 多线程下载百度图片搜索结果
- vim搜索及高亮取消
- (2022.02)取消idea双击shift键时出现的全局搜索
- Linux经常使用命令-文件搜索命令-文件搜索命令find
- [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点