Archive for 五月 13th, 2008
Posted on 五月 13th, 2008.
具体题解看这里:http://www.briefdream.com/sgu-116/
这道题很囧的一点是,我一直不知道背包的一维写法…其实就是f[i]=min(f[i-a[j]])+1,然后就ok了…囧死了,因为这个MLE了…改后AC.
{ SGU 116; Index of super-prime - sqybi’s code - DP(package)}//for my winstyprogram sgu116_sqybi; const nn = 10000; inf = 1000000;
var n, i, j, lp, lsp, outl: longint; sp, p, outArr: array[1..nn]of longint; pf: array[1..nn]of boolean; d, path: array[0..nn]of longint;
procedure qsort(l, r: longint); var i, j, d, t: longint; begin if […]
Read Full Post |
Make a Comment ( None so far )
Posted on 五月 13th, 2008.
很囧的一道题.这道题我刚开始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 winstyprogram 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); […]
Read Full Post |
Make a Comment ( None so far )
Posted on 五月 13th, 2008.
这道题其实就是等价于问A1+A1*A2+…+A1*A2*…*An对9的余数,注意如果余数是0的话就输出9.
不过这里我有一点疑问,为什么0的digital root应该是9才能AC…难道是题目出的有问题…囧.
{ SGU 118; Digital Root - sqybi’s code - Why AC… what should root(0) be?!}//for my winstyprogram sgu118_sqybi; var n, s, t, x, i, times, cases: longint;
function root(x: longint): longint; begin if x mod 9 = 0 then root := 9 else root := x mod 9; end;
begin readln(cases); for […]
Read Full Post |
Make a Comment ( None so far )