A - Factstone Benchmark

POJ2661
题意：
从1960年开始，每10年更新一次计算机的最长存储位数，其中，最开始的1960年字长为4位，以后每隔10年就增长一倍的长度。给你一个年份，问这一年时，计算机可以执行n！而不溢出的最大的n值。
思路：
我们可以用log的性质去求解；
解法一：

#include<iostream>
#include<stdio.h>
using  namespace std;
int n;
int main(){
while(~scanf("%d",&n)&&n){
   int p=1<<((n-1960)/10+2);//位数
   double sum=1;
   int k=1;
   for(int i=1;i<=p;i++)
     {
          sum*=2;
          if(sum>k){
           k++;
           sum/=k;
          }


     }
     cout<<k<<endl;
}
return 0;
}

解法二：

#include <iostream>
using namespace std;
int n;
int f[] ={ 3, 5, 8, 12, 20, 34, 57, 98, 170, 300, 536, 966, 1754, 3210, 5910, 10944, 20366, 38064, 71421, 134480, 254016};
int main()
{
    while (scanf("%d", &n), n)
    {
        n = (n - 1960) / 10;//位数
        printf("%d\n", f[n]);
    }
    return 0;
}

B - Bridge

POJ2573
该题考一个方案选择
题意：
有一群人要过桥，但是他们一次只能过两个，而且他们还需要手电筒（只有一个），问他们所需的时间，以及人员安排！
思路：
方案一：先按时间排序，我们可以让最快的人去送一个人过去，然后送手电筒再回去!所以时间为 a[0]2+a[i]+a[j];
方案二：我们让最快送最慢，次快送次慢的人！a[0]+2a[i]+a[j];
ac代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int s[1050];
int main()
{
    int a;
    scanf("%d",&a);
    for(int i=0;i<a;i++)
        scanf("%d",&s[i]);
    if(a==1)
    {
        printf("%d\n%d\n",s[0],s[0]);
        return 0;
    }
    sort(s,s+a);
    int ans=a,cne,sum=0,d,e;
    while(ans>3)
    {
        int sum1=2*s[0]+s[ans-2]+s[ans-1];
        int sum2=2*s[1]+s[0]+s[ans-1];
        if(sum1>sum2)
            sum+=sum2;
        else
            sum+=sum1;
        ans-=2;
    }
    if(ans==3)
        printf("%d\n",sum+=s[0]+s[1]+s[2]);
    else
        printf("%d\n",sum+=s[1]);
    while(a>3)
    {
        if(s[0]+s[a-2]<2*s[1])
            printf("%d %d\n%d\n%d %d\n%d\n",s[0],s[a-1],s[0],s[0],s[a-2],s[0]);
        else
            printf("%d %d\n%d\n%d %d\n%d\n",s[0],s[1],s[0],s[a-2],s[a-1],s[1]);
        a-=2;
    }
    if(a==3)
        printf("%d %d\n%d\n%d %d\n",s[0],s[2],s[0],s[0],s[1]);
    else
        printf("%d %d\n",s[0],s[1]);
    return 0;
}

C - Ants

POJ1852
题意：在一根长为L的水平木棍上有一群数量为n的蚂蚁，它们以每秒1cm/s的速度走到木棍一端就会掉下去。现在知道它们的起始位置是距离木根左端点的x处。但是不知道它们爬行的方向。在相向而行的两只蚂蚁相遇后，它们会掉头往反方向走。问所有蚂蚁都落下木棍的最快时间和最慢时间。

题解：一开始觉得可以暴搜，每只蚂蚁只有两种情况，不过掉头的事情感觉很复杂。时间复杂度为2的n次幂。肯定超时。 因为是同时出发的，相遇时的两只蚂蚁用的时间是相同的，我们可以无视蚂蚁的区别，当两只蚂蚁相遇时它们保持原样交错而行。这样每只蚂蚁都是独立运动的，那么只要找每只蚂蚁掉下去的时间就行了。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int main(){
int l,n,t;
cin>>t;
while(t--){
cin>>l>>n;
for(int i=0;i<n;i++)cin>>a[i];
int minx=0;
int maxy=0;
for(int i=0;i<n;i++)
 {
  minx=max(minx,min(a[i],l-a[i]));
  maxy=max(maxy,max(a[i],l-a[i]));
}
cout<<minx<<" "<<maxy<<endl;
}
return 0;

}

