鸽巢原理与同余

写ural 1032，学到了一点数论知识…

鸽巢原理:
  若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。

同余
  m|(a-b) <=> a≡b (mod m)

program ural_1032;
var i,j,k,m,n,l:longint;
    f,a,sum:array[0..15000]of longint;

begin
     fillchar(f,sizeof(f),$ff);
     readln(n);
     for i:=1 to n do readln(a[i]);
     for i:=1 to n do sum[i]:=sum[i-1]+a[i];
     for i:=0 to n do
     begin
          k:=sum[i] mod n;
          if f[k]=-1 then f[k]:=i
          else begin
                    writeln(i-f[k]);
                    for j:=f[k]+1 to i do writeln(a[j]);
                    halt;
               end;
     end;
     writeln(0);
end.
2010
05/01
分类：
Informatics
TAGS

抢沙发

由经纬求两点的距离

ural1030有一点恶心, 写了半天才把公式推出来

/*以地心为原点建立空间直角坐标系*/
const s=纬度; t=经度; r=6875/2;

x=r*cos(s)*sin(t);
if t in west then x:=x*(-1);

y=r*cos(s)*cos(t);

z=r*sin(s);
if s in south then z:=z*(-1);

d:=sqrt(sqr(x1-x2)+sqr(y1-y2)+sqr(z1-z2));
ans:=arcsin((d/2)/r)*2*r;

//代码有点乱
const r=6875/2;

var i,j,k,m,n,l:longint;
    direction:array[1..2,1..3]of extended;
    ss,t:string;

function get(var s:string):longint;
var k:longint;
begin
     k:=0;
     while (s[1]<'0')or(s[1]>'9') do delete(s,1,1);
     while (s[1]>='0')and(s[1]<='9') do
     begin
          k:=k*10+ord(s[1])-ord('0');
          delete(s,1,1);
     end;
     get:=k;
end;

procedure get_direction(e:longint);
var ok,h,m,s:longint;
    temp:extended;
begin
     h:=get(ss);
     m:=get(ss);
     s:=get(ss);
     direction[e,3]:=r*sin((h+m/60+s/3600)/180*pi);
     temp:=r*cos((h+m/60+s/3600)/180*pi);
     if ss[3]='S' then direction[e,3]:=-1*direction[e,3];
     h:=get(t);
     m:=get(t);
     s:=get(t);
     direction[e,1]:=temp*sin((h+m/60+s/3600)/180*pi);
     direction[e,2]:=temp*cos((h+m/60+s/3600)/180*pi);
     if t[3]='W' then direction[e,1]:=-1*direction[e,1];
end;

procedure solve;
var dis,ans:extended;
begin
     for i:=1 to 4 do readln(ss);
     readln(t);
     get_direction(1);
     for i:=1 to 2 do readln(ss);
     readln(t);
     get_direction(2);
     dis:=0;
     for i:=1 to 3 do dis:=dis+sqr(direction[1,i]-direction[2,i]);
     dis:=sqrt(dis)/2;
     if dis=r then ans:=r*pi
     else ans:=arctan(dis/sqrt(sqr(r)-sqr(dis)))*2*r;
     writeln('The distance to the iceberg: ',ans:1:2,' miles.');
     if round(ans*100)<10000 then writeln('DANGER!');
end;

begin
     solve;
end.
2010
04/30
分类：
Informatics
TAGS


抢沙发

离散化

写几何染色写了这么久，才知道什么是离散化 -_-|||
感觉比较恶心，因为写快排都爆栈，只好删除快排的局部变量

const maxn=5000;
      black=0; white=1;
      maxh=48889;

var i,j,k,m,n,l,t:longint;
    c:char;
    a:array[0..maxn]of record l,r,c:longint; end;
    d:array[0..maxn*2+1]of longint;
    g,f,temp:array[0..maxh]of longint;
    line:array[1..maxn*2+1]of longint;
    ans_a,ans_b,max,now_a,tot:longint;

procedure sort(x,y:longint);
var i:longint;
begin
     t:=random(y-x+1)+x;
     k:=d[t]; d[t]:=d[x]; d[x]:=k;
     i:=x; j:=y; t:=x;
     repeat
           while (i<j)and(d[j]>=k) do dec(j);
           if i<j then begin d[t]:=d[j]; t:=j; end;
           while (i<j)and(k>=d[i]) do inc(i);
           if i<j then begin d[t]:=d[i]; t:=i; end;
     until i=j;
     d[t]:=k;
     if x<i-1 then sort(x,i-1);
     if i+1<y then sort(i+1,y);
end;

