一劍淩雲御風行

7.4-7.8,GDOI2008

Leewings — Thu, 03 Jul 2008 19:52:21 +0800

明天去珠海了..!!呼呼.~
for GDOI2008..

P.S.:昨天要交政治作业….没交.今天刘总(政治老师)问限令我明天下午前交….
课后,跟他说明天要去比赛一个星期,
刘总say:噢噢,好好比赛吧,这个没事,特殊情况,没事的.

KO.
刘总真棒~!!
爽~^^

GDOI2008,
目标:前30.冲击!!

标签：FLY, GDOI, OI

EVA QQ 字体完美设置

Leewings — Wed, 02 Jul 2008 10:37:23 +0800

好久没写关于ubuntu的文章了….
EVA字体设置,以前说过,不过,方法不是很完美..仅能修改一部分的字体..
在逛鲜果的时候,在 OwnLinux.cn上看到这篇文章,很强大,故转之.
以下内容皆转载,其中的”我”指原作者….

EVA 是目前LINUX中功能最强大的聊QQ的工具了。笔者的系统是Ubuntu 8.04 Gnome界面，用上Linux才半年，在网上找了很多篇改EVAQQ字体的文章，都没有一篇能够全面都修改字体，一般都只能修改部分字体，于是自己去摸索一下吧～呵呵，结果花了几个小时终于给我找到我认为比较完美的设置。如果你觉得好，欢迎你给我鲜花或顶帖，你的支持是我最大的回报，不喜欢的话请留意见给我，我会尽力去修改。废话不说，先上图吧～

配置方法:
gedit ~/.kde/share/config/kdeglobals

[$Version]

update_info=kded.upd:kde3.0

[General]

StandardFont=tahoma,11,-1,5,50,0,0,0,0,0

XftHintStyle=hintfull

activeFont=tahoma,11,-1,5,75,0,0,0,0,0

fixed=DejaVu Sans Mono,9,-1,5,50,0,0,0,0,0

font=微软雅黑,9,-1,5,50,0,0,0,0,0

menuFont=微软雅黑,9,-1,5,50,0,0,0,0,0

taskbarFont=微软雅黑,9,-1,5,50,0,0,0,0,0

toolBarFont=微软雅黑,9,-1,5,50,0,0,0,0,0

[KFileDialog Settings]

Automatically select filename extension=true

Height 1024=288

LocationCombo Completionmode=5

PathCombo Completionmode=5

Recent URLs[$e]=$HOME/.eva/187205/customCaches/,$HOME/图片/

Separate Directories=false

Show Bookmarks=false

Show Preview=false

Show Speedbar=true

Show hidden files=false

Sort by=Name

Sort case insensitively=true

Sort directories first=true

Sort reversed=false

View Style=Simple

Width 1280=634

[Paths]

Trash[$e]=$HOME/桌面/Trash/

[WM]

activeFont=微软雅黑,9,-1,5,50,0,0,0,0,0

这是本人自己摸索出来的设置，欢迎转载，但转载时请注明作者，谢谢！

作者：Jason@月影

标签：EVA, IM, linux, QQ, 贴图

Pirates Of Silicon Valley

Leewings — Sun, 29 Jun 2008 17:59:18 +0800

中文名:硅谷海盗.
故事说的是Apple和Microsoft的起步和恩怨,一群年轻人的奋斗史….
记得有译为<微软英雄>的..看了之后,觉得,是个错误的翻译吧.
这部片是以Jobs为主轴的,英雄是Jobs…而Gates..第二主角吧,看似是奸雄..
片中有句他们两人都奉承的话,很强大:

优秀的艺术家复制别人的作品,伟大的艺术家偷窃别人的作品.

不过,有趣的是,Jobs认为是毕加索说的,而Gates认为是凡高说的….呵呵.
很喜欢他们那个时代,奋斗的时代.
未来的一年半,属于我的时代已经来临!

给自己定下了一个空前宏大的目标,为期1年半.!我要拼尽所有! 2008-06-28 22:29

证明.. 2008-06-29 10:52

标签：Apple, FLY, IT, Microsoft, 影音, 贴图

姐姐·高考

Leewings — Fri, 27 Jun 2008 19:10:50 +0800

广东文科重本线570.

姐姐568.

不甘.

不喜欢高考.

标签：FLY, 姐姐, 高考

KVM有可视化软件啦—-oVirt

Leewings — Sat, 21 Jun 2008 11:15:28 +0800

