SGU 108 — Self-numbers 2
很囧的一道题.
这道题我刚开始TLE,后来发现原来是RE,SGU的系统报TLE而已…然后改了个越界的地方就AC了.
首先定义了generator:首先我们定义d(n)为n和n的每一位数字相加的和,那么n就叫做d(n)的generator.一个没有generator的数叫做self-number(总觉得这东西应该是什么守形数才对…).
做法是改进的筛法.刚开始没想出来于是去WindyWinter牛的blog上看了下,然后发现筛法数组开到64就可以(9*7=63),只需要循环使用一下.
然后就是这样…每次通过n筛掉d(n),然后就OK了…
最后差一点TLE…rp比较好…
{
SGU 108; Self-numbers 2
- sqybi’s code
}
//for my winsty
program sgu108_sqybi;
const
rr = 64;
nn = 10000000;
mm = 5000;
type
rec = record
v, k: longint;
end;
var
n, m, i, t, p: longint;
a: array[1..mm]of rec;
b: array[1..mm]of longint;
f: array[0..rr-1]of boolean;
getArr: array[0..9999]of longint;
procedure qsort(l, r: longint);
var
i, j, d: longint;
t: rec;
begin
if l >= r then exit;
i := l;
j := r;
d := a[(l+r) div 2].v;
repeat
while a[i].v < d do inc(i);
while a[j].v > d do dec(j);
if i <= j then begin
t := a[i];
a[i] := a[j];
a[j] := t;
inc(i);
dec(j);
end;
until i > j;
qsort(l, j);
qsort(i, r);
end;
function get(x: longint): longint;
var
t: longint;
begin
t := 0;
while x <> 0 do begin
t := t + x mod 10;
x := x div 10;
end;
get := t;
end;
function get_(x: longint): longint;
var
t: longint;
begin
t := x;
while x <> 0 do begin
t := t + getArr[x mod 10000];
x := x div 10000;
end;
get_ := t;
end;
begin
readln(n, m);
for i:=1 to m do begin
read(a[i].v);
a[i].k := i;
end;
qsort(1, m);
for i:=1 to 9999 do
getArr[i] := get(i);
fillchar(f, sizeof(f), true);
t := 0;
p := 1;
for i:=1 to n do begin
f[(i-1) mod rr] := true;
f[get_(i) mod rr] := false;
if f[i mod rr] then inc(t);
while (p <= m) and (a[p].v = t) do begin
b[a[p].k] := i;
inc(p);
end;
end;
writeln(t);
for i:=1 to m do write(b[i], ‘ ‘);
end.
阅读(46 次)