线程 机器学习 servlets video deployment cmake hyperlink onclick jvm Amaze UI vue双向绑定 jq绑定click事件 jquery去空格 mysql操作日志 oracle删除字段sql coreldraw学习 linux管道符 图片生成链接 mysql连接 python创建数据库 python定义一个变量 python调用自定义函数 java正则匹配 java日期 java中的多态 java8教程 java开发环境安装 linuxshell linux目录系统 php连接mssql win7loader 手机照片恢复免费软件 微信超级好友 蒙文字体 苹果双微信 win10环境变量 梦幻手游助手 ABViewer php取整 pr放大画面
当前位置: 首页 > 学习教程  > 编程语言

2021-02-13poj 1426 Find The Multiple

2021/2/13 19:09:46 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

poj 1426 Find The Multiple 1.基本的BFS 2.剪枝的方法&#xff1a;比如说x%ny%nc,x<y,根据同余模定理&#xff0c;&#xff08;x101(或0&#xff09;&#xff09;%n(x%n10%n)%n1(或0&#xff09;%n(c10%n)%n1(或0&#xff09;%n 同理&#xff08;y101(或0&#xff09;&…

poj 1426 Find The Multiple

1.基本的BFS
2.剪枝的方法:比如说x%n=y%n=c,x<y,根据同余模定理,(x10+1(或0))%n=(x%n10%n)%n+1(或0)%n=(c10%n)%n+1(或0)%n
同理(y
10+1(或0))%n=(y%n10%n)%n+1(或0)%n=(c10%n)%n+1(或0)%n
BFS最先搜索到的数是小的x,可以看出 x,y往下继续搜索到的数算出的余数是一样的,因为x最早开始,比y快,所以把y剪掉,用vis数组记录一下就行(我看到网上也有不剪枝直接 BFS过的)

#include<iostream> 
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long ll;
int vis[210];
ll BFS(int n){
	queue <ll> q;
	ll now, next; 
	while(!q.empty()) q.pop();
	q.push(1);
	vis[1%n] = 1;
	if (1%n == 0) return 1;//处理第一个数 
	while(!q.empty()){
		now = q.front();
		q.pop();
		for(int i=0; i<2; ++i){
			next = 10 * now + i;
		    if(next%n == 0) return next;
			if (!vis[next%n]){
				q.push(next);
				vis[next%n] = 1;
			} 
		}
	}
	return -1;
}
int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		if (n == 0) break;
		memset(vis, 0, sizeof(vis));
		printf("%lld\n", BFS(n));
	}
} 

本文链接: http://www.dtmao.cc/news_show_700286.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?