刚搜到的消息:KVM有可视化软件啦!!
Red Hat 在本周发布了一个新的虚拟化平台──oVirt!基于KVM的哦^^
来看下界面先~

挺好看的吧..嘿嘿.
来看下官网对其的介绍吧:

oVirt is:

A small host image that provides libvirt and hosts virtual machines

A Web-based virtual machine management console

oVirt goals:

Empower virtual machine owners without giving up control of hardware

Automate virtual machine clustering, load balancing, and SLA maintenance

Simplify management of large numbers of machines

Work across platforms and architectures

oVirt uses:

A kerberos/LDAP server for authentication and authorization (oVirt ships with FreeIPA)

DNS/DHCP services on the local LAN — or provides them for oVirt hosts over a private network if desired

libvirt for virtual machine management, storage management, and secure remote communication

collectd for stats gathering and monitoring

Rails for rapid, flexible development

目前的版本是oVirt 0.91-1 beta ,可以在这里下载~~

标签：KVM, linux, 虚拟机, 贴图

WAITing but GOing On

Leewings — Thu, 19 Jun 2008 08:11:26 +0800

一份心事的湮灭,如释重负.

一个心愿的默诺,动力无穷.

6.17

标签：Cherry, FLY, OI

《购物问题》解题报告

Leewings — Tue, 17 Jun 2008 09:49:16 +0800

题目描述

GDOI商场(这题是弄GDOI的人出的….)…….(忽略故事性描述.~)

有一堆商品,每种都能省到一定的钱,但每种只能买一件,而且有些是不能同时买的.不能同时买的商品中,不会出现一个环(即类似于”C1与C2不能同时买,C2与C3不能同时买,C3与C1不能同时买”这样的情况是不会出现的).

编程求能节省的最大金额数.

这回稍微说明下输入:

输入中,第一行K(商品种数),M(不能同时买的对数).
接下来K行,第i行有一个整数表示购买编号i的商品可以节省的金额;再接下来M行,每行两个数,表示这两件商品不能同时购买.

题目分析

图啊图啊图….对于图知识约等于0的我来说..分析这题花了很多时间…..

据说,这题的关键是构造一个结点带权的图,结点表示商品,结点的权就是购买该商品能节省的$$,边表示边所连的两个点的商品不能同时购买.这就相当于在这幅图中找出一系列的没有边相连的点,且权值之和最大~~
由于题目的最后一个条件,这张图里面是没有环滴..也就是,是树林吖….我们的目的就是算出每棵树的最大节省金额,然后求和.

这题DP起来,状态方程倒不难得出,一颗颗树来做啦,请看~~

F[i]表示选择这个结点的最优值;G[i]表示不选择这个结点的最优值;S[i]表示这个结点原来的权值.

对于叶子来说,F[i]=S[i],G[i]=0;

对于非叶子,

F[i]=∑G[j] +S[i]

G[i]=∑max(F[j],G[j])

其中,j是i儿子~

r为根,该树的结果就是max(F[r],G[r])啦^^

问题是….菜鸟的我不知道怎么构建树….看了例程,是C++写的,而且用了指针….好吧,看不懂.没办法…..还是硬着头皮自己想怎么去构建吧.

想啊想,想啊想,想到啦!!
想到建立一个二维数组T[i,j,k],i表示层数,j表示这一层的老爸,k肯定就是这个老爸的儿子们啦.按照宽度优先的规则将结点存进去就是了….
不过,在实际编程的时候,运用了深搜来建造这颗树,结合上面说的思路,发现从最低层开始,访问每个结点,顺便计算….这样,就不用记录下这颗树了,也就不用开数组来存它啦^^
这个可能是最笨的方法吧?….

源代码

program shopping;
type style=record //突然发现,记录类型太好用了…
             F,G,S:longint; //F:选择该结点的最优值;G:不选择该结点的最优值;S:该结点原来的权值.
             son:array[0..1000] of longint; //该结点的儿子们~
             used:boolean; //该结点是否被访问过
           end;
 
var thing:array[1..1000] of style; //商品
    k,m,i,temp,a,b,ans:longint; 
 
function max(a,b:longint):longint;
begin
  if a>b then max:=a else max:=b;
end;
 
