未分类
Posted on 六月 10th, 2008.
枚举一个素因子i,再判断n div i是不是素数就可以.数据太水了,我刚开始的程序有bug,枚举的不是素因子而是任意因子…我shaz…把自己的算法给忘了…刚才看了一下,枚举到的第一个因子一定是素因子(除了1最小的因子啊…),而只对这一个因子进行判断就可以…不用筛法,朴素判素就能AC.
{ SGU 113; Nearly prime numbers - sqybi’s code}//for my winstyprogram sgu113_sqybi; var f: boolean; i, times, cases, n: longint;
function prime(x: longint): boolean; var i: longint; begin prime := false; for i:=2 to trunc(sqrt(x)) do if x mod i = 0 then exit; prime := true; end;
begin readln(cases); for […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 21st, 2008.
这道题的解法的确很强大啊,大概意思就是把每个数分为二进制位,然后每一位的xor都不互相影响而且每一位只有0和1两种状态.然后可以求最小割来解题.具体解法见Amber在2007年的论文,请点开页面下载.这道题在论文的第13页,这里不再赘述.
做题时不知怎么心血来潮把31写成30,于是WA了几次(开始还因为数组开小TLE了几次,怎么SPOJ不报RE…).还有就是给出的点的权值有可能是0,所以不能通过判断v1数组来判断某个点是不是给出的(这也是我的flag数组的作用).这道题排在Pascal第11.
SPOJ已经2.8分了,1295名…
{SPOJ 839; Optimal Marks; OPTM- sqybi’s code- 按照二进制位建图,最小切割最大流- Dinic}program optm_sqybi; const nn = 500; mm = 3000; tt = nn + mm * 2;
type TGraph = object edgeNum, s, t: longint; adj, next, capa, flow: array[-tt..tt]of longint; visit: array[0..nn+1]of boolean; head, place, dist: array[0..nn+1]of longint; q: array[1..nn+2]of longint; procedure addEdge(x, y, z: longint); […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 21st, 2008.
同上题,无代码无题解.SGU水题怎么这么多…
to raulliubo:这道题本来不想做的,不过你的程序实在是太xx了…
阅读(96 次)
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 6th, 2008.
有史以来做的第一道网络流的题目…用了Dinic,果然好写.原来HopCroft就是简化版的Dinic,有了以前HopCroft的经验,Dinic写起来也就方便的多了.
这道题是裸的网络流,1号节点是源,n号是汇,只要流一下就可以了.
1Y掉,Dinic果然很猛.
附代码,以后Dinic用这个代码套~
{ Drainage Ditches; poj 1273 - sqybi’s code - 最大流 - Dinic}//for my winstyprogram pku1273_sqybi; const nn = 200; mm = 200;
type arr = array[1..nn]of longint;
var n, m, i, x, y, z, s, t, r: longint; head, place, dist: arr; adj, next, f, c: array[-mm..mm]of longint;
function bfs: boolean; var […]
Read Full Post |
Make a Comment ( None so far )