http://docs.google.com/gview?a=v&q=cache:Up-jSb3wqOAJ:www.cs.dartmouth.edu/~doug/mdmspe.pdf
posted @
2009-07-26 14:38 wyiu 阅读(89) |
评论 (0) |
编辑 收藏
#define M 10000
bool prime[M];
int pri[M];
void prime()
{
//1表示不是素数，0表示是素数
//memset(prime,0,sizeof(prime));
int i,j,
k=0;
prime[0]=prime[1]=1;
for(i=2;i<M;i++)
if(prime[i]==0)
{
//pri[k++]=i;
for(j=2*i;j<M;j+=i)
prime[j]=1;
}
}posted @
2009-07-26 10:39 wyiu 阅读(175) |
评论 (0) |
编辑 收藏
筛个素数表+BFS
貌似数据里没有impossible的情况
#include<iostream>
using namespace std;
#define M 10000
bool prime[M];
bool visit[M];
int s,e;
int step;
void crearprimetable()//筛素数表
{
int i,j;
//prime[0]=prime[1]=1;
for(i=2;i<M;i++) //判断i是不是素数
if(prime[i]==0) //是
for(j=i+i;j<M;j+=i) //把是i倍数的数j记上1,不是素数.
prime[j]=1;
}
void bfs()
{
int i,j,k,num,t;
int que[10000];
int front,rear,trear;
step=0;
if(s==e) return ;
front=rear=0;
que[rear++]=s;
while(front<rear)
{
step++;
trear=rear;
while(front<trear)
{
num=que[front++];
for(i=1;i<10;i++)//换个位
{
t=num/10*10+i;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换十位
{
t=num/100*100+i*10+num%10;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换百位
{
t=num/1000*1000+i*100+num%100;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
for(i=1;i<10;i++)//换百位
{
t=i*1000+num%1000;
if(!prime[t] && !visit[t])
if(t==e) return ;
else {que[rear++]=t;visit[t]=true;}
}
}
}
}
int main()
{
int n;
crearprimetable();
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&s,&e);
memset(visit,0,sizeof(visit));
bfs();
printf("%d\n",step);
}
return 0;
}
posted @
2009-07-23 16:27 wyiu 阅读(170) |
评论 (0) |
编辑 收藏
//模拟洗牌，不知道为什么分类是bfs
#include<iostream>
using namespace std;
char s1[101];
char s2[101];
char s12[201];//每次洗牌后的串
char s[201]; //目标串
char first[201];//第一次洗牌后的串
int n,len,len2;
int step;
void shuf()
{
int i,j;
step=1;
while(step)
{
for(i=0,j=0;i<len;i++)
{
s12[j++]=s2[i];
s12[j++]=s1[i];
}
len2=j;
if(step==1) strcpy(first,s12);
if(strcmp(s,s12)==0) return ;
if(step!=1 && strcmp(s12,first)==0) { step=-1;return ;}
for(j=0;j<len;j++)
s1[j]=s12[j];
for(;j<len2;j++)
s2[j-len]=s12[j];
step++;
}
}
int main()
{
int i,j,k;
scanf("%d",&n);
for(k=1;k<=n;k++)
{
memset(s,0,sizeof(s));
memset(first,0,sizeof(first));
memset(s12,0,sizeof(s12));
scanf(" %d %s %s %s",&len,&s1,&s2,&s);
shuf();
if(step==-1) printf("%d -1\n",k);
else printf("%d %d\n",k,step);
}
return 0;
}
posted @
2009-07-23 15:12 wyiu 阅读(199) |
评论 (0) |
编辑 收藏
//菜鸟做法，BFS,n==99，内存空间无敌的大...
#include<iostream>
using namespace std;
//usig64_18,446,744,073,709,551,615_20wei
__int64 que[800000];
__int64 n;
__int64 t;
__int64 bfs()
{
int front=0,rear=0;
que[rear++]=1;
while(front<rear)
{
t=que[front++];
t*=10;
if(t%n==0) return t;
que[rear++]=t;
t+=1;
if(t%n==0) return t;
que[rear++]=t;
}
}
int main()
{
while(scanf("%I64d",&n)!=EOF && n)
{
printf("%I64d\n",bfs());
}
return 0;
}
posted @
2009-07-23 13:57 wyiu 阅读(462) |
评论 (0) |
编辑 收藏
这题想起魔方了,改改A了2225
#include<iostream>
using namespace std;
char dung[35][35][35];
bool visit[35][35][35];
int dx[6]={-1,0,0,0,0,1};
int dy[6]={0,-1,0,0,1,0};
int dz[6]={0,0,-1,1,0,0};
int que[82000];//3*30*30*30,一开始开得太小了2700,27000,30000,40000,50000,640000全TM的WA||RE
int L,R,C;
int sx,sy,sz,ex,ey,ez;
int step;
void bfs()
{
int i,x,y,z,tx,ty,tz;
int rear,front,trear;
bool reach=false;
memset(que,0,sizeof(que));
rear=front=0;
que[rear++]=sx;
que[rear++]=sy;
que[rear++]=sz;
visit[sx][sy][sz]=true;
while(front<rear )//&& !visit[ex][ey][ez])
{
if(visit[ex][ey][ez]) {reach=true;break;}//找到E，停
trear=rear;
step++;
while(front<trear )//&& !visit[ex][ey][ez])
{
//if(visit[ex][ey][ez]) {reach=true;break;}
x=que[front++];
y=que[front++];
z=que[front++];
for(i=0;i<6;i++)
{
tx=x+dx[i];
ty=y+dy[i];
tz=z+dz[i];
if(tx>=0 && tx<L && ty>=0 && ty<R && tz>=0 && tz<C && !visit[tx][ty][tz] && dung[tx][ty][tz]!='#')
{
visit[tx][ty][tz]=true;
que[rear++]=tx;
que[rear++]=ty;
que[rear++]=tz;
}
}//for
}//while
}//while
if(!reach) step=-1;//找不到E,trapped
}
int main()
{
int i,j,k;
while(scanf("%d%d%d",&L,&R,&C)!=EOF && L && R && C)
{
memset(visit,0,sizeof(visit));
for(i=0;i<L;i++)
for(j=0;j<R;j++)
scanf(" %s",dung[i][j]);
for(i=0;i<L;i++)
for(j=0;j<R;j++)
for(k=0;k<C;k++)
{
if(dung[i][j][k]=='S') {sx=i;sy=j;sz=k;}
else if(dung[i][j][k]=='E') {ex=i;ey=j;ez=k;}
}
step=0;
bfs();
if(step==-1) printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n",step);
}
return 0;
}
posted @
2009-07-23 11:39 wyiu 阅读(558) |
评论 (0) |
编辑 收藏
//很有趣的一题，让我想起口袋怪兽
WA了老半天，原来是两个if()放反了，居然不判RE判WA，o(╯□╰)o
#include<iostream>
using namespace std;
char map[21][21];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int h,w,sx,sy;
int step;
int res;
void dfs(int x,int y)
{
int dir,tx,ty;
if(step>=10) return ;
for(dir=0;dir<4;dir++)
{
tx=x;ty=y;
while(1)
{
tx=tx+dx[dir]; ty=ty+dy[dir];
if(tx<0 || tx>=h || ty<0 || ty>=w )break;
if(map[tx][ty]=='3')
{
step++;
//printf("--%d--\n",step);
if(res>step) res=step;
step--;
return ;
}
else
if(map[tx][ty]=='1')
{
tx=tx-dx[dir];ty=ty-dy[dir];
if(tx!=x || ty!=y)
{
map[tx+dx[dir]][ty+dy[dir]]='0';
step++;
dfs(tx,ty);
step--;
map[tx+dx[dir]][ty+dy[dir]]='1';
}
break;
}
}//while
}//for
}//dfs
int main()
{
int i,j;
while(scanf("%d%d",&w,&h)!=EOF && w)
{
step=0;
for(i=0;i<h;i++)
for(j=0;j<w;j++)
scanf(" %c",&map[i][j]);
for(i=0;i<h;i++)
for(j=0;j<w;j++)
if(map[i][j]=='2') {sx=i;sy=j;break;}
res=9999999;
dfs(sx,sy);
if(res>10) printf("-1\n");
else printf("%d\n",res);
}
return 0;
}
posted @
2009-07-22 23:46 wyiu 阅读(997) |
评论 (10) |
编辑 收藏
//解释转的~~~~~~
『题目大意』
一次比赛中，共M道题，T个队，p[i][j]表示队i解出题j的概率；问每队至少解出一题且
冠军队至少解出N道题的概率。
『算法』
设a[i][j][k]表示第i队在前j道题中共解出k道题的概率，易得a[i][j][k]有如下递推
关系(另需考虑边界条件)：
a[i][j][k] = a[i][j-1][k-1] * p[i][j] + a[i][j-1][k] * (1-p[i][j])
设s[i][j]表示a[i][M][0] + a[i][M][1] + ... + a[i][M][j]
问题的解可以转化为：每队均至少做一题的概率（用P1表示）减去每队做题数均在1到N-1
之间的概率（用P2表示）。
P1 = (s[1][M] - s[1][0])*(s[2][M]-s[2][0])*...*(s[T][M]-s[T][0])
P2 = (s[1][N-1] - s[1][0])*(s[2][N-1]-s[2][0])*...*(s[T][N-1]-s[T][0])
『算法复杂度』
O(T*M^2)
『说明』
感谢UESTC的zhucheng在poj的提示！
#include<iostream>
using namespace std;
#define MM 30
#define MT 1000
double p[MT+1][MM+1];
double d[MT+1][MM+1][MM+1];
double MTO[MT+1]; //每队至少做出一题的概率
double LTN[MT+1];//少于N道，亦即1N-1
int main()
{
int i,j,k;
int M,T,N;
double tmp1,tmp2;
while(scanf("%d%d%d",&M,&T,&N)!=EOF && M)
{
memset(MTO,0,sizeof(MTO));
memset(LTN,0,sizeof(LTN));
for(i=1;i<=T;i++)
for(j=1;j<=M;j++)
scanf("%lf",&p[i][j]);
for(i=1;i<=T;i++)
{
d[i][0][0]=1;
for(j=1;j<=M;j++)
{
d[i][j][0] = d[i][j-1][0]*(1-p[i][j]);
for(k=1;k<=M;k++)
d[i][j][k]=p[i][j]*d[i][j-1][k-1]+(1-p[i][j])*d[i][j-1][k];
}
}
tmp1=tmp2=1.0;
for(i=1;i<=T;tmp1*=MTO[i],i++)
for(k=1;k<=M;k++)
MTO[i]+=d[i][M][k];
for(i=1;i<=T;tmp2*=LTN[i],i++)
for(k=1;k<N;k++)
LTN[i]+=d[i][M][k];
printf("%.3lf\n",tmp1-tmp2);
}
return 0;
}
附上discuss上一组数据：
10 20 10
0.1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.2
1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.8
0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.7
0.2 0.23 0.56 0.2 0.23 0.56 0.2 0.23 0.56 0.88
0.56 0.2 0.23 0.56 0.88 0.56 0.2 0.23 0.56 0.88
0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12 0.82 0.47
0.82 0.47 0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12
0.37 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82 0.47
0.472 0.373 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82
0.1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.2
1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.8
0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.7
0.2 0.23 0.56 0.2 0.23 0.56 0.2 0.23 0.56 0.88
0.56 0.2 0.23 0.56 0.88 0.56 0.2 0.23 0.56 0.88
0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12 0.82 0.47
0.82 0.47 0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12
0.37 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82 0.47
0.472 0.373 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82
0.56 0.88 0.56 0.2 0.23 0.373 0.99 0.12 0.82 0.472
0.472 0.373 0.99 0.12 0.82 0.82 0.472 0.373 0.99 0.33
结果：0.740
posted @
2009-07-19 17:13 wyiu 阅读(438) |
评论 (1) |
编辑 收藏#include<iostream>
using namespace std;
#define M 26
bool grap[M+1][M+1];
int squ[M+1];
char equ[M*M][4];
int ind[M+1];
int indcop[M+1];
int cnt,n,m;
int topsort()
{
int i,j,p,num=0,
flag=0,
now=0;
for(i=0;i<n;i++)
indcop[i]=ind[i];
for(i=0;i<n;i++)
{
num=0;
for(j=0;j<n;j++)
if(indcop[j]==0)
{
num++;
p=j;
}
if(num==0) //有回路
return 0;
if(num>1) //不确定
flag=1;
//return -1; //不确定的情况下还要判断有没回路，o(╯□╰)o
indcop[p]=-1; //置为负值
squ[now++]=p;
for(j=0;j<n;j++) //删除相关的边
if(grap[p][j])
indcop[j]--;
}
if(flag) return -1; //不确定
return 1;
}
int main()
{
int i,j,ret;
char l,r;
bool done;
while(scanf("%d%d",&n,&m)==2 && n )
{
for(i=0;i<m;i++)
scanf(" %s",&equ[i]);
done=false;
memset(ind,0,sizeof(ind));
memset(grap,0,sizeof(grap));
for(i=0;i<m;i++)
{
l=equ[i][0];r=equ[i][2];
grap[l-'A'][r-'A']=true;
ind[r-'A']++;
ret=topsort();
if( ret==0 ) { printf("Inconsistency found after %d relations.\n",i+1); done=true; break;}
if( ret==1)
{
printf("Sorted sequence determined after %d relations: ",i+1);
for(j=0;j<n;j++)
printf("%c",'A'+squ[j]);
printf(".\n");
done=true;
break;
}
}
if(!done) printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
posted @
2009-07-13 14:00 wyiu 阅读(195) |
评论 (0) |
编辑 收藏#include<iostream>
using namespace std;
#define MAXN 500000
int x[MAXN+1];
int z[MAXN+1];
__int64 reverse;
void merge(int low,int mid,int high)
{
int i=low,j=mid+1,q=0;
while (i<=mid && j<=high)
{
if (x[i]<=x[j])
z[q++]=x[i++];
else {
z[q++]=x[j++];
reverse+=mid-i+1;
}
}
while (i<=mid)
z[q++]=x[i++];
while (j<=high)
z[q++]=x[j++];
for(i=0;i<q;i++)
x[low+i]=z[i];
}
void mergesort(int low,int high)
{
int mid;
if ( low< high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
int main()
{
int n,i;
while(scanf("%d",&n)==1 && n!=0)
{
for(i=0;i<n;i++)
scanf("%d",&x[i]);
reverse=0;
mergesort(0,n-1);
printf("%I64d\n",reverse);
}
return 0;
}
posted @
2009-07-12 14:59 wyiu 阅读(93) |
评论 (0) |
编辑 收藏