以前和最近寫的幾題
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的加強版
#include<cstdio>
#include<cstring>
#include<iostream>
bool Hash[51][51][51];
int place[51][51][51];
int x[8]={1,-1,0,0,0,0};
int y[8]={0,0,1,-1,0,0};
int z[8]={0,0,0,0,1,-1};
int A[51*51*51],B[51*51*51],C[51*51*51],Head,Tail;
int count=0;
inline int abs(int i){return (i>0?i:-i);}
int main(){
freopen("scan.in","r",stdin);
freopen("scan.out","w",stdout);
memset(Hash,true,sizeof(Hash));
int l,w,h,m;
scanf("%d %d %d",&l,&w,&h);
scanf("%d",&m);
for(int i=1;i<=l;i++)
for(int j=1;j<=w;j++)
for(int k=1;k<=h;k++)
scanf("%d",&place[i][j][k]);
for(int i=1;i<=l;i++)
for(int j=1;j<=w;j++)
for(int k=1;k<=h;k++)
if(Hash[i][j][k]){
//printf("'");
Hash[i][j][k]=false;
count++;
Head=1;
Tail=1;
A[Head]=i;
B[Head]=j;
C[Head]=k;
while(Head<=Tail){
//printf("%d %d %d %d\n",A[Head],B[Head],C[Head],place[A[Head]][B[Head]][C[Head]]);
for(int c=0;c<=7;c++)
if(Hash[A[Head]+x[c]][B[Head]+y[c]][C[Head]+z[c]]&&A[Head]+x[c]>=1&&A[Head]+x[c]<=l)
if(B[Head]+y[c]>=1&&B[Head]+y[c]<=w&&C[Head]+z[c]>=1&&C[Head]+z[c]<=h)
if(abs(place[A[Head]+x[c]][B[Head]+y[c]][C[Head]+z[c]]-place[A[Head]][B[Head]][C[Head]])<=m){
Tail++;
Hash[A[Head]+x[c]][B[Head]+y[c]][C[Head]+z[c]]=false;
A[Tail]=A[Head]+x[c];
B[Tail]=B[Head]+y[c];
C[Tail]=C[Head]+z[c];
}
Head++;
}
}
printf("%d",count);
return 0;
}