题目一（poj-2965）：传送门
思路：递归+枚举，遍历每一种情况，然后找出最小步骤的结果，与poj-1753类似。
#include<iostream>
#include<cstdio>
#include<cstring>
//#include<ctime>
using namespace std;
int x[],y[],xx[],yy[],ans=;
char str[];
int a[][];
void turn(int len)
{
int x=len/,y=len%;
for(int i=;i<;i++)
{
a[x][i]=!a[x][i];
a[i][y]=!a[i][y];
}
a[x][y]=!a[x][y];
}
bool pd()
{
for(int i=;i<;i++)
for(int j=;j<;j++)
if(a[i][j]!=) return false;
return true;
}
void dfs(int len,int num) //要用len,否则时间超限。
{
if(pd())
{
if(ans>num)
{
ans=num;
for(int i=;i<=ans;i++)
{
xx[i]=x[i];
yy[i]=y[i];
}
}
return ;
}
if(len>=) return ; //基准情形
dfs(len+,num);//先搜索
turn(len); //再变化
x[num+]=len/+;
y[num+]=len%+;
dfs(len+,num+); //记得回溯。
turn(len);
}
int main(void)
{
int i,j;
//int st=clock(),ed;
for(i=;i<;i++)
{
scanf("%s",str);
for(j=;j<;j++)
if(str[j]=='-') a[i][j]=;
else a[i][j]=;
}
dfs(,);
printf("%d\n",ans);
for(i=;i<=ans;i++)
{
printf("%d %d\n",xx[i],yy[i]);
}
//ed=clock();
//printf("time==%d\n",ed-st);
return ;
} //原来用x,y作为参数，时间超限
/*#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
using namespace std;
int a[10][10],mi=99;
int x[100],y[100],cnt=0;
int xx[100],yy[100];
char str[10];
bool pd()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(a[i][j]==1) return false;
return true;
}
void turn(int x,int y)
{
for(int i=0;i<4;i++)
{
a[x][i]=!a[x][i];
a[i][y]=!a[i][y];
}
a[x][y]=!a[x][y];
}
void dfs(int x1,int y1,int num)
{
if(pd())
{
if(mi>num)
{
mi=num;
for(int i=1;i<=num;i++)
{
xx[i]=x[i];
yy[i]=y[i];
}
}
return ;
}
if(x1*y1>9) return ; if(y1==3) dfs(x1+1,0,num);
else dfs(x1,y1+1,num);
turn(x1,y1);
x[num+1]=x1+1;y[num+1]=y1+1;
if(y1==3) dfs(x1+1,0,num+1);
else dfs(x1,y1+1,num+1);
turn(x1,y1);
}
int main(void)
{
int i,j;
int st,ed;
st=clock();
for(i=0;i<4;i++)
{
scanf("%s",str);
for(j=0;j<4;j++)
if(str[j]=='+') a[i][j]=1;
else a[i][j]=0;
}
dfs(0,0,0);
printf("%d\n",mi);
for(i=1;i<=mi;i++)
{
printf("%d %d\n",xx[i],yy[i]);
}
ed=clock();
printf("time==%d\n",ed-st);
return 0;
}*/
题目二（poj-2368）：传送门
思路：巴什博奕，求出使后者成功的最小的L，就是求n的非一最小因子-1，要用素数筛法，否则超时。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = ;
int a[maxn];
int main(void)
{
int n,i,m;
while(~scanf("%d",&n))
{
int len=;
for(i=;i*i<=n;i++)
{
if(n%i==)
{
a[len++]=i;
a[len++]=n/i;
}
}
sort(a,a+len);
int fg=;
for(i=;i<len;i++)
{
if(a[i]>=)
{
fg=;
printf("%d\n",a[i]-);
break;
}
}
if(fg==) printf("0\n");
}
return ;
}
总结：递归不要忘记确立分清楚基准情况，先搜索，再回溯。