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 閱讀(182) |
評論 (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 閱讀(178) |
評論 (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 閱讀(205) |
評論 (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 閱讀(470) |
評論 (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 閱讀(563) |
評論 (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 閱讀(1008) |
評論 (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 閱讀(448) |
評論 (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 閱讀(201) |
評論 (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 閱讀(96) |
評論 (0) |
編輯 收藏