c++&oi

搜索几题（1～6）

1.AP数：重写了一下，比原来好一点，写的过程中错漏较多。其实显然就是找[1,n]中因数最多且在这些数中最小的数。(与AP数有关的题目：poj2886)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int prime[21]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};

int ans,n;

int max_tt=0;

void dfs(int i,int t,int tt,int x);

int main()

{

freopen("ap.in","r",stdin);

freopen("ap.out","w",stdout);

while(scanf("%d",&n)!=EOF)

{

ans=0;max_tt=0;

dfs(0,1000000000,1,1);

printf("%d\n",ans);

}

return 0;

}

void dfs(int i,int t,int tt,int x)

{

int xx=(int)(log(n/x)/log(prime[i]));// 可行性剪枝

t=xx<t?xx:t;//这个不加就只有70分了。。。。。

for(int j=1;j<=t;j++)

{

x*=prime[i];

if(x>n)return;

tt*=(j+1);

if(tt>max_tt||(tt==max_tt&&x<ans))

{

max_tt=tt;

ans=x;

}

dfs(i+1,j,tt,x);

tt/=(j+1);

}

}

2. 山峰和山谷:

一开始写dfs，结果诸多点栈崩溃，130分，10*(9)10+20*(2)5.又想起NOI二试第一题，写BFS就AC了，写DFS才70。于是决定以后都写BFS了（DFS是普及组的王牌。。。。）。遂写BFS，结果一直超时（难道被卡了常数？？）。突然发现把两句memset(Queuex,0,sizeof(Queuex));memset(Queuey,0,sizeof(Queuey));去掉后就AC了。。。。。。啊。。发现了我一个不好的习惯。以后要看是否需要初始化，不需要的坚决不写！

看了一下标程，在统计山峰和山峰时略有改进。用//标出

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=1001;

int n;

int place[maxn][maxn];

int xx[8]={1,1,1,0,0,-1,-1,-1};

int yy[8]={1,-1,0,-1,1,1,-1,0};

int Queuex[maxn*maxn],Queuey[maxn*maxn],Head,Tail;

bool use[maxn][maxn];

int C1=0,C2=0,T1,T2;

void work(int x,int y);

int main()

{

int a,b,c;

freopen("grz.in","r",stdin);

freopen("grz.out","w",stdout);

scanf("%d",&n);

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

scanf("%d",&place[i][j]);

memset(use,false,sizeof(use));

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

if(!use[i][j])

work(i,j);

/*if(C1==0&&C2==0)

printf("%d %d",1,1);

else*/

printf("%d %d",C1,C2);

return 0;

}

void work(int x,int y)

{

int T1=1;T2=1;

int T=0;

int a,b;

use[x][y]=1;

Head=1;Tail=1;

Queuex[Head]=x;

Queuey[Head]=y;

while(Head<=Tail)

{

for(int i=0;i<=7;i++)

{

a=Queuex[Head]+xx[i];

b=Queuey[Head]+yy[i];

if(a>=1&&a<=n&&b>=1&&b<=n)

{

if(place[a][b]>place[x][y])

T1=0;

else if(place[a][b]<place[x][y])

T2=0;

else if(!use[a][b])

{

use[a][b]=1;

Tail++;

Queuex[Tail]=a;

Queuey[Tail]=b;

}

}

/*if(a<1||a>n||b<1||b>n)continue;

if(place[a][b]==place[x][y])

{

if(!use[a][b])

{

use[a][b]=1;

Tail++;

Queuex[Tail]=a;

Queuey[Tail]=b;

}

continue;

}

if(place[x][y]<place[a][b])

T|=2;

else T|=1; */

}

Head++;

}

//if(T==1)C1++;

//if(T==2)C2++;

if(T1)C1++;

if(T2)C2++;

}

3. 超级马

一个是写gcd时，忘记了处理负数，一个是写x,y两个队列时，开的大小不一样。悲剧了很久。最后AC了，但过不了附加的BT数据，后来把判断写在了while里面，一判断就break；果然跑的飞快。最终代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=101;

int x[101],y[101];

int xx,yy;

int n;

bool Hash[maxn*maxn*5];

int Queuex[maxn*maxn*maxn],Queuey[maxn*maxn*maxn],Head,Tail;

inline int tt(int x,int y){return (x+100)*200+y+100;}

int gcd(int a,int b);

int main()