function hash(i:longint):longint;
var k:longint;
begin
     k:=i mod maxh;
     while (temp[k]<>-1)and(temp[k]<>i) do k:=(k+1)mod maxh;
     if temp[k]=-1 then
     begin temp[k]:=i; inc(tot); f[k]:=tot; g[tot]:=i; end;
     hash:=k;
end;

begin
     randomize;
     readln(n);
     a[0].l:=0; a[0].r:=round(1e9); a[0].c:=white;
     d[0]:=0; d[1]:=round(1e9);
     for i:=1 to n do
     begin
          readln(a[i].l,a[i].r,c,c);
          if c='w' then a[i].c:=white else a[i].c:=black;
          d[i*2]:=a[i].l; d[i*2+1]:=a[i].r;
     end;
     sort(0,n*2+1);

     fillchar(temp,sizeof(temp),$ff);
     for i:=0 to n*2+1 do hash(d[i]);

     for i:=0 to n do
       for j:=f[hash(a[i].l)] to f[hash(a[i].r)]-1 do line[j]:=a[i].c;

     max:=-maxlongint;
     now_a:=-1;
     for i:=1 to tot-1 do
       if line[i]=white then
       begin
            if now_a=-1 then now_a:=g[i];
            if max<g[i+1]-now_a then
            begin
                 max:=g[i+1]-now_a;
                 ans_a:=now_a;
                 ans_b:=g[i+1];
            end;
       end
       else now_a:=-1;
     writeln(ans_a,' ',ans_b);
end.
2010
04/28
分类：
Informatics
TAGS

抢沙发

准备

    准备，这一个词无时无刻的出现在我们的生活中。我们在为高考而准备，我们在为以后的工作做准备，我们在为以后成家立业而准备，然而没有人会说我们为此刻而准备。也许当我们对未来憧憬时，我们更要记住此时此刻，不是未来成就了我们，是此时成就了我们，是准备成就了我们。

    当我们高考中榜时，当我们站在领奖台上时，我们回忆起就是此时此刻的准备。为什么我们成功时会如此的喜悦，因为我们准备时经历了千辛万苦，就如中国的载人航天工程，一共发射了四艘航天飞船，为的就是为神舟五号升天做准备，然而他们没有白费心，正是有了前面四艘航天飞船，才有现在中国航天事业的功绩，这就是准备的作用。

    就如哲学里所说的一样，万事万物的发展都需要过程，如共产主义的发展需要经历社会主义。冰变成气体先要变成水。人不可能一口吃成以大胖子。这些事物发展都需要准备。有的准备时间长，有的准备时间短。冰放在火中瞬间变成气体，从社会主义变成共产主义却需要上百年的时间。

    准备是如此的重要，如果没有准备，那么一切不复存在，正是由于准备才使得世界如此的缤纷多彩，五彩斑斓。我们要重视未来，跟要重视准备，重视现在。我们要从现在做起，从准备做起，才能做好每一件事，完成好每一件事。

    准备就如事物的基础，如果没有基础，那么一切都是白费，只有做好准备，做基础，摩天大楼才能耸立在万里之空。所以我们要做准备，不要得意忘形，这样才能取得成功，立于不败之地。

    准备无时无刻的存在，我们要重视准备，不要轻视现在，每一步都很重要，做好每一步，让胜利为准备而出现。

2010
04/23
分类：
Studies
TAGS


抢沙发

Tarjan

//Strongly Connected Component

const maxn=1000;

type node=^nd;
     nd=record nam,val:longint; next:node; end;

var i,j,k,m,n,l:longint;
    a:array[1..maxn]of node;
    belong,ins,s,dfn,low:array[1..maxn]of longint;
    v:array[1..maxn]of boolean;
    head,now,temp:longint;

procedure dfs(i:longint);
var p:node;
begin
     inc(now); dfn[i]:=now; low[i]:=now;
     inc(head); s[head]:=i; v[i]:=true; p:=a[i];
     while p<>nil do
     begin
          if dfn[p^.nam]=0 then
          begin dfs(p^.nam); if low[p^.nam]<low[i] then low[i]:=low[p^.nam]; end
          else if v[p^.nam] and(dfn[p^.nam]<low[i]) then low[i]:=dfn[p^.nam];
          p:=p^.next;
     end;
     if low[i]=dfn[i] then
     begin
          inc(temp);
          repeat
                k:=s[head]; belong[k]:=temp; v[k]:=false; dec(head);
          until k=i;
     end;
end;

begin
     for i:=1 to n do if dfn[i]=0 then dfs(i);
end.
2010
04/22
分类：
Informatics
TAGS


抢沙发

Photos

www.flickr.com
Copyright © 2007 ihost.tw All rights reserved. Tech Support: coz.tw