procedure get(l,f:longint); //建造树,并顺便算最优值
var i:longint;
begin
  if thing[f].used or (thing[f].son[0]=0) then begin //如果该结点已被访问过或他没有儿子
    thing[f].F:=thing[f].S;
    thing[f].used:=true;
    exit;
  end;
  thing[f].used:=true;
  for i:=1 to thing[f].son[0] do get(l+1,thing[f].son[i]); //对每个儿子构造一次
  thing[f].F:=thing[f].S;
  for i:=1 to thing[f].son[0] do begin //顺便计算每个结点的最优值
    thing[f].F:=thing[f].F+thing[thing[f].son[i]].G; //F[i]=∑G[j] +S[i]
    thing[f].G:=thing[f].G+max(thing[thing[f].son[i]].F,thing[thing[f].son[i]].G); //G[i]=∑max(F[j],G[j])
  end;
end;
 
begin
  assign(input,'shopping.in');assign(output,'shopping.out');
  reset(input);rewrite(output);
  readln(k,m);
  fillchar(thing,sizeof(thing),0);
  for i:=1 to k do begin
    fillchar(thing[i].son,sizeof(thing[i].son),0);
    readln(thing[i].S);
  end;
  for i:=1 to m do begin //帮老爸找到儿子
    readln(a,b);
    if a>b then begin //为避免重复,不能同时购买的商品中,编号小的是老爸
      temp:=a;a:=b;b:=temp;
    end;
    inc(thing[a].son[0]);
    thing[a].son[thing[a].son[0]]:=b;
  end;
 
  ans:=0;
  for i:=1 to k do //枚举每棵树
    if thing[i].used=false then begin
      get(1,i); //造树+计算最优值..
      ans:=ans+max(thing[i].F,thing[i].G); //累加最优值
    end;
 
  writeln(ans);
  close(input);close(output);
end.

标签：GDOI, OI, pascal, programmer, 代码, 解题报告

《分组游戏》解题报告

Leewings — Sun, 15 Jun 2008 15:56:31 +0800

题目描述

有一群人,他们之中任意两个人的关系是认识或不认识(当然,也可能出现A认识B而B不认识A的情况),现在需要你按照一定的规则将他们分成两组,分组的规则如下:

每个人属于其中的一组;

每组至少有一个人;

同一组种任何一个人都认识该组中的其他人;

两组的人数要尽可能的接近

这个任务可能有多个解,你只需要输出其中任意一个或者输出无解信息.

题目分析

这题例程是用DP+集合的方法的,写了瞒长的….

我是用什么方法我自己都不知道….只是,这个思路MS很棒(自恋下..).当然,基本思想还是有滴,是集合啦.

读完数据,也就是每个人的关系后,创建两个集合A、B(不是真的集合类型,是两个数组….).A[0](B[0])记录集合元素的个数.
然后把第一个人仍进集合A.
接着按照以下规则依次把人扔进集合中:
- 若此人与A中任何一个人都认识,仍进A中;
- 否则,若此人与B中任何一个人都认识,仍进B中;
- 否则,输出无解,结束程序.

这样就保证了两个集合中人员编号的有序(输出要求..),同时也可以及时判断无解.这样有一个问题,就是无法满足条件4:两组的人数要尽可能的接近.

这个问题嘛,也不难.使A为人数多的集合,B为人数少的.每次从A中抽出B中任何一个人都认识的人插入到B中知道两个集合人数相等或不能再A中不能再向B插入任何人.

KO.

源代码

program group;
const mp{maxpeople}=1000;
var g1,g2,tg:array[0..mp] of integer;
//g1=集合A,g2=集合B,处理条件4时的中间变量
    re{relation}:array[1..mp,1..mp] of boolean;
    n,i,j,k,temp:integer;
    check,swap:boolean;
 
