编号.题目 来源 简单说明 D3A.Bishops not found 简单公式题 D3B.Football Coach not found 最大流 D3C.CLRS not found DFS或者强联通分量 D3D.Sequence Again POJ2478 筛素数法求欧拉函数 D3E.Intervals not found 线段树 D3F.Matrix not found 矩阵构造+矩阵乘法 D4A.area not found DP+凸包 D4B.Prime not found 求素数距离,筛法求素数到3*10^7 D4C.Traveling Queen Problem POJ2919 BFS+集合DP,BT题,我看标程都头大 D4D.Squares not found BFS+Hash打表或双向BFS D4E.Candies not found 贪心带硬搞 D4F.Card Game POJ2062 最大匹配或者贪心 p.s.来源标注为not found均为目前还未找到来源的题,其中部分为KO原创,部分为 只改描叙的陈题
VIM中文文档
VIM的中文手册,好东西,记录一下
Try a small tool from M$
As the title, I used a small tool download from Microsoft called Windows Live Writer, a beautiful tool, I’m trying it now.
You can download it from this url: 点击下载
个人赛,前两天
发信人: snoopy (Snoopy@T13), 信区: ACM_ICPC 标 题: 个人赛前两天题目来源 发信站: 珞珈山水BBS站 (Sat Aug 12 10:05:22 2006), 转信 非官方版本,今天早上找了一个小时找全了的 第二天的G据KO说是原创,但是和Tongji的1004防御导弹是一样的 编号.题目 来源 简单说明 D1A.dna POJ1080 DP D1B.Game POJ1143 集合DP+博弈? D1C.spell POJ1035 直接硬搞 D1D.Frames POJ1128 模拟? D1E.Cable POJ1064 转换成整数二分 D1F.2046 POJ1733 并查集+Hash D1G.Transmitters POJ1106 简单计算几何,算叉乘 D2A.Excel-lent POJ2273 模拟,类进制转换 D2B.Dice POJ1481 简单双重DFS D2C.Rocket Height POJ2276 初等几何,推公式 D2D.Slides POJ1486 类匹配思想,硬搞 D2E.Lotto POJ2193 DP,要用longlong D2F.Optimal POJ1480 BFS硬搞 D2G.Sequence Tongji1004 贪心 除了第二天的G,全部都是没做过的...ft
最优匹配(Kuhn_Munkras算法)
// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^3)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-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 are start at 1
int nx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];
int path(int u)
{
int v;
fx[u]=1;
for(v=1;v<=ny;v++)
if((lx[u]+ly[v]==w[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((lx[u]...
return(0);
} // end of int path()
int PerfectMatch()
{
int ret=0,i,j,k,p;
memset(ly,0,sizeof(ly));
for(i=1;i<=nx;i++) {
lx[i]=-INF;
for(j=1;j<=ny;j++)
if(w[i][j]>lx[i])
lx[i]=w[i][j];
} // end of for(i...
memset(matx,-1,sizeof(matx));
memset(maty,-1,sizeof(maty));
for(i=1;i<=nx;i++) {
memset(fx,-1,sizeof(fx));
memset(fy,-1,sizeof(fy));
if(!path(i)) {
i--;
p=INF;
for(k=1;k<=nx;k++)
if(fx[k]>0)
for(j=1;j<=ny;j++)
if((fy[j]<0)&&(lx[k]+ly[j]-w[k][j]<p))
p=lx[k]+ly[j]-w[k][j];
for(j=1;j<=ny;j++) ly[j]+=(fy[j]<0?0:p);
for(k=1;k<=nx;k++) lx[k]-=(fx[k]<0?0:p);
} // end of if(!path(i))
} // end of for(i...
for(i=1;i<=ny;i++) ret+=w[maty[i]][i];
return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************
最大匹配(匈牙利算法)
// ** 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 *********************************
最近要做的事情(08/05)
给自己一些没做完或者要打算做的事情做个记录吧
继续看CLRS上的Graph Algorithms, 8.7开始做题调整状态
几个匹配的题,可以测一下自己对标程的应用
最大匹配: 1274, 1422, 1469, 1719, 2060, 2239, 2495, 2536
最优匹配: 2195
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;
}
关于Baidu的一些思考 – 不要争执那些没意义的东西
昨天看的Baidu的一本更多意义是宣传的书,虽然有广告的肉麻嫌疑,不过还是有很多值得慢慢讨论一下的.说一些书里的内容,说一些自己的体会.
1st,不要争论那些与己无关的东西,除非你是在大专辩论赛上.
这是一个很重要的命题,以前的自己,总是花了太多时间在跟别人争吵,或者自己一厢情愿的认为那是一种辩论,是一种人生观价值观的体现,其实是一种很无聊的东西,有什么意义呢?毫无意义,只是在没有价值的浪费自己的时间.以前的自己,总喜欢对很多东西发表评论,自以为是,以为看明白了世间的种种,其实也不过是井底之蛙,并且,智者的重要表现之一,就是学会保持沉默.往往,沉默是金,因为过分的争执和自大,会失去很多朋友,同时,过度的自我膨胀会遮挡自己的眼睛,从而不能看清楚很多东西.往往,真正的智者都是一语中的,没有丝毫的拖泥带水.
2nd,在没看明白自己面对的问题前,不要轻易评论,哪怕是在心里.
这个是我自己加入的,以前的自己就经常是这样,别人话说到一半,或者一个事情的背景完全不明白的情况下,就在大放厥词,往往,在贬低了自己的同时也让其他人看轻了自己.现在起要好好的观察,学习,这就够了,关于谁是谁非,那是后来的无聊人做的事情.
3rd,少说多做,努力,努力.
俞军每周工作100个小时,以至现在的搜索引擎泰斗,不知道书里对这个有没有夸大其词,不过,至少那个态度还是在那里的,回头看看自己,每周真正投入在学习中的有多少?更多的时间自己都用来干吗了?今天看了很多题,结果都是自己不会的算法,虽然一个敏感度能告诉自己应该如何去做,但是无法实现,什么都不算,一个白日梦而已.
4th,我总是在进行所谓的思考,继续思考,直到发现思考的问题过时转而去思考下一个问题.
这很不好,那么多的时间为什么都要浪费在空想上,给自己一个目标,继而为之努力.从现在来说,重要的内容是考研和工作,今天想到的是能不能两者兼而有之.对自己的能力有充分的信心,虽然因为那个事情对自己的打击非常的大,但是自己还是非常的自信,这不是盲目的自大,而是自信,虽然现在的自己好像颓废的完全不成样子,只要振作起来,我还会是最好的.对过去的两年或者更久,浪费的时间已经无法挽回,自己需要的,只是从现在开始努力,做最好的自己,燃烧力量,给所有人证明自己的价值,最需要看到的,是自己.
以后要注意克制自己不要总把时间花在这种事情上,一段时间能安心下来想明白一件事情就好,不必要太过于探究.好好努力,好好加油,好好生活.