水题.求出中位数即可.
根据WindyWinter的blog,有两点注意.
Pascal注意,读入n对数时,应该用read而不是readln,因为虽然样例数据有换行,但题目中的描述是没有换行的.否则会像我一样WA on 14.
C++注意,iostream会TLE on 12.
{ SGU 114; Telecasting station - sqybi’s code}//for my winstyprogram sgu114_sqybi; const nn = 15000;
type rec = record p, v: longint; end;
var s, t, n, i: longint; a: array[1..nn]of rec;
procedure qsort(l, r: longint); var i, j, d: longint; t: rec; begin if l >= r […]
这道题很神奇…好久没做这么神奇的题目了.
首先对于两个数a,b,如果可以解出的话,一定可以用如下方法解决(一定在500步以内):首先定义minP(x)为x除了1以外最小的因数.如果a是奇数,那么a’<-a+minP(a);如果b是奇数,那么b’<-b-minP(b).这样a和b就都成了偶数.然后假设每次存在最大的k使得a’+2^k<b’,那么让a’<-a’+2^k,直到a’=b’为止.这样就找到了一个解(a, a’, a”, a”’, …, b’, b).
挺神奇的…
{ SGU 330; Numbers - sqybi’s code}//for my winstyprogram sgu330_sqybi; var da, db: double; a, b, pa, pb, t, r: int64; i, l: longint; path: array[1..500]of int64;
begin readln(a, b); if a = 2 then begin writeln(’Impossible’); halt; end; da := a; db := b; pa := 0; […]
具体题解看这里: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 […]
很囧的一道题.这道题我刚开始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); […]
这道题其实就是等价于问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 […]
Liked it here?
Why not try sites on the blogroll...