begin
  assign(input,'group.in');assign(output,'group.out');
  reset(input);rewrite(output);
  readln(n);
  if n=2 then begin
  //如果是2个人….想都别想,理他3721,答案肯定是这样的..
    writeln('1 1');
    writeln('1 2');
    close(input);close(output);
    halt;
  end;
  fillchar(re,sizeof(re),false);
  for i:=1 to n do begin
    read(j);
    while j<>0 do begin
      re[i,j]:=true;
      read(j);
    end;
    readln;
  end;
  fillchar(g1,sizeof(g1),0);
  g2:=g1;
  g1[0]:=1;g1[1]:=1; //将第一个人仍进集合A
 
  for i:=2 to n do begin //依次将人扔进集合中
    check:=true;
    for j:=1 to g1[0] do
      if (re[i,g1[j]]=false) or (re[g1[j],i]=false) then begin
      //如果和A中某个人不认识
        check:=false;
        break;
      end;
    if check then begin
    //如果和A中任何一个人都认识,扔进集合A中
      inc(g1[0]);
      g1[g1[0]]:=i;
    end
    else begin
    //否则,判断下是否和B中的任何一个人都人之
      for j:=1 to g2[0] do
        if (re[i,g2[j]]=false) or (re[g2[j],i]=false) then begin
        //惨了….和B中的某个人不认识.好吧,此题无解
          writeln('No solution');
          close(input);close(output);
          halt;
        end;
      //都认识噢?扔进集合B中..
      inc(g2[0]);
      g2[g2[0]]:=i;
    end;
  end;
 
  if g1[0]<g2[0] then begin
  //使A为人数多的集合,B为人数少的
    tg:=g1;g1:=g2;g2:=tg;
  end;
  if g1[0]=g2[0] then swap:=false else swap:=true;
  //如果两个集合人数相等,就不用再处理什么啦啦..
 
  while (g1[0]>g2[0]) and swap do begin
  //处理条件4
    temp:=g1[0];
  for i:=1 to g1[0] do begin
  //枚举A中的每个元素
      check:=true;
      for j:=1 to g2[0] do
        if (re[g1[i],g2[j]]=false) or (re[g2[j],g1[i]]=false) then begin
        //如果和B中某个人不认识,那就不能把他T出去了
          check:=false;
          break;
        end;
        if check then begin
        //如何条件,他被无情的T过去了
          for j:=1 to g2[0] do
            if g1[i]<g2[j] then begin
            //保证有序,把他插进去..
              for k:=j to g2[0] do g2[k+1]:=g2[k];
              g2[j]:=g1[i];
              inc(g2[0]);
              break;
            end;
          for k:=i to g1[0] do g1[k]:=g1[k+1];
          g1[k]:=0;
          dec(g1[0]);
          break;
        end;
      end;
    if g1[0]=temp then swap:=false;
    //说明集合A中没有任何人给T出去了,也就是不用再T人了…
  end;
 
  for i:=0 to g1[0]-1 do write(g1[i],' ');
  writeln(g1[g1[0]]);
  for j:=0 to g2[0]-1 do write(g2[j],' ');
  writeln(g2[g2[0]]);;
  close(input);close(output);
end.

标签：GDOI, OI, pascal, programmer, 代码, 解题报告

《可怜的绵羊问题》解题报告

Leewings — Sun, 15 Jun 2008 09:49:31 +0800

题目描述

忽略无聊的故事性描述….直接写上这个问题的本质吧。实质上，这道题是这样的：

按逆时针顺序给出n个点（类型A）的坐标，这些点顺次相连成一个凸多边形（该多边形只是形状是凸的，即某些点可能落在多边形边上）。还给出一些点（类型B）的坐标，这些点可能在平面任何一个地方，当然，不与类型A的点重合。

你的任务是选出一些类型A的点围成一个新的凸多边形，并使它不包含类型B的点（类型B的点可以在边上）且面积尽可能的大。如果无法找到这样的多边形，则输出”die”;否则输出最大面积（保留两位小数）。

题目分析

进一步浓缩题目可得出，本题的实质是在凸多边形内求一面积最大的新的凸多边形，且该多边形内无点。

如果以点u为起点，可以找到一个最大凸n边形VuV1V2…Vn，这个多边形以点n为尾且n与u相连；则凸n＋1边形也必是以u为起点，n＋1为尾的最大凸多边形。由此可见，此题满足最优化原理，可用动态规划解决。

如何划分状态呢？
我是将多边形划分成三角形的，从3个点开始，每次加一个点，即加一个三角形，原图形的面积加上新加三角形的面积即为此次的状态。

