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

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出现的次数是否符合

 var a,b:array[..]of longint;

     pt,i,n:longint;

     s,q,ans,m,max:int64;

     p:boolean;

 procedure dfs(k,g,t:longint);  //g shengyugeshu t shuweihe

 var i,tt:longint;

     flag:boolean;

     q:int64;

 begin

  if p then exit;

  if k= then

  begin

   if g> then exit;

   q:=t*m-s; ans:=q;

   if q>max then exit;

   if q< then exit;

   fillchar(b,sizeof(b),); tt:=n;

   while q> do

   begin

    inc(b[q mod ]);

    q:=q div ; dec(tt);

   end;

   b[]:=b[]+tt;

   flag:=true;

   for i:= to  do

    if a[i]<>b[i] then begin flag:=false; break; end;

   if flag then begin pt:=tt; p:=true; end;

   exit;

  end;

  if g= then

  begin

   dfs(,,t);

   exit;

  end;

  {if k=9 then

  begin

   a[9]:=g;

   dfs(10,0,t+g*9);

   a[9]:=0;

   exit;

  end; }

  for i:= to g do

  begin

   a[k]:=i;

   dfs(k+,g-i,t+k*i);

   a[k]:=;

   if p then exit;

  end;

 end;

 begin

  readln(n);

  for i:= to n do m:=m*+;

  for i:= to n- do m:=m*i;

  readln(s);

  for i:= to n do max:=max*+;

  p:=false;

  dfs(,n,);

  for i:= to pt do write();

  write(ans);

 end.

巴特西

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

Description

最新文章

热门文章

巴特西

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

Description

最新文章

热门文章

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