{

int k,a,b,q=0;

freopen("sup.in","r",stdin);

freopen("sup.out","w",stdout);

scanf("%d",&k);

for(;k>=1;k--)

{

q=0;

scanf("%d",&n);

scanf("%d %d",&x[1],&y[1]);

xx=abs(x[1]);//

yy=abs(y[1]);//

for(int i=2;i<=n;i++)

{

scanf("%d %d",&x[i],&y[i]);

xx=gcd(xx,abs(x[i]));//

yy=gcd(yy,abs(y[i]));//

}

if(!(xx==1&&yy==1))

{

printf("NIE\n",xx,yy);

continue;

}

memset(Hash,false,sizeof(Hash));

Head=Tail=1;

Queuex[Head]=Queuey[Head]=0;

Hash[tt(0,0)]=true;

while(Head<=Tail)

{

for(int i=1;i<=n;i++)

{

a=Queuex[Head]+x[i];

b=Queuey[Head]+y[i];

if(a<-100||a>100||b<-100||b>100)continue;

if(!Hash[tt(a,b)])

{

Hash[tt(a,b)]=true;

Tail++;

Queuex[Tail]=a;

Queuey[Tail]=b;

}

if(a==0&&b==1)q|=1;

else if(a==0&&b==-1)q|=2;

else if(a==1&&b==0)q|=4;

else if(a==-1&&b==0)q|=8;

}

if(q==15)

break;

Head++;

}

if(q==15)

printf("TAK\n");

else

printf("NIE\n");

}

return 0;

}

int gcd(int a,int b)

{

if(!a)return b;

return gcd(b%a,a);

}

4. 传递游戏

主要是最优性剪枝，话说我把边按从小到大派了一下序，与不排序比的确是快了一些，但多了一个变量to，结果还是变慢了，贴上变慢的程序（还是AC了……）。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=19;

const int maxint=100000000;

inline void change(int &a,int &b){a^=b;b^=a;a^=b;}

int n;

int to[maxn][maxn];

int wi[maxn][maxn];

bool use[maxn];

void dfs(int k,int i,int now);

int M=maxint;

int main()

{

memset(use,true,sizeof(use));

freopen("pass.in","r",stdin);

freopen("pass.out","w",stdout);

scanf("%d",&n);

for(int j=1;j<=n;j++)

{

to[0][j]=j;

wi[0][j]=0;

}

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

scanf("%d",&wi[i][j]);

to[i][j]=j;

if(wi[i][j]==-1)

wi[i][j]=maxint;

}

for(int i=1;i<=n;i++)

for(int k=1;k<=n;k++)

for(int j=k+1;j<=n;j++)

if(wi[i][j]<wi[i][k])

{

change(wi[i][j],wi[i][k]);

change(to[i][j],to[i][k]);

}

use[0]=false;

dfs(0,0,0);

printf("%d\n",M);

return 0;

}

void dfs(int k,int i,int now)

{

if(now>M)

return;

if(k==n)

{

if(now<M)

M=now;

return ;

}

for(int j=1;j<=n;j++)

if(use[to[i][j]])

{

use[to[i][j]]=false;

dfs(k+1,to[i][j],now+wi[i][j]);

use[to[i][j]]=true;

}

}

5. 王后守卫

估计了一个上界8*8是5,9*9最多是6，然后用最优性剪枝。（题解说上界是5），一开始想先写一个朴素的，结果太朴素了，10min不能出解，于是出位运算，结果竟然AC了……看到题解上还写了一大堆剪枝。加上这些剪枝，发现变得更慢了……原版程序：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=11;

int n,m;

int bit[21]={1};

bool p[maxn][maxn];

bool now[maxn][maxn];

bool Hash[maxn][maxn];

inline int aa(int x,int y){return n-x+y;}

inline int bb(int x,int y){return x+y-1;}

int na=0,nb=0,nx=0,ny=0;

int ans=0;

void dfs(int i,int a,int b,int x,int y);

bool judge(int a,int b,int x,int y);

int main()

{

int c=0;

char t;

freopen("queen.in","r",stdin);

freopen("queen.out","w",stdout);

for(int i=1;i<=20;i++)

bit[i]=bit[i-1]<<1;

while(scanf("%d %d ",&n,&m))

{

memset(Hash,true,sizeof(Hash));

ans=6;

if(!n)

break;

c++;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

scanf("%c ",&t);

if(t=='X')

p[i][j]=true;

else

p[i][j]=false;

}

dfs(0,0,0,0,0);

printf("Case %d: %d\n",c,ans);

}

return 0;

}

void dfs(int i,int a,int b,int x,int y)

{

if(judge(a,b,x,y))

{

if(i<ans)

ans=i;

return ;

}

else if(i>=ans-1) return ;

for(int j=1;j<=n;j++)

for(int k=1;k<=m;k++)

dfs(i+1,a|(bit[aa(j,k)]),b|(bit[bb(j,k)]),x|(bit[j]),y|(bit[k]));

}

bool judge(int a,int b,int x,int y)

{

bool flag=true;

for(int i=1;i<=n&&flag;i++)

if(!((bit[i])&x))

for(int j=1;j<=m&&flag;j++)

if(p[i][j])

if(!((bit[j])&y))

if(!((bit[aa(i,j)])&a))

if(!((bit[bb(i,j)])&b))

flag=false;

return flag;

}

6.三维扫描

floodfilled的加强版

posted on 2011-09-20 22:28 zyn.cpp 阅读(173) 评论(0)  编辑 收藏 引用