Archive for 五月 10th, 2008
Posted on 五月 10th, 2008.
Dijkstra的改进方法.考虑依然能够满足贪心,而且没有负权环,所以只要用dijkstra,在更新的时候加上等待时间就可以.等待时间用waittime子程序判断,注意waittime子程序判断-1的时候要注意,详见WindyWinter牛的题解:http://www.briefdream.com/sgu-103/
剩下没什么了.第一次提交WA,忘了判断无解=.=.第二次提交RE,n的范围是300我开成200了…然后AC…
准确性还算可以…Dijkstra好久没写了…
{ SGU 103; Traffic lights - sqybi’s code - Dijkstra (extended)}//for my winstyprogram sgu103_sqybi; const nn = 300;
var s, t, n, m, i, j, k, min, x, y, z, r: longint; ch: char; a: array[1..nn]of record c: boolean; w, b, p: longint; end; table: array[1..nn, 1..nn]of longint; path, dist: array[1..nn]of longint; flag: array[1..nn]of […]
Read Full Post |
Make a Comment ( None so far )
Posted on 五月 10th, 2008.
一道数学题…做法如下:如果log(2, (a+b)/gcd(a, b))是整数,那么它就是答案;否则无解.
Wind牛的证明如下(有删减):
疾风剑客 01:50:46很简单- -
疾风剑客 01:50:51证明
Killa.sqybi 01:50:50哇
Killa.sqybi 01:50:54赞..我要听
疾风剑客 01:51:11显然2个约完该约的是2个奇数吧
疾风剑客 01:51:32如果2个奇数不相等
疾风剑客 01:51:37运算1次后
疾风剑客 01:51:42是2个偶数吧
疾风剑客 01:51:55然后约掉该约的
疾风剑客 01:52:00应该又是2个奇数吧
Killa.sqybi 01:52:04我明白了..
Killa.sqybi 01:52:08最后约到1 1…
疾风剑客 01:52:17否则就无解
疾风剑客 01:52:30而因为每次都是约2
疾风剑客 01:52:35所以是2^n
疾风剑客 01:52:36over
看不懂就算了…网上某牛(flyfox牛吧…)给出的答案有误…
{ SGU 126; Boxes - sqybi’s code}//for my winsty{$APPTYPE CONSOLE}program sgu126_sqybi; const e = 1e-6;
var a, b, g: longint; t: double;
function gcd(x, y: longint): longint; begin if y = 0 then […]
Read Full Post |
Make a Comment ( 4 so far )
Posted on 五月 10th, 2008.
一道极其经典的欧拉路径问题.做法可以见这里:http://www.briefdream.com/sgu-101/很详细了…
第一次写欧拉路径,写的还是比较恶心(自己瞎写的=.=).本来是1Y的,结果…把No solution写成了Impossible=.=…本不想贴代码的,太恶心了…
{ SGU 101; Domino - sqybi’s code - Eular Path}//for my winstyprogram sgu101_sqybi; const nn = 100; tt = 6;
var n, i, s, st, l: longint; a: array[0..1, 1..nn]of longint; q: array[1..nn]of longint; head, d: array[0..tt]of longint; v: array[1..nn]of boolean; next, adj: array[-nn..nn]of longint;
procedure addEdge(x, y: longint); begin adj[i] := […]
Read Full Post |
Make a Comment ( None so far )
Posted on 五月 10th, 2008.
很经典的DP了.f[i, j]表示前i束花放在前j个花瓶里,其中第i束花必须放在第j个花瓶.转移方程很显然.似乎没有第i束花必须放在第j个花瓶的条件,转移复杂度会低…反正随便写写就可以AC啦…
{ SGU 104; Little shop of flowers - sqybi’s code - DP}//for my winstyprogram sgu104_sqybi; const nn = 100;
var n, m, i, j, p, min: longint; a, d, path: array[1..nn, 1..nn]of longint;
procedure f(x, y: longint); var i: longint; begin if x = y then begin d[x, y] := 0; for […]
Read Full Post |
Make a Comment ( 2 so far )