综上便可得出状态转移方程：
ms[u,j]=max{ms[u,i]+s(u,i,j)}(0
此方程中，u是枚举起点，i、j是往后的2个点(这两点不一定是连续的,因为某些点是不会成为新凸多边形的顶点的,要枚举忽略掉).

但是,这样还不算完成.还有一个条件,新凸多边形中不包含类型B的点.这条的实现要有数学的基础了(好吧,我承认,我是G出来的公式…)….
首先,用下面这条公式来计算三角形的面积(其实我也不知道是怎么得到的..):
公式一:
s=abs((x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)/2)

用下面这条公式来判断点是否在直线上,成立则在.(高中数学必修一的内容了.~)
公式二:(x1-x)*(y2-y)=(x2-x)*(y1-y)
判断点是否在三角形内的方法:
计算每条边和这个点组成的三个三角形的面积之和,若等于原三角形面积,则点在三角形上(用公式二排除掉)或三角形内;不等于则说明点在三角形外.
这样一来,就不难得出,最后的状态转移方程是这样的:
ms[u,j]=max{
s(u,i,j) //边上有类型B的点
ms[i]+s(u,i,j) //边上无类型B的点
}
其中, 0 < u <= n, u < i < j < n+u-1,三角形VuViVj内无类型B的点.

说得不清楚?或许….你可以直接读源代码….

源代码

program sheep;
type map=record //记录点坐标的记录类型
     x,y:longint;
   end;
 
var p:array[1..300] of map;
 //前100个为类型A的点;为了枚举起点需要,中间100个同前100个一摸一样;后100个为类型B的点
   n,m,i,j,u:longint;
   ms:array[0..100,0..200] of real; //保存状态
   ts:real;
 
function gets(a,b,c:longint):real;
//计算三角形面积
begin
gets:=abs((p[a].x*p[b].y+p[b].x*p[c].y+p[c].x*p[a].y-p[a].x*p[c].y-p[b].x*p[a].y-p[c].x*p[b].y)/2);
end;
 
function checkside(a,b:longint):boolean; 
//检查边上是否有类型B的点,有则返回true;
var d:longint;
begin
  checkside:=false;
  for d:=201 to m+200 do
    if (p[a].x-p[d].x)*(p[b].y-p[d].y)=(p[b].x-p[d].x)*(p[a].y-p[d].y) then begin
      checkside:=true;
      break;
    end;
end;
 
function cside(a,b,d:longint):boolean;
//为方便在检查三角形边上是否有点而在上一个函数的基础上增加一个参数
begin
  cside:=false;
  if (p[a].x-p[d].x)*(p[b].y-p[d].y)=(p[b].x-p[d].x)*(p[a].y-p[d].y) then 
    cside:=true;
end;
 
function checkin(a,b,c:longint):boolean;
//检查三角形内是否有点,有则返回true
var d:longint;
begin
  checkin:=false;
  for d:=201 to m+200 do
    if (gets(a,b,c)=gets(a,b,d)+gets(a,c,d)+gets(b,c,d)) and (cside(a,b,d)=false) then begin
      checkin:=true;
      break;
    end;
end;
 
function max(a,b:real):real;
begin
  if a>b then max:=a else max:=b;
end;
 
begin
  assign(input,'sheep.in');
  assign(output,'sheep.out');
  reset(input);rewrite(output);
  readln(n);
  for i:=1 to n do begin
    readln(p[i].x,p[i].y);
    p[i+n].x:=p[i].x;p[i+n].y:=p[i].y;
  end;
  readln(m);
  for i:=1 to m do
    readln(p[i+200].x,p[i+200].y);
  fillchar(ms,sizeof(ms),0);
 
  for u:=1 to n do
  //枚举起点
    for i:=u+1 to n+u-1 do
    //枚举起点以后的另一个点
      for j:=i+1 to n+u-1 do
      //枚举新增的点
        if checkin(u,i,j)=false then begin
        //如果三角形内无点,则可加入此三角形到多边形中
          ts:=gets(u,i,j);
          if checkside(u,j) then ms[u,j]:=max(ms[u,j],ts)
          else ms[u,j]:=max(ms[u,j],ms[u,i]+ts);
        end;
 
  ts:=0;
  for u:=1 to n do 
  //寻找枚举顶点得到的面积最大的多边形
    if ms[u,n+u-1]>ts then ts:=ms[u,n+u-1];
  if ts=0 then writeln('die') else writeln(ts:0:2);
  close(input);close(output);
end.

标签：GDOI, OI, pascal, programmer, 代码, 解题报告

一劍淩雲御風行

7.4-7.8,GDOI2008

相关日志

EVA QQ 字体完美设置

相关日志

Pirates Of Silicon Valley

相关日志

姐姐·高考

相关日志

KVM有可视化软件啦—-oVirt

oVirt is:

oVirt goals:

oVirt uses:

相关日志

WAITing but GOing On

相关日志

《购物问题》解题报告

题目描述

题目分析

源代码

相关日志

《分组游戏》解题报告

题目描述

题目分析

源代码

相关日志

《可怜的绵羊问题》解题报告

题目描述

题目分析

源代码

相关日志