[Sdoi2010]魔法猪学院 【A*搜索】【堆】【K短路】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1975
【算法分析】
股价函数设为Dis(i,n)。
然后直接A*不用判重。
【其它】没有1Y。大家来BS我。。。第一次到CENA上测,90分。。。泪流满面。后来发现有个非常小的细节搞错了。。。然后这个细节如果不是刻意去搞的话,随即数据基本不可能出错,于是得了90分。
改了以后就Y了。
【CODE】
#include #include #include #include #define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int N=5005;
const int E=200005;
const int MaxL=2000005;
const double INF=1e40;
struct edge{int x,y;double w;edge *next;}g[E],*ls[N];
int n,m,e,cnt;
int L[N],v[N];
double Limit,d[N];

void addedge(int x,int y,double w){
g[++e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];
}

void init(){
int i,x,y;
double w;
e=cnt=0; clr(ls);
scanf("%d%d%lf",&n,&m,&Limit);
for (i=0;i scanf("%d%d%lf",&x,&y,&w);
addedge(y,x,w);
}
}

void spfa(){
int head=0,tail=1;
for (int i=1;i<=n;i++) d[i]=INF;
clr(v);
d[n]=0; v[n]=1;
L[1]=n;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (d[t->x]+t->w d[t->y]=d[t->x]+t->w;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
}

void Graph_op(){
int tmp=e;
e=0; clr(ls);
for (int i=1;i<=tmp;i++)
addedge(g[i].y,g[i].x,g[i].w);
}

struct Node{double w;int p;};
struct Heap_t{
Node a[MaxL];
int tot;
void up(int k){
while (k>1 && a[k].w swap(a[k],a[k>>1]);
k>>=1;
}
}

void down(int k){
int p;
while ((k<<1)<=tot){
p=k<<1;
p+=(p if (a[p].w swap(a[p],a[k]);
k=p;
}else break;
}
}

void Insert(int p,double w){
if (w>Limit) return;
tot++;
a[tot].p=p;
a[tot].w=w;
up(tot);
}

void Del(int p){
swap(a[p],a[tot]);
tot--;
down(p);
up(p);
}
}Heap;

void A_star(){
Heap.tot=0;
Heap.Insert(1,d[1]);
Node T;
while (Heap.tot && Heap.a[1].w<=Limit){
T=Heap.a[1];
Heap.Del(1);
if (T.p==n){
cnt++;
Limit-=T.w;
}
else
for (edge *t=ls[T.p];t;t=t->next)
Heap.Insert(t->y,T.w-d[T.p]+t->w+d[t->y]);
}
printf("%dn",cnt);
}

int main(){
init();
spfa();
Graph_op();
A_star();
}

[USACO2010 Feb Gold 【ice】]hash+BFS+n多个二分

【题目链接】http://ace.delos.com/ioigate
八中也有
【题目大意】
给定一个无穷大的棋盘,和上面的n个石头,n<=20000。他们的坐标范围是-1e9<=x<=1e9
然后有一只牛在上面滑。
它每次可能选上下左右这4个方向滑,如果遇到石头,那么它就会停下来,并且它没办法在不遇到石头的情况下停下来。
当然了,它是不能穿越石头的。
给定起点和终点,为最少滑多少步能到达终点。
保证有解。
【算法分析】
呃,就是一最短路问题,而边权都为1,所以就只裸的BFS。
由于只能碰到石头才停下,所有最多有4*n个可达位置。
然后扩展就比较纠结。。。可能离散化比较好写,但是离散化的话还要对相隔的搞多一层。
也不是非常好处理。
我就是写了12个二分,泪流满面地1Y。
我的扩展是这样的:
开两个数组装那些石头,
第一个是x为第一关键字,y为第二关键字排序的。
第二个是y为第一关键字,x为第二关键字排序的。
然后走的时候就像前向星那样二分出x(y)相等的区间,然后再找一个y(x)刚好小于(大于)当前点的石头,扩展即可。最后利用hash判下重。。。
【其它】。。。之前代码贴错了。
【CODE】
/*
ID:jie22221
TASK:ice
LANG:C++
*/
#include #include #include #define AA (*((Node*)A))
#define BB (*((Node*)B))
using namespace std;
const int N=25555;
const int INF=0x7FFFFFFF;
const int Mod=200003;
struct Node{int x,y;}S,T,p[N],q[N],L[N*4];
struct edge{Node data;edge *next;}*ls[Mod];
int n,step[N*4],ans=INF,head,tail,fa[N*4];

void init(){
memset(ls,0,sizeof(ls));
cin >> n >> S.x >> S.y >> T.x >> T.y;
for (int i=1;i<=n;i++){
cin >> p[i].x >> p[i].y;
q[i]=p[i];
}
}

int cmp_p(const void *A,const void *B){
if (AA.x!=BB.x) return AA.x-BB.x;
return AA.y-BB.y;
}

int cmp_q(const void *A,const void *B){
if (AA.y!=BB.y) return AA.y-BB.y;
return AA.x-BB.x;
}

Node Findu(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.y<=q[mid].y) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.y else l=mid;
if (q[r].y==W.y) l=r;
Ed=l;
if (q[l].y!=W.y || q[St].x>=W.x) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l+1 if (q[mid].x else r=mid-1;
if (q[r].x res.x=q[l].x+1;
res.y=W.y;
return res;
}

Node Findd(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.y<=q[mid].y) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.y else l=mid;
if (q[r].y==W.y) l=r;
Ed=l;
if (q[l].y!=W.y || q[Ed].x<=W.x) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l if (q[mid].x>W.x) r=mid;
else l=mid+1;
res.x=q[l].x-1;
res.y=W.y;
return res;
}

Node Findl(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.x<=p[mid].x) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.x else l=mid;
if (p[r].x==W.x) l=r;
Ed=l;
if (p[l].x!=W.x || p[St].y>=W.y) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l+1 if (p[mid].y else r=mid-1;
if (p[r].y res.x=W.x;
res.y=p[l].y+1;
return res;
}

Node Findr(Node W){
Node res; res.x=INF;
int l,r,mid,St,Ed;
for (l=1,r=n,mid=(l+r)>>1;l if (W.x<=p[mid].x) r=mid;
else l=mid+1;
St=l;
for (l=1,r=n,mid=(l+r)>>1;l+1 if (W.x else l=mid;
if (p[r].x==W.x) l=r;
Ed=l;
if (p[l].x!=W.x || W.y>=p[Ed].y) return res;
for (l=St,r=Ed,mid=(l+r)>>1;l if (W.y else l=mid+1;
res.x=W.x;
res.y=p[l].y-1;
return res;
}

inline long long ABS(int x){
if (x<0) return -x;
return x;
}
inline int f(Node W){return (int)(((ABS(W.x)*17+ABS(W.y)*31)&INF)%Mod);}

bool Inhash(Node W){
for (edge *t=ls[f(W)];t;t=t->next)
if (t->data.x==W.x && t->data.y==W.y) return true;
return false;
}

void Insert(Node W){
edge *t=(edge *)malloc(sizeof(edge));
int h=f(W);
t->next=ls[h];
t->data=W;
ls[h]=t;
}

void expand(Node res){
if (res.x==INF || Inhash(res)) return;
Insert(res);
tail++;
L[tail]=res;
step[tail]=step[head]+1;
fa[tail]=head;
if (res.x==T.x && res.y==T.y)
ans=min(ans,step[tail]);
}

int solve(){
if (S.x==T.x && S.y==T.y) return 0;
L[0].x=S.x; L[0].y=S.y; step[0]=0; Insert(L[0]);
for (head=0,tail=0;head<=tail;head++){
expand(Findu(L[head]));
expand(Findd(L[head]));
expand(Findl(L[head]));
expand(Findr(L[head]));
if (ans }
return ans;
}

int main(){
freopen("ice.in","r",stdin);
freopen("ice.out","w",stdout);
ios::sync_with_stdio(false);
init();
qsort(p+1,n,sizeof(Node),cmp_p);
qsort(q+1,n,sizeof(Node),cmp_q);
cout << solve() << endl;
}

[ZSOI 简单数谜]DFS+调整搜索顺序

【题目】

Description

  很多人都曾经听说过数独,但你是否听说过数谜(Karuro)呢?实际上,数谜是数独的更大(且更难)的兄弟问题,而且在日本也是非常受欢迎的。
数谜问题和填字游戏类似,不过它要填的不是文字而是数字。数谜游戏的目标是用1-9填满所有空格,且这些数字相加的和满足相应的要求(或者称为“提 示”),且在同一栏(“栏”是指一些水平或者竖直的连续的空格,用于提示的格子不算空格)不能填重复的数字。当所有格子按要求被填满后,这个数谜就看作被 解决了。图1和图2是一个可能的数谜游戏示例。
当然,直接求解数谜问题的话会比较困难。所以现在我们需要解决的是一个更简单的数谜问题。简单数谜的形状是一个(n+1)行乘(m+1)列的矩 形。而简单数谜也只有两种要求,就是行要求和列要求,且分别处于第一行和第一列,其他格子则是空格,而左上角是忽略不计的。coolzzz同学爱好简单数 谜,他已经给一些简单数谜填好了其中的一些空格。现在,他想寻求你的帮助,来帮他完成这些简单数谜。如图3所示,2和9是coolzzz同学已经填好的空 格,图4则是一个基于图3 的一个可能的解答。

Input

  输入包含多组测试数据。第一行包含一个正整数T,表示测试数据数目。每组数据第一行是n(n<10)和m(m<10),表示数谜的形状的 大小。接下来一行有n个整数,是相应的行要求;然后一行是m个整数,是相应的列要求。接下来的n行每行有m个小于10的非负整数,0表示该空格还没有被填 数字,其他表示coolzzz同学已经填好的数字。输入数据保证未填数字的空格不会超过16个。

Output

  对于每组测试数据,输出若干行。如果基于coolzzz已填的结果,该数谜只有一个解,则输出该解;如果不止一个解,则输出一行“Not unique.”;如果没有解,则输出一行“No answer.”。

Sample Input

3
3 3
6 6 6
6 6 6
0 0 0
0 3 0
0 0 0
2 3
10 17
5 16 6
2 0 0
0 9 0
2 2
3 5
4 4
0 0
0 0

Sample Output

Not unique.
2 7 1
3 9 5
No answer.

【算法分析】
类似数独的搜索题,然后就是设一个简单的估价函数,按它的值排下序,然后再用位运算优化一下就可以很快出解。
另外传说的DLX应该会有更好的表现。。。
【CODE】
#include #include #include const int N=10;
const double rate=0.02;
struct LL{int x,y;double w;}L[N*N];
int n,m,tot,ans;
int limitx[N],limity[N],canx[N],cany[N],donex[N],doney[N];
int a[N][N],lg[2000],ansl[N][N];
bool flag;

void input(){
memset(donex,0,sizeof(donex));
memset(doney,0,sizeof(doney));
flag=true;
tot=0;
scanf("%d%d",&m,&n);
for (int i=0;i for (int i=0;i for (int i=0;i for (int i=0;i for (int i=0;i for (int j=0;j scanf("%d",&a[i][j]);
if (a[i][j]){
limitx[i]-=a[i][j];
limity[j]-=a[i][j];
if (canx[i]&(1< if (cany[j]&(1< if (limitx[i]<0) flag=false;
if (limity[j]<0) flag=false;
canx[i]^=1< cany[j]^=1< donex[i]++;
doney[j]++;
}else{
tot++;
L[tot].x=i;
L[tot].y=j;
}
}
}

int cmp(const void *x,const void *y){
if (((LL*)x)->w>((LL*)y)->w) return 1;
if (((LL*)x)->w<((LL*)y)->w) return -1;
if (((LL*)x)->w==((LL*)y)->w) return 0;
}

void init(){
for (int i=1;i<=tot;i++)
L[i].w=donex[L[i].x]+doney[L[i].y]+rate*(limitx[L[i].x]+limity[L[i].y]);
qsort(&L[1],tot,sizeof(LL),cmp);
}

inline int sqr(int x){return x*(x+1)/2;}

void dfs(int dep){
LL &Node=L[dep];
if (dep==tot+1){
ans++;
if (ans>1) return;
memcpy(ansl,a,sizeof(a));
}
int state=canx[Node.x]&cany[Node.y],p;
while (state){
p=state&-state;
if (limitx[Node.x]-lg[p] if (limity[Node.y]-lg[p] a[Node.x][Node.y]=lg[p];
limitx[Node.x]-=lg[p];
limity[Node.y]-=lg[p];
donex[Node.x]++;
doney[Node.y]++;
canx[Node.x]-=p;
cany[Node.y]-=p;
if (!(donex[Node.x]==n && limitx[Node.x]!=0))
if (!(doney[Node.y]==m && limity[Node.y]!=0))
dfs(dep+1);
if (ans>1) return;
a[Node.x][Node.y]=0;
limitx[Node.x]+=lg[p];
limity[Node.y]+=lg[p];
donex[Node.x]--;
doney[Node.y]--;
canx[Node.x]+=p;
cany[Node.y]+=p;
state-=p;
}
}

void solve(){
if (ans>1) printf("Not unique.n");
if (ans==0) printf("No answer.n");
if (ans==1)
for (int i=0;i for (int j=0;j printf("%d",ansl[i][j]);
if (j==n-1) printf("n");
else printf(" ");
}
}

int main(){
lg[1]=0;
for (int i=2;i<=1024;i++){
lg[i]=lg[i-1];
if (i==1< }
for (int i=1;i<=1024;i++) lg[i]++;
freopen("kakuro.in","r",stdin);
freopen("kakuro.out","w",stdout);
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
input();
if (!flag){
printf("No answer.n");
continue;
}
ans=0;
init();
dfs(1);
solve();
}
}

[2010年江苏省选拔赛第三轮 第一试 找零钱的洁癖]BFS、Hash、贪心

【题目大意】
给出N个数和一个X,问这些数最少用多少个加加减减可以得到X。
X<=0x7FFFFFFF
【算法分析】
显然,这是搜索题。
然后。。。我的是cheat的。
一开始我是写双向广搜,貌似没多少分。
然后我同学直接单向暴力:80分。。。
好吧,沿用这个单向暴力广搜,然后发现TLE的两个点的数据都是由2^0 2^1 2^2..... 2^32组成的。
然后就是从2^32一直弄下来贪心就行了。。。就是二进制
下面的BFS,爆队列的话,直接就return INF。
然后。。。这样就可以弱弱地AC了。
【其它】
求正解。。。
【CODE】
#include using namespace std;
typedef long long big;
const big N=1000003;
const big INF=0x7FFFFFFF;
struct link{big y,next;}g[N];
big e,ans,n;
big ls[N],step[N];
big list[N],X,a[N];

void init(){
e=0; memset(ls,0,sizeof(ls));
cin >> X;
n=0;
while (cin >> a[n]) n++;
sort(a,a+n);
}

big greedy(big mb){
big times=0;
for (big i=n-1;i>=0;i--){
times+=mb/a[i];
mb-=mb/a[i]*a[i];
}
if (mb) return INF;
return times;
}

big inhash(big k){
big key=(k+INF)%N;
for (big t=ls[key];t;t=g[t].next)
if (list[g[t].y]==k) return g[t].y;
return 0;
}

void ins(big zz){
e++;
big key=(big)((list[zz]+INF)%N);
g[e].y=zz;
g[e].next=ls[key];
ls[key]=e;
}

big bfs(){
if (X==0) return 0;
big head=0,tail=1,i,pos;
list[1]=0; step[1]=0;
while (head head++;
for (i=0;i tail++;
if (tail>=N-22) return INF;
step[tail]=step[head]+1;
if (list[head] else list[tail]=list[head]-a[i];
if (list[tail]==X) return step[tail];
pos=inhash(list[tail]);
if (pos) {tail--; continue;}
ins(tail);
}
}
}

int main(){
init();
ans=greedy(X);
big tmp=bfs();
ans=min(ans,tmp);
cout << ans << endl;
}

[ZOJ 3304 Prison Break]BFS、模拟、种子染色法

【题目大意】

如果把P视作不能去的区域,哪个人不能通过上下左右走到达牢房边缘的话,直接就变成Ghost

然后在剩下的人里,找最大的上下左右对角线连通的连通块。

【算法分析】

一开始处理Ghost的话,从牢房边缘bfs进来,如果不能到达某个P,他就死了。

然后剩下的就是种子染色法了。

【CODE】

#include #include int m,n,lx[1111111],ly[1111111],ans,head,tail;
char map[1111][1111];
bool v[1111][1111];

inline void expand1(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty]) return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void getghost(){
    head=0; tail=0;
    for (int i=1;i<=m;i++){
        tail++;
        lx[tail]=i;
        ly[tail]=0;
        tail++;
        lx[tail]=i;
        ly[tail]=n+1;
    }   
    for (int i=1;i<=n;i++){
        tail++;
        lx[tail]=0;
        ly[tail]=i;
        tail++;
        lx[tail]=m+1;
        ly[tail]=i;
    }
    while (head        head++;
        if (map[lx[head]][ly[head]]=='P' && lx[head]>0 && lx[head]<=m && ly[head]>0 && ly[head]<=n)
          continue;
        expand1(lx[head]-1,ly[head]);
        expand1(lx[head]+1,ly[head]);
        expand1(lx[head],ly[head]-1);
        expand1(lx[head],ly[head]+1);
    }   
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]=='P' && !v[i][j])
          map[i][j]='G';
}

inline void expand(int tx,int ty){
    if (tx<1 || tx>m || ty<1 || ty>n || v[tx][ty] || map[tx][ty]!='P') return;
    v[tx][ty]=true;
    tail++;
    lx[tail]=tx;
    ly[tail]=ty;
}   

void bfs(int sx,int sy){
    head=0,tail=1;
    lx[1]=sx; ly[1]=sy;
    v[sx][sy]=true;
    while (head        head++;
        expand(lx[head]-1,ly[head]);
        expand(lx[head]+1,ly[head]);
        expand(lx[head],ly[head]-1);
        expand(lx[head],ly[head]+1);
        expand(lx[head]-1,ly[head]-1);
        expand(lx[head]-1,ly[head]+1);
        expand(lx[head]+1,ly[head]-1);
        expand(lx[head]+1,ly[head]+1);
    }   
    if (tail>ans) ans=tail;
}   

void solve(){
    memset(map,'P',sizeof(map));
    memset(v,false,sizeof(v));
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        for (map[i][j]=getchar();map[i][j]==' ' || map[i][j]=='n';map[i][j]=getchar());
    getghost();
    memset(v,false,sizeof(v));
    ans=0;
    for (int i=1;i<=m;i++)
      for (int j=1;j<=n;j++)
        if (map[i][j]=='P' && !v[i][j])
          bfs(i,j);
    printf("%dn",ans);
}   

int main(){
    while (scanf("%d%d",&m,&n)!=EOF) solve();
    return 0;   
}