D - Matches Game

签到题：
就是简单的博弈论——————nim游戏！

#include<iostream>
#include<stdio.h>
using  namespace std;
int n,res;
int main(){
while(scanf("%d",&n)!=EOF){
    res=0;
  while(n--){
    int x;
    cin>>x;
    res^=x;
  }
  if(res)puts("Yes");
  else puts("No");
}
return 0;
}

E - Perfection

POJ1528
题意：
分解约数，简单的约数和！
思路：
判断n与约数和的关系！

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

代码：

#include<iostream>
#include<stdio.h>

using namespace std;
int main()
{
    int a[110],num=1,i,j;
    while(~scanf("%d",&a[num]),a[num])
    {
        num++;
    }
    printf("PERFECTION OUTPUT\n");
    for(i=1;i<num;i++)  
    {
        int sum=0;
        for(j=1;j<=a[i]/2;j++)
        {
            if(a[i]%j==0)
            {
                sum+=j;
            }
        } 
        if(sum==a[i])
        printf("%5d  PERFECT\n",a[i]);
        else if(sum>a[i])
        printf("%5d  ABUNDANT\n",a[i]);
        else 
        printf("%5d  DEFICIENT\n",a[i]);
    }
    printf("END OF OUTPUT\n");
    return 0;

}

F - The House Of Santa Claus

原题链接

题意：
画一个连通图,选择路径，走完所用道路！用DFS递归！

#include<iostream>

#include <string >

#include <cstring >

using namespace std;

int map[6][6];                 //在这里注意第一行时没有用的，全部设置为0

void makemap()

{

 memset(map,0,sizeof(map));

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

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

   if(i!=j)           //标记除了自己外不能访问自己

    map[i][j]=1;

 map[4][1]=map[1][4]=0;      //由于2和4  1和4不能直接相连，所以为0

 map[4][2]=map[2][4]=0;

}

void dfs(int x,int k,string s)

{

 s=s+char(x+'0');    //记录路径

 if(k==8)            //记录路径的长度

 {

  cout<<s<<endl;

  return ;

 }

 for(int y=1;y<=5;y++)

  if(map[x][y])

  {

   map[x][y]=map[y][x]=0;

   dfs(y,k+1,s);              //递归求出所有路线

   map[x][y]=map[y][x]=1;//恢复原形状

  }

}

int main ()

{

 makemap();

 dfs(1,0,""); //第三个参数为路径字符串

  return 0;

}

G - WERTYU

原题链接

思路：

（C/cpp语言中）每输入一个字符，都可以直接输出一个字符，因此getchar是输入的理想方法。问题在于：如何进行这样输入输出变换呢？一种方法是使用if语句或者switch语句，如”if(c == ‘W’) putchar(‘Q’)“。但很明显，这样做太麻烦。一个较好的方法是使用常量数组。

#include<iostream>
#include<stdio.h>
char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
int main() {
    int i, c;
    while ((c = getchar()) != EOF) {
        for (i = 1; s[i] && s[i] != c; i++);
        if (s[i]) putchar(s[i - 1]);
        else putchar(c);
    }
    return 0;
}

1、在常量数组c中为什么有 ‘\ ‘’ 这”两个“字符呢？实际上我们应该想到转义字符这个概念。不只是在C语言中，在Java、Cpp中也同样，用 \ 这个字符（没错，它是一个字符）来表示真正意义上的反斜线即 \ 。

2、关于while((c = getchar()) != EOF)这段代码，实际上是每输入一个字母或数字，循环就会执行一次，有兴趣的同学可以把上面的注释去掉，看看循环的次数。

3、关于for (i = 1; s[i] && s[i] != c; i++); 这个循环的在代码中作用，用来找到输入当前字母的位置，找到得到 i, 用于下面的操作。

此循环在操作意义上，相当于：for (i = 1; s[i] && s[i] != c; i++){ ;} 即单纯做循环，不做具体操作。

H - Prime Path

