Tue, 24 Jun 2008 13:36:29 GMTThis is not only a blog.http://sqybi.72pines.comenTue, 24 Jun 2008 13:36:29 GMT2008-06-24T13:36:29Zenhttp://item.feedsky.com/~feedsky/notablog/~6950155/87253217/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/86/feed求逆序对个数,很经典了.可以归并排序求,可我不喜欢归并,所以我的做法是离散化之后用树状数组维护一下.复杂度一样,离散化也不是很难写,树状数组也巨简单.强烈推荐. 这题极其bt的是,答案是int64的…用longint存答案就WA on 14(还是12?)… { SGU 180; Inversions - sqybi’s code - 逆序对}//for my winstyprogram sgu180_sqybi;  const    nn = 65537;   type    rec = record      v, p: longint;    end;   var    n, i, t, r: longint;    s: int64;    a: array[1..nn]of rec;    b, c: array[1..nn]of longint;   procedure qsort(l, r: longint);    var      i, j, d: longint;      t: rec;    [...]归并排序SGU树状数组逆序对Tue, 24 Jun 2008 21:36:29 +0800sqybihttp://sqybi.72pines.com/posts/86#commentshttp://sqybi.72pines.com/posts/86sqybihttp://sqybi.72pines.com/posts/86http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253217/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253218/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/84/feed给出n个数,判断它们的m次方能不能被k整除.对每个数和k分解质因数即可(注意对于每个数只需要分解k的因子). { SGU 117; Counting - sqybi’s code}//for my winstyprogram sgu117_sqybi;  const    nn = 10000;   var    i, j, k, kk, l, n, m, s, t: longint;    a, b, p: array[1..nn]of longint;    f: boolean;   begin    readln(n, m, k);    kk := k;    l := 0;    for i:=2 to kk do begin      if k = 1 then [...]SGUTue, 10 Jun 2008 13:30:47 +0800sqybihttp://sqybi.72pines.com/posts/84#commentshttp://sqybi.72pines.com/posts/84sqybihttp://sqybi.72pines.com/posts/84http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253218/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253219/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/83/feed枚举一个素因子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 [...]素数SGU未分类Tue, 10 Jun 2008 13:25:25 +0800sqybihttp://sqybi.72pines.com/posts/83#commentshttp://sqybi.72pines.com/posts/83sqybihttp://sqybi.72pines.com/posts/83http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253219/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253220/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/82/feed可以发现,一个数平方的最后9位只和这个数的最后9位有关.对1~9位数随便写个小程序枚举一下,就可发现:对于1位数到8位数,没有任何符合条件;对于9位数,有8个数符合条件;对于n位数(n>9),最高位有9种(1~9),后9位有8种,剩余n-10位每位10种(0~9),总共72*10^(n-10)种. {SGU 107; 987654321 Problem- sqybi’s code}//for my winstyprogram sgu107_sqybi;  var    i, n: longint;   begin    readln(n);    if n <= 8 then      writeln(0)    else if n = 9 then      writeln(8)    else begin      write(72);      for i:=1 to n-10 do write(0);    end;  end. 阅读(21 次)SGUTue, 10 Jun 2008 13:17:48 +0800sqybihttp://sqybi.72pines.com/posts/82#commentshttp://sqybi.72pines.com/posts/82sqybihttp://sqybi.72pines.com/posts/82http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253220/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253221/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/81/feed找到最靠后的一个满足它左边的’('比’)'数量多的’(',改成’)',然后在后面补(…()…)和)…).好久以前就写过的题.刚才写错了一点,在最后填括号的时候先填(…()…),再填)…). { SGU 179; Brackets light - sqybi’s code}//for my winstyprogram sgu179_sqybi;  var    i, l, r, tr, t: longint;    s: ansistring;   begin    readln(s);    l := length(s);    t := 0;    r := 0;    for i:=1 to l do begin      if (t > 0) and (s[i] = ‘(’) then begin        tr := t;        r := i;      end;      [...]SGUSun, 08 Jun 2008 21:28:16 +0800sqybihttp://sqybi.72pines.com/posts/81#commentshttp://sqybi.72pines.com/posts/81sqybihttp://sqybi.72pines.com/posts/81http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253221/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253222/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/80/feed这道题WindyWinter牛给出的算法是并查集,实际上可以DFS解决(感谢alft…). 每个人选的两个课程之间连无向边,然后DFS时进行黑白染色,DFS树上每个结点和他的父亲节点不同色.然后考虑横向边和返祖边,如果有一条边两边的结点颜色相同则说明无解,否则将白色的考试放在一天,黑色的放在另一天就可以了…并查集当然也没错… 注意会是一个森林,需要多次DFS… { SGU 172; eXam - sqybi’s code - DFS}//for my winstyprogram sgu172_sqybi;  const    nn = 200;    mm = 30000;   var    n, m, tot, i, x, y, t: longint;    flag: boolean;    head, p: array[1..nn]of longint;    adj, next: array[-mm..mm]of longint;   procedure addEdge(x, y: longint);    begin      inc(tot);      adj[tot] := y;      next[tot] := head[x];      head[x] := tot;      [...]DFS并查集SGUTue, 27 May 2008 21:09:39 +0800sqybihttp://sqybi.72pines.com/posts/80#commentshttp://sqybi.72pines.com/posts/80sqybihttp://sqybi.72pines.com/posts/80http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253222/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253223/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/79/feed其实真的不难…自己找一下规律吧.因为有mod m嘛…然后就几个一循环而已… { SGU 181; X-Sequence - sqybi’s code}//for my winstyprogram sgu181_sqybi;  const    mm = 1000;   var    n, i: longint;    x, a, b, c, m, stop, r: int64;    f, t: array[0..mm]of longint;   begin    readln(x, a, b, c, m, n);    if n = 0 then begin      writeln(x);      halt;    end;    fillchar(f, sizeof(f), 0);    stop := 0;    [...]SGUSun, 25 May 2008 23:17:25 +0800sqybihttp://sqybi.72pines.com/posts/79#commentshttp://sqybi.72pines.com/posts/79sqybihttp://sqybi.72pines.com/posts/79http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253223/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253224/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/78/feedbt的数学题.题解看这里:http://www.mydrs.org/dvp/dispbbs.php?boardid=13&id=436842楼说的还算比较详细…我刚开始把题目里P的定义的乘法看成了加法所以一直不懂2楼说的,后来看题之后才发现自己看错了… { SGU 169; Numbers - sqybi’s code - Maths}//for my winstyprogram sgu169_sqybi;  var    n, t: longint;   begin    readln(n);    if n = 1 then      writeln(8)    else begin      t := 1;      if (n - 1) mod 3 = 0 then t := t + 2;      if (n - 1) mod 6 = 0 then t := [...]SGU数学Sun, 25 May 2008 19:24:28 +0800sqybihttp://sqybi.72pines.com/posts/78#commentshttp://sqybi.72pines.com/posts/78sqybihttp://sqybi.72pines.com/posts/78http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253224/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253225/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/77/feed稍微推导一下就可以得到一个递推式(这里直接借用WindyWinter的式子):pos[1,1]=1pos[n,q]=n-k+pos[k,k-q+1] (q<=k)             =pos[n-k,n-q+1] (q>k) 求pos[n, q]即可. { SGU 175; Encoding - sqybi’s code}//for my winstyprogram sgu175_sqybi;  var    n, t, q, k: longint;   begin    readln(n, q);    t := 0;    while n <> 1 do begin      k := n div 2;      if q <= k then begin        t := t + n - k;        n := k;        q [...]SGU递推Sun, 25 May 2008 19:09:57 +0800sqybihttp://sqybi.72pines.com/posts/77#commentshttp://sqybi.72pines.com/posts/77sqybihttp://sqybi.72pines.com/posts/77http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253225/5058046http://item.feedsky.com/~feedsky/notablog/~6950155/87253226/5058046/1/item.htmlhttp://sqybi.72pines.com/posts/76/feed只说一句:图像法解决概率问题真好用.公式见程序. { SGU 144; Meeting - sqybi’s code - Maths}//for my winstyprogram sgu144_sqybi;  var    x, y, z: double;   begin    readln(x, y, z);    writeln((1-sqr((y-x)*60-z)/sqr((y-x)*60)):0:7);  end. 阅读(45 次)SGU数学Sun, 25 May 2008 18:53:48 +0800sqybihttp://sqybi.72pines.com/posts/76#commentshttp://sqybi.72pines.com/posts/76sqybihttp://sqybi.72pines.com/posts/76http://sqybi.72pines.com/feedfeedsky/notablog/~6950155/87253226/5058046