首页 > 代码库 > 【bzoj入门】3189 猜数字（数学，搜索）

【bzoj入门】3189 猜数字（数学，搜索）

2024-08-18 23:49:40   224人阅读

Description

味味最近在玩猜数字的游戏,现在她也希望你来玩一下这个游戏。猜数字游戏的规则是这样的,告诉你一个正整数 n
(2<=n<=11),然后味味心中会想一个 n 个数字组成的数字串 (数字串最前面若干位可能是 0)。味味会随意排列 n 
位数上的数字,这样可能产生 n!个 n 位数。(n!=1×2×3×4×5×......×n,n!念作“n 阶乘”).比如味味想了一
个三位数 abc,那么一共会产生六个三位数,分别为 abc,acb,bac,bca,cab,cba然后味味会把这 n!个 n 位数求和得
到 S(若某数第一位开始有若干个 0,则求和时这些 0 舍去。如有数“0123”,则求和时加到 s 中的值是 123),她
会告诉你总和 S 减去她心中想的那个数的值,请你猜出味味心中想的那个数。
 
输入共包含两行。第一行一个整数 n(含义如前面所述),第二行一个正整数S,表示 n!个数的总和减去味味心中那个数的值。
2≤n≤11 ,0≤S≤10^18。如果该数第一位开始有若干个 0,则输出时这些 0 也必须输出(详见样例 3)。 
 
思路：设已经知道答案每个位置上的数，推导公式可发现S只与数位之和与原数有关 
        直接搜索原数会超时，所以枚举0-9各自出现了几次，利用S与数位之和反推出原数，验证0-9出现的次数是否符合
 1 var a,b:array[0..9]of longint;
 2     pt,i,n:longint;
 3     s,q,ans,m,max:int64;
 4     p:boolean;
 5  
 6 procedure dfs(k,g,t:longint);  //g shengyugeshu t shuweihe
 7 var i,tt:longint;
 8     flag:boolean;
 9     q:int64;
10  
11 begin
12  if p then exit;
13  
14  if k=10 then
15  begin
16   if g>0 then exit;
17   q:=t*m-s; ans:=q;
18   if q>max then exit;
19   if q<0 then exit;
20   fillchar(b,sizeof(b),0); tt:=n;
21   while q>0 do
22   begin
23    inc(b[q mod 10]);
24    q:=q div 10; dec(tt);
25   end;
26   b[0]:=b[0]+tt;
27   flag:=true;
28   for i:=0 to 9 do
29    if a[i]<>b[i] then begin flag:=false; break; end;
30   if flag then begin pt:=tt; p:=true; end;
31   exit;
32  end;
33  
34  if g=0 then
35  begin
36   dfs(10,0,t);
37   exit;
38  end;
39  
40  {if k=9 then
41  begin
42   a[9]:=g;
43   dfs(10,0,t+g*9);
44   a[9]:=0;
45   exit;
46  end; }
47  
48  for i:=0 to g do
49  begin
50   a[k]:=i;
51   dfs(k+1,g-i,t+k*i);
52   a[k]:=0;
53   if p then exit;
54  end;
55 end;
56  
57 begin
58   
59  readln(n);
60  for i:=1 to n do m:=m*10+1;
61  for i:=1 to n-1 do m:=m*i;
62  readln(s);
63  for i:=1 to n do max:=max*10+9;
64  p:=false;
65  dfs(0,n,0);
66  for i:=1 to pt do write(0);
67  write(ans);
68   
69 end.

 

【bzoj入门】3189 猜数字（数学，搜索）


联系
我们