原题链接
题意：给两个质数n,m，每次只能改变n中的一个数字且改变后的数字依旧是一个质数，问最少需要多少步可以将n变成m。
方法：
此题需要先打出一个素数表，然后在广搜，分别将n中的每一位遍历即可。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
int num[10005];
void prime(int a, int b)
{
    int c;
    for(int i = a; i<=b; i++)
    {
        int s = sqrt(i+0.5);
        c = 0;
        for(int j = 2;  j<=s; j++)
        {
            if(i%j == 0)
            {
                c = 1;
            }
        }
        if(c == 0)
        {
            num[i] = 1;
        }
    }
}
int ban(int i,int s){
    int c;
    char a[6]={0};
    sprintf(a,"%d",s);
    a[i]='0';
    sscanf(a,"%d",&c);
    return c;
}
int bfs(int a,int b){
      queue<int>q;
      q.push(a);
      int arr[10000]={0};
      arr[a]=1;
      while(q.size()){
          int t=q.front();
          q.pop();

          if(t==b)return arr[t];

          int n=1000;
          for(int i=0;i<4;i++)
           {
               int g=ban(i,t);
               for(int j=0;j<=9;j++)
               {
                   int h=g+n*j;
                   if(num[h]==1&&arr[h]==0)
                   {
                       arr[h]=arr[t]+1;
                       q.push(h);
                   }
                   }
                   n/=10;
           }
      }

}
int main(){
    int m;
    prime(1000,10000);
    cin>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        cout<<bfs(a,b)-1<<endl;

    }
    return 0;
}

I - Soundex

题意：
26个字母分别对应了不同的值，现在给一个字符串，按照如下规则输出：
1）如果字母有值，则考虑输出;否则不输出。
2）多个拥有相同值的字母并列，仅输出一个值。
思路：
直接比较，如果对每一个字符进行取值，取上一次不同字符值的值last，进行比较，如果本字符有值（不为0），且不同于上一次的值last，就输出其值。
注意点：
1）注意打表正确（hhh）。
2）无论这个值是否输出，皆保存本次值为last。

#include<iostream>
using namespace std;
char a[30];
int map(char a)

{
    if(a=='B'||a=='F'||a=='P'||a=='V') return 1;
    if(a=='C'||a=='G'||a=='J'||a=='K'||a=='Q'||a=='S'||a=='X'||a=='Z') return 2;
    if(a=='D'||a=='T') return 3;
    if(a=='L') return 4;
    if(a=='M'||a=='N') return 5;
    if(a=='R') return 6;
    else return 0;

}
int main()
{
    while(gets(a))
    {
    int l=strlen(a);
        for(int i=0,now=0,last=0;l-i;i++)
        {
        now=map(a[i]);
            if(now&&now!=last)
            {
                cout<<now;
            }
            last=now;
        }
        cout<<endl;
    }
}

J - Goldbach’s Conjecture

原题链接
题目大意：

 给定一个大于4的数num，求两个奇素数使得num = p1 + p2.

解题报告：
其实这一性质可以当一个结论去记住。。。给定一个大于4的偶数num，求两个奇素数使得num = p1 + p2.不难分析出给出的num一定是个偶数（因为奇+奇=偶）。另外我们只需要从小到大遍历其中一个，然后看另一个是否在里面就可以了，不需要双重循环。因为我们通过其中一个，和num，就可以推断出另一个是多少，所以不需要在进行一轮循环，做了很多无用的操作。

模板：

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

AC代码：

#include<iostream>
#include<algorithm>
using namespace std;
bool prime(int n)
{
    if(n==2)
        return true;

    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false;

    return true;
}
int main()
{
    int n;
    while(~scanf("%d",&n)&&n)
    {
        bool flag=true;
        for(int i=3;i<=n;i+=2)
        {
            if(prime(i)&&prime(n-i))
            {
                printf("%d = %d + %d\n",n,i,n-i);
                flag=false;
                break;
            }
        }

        if(flag)
            printf("Goldbach's conjecture is wrong.\n");
    }

    return 0;

}

小结

dayone感觉重在与让我们放松，基本知识点有质数，约数与nim，还有DFS,BFS!相对来说比较简单，但是代码个别错误，以及输入输出的处理，和题型模板的流畅度不佳！