题目链接:uva 1341 - Different Digits
题目大意:给定一个数字n,要求求一个数字m,m可以整除n,并且尽量组成的数字种类(0~9)尽量少,在种类相同的情况下数值尽量小。
解题思路:可以证明两种数字肯定可以组成m,假设有数字k,一种数字可以有k,kk,kkk,kkkk,…整除n剩的数一定在0~n-1之间,所以肯定存在两个由k数字组成的数字同模,那么这两个数相减所得到的数即使kkk00000,两种数字。于是肯定了范围,枚举数字,然后用bfs获取答案,维护最小值即可。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 65536;
int n, vis[maxn+10];
struct state {
int key, len, vec[maxn];
state () {
key = 0;
}
bool operator < (const state& a) {
if (a.key == 0)
return true;
if (key == 0)
return false;
if (key != a.key)
return key < a.key;
if (len != a.len)
return len < a.len;
int l = len;
for (int i = 0; i < l; i++)
if (vec[i] != a.vec[i])
return vec[i] < a.vec[i];
return false;
}
};
struct node {
int mod, len, num;
void set (int mod, int num, int len) {
this->mod = mod;
this->num = num;
this->len = len;
}
}que[maxn*2];
void put (int d, state& w, int x) {
if (d < 0 || x < 0)
return;
w.vec[d] = que[x].num;
put(d-1, w, vis[que[x].mod]);
}
state judge (int a, int b) {
int head = 1, rear = 1;
memset(vis, -1, sizeof(vis));
state w;
node u, v;
w.key = (a==b?1:2);
if (a) {
que[rear++].set(a%n, a, 1);
vis[a%n] = 0;
}
if (b) {
que[rear++].set(b%n, b, 1);
vis[b%n] = 0;
}
while (head < rear) {
u = que[head++];
if (u.mod == 0) {
w.len = u.len;
put(u.len-1, w, head-1);
return w;
}
for (int i = 0; i < w.key; i++) {
int t = (i?b:a);
v.set((u.mod*10+t)%n, t, u.len+1);
if (vis[v.mod] != -1)
continue;
vis[v.mod] = head-1;;
que[rear++] = v;
}
}
w.key = 0;
return w;
}
int main () {
while (scanf("%d", &n) == 1 && n) {
state ans;
for (int i = 1; i <= 9; i++) {
state c = judge(i, i);
if (c < ans)
ans = c;
}
if (ans.key == 0) {
for (int i = 0; i <= 9; i++) {
for (int j = i+1; j <= 9; j++) {
state c = judge(i, j);
if (c < ans)
ans = c;
}
}
}
for (int i = 0; i < ans.len; i++)
printf("%d", ans.vec[i]);
printf("\n");
}
return 0;
}
分享到:
相关推荐
统信系统UOS资源包4digits_1.1.4-1+b1 资源列表: 4digits_1.1.4-1+b1_amd64.deb 4digits_1.1.4-1+b1_arm64.deb 4digits_1.1.4-1+b1_i386.deb 4digits_1.1.4-1+b1_mips64el.deb 4digits_1.1.4.orig.tar.gz 4digits_...
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
uva 11198 - Dancing Digits.cpp 的代码
-----+--------------------+-------------+-------------+ | | | | V V | | +---------+ n0, n1 +----------+ | | | Model 1 |--------->| Mixer 1 |\ p | | +---------+ \ / | | \ V V \ / +----------+ \ ...
Laravel开发-unique-digits 为PHP的不同需求(票号和其他)创建数字值。
So far we know that most Tait equipment uses 3 digits to indicate the basic RF configuration of the radio. Let's use the model number T2020-XYZ-AAA as an example... Tait calls the XYZ digits the "RF ...
L = {Postfix expression consisting of digits, plus and multiple signs} 2.2.2 What language is generated by the following grammars? In each case justify your answer. S -> 0 S 1 | 0 1 S -> + S S | - S S...
开源项目-dghubble-go-digits.zip,Go packages for Digits - make a phone number login app in ~100 lines
本代码为自制:自动获取时间戳10位10进制,亲测可运行。
FParsec-管道该库是FParsec库( )的扩展。 请参阅或阅读。 FParsec-Pipes没有定义新的... [ count ] * digit ) -|> ( String >> Int32.Parse ) %% + .digits 4 -- '-' -- + .digits 2 -- '-' -- + .digits 2 -- 'T'
上机测试-数科20-digits.py
以C51为主采用74HC573进行proteus仿真,可实现六位(可调)数字右闪输出,输出结果显示在数码管上
“#t-mobile-digits”
Digits.com的Cordova插件 安装 cordova plugin add https://github.com/cosmith/cordova-digits.git --variable FABRIC_API_KEY=your_api_key --variable FABRIC_API_SECRET=your_api_secret 用法 目前仅实现一种...
手写数字识别数据集,MNIST,包括原始数据集的所有样本,以及抽取的2000个样本的子集,.mat格式。美国著名数据集NIST的子集,模式识别常用实验数据集
Gray-scale-Hand-Written-Digits-Pytorch 手写数字识别Mnist的Pytorch实现 博客: 一、引言(Introduction) 手写数字识别时经典的图像分类任务,也是经典的有监督学习任务,经常被用于测试图像的特征提取效果、...
iOS 4位数字密码-Swift 2.0 iOS的4位数字别针用户界面
PFUser-Digits:使用Twitter Digits验证解析用户
数学工作表生成器 背景 我最好的朋友从商店购买的材料中测试了他5岁的基本数学问题,这一次可以使用(他的儿子会记住答案)……。 但他想给他更多练习。... python3 run.py --type [+|-|x|/|mix] --digits [1|2|3] [-