usaco-1.5-总结

1.5.1

动态规划。从下往上走。

对于走到的每一个点，都为这个点，和这个点下面两个点中最大的那个点的和。

1.5.2

可以先找出所有的回文数。然后在对所有的回文数判断素数。

注意：偶数的回文数一定不是素数，因为可以被11整除。

1.5.3

可以先求出依次求出1~8位数中是素数的数，只有尾数是1，3，7，9的时候才可以是素数。

/*
ID: rowanha3
LANG: C++
TASK: sprime
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int num[1000000]={2,3,5,7};
int shu[4]={1,3,7,9};
int biao[10];
int pan(int x)
{int i,n;n=sqrt(x);for(i=2;i<=n;i++){if(x%i==0)return 0;}return 1;
}
void dos()
{int l=0;int r=4;int s;int leap=4;int i,j,k;for(i=2;i<=8;i++){biao[i]=leap;for(j=l,l=r;j<r;j++){for(k=0;k<4;k++){s=num[j]*10+shu[k];if(pan(s))num[leap++]=s;}}r=leap;}biao[i]=leap;
}
int main()
{freopen("sprime.in","r",stdin);freopen("sprime.out","w",stdout);dos();int n,i;cin>>n;for(i=biao[n];i<biao[n+1];i++){printf("%d\n",num[i]);}fclose(stdin);fclose(stdout);return 0;
}

n皇后问题。

 n皇后问题的经典解法，记录每个皇后的位置。