// ** Start of MaximumMatch *******************************
// Name: MaximumMatch by Hungray O(n^3)
// Description: mat is the adjacency matrix, nx,ny are the size of x and y,
// fy is used for marking whether the k-th node is visited, matx[x] means x
// match matx[x], maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays start at 1
int nx,ny,mat[MAXN][MAXN],fy[MAXN],matx[MAXN],maty[MAXN];
int path(int u)
{
int v;
for(v=1;v<=ny;v++)
if((mat[u][v])&&(fy[v]<0)) {
fy[v]=1;
if((maty[v]<0)||(path(maty[v]))) {
matx[u]=v;
maty[v]=u;
return(1);
} // end of if((maty[v]...
} // end of if((mat[u][v]...
return(0);
} // end of int path()
int MaximumMatch()
{
int i,ret=0;
memset(matx,-1,sizeof(matx));
memset(maty,-1,sizeof(maty));
for(i=1;i<=nx;i++)
if(matx[i]<0) {
memset(fy,-1,sizeof(fy));
ret+=path(i);
} // end of if(matx[i]...
return(ret);
} // end of int MaximumMatch()
// ** End of MaximumMatch *********************************
技术手记
KMP
直接抄的武大李春葆老师的数据结构上的改进KMP
// return the first matching string2 in the string1
#include <stdio.h>
#include <string.h>
#define MaxSize 1000
typedef struct
{
char ch[MaxSize];
int len;
} SqString;
void GetNextval(SqString t,int nextval[])
{
int j=0,k=-1;
nextval[0]=-1;
while(j<t.len)
{
if((k==-1)||(t.ch[j]==t.ch[k]))
{
j++;
k++;
if(t.ch[j]!=t.ch[k]) nextval[j]=k;
else nextval[j]=nextval[k];
}
else k=nextval[k];
}
}
int KMP(SqString s,SqString t)
{
int nextval[MaxSize],i=0,j=0,v;
GetNextval(t,nextval);
while((i<s.len)&&(j<t.len))
{
if((j==-1)||(s.ch[i]==t.ch[j]))
{
i++;
j++;
}
else j=nextval[j];
}
if(j>=t.len) v=i-t.len;
else v=-1;
return(v);
}
int main()
{
// freopen("kmp.in","r",stdin);
// freopen("kmp.out","w",stdout);
SqString str1,str2;
gets(str1.ch);
str1.len=strlen(str1.ch);
gets(str2.ch);
str2.len=strlen(str2.ch);
printf("%dn",KMP(str1,str2));
return(0);
}
RMQ
从whummd的blog上copy来的,加了点自己的修改,正在看,集训加油
// StandCode for RMQ, return the smallest number in array s[i..j]
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 1000000
int f2[30];
int s[MAXN];
int r[MAXN][22];
void make_f2(int n)
{
int i;
for(i=0;i<=n;i++)
f2[i]=1<<i;
return;
}
void make_RMQ(int n)
{
int i,j;
for(i=1;i<=n;i++)
r[i][0]=s[i];
for(j=1;j<=log(n)/log(2);j++)
for(i=1;i<=n;i++)
r[i][j]=min(r[i][j-1],r[i+f2[j-1]][j-1]);
return;
}
int RMQ(int i,int j)
{
int k=int(log(j-i+1)/log(2));
return(min(r[i][k],r[j-f2[k]+1][k]));
}
int main()
{
freopen("rmp.in","r",stdin);
freopen("rmp.out","w",stdout);
int n,i,start,end;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&s[i]);
make_f2(20);
make_RMQ(n);
while(scanf("%d%d",&start,&end)!=EOF)
printf("%dn",RMQ(start,end));
return 0;
}
在尝试IE7beta2和WindowsMediaPlayer11
RT.好奇啊…本来不是这么喜欢尝鲜的人的,但是挂在山水上做Software斑竹,好歹也要在其位谋其政吧.最近试用的东西不是太多了,但是比较敏感的东西还是在试,比较有代表性的就是IE7beta2和WindowsMediaPlayer11了吧.
自己已经发的关于这两个东西的意见都在武大珞珈山水BBS的Software上,也上了一些图.有图的Link写一下吧:
http://202.114.68.70/bbscon.php?bid=46&id=13141
http://202.114.68.70/bbscon.php?bid=46&id=13139
http://202.114.68.70/bbscon.php?bid=46&id=13000
http://202.114.68.70/bbscon.php?bid=46&id=12999
下面开始介绍,IE7beta2是微软官方发布的,所有WindowsXP用户均可使用,当然,现在要通过正版验证.我下了后传了一个到C.S.的ftp上,有兴趣的可以去看看.
ftp://cs:cs2006@cs.whu.edu.cn/incoming/IE7B2P-WindowsXP-x86-enu.exe
现在只有英文版的,还好一般软件的英文还是挺简单的,特别是这种常用软件,菜单也都能背下来了.IE7变PP了很多,很有Vista的风格,传统的菜单栏默认是不显示的,从而腾出了更多空间来浏览页面.
IE7默认就是分页浏览(Tabs),对Tab的配置可以进入Option里面调整(就是Internet选项啦),IE7还是加入了不少的新内容需要去适应.我的习惯都是在新的Tab里面打开网页,所以调了一下.不过好像在很多地方反应还是没Maxthon好,还是会去打开一个新的窗口就是一个新的IE而不是一个新的Tab.还有一个不是很爽的地方就是默认都是激活新的Tab页,没找到类似Maxthon那个选项,即打开新Tab后当前激活Tab是目前的还是新的.IE7里面对Tab的控制个人感觉还是不够人性化,经常出现点开一个新的Link然后覆盖了当前查看的内容.Tabs这个新的功能对那些习惯了Maxthon的人很不错,并且在打开非常多的Tab的时候上面不会成为一排密密麻麻的小标签,而是保持了一个最小宽度,左右加入了<>这样的滑动按钮.关闭Tab方面,IE7在有多个Tab的时候会在当前激活Tab的标签右边出现一个X号来关闭,要关闭非激活Tab需要先点激活然后关闭,无法跟Maxthon一样通过双击来实现.在只有一个Tab的情况下,无法关闭此Tab,就是说,没办法保持只有一个空的页面,当然,也可以通过新开一个新空白Tab然后关闭有内容的.存在多个Tab的情况下,IE7加入了一个缩略页的功能,可以同时显示多个小页面,能比较方便找到自己要的页面然后直接点开.
IE7里面加入的Feed是我非常喜欢的功能,虽然RSS这个Web2.0的一个前端概念早就知道也通过其他一些乱七八糟的RSS阅读器了解了一下,不过一直没太去刻意用这个.最近去看了看很多好朋友的Blog,发现如果只是用浏览器一个一个打开太慢了,刚好有Feed这个功能,就整合进去算了.现在没事刷新看看有没更新.然后打开Feed看,风格都比较统一,比较顺眼 :P
关于MS历来是一个诟病的资源占用问题,beta2的IE7解决的还是不好.我一般使用下都是75-90M内存,今天中午居然都截到了占有240M+内存,90%+CPU的图,当然,那个是我在开多个包含Flash,图片并且正在打开过程中截的,平时用Maxthon遇见这种情况也是比较卡.不过现在还好,我的Sempron2400+(1.833G)和512M内存跑起来没卡的感觉.
说完了IE7,我们来讨论WMP11,WMP11发布的消息我是在几天前知道的,然后就有人说5.17正式发布XP版,不过在昨天5Q上开始有泄漏出来的下载,开始没敢下,怕病毒,后来有人用了没问题就用吧.同样的,我也传了一个到C.S.的ftp服务器上:
ftp://cs:cs2006@cs.whu.edu.cn/incoming/mpsetup.exe
中午才下到的,没仔细测试乱七八糟的功能.第一反应是:PP了好多,为了Vista啊…然后是:真PP.
系统资源占有方面,没仔细注意,反正不卡,我上面那个IE截图240+M内存的时候就开了WMP.没去MS的主页看WMP11到底改变了什么,对我有影响的就是界面好看了很多,然后Library也好看了很多,没细看Library的功能变化.在对文件格式的支持上,我一般听的mp3和wma都没问题,不过还是不支持ape/cue,不能不说是一个遗憾.
WMP11还是没有加入官方的新皮肤,就是skin mode里面的,现在大家貌似还都是在用的9里面的那个,其他的个人都觉得不是很PP…
用了半天WMP11,唯一的感觉就是PP了好多,其他,没有了.呵呵,以后有了可以再发吧.
机器今天晚上准备重装,习惯…机器一直都还在裸奔,中毒不浅,QQ还连续被盗了两次,第一次是我去重庆了,结果天天在发垃圾消息,回来后被好友名单里半数拉黑名单了.55~第二次就在昨天吧,不过更多的是怀疑是系统的问题,好友丢失了近50个,奇怪.
西方俗语说:好奇会使猫丧命.希望不要太好奇真的让偶家猫猫挂了.乌鸦嘴:P
读书计划
不能一直只沉迷于同一件事情上,开始好好学点实用的东西.给自己一个计划,让自己好好进步.
HTML语言入门.五一前看完书,做基本的应用,开始接手维护OJ的首页.
离散数学及其应用.花一个学期好好看看吧,计算机科学的灵魂所在.
DreamWeaver.考四级前看完,能基本应用,以后可以考虑自己做东西玩.
Windows编程.用2个星期看完,串讲式的看一遍,了解一下.
有能力去看看asp和jsp吧,以后还想去维护OJ玩呢.
最后,四级.过掉,最好能漂亮的过掉.