摘要: 据说，Hash的优劣顺序为：BKDRHash, APHash, DJBHash, JSHash, RSHash, SDBMHash, PJWHash, ELFHash。
unsigned int SDBMHash(char *str){ unsigned int hash = 0;...
阅读全文
posted @
2011-02-23 22:16 小阮 阅读(379) |
评论 (0) |
编辑 收藏题意：求最大子矩阵。
设h[i,j]是点(i, j)向上的最长距离，l[i,j]是点(i, j)向左的最长距离，r[i,j]是点(i, j) 向右的最常距离，
点(i, j)处的矩形面积 ＝ h[i, j]*(l[i, j]+r[i, j]-1)
h[i, j] = h[i-1,j]+1 （ 点(i, j)是好的）
h[i, j] = 0 （ 点(i, j)是坏的）
l[i, j] = min( l[i-1, j] , k) （ 点(i, j)是好的）
l[i, j] = 0 （ 点(i, j)是坏的）
r[i, j] = min(l[i-1, j], k) （ 点(i, j)是好的）
r[i, j] = 0 （ 点(i, j)是坏的）
/**//*
ID: lorelei3
TASK: rectbarn
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAX = 3005;
ifstream fin("rectbarn.in");
ofstream fout("rectbarn.out");
bool map[MAX][MAX];
int h[MAX], l[MAX], r[MAX];
int R,C,P,ans;
void input()
{
int x,y;
fin>>R>>C>>P;
for(int i=0; i<P; ++i){
fin>>x>>y;
map[x][y]=true;
}
}
inline int min(int a, int b){
if (a<b && a!=0)
return a;
return b;
}
inline int max(int a, int b){
return a>b?a:b;
}
void dp(){
int i,j,k;
for(i=1; i<=R; ++i){
k=0;
for(j=1; j<=C; ++j){
if(!map[i][j]){
h[j]=h[j]+1;
l[j]=min(l[j], ++k);
}else
h[j]=0, l[j]=0, k=0;
}
k=0;
for(j=C; j>=1; --j){
if(!map[i][j]){
r[j]=min(r[j], ++k);
ans=max(ans, h[j]*(l[j]+r[j]-1));
}else
r[j]=0, k=0;
}
}
}
void output(){
fout<<ans<<endl;
}
int main(){
input();
dp();
output();
return 0;
}posted @
2011-02-18 15:43 小阮 阅读(579) |
评论 (0) |
编辑 收藏
摘要: 题意是求哈密顿回路的多少，可以用《基于连通性状态压缩的动态规划问题》来解，但由于只有4行，所以可以发现一些规律，其他人写的比较多了，就不列举出来，设f[i] 表示前i列中，第i列的第一个格子到第二个格子的哈密顿路的条数。本题的答案自然就是f[n]。设g[i]表示前i列中，第i列的第一个格子到第四个格子的哈密顿路的条数。f[i]的递推关系： f[i] = f[i-1] + g[i-1]g[i]的递推...
阅读全文
posted @
2011-02-18 11:58 小阮 阅读(808) |
评论 (0) |
编辑 收藏
等待补充
posted @
2011-02-18 11:50 小阮 阅读(440) |
评论 (0) |
编辑 收藏
摘要: 后缀数组的简单应用。
/**//*ID: lorelei3TASK: hiddenLANG: C++*/#include <fstream>#include <iostream>#include <memory.h>using namespace std;const in...
阅读全文
posted @
2011-02-17 17:10 小阮 阅读(491) |
评论 (0) |
编辑 收藏
将每个矩形拆分为2条横边和2条纵边，用一个结构体记录，
以横边为例，记录开始的横坐标s，结束的横坐标e，该横边的纵坐标p，若该横边是一个矩形下边的边，则start为ture，若是一个矩形上边的边，则为false，
记录后按纵坐标从小到大排序，若纵坐标相等的，start为ture的优先。
(PS：STL的sort中，对于比较函数，若两个元素相等，则必需返回false，否则会导致sort死循环）
排序后，从小到大进行扫描。
使用level作为记录数组，
对于start = true 的横边，对于j = [s, e) ，进行level[j] ++ 若level[j]==1， ans++；
对于start = false的横边，对于j = [s, e)，进行level[j] -- 若level[j]==0， ans++；
（画个简图领会下）
纵边如此类推。
/**//*
ID: lorelei3
TASK: picture
LANG: C++
*/
#include <fstream>
#include <algorithm>
#include <memory.h>
using namespace std;
const int MAX = 20005;
struct Line{
int s,e,p;
bool start;
bool operator < ( const Line &l) const{
if(p==l.p){
if(l.start == start)
return false;
if(start)
return 1;
else
return 0;
}
return p<l.p?1:0;
}
};
ifstream fin("picture.in");
ofstream fout("picture.out");
Line lx[MAX], ly[MAX];
long ans;
int n,m;
void input(){
fin>>n;
int x1,x2,y1,y2,lenx=0,leny=0;
m=n+n;
for(int i=0; i<=n; ++i){
fin>>x1>>y1>>x2>>y2;
lx[lenx].s=x1, lx[lenx].e=x2, lx[lenx].p=y1;
lx[lenx].start=true;
lenx++;
lx[lenx].s=x1, lx[lenx].e=x2, lx[lenx].p=y2;
lx[lenx].start=false;
lenx++;
ly[leny].s=y1, ly[leny].e=y2, ly[leny].p=x1;
ly[leny].start=true;
leny++;
ly[leny].s=y1, ly[leny].e=y2, ly[leny].p=x2;
ly[leny].start=false;
leny++;
}
qsort(lx, m, sizeof(Line), cmp);
qsort(ly, m, sizeof(Line), cmp);
sort(lx, lx+m);
sort(ly, ly+m);
}
int level[20005], zero=10000;
void solve(Line *l){
memset(level, 0, sizeof(level));
for(int i=0; i<m; ++i){
if(l[i].start){
for(int k=zero+l[i].s; k<(zero+l[i].e); ++k){
level[k]++;
if(level[k]==1)
ans++;
}
}else{
for(int k=zero+l[i].s; k<(zero+l[i].e); ++k){
level[k]--;
if(level[k]==0)
ans++;
}
}
}
}
void output(){
fout<<ans<<endl;
}
int main(){
input();
solve(lx);
solve(ly);
output();
return 0;
}
posted @
2011-02-17 13:56 小阮 阅读(405) |
评论 (0) |
编辑 收藏
摘要: 本题是求最大点割集。首先，构造图。对于点i，分成u和v两点，并且dist[u][v]=1，dist[v][u]＝0；对于边(i, j)， 对于i，根据上述方法分成a1，a2两点，j分成b1，b2； 使dist[b1][a2]=INF，dist[a2][b1]=0； dist[b2][a1]=INF，dist[a1][b2]=0；然后根据最大流最小割定理，求最大流，使用Dinic。Dinic的原理是...
阅读全文
posted @
2011-02-17 13:47 小阮 阅读(691) |
评论 (0) |
编辑 收藏优化1：黑书P184, 一条完整的路径对于中间各点(除起点和目标点外)，必需包含一进一出，所以中间点必需至少有两个未经过的相邻点（除非当前点在旁边）
优化2：预防形成孤零区域。
/**//*
ID: lorelei3
TASK: betsy
LANG: C++
*/
#include <fstream>
using namespace std;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
const int MAXN = 10;
ifstream fin("betsy.in");
ofstream fout("betsy.out");
bool map[MAXN][MAXN];
int n,ans,num;
void input(){
fin>>n;
for(int i=0; i<=n+1; ++i){
map[0][i]=true, map[i][0]=true, map[n+1][i]=true, map[i][n+1]=true;
}
num=n*n;
}
inline int get(int x, int y){
int cnt=0;
for(int i=0; i<4; ++i)
if(!map[x+dx[i]][y+dy[i]])
cnt++;
return cnt;
}
void dfs(int x, int y, int t){
if(x==n&&y==1){
if(t==num)
ans++;
return;
}
//优化2
if(map[x][y-1]&&map[x][y+1]&&!map[x+1][y]&&!map[x-1][y] ||
!map[x][y-1]&&!map[x][y+1]&&map[x+1][y]&&map[x-1][y] )
return;
//优化1
int i,xi,yi,count=0;
for(i=0; i<4; ++i){
int tx=x+dx[i];
int ty=y+dy[i];
if(map[tx][ty] || (tx==n&&ty==1))
continue;
int p = get(tx,ty);
if(p<=1){
count++;
xi=tx, yi=ty;
}
}
if(count>1)
return;
else{
if(count==1){
map[xi][yi]=true;
dfs(xi,yi,t+1);
map[xi][yi]=false;
}else{
for(i=0; i<4; ++i){
int tx=x+dx[i];
int ty=y+dy[i];
if(!map[tx][ty]){
map[tx][ty]=true;
dfs(tx,ty,t+1);
map[tx][ty]=false;
}
}
}
}
}
void solve(){
map[1][1]=true;
dfs(1,1,1);
}
void output(){
fout<<ans<<endl;
}
int main(){
input();
solve();
output();
return 0;
}
posted @
2011-02-16 15:28 小阮 阅读(555) |
评论 (0) |
编辑 收藏动态规划
posted @
2011-02-16 15:23 小阮 阅读(409) |
评论 (0) |
编辑 收藏可以看成甲乙两个人同时从A点出发，经过不同的路径，到达B点的最长路径和。
设f[i,j]为甲走到第i座城市，乙走到第j座城市，路径的总和。
初始状态：f[1][1]=1；
转移方程：f[j, i ] = f[i,j] = max{f[i,k]+1} j,k间有路，1<=k<j
结果：ans = max{f[i,n]} i,n之有路
/**//*
ID: lorelei
TASK: tour
LANG: C++
*/
#include <fstream>
#include <string>
using namespace std;
const int MAX = 105;
const int INF = 0x7FFFFFF;
ifstream fin("tour.in");
ofstream fout("tour.out");
string city[105];
bool adj[MAX][MAX];
int n,v,ans;
inline int find(string str){
for(int i=1; i<=n; ++i)
if(str==city[i])
return i;
}
void input(){
int i;
fin>>n>>v;
for(i=1; i<=n; ++i)
fin>>city[i];
string s,t;
for(i=1; i<=v; ++i){
fin>>s>>t;
int v1 = find(s);
int v2 = find(t);
adj[v1][v2]=adj[v2][v1]=true;
}
}
int f[MAX][MAX];
void solve(){
f[1][1]=1;
for(int i=1; i<=n; ++i)
for(int j=i+1; j<=n; ++j){
f[i][j]=-INF;
for(int k=1; k<j; ++k){
if(adj[k][j] && f[i][k]>0 && f[i][k]>f[i][j])
f[i][j]=f[i][k];
}
f[j][i]= ++f[i][j];
}
}
void output(){
ans=1;
for(int i=1; i<n; ++i)
if(adj[i][n] && f[i][n]>ans)
ans=f[i][n];
fout<<ans<<endl;
}
int main(){
input();
solve();
output();
return 0;
}
posted @
2011-02-14 22:49 小阮 阅读(544) |
评论 (1) |
编辑 收藏