Brian Warehouse

#include <stdio.h>
int main()
{
    int i,a,b,c,d,days=0;
    while(1)
    {
        days++;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if (a+b+c+d == -4) break;
        for (i=d+1; ; i++) // pay attention: from d+1
        {
            if ((i-a)%23==0)
                if ((i-b)%28==0)
                    if ((i-c)%33==0)
                    {
                        printf("Case %d: the next triple peak occurs in %ld days.\n",days,i-d);
                        break;
                    }
        }
    }
    return 0;
}

Description

Input

Output

正宗水题，就是输入12个浮点数，让你求平均值，不解释。

#include<stdio.h>

int main()

{

 float i=0,m,s=0;

 for(;i<12;i++)

 {

  scanf("%f",&m);

  s+=m;  

 }

 printf("$%.2f\n",s/12);

 return 0;

}

正宗水题，题目把最主要的公式都给你了，只要计算1/2+1/3+1/4+......+1/(n+1) >= x中最小的n值即可，我这里的cards用的是整形，注意底下一定要乘以1.0，否则会让你调试的生不如死的，要不你就让cards 是浮点型，其他的不解释。
#include<stdio.h>

int main()
{
 int cards;
 float length,c;
 for(scanf("%f",&c); c!=0.0; scanf("%f",&c))
 {
  for(cards=0,length=0; length<c; )
  {
   cards++;
   length+=1/(cards*1.0+1);
  }
  printf("%d card(s)\n",cards);  
 }
    return 0;
} //180K  0MS

事先申明，该程序虽然AC，但是效率极其低下，低下到让人发指的程度，我也不知道为什么。估计是用了STL的原因，具体我也说不清楚。其实思路不难，就是将字符转化成对应数字，然后将结果存放在一个整型向量中，接收字符串用的是字符串向量，处理的时候跟一般的字符串处理时一模一样的。处理结束之后要进行字典排序，显然要用排序函数，可以用冒泡，选择，快排，甚至是Hash，但是据说STL的sort 效率比快排还要快。源程序后附加了MSDN上的一些简单解释。没有翻译！

Description

Input

Output

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // STL sort function
using namespace std;

char map[] = "2223334445556667#77888999#";
                  //ABCDEFGHIJKLMNOPQRSTUVWXYZ
void visited(char &ch) // visit and format strings
{
   if (ch >= 'A' && ch <= 'Z')
    ch=map[ch-'A']; // ch equals to its real number
}

int main()
{
    int N,i=0,j,flag=0;
 string s;
 vector<string> stored(100000); // be visited & stored (up to 100,000)
    cin>>N;
 vector<int> counter(N,1); // stored times
   
 for (; i<N; i++)
 {
  cin>>s;
  for (j=0; j<s.length(); j++) // MSDN
  {
   visited(s[j]);
   if (s[j]!='-')
   {
    stored[i] += s[j];
    if (stored[i].length()==3)
     stored[i] += '-'; // 487 -[3] 3279
   }
  }
 }
    sort(stored.begin(),stored.begin()+N); // Quicker than QuickSort!
 // should not used stored.end() !
 i=0; j=1;
    while (i<N)
 {
  while(stored[i] == stored[j])
  {
   counter[i]++;
   j++;
   flag=1;
  }
  i=j;
  j++;
 }
 
    if (flag)
  for (i=0; i<N; i++)
  {
   if (counter[i]>1)
    cout<<stored[i]<<" "<<counter[i]<<endl;
  } // must have { }
 else cout<<"No duplicates."<<endl;
  
 return 0;
}

Sort ：
Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate.

 
template<class RandomAccessIterator>
   void sort(
      RandomAccessIterator _First,
      RandomAccessIterator _Last
   );

分类开篇语: 第一个程序搞了好几天，发现了很多问题。POJ不保证按顺序做且更新速度肯定不会很快。有些题自己做不出来借鉴别人的会注明出处。很多算法都需要从网上找，第一题的大浮点数相乘的核心算法就是这样找来的。我心里明白，虽然AC了，但是边缘数据处理的很粗糙，我自己都发现几个bug了，但是依然AC了。

本题主要注意将字符串转化为实际的数字然后借鉴数制的思想来进行大数相乘。

Description

Input

Output

Sample Input

95.123 12
0.4321 20
5.1234 15
6.7592  9
98.999 10
1.0100 12

Sample Output

548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

编译器C++ 源码:

#include <iostream>
#include <string>
using namespace std;
#define MAX 255
  
int getnum(string s,int *c) // get real number of R
{ 
    int i=0,j=0,t[MAX];
    memset(t,0,sizeof(int)*MAX); // a stores 0
    
 while (i < 6) // R value 1 through 6
 {
  if (s[i] != '.')
  {
   t[j]=s[i]-'0';
   j++;
  }    
  i++;
 }     // a`s length = 5
    
 for (j=0; j<5; j++)
  c[j]=t[4-j]; // c stores in order from a
  
 for (i=0; s[i] != '.'; i++); // find decimal point
 return (5-i); // the position of . point
}
 
void multi(int *a,int *b) // big-multiplication
{ 
    int i=0,j,r=0,t[MAX];
    memset(t,0,sizeof(int)*MAX); // t stores 0
    
 for (; i<5; i++)
  for (j=0; j<255; j++)
   t[i+j] += a[i]*b[j]; // core algorithms!
 
 for (i=0; i<255; i++)
 {
  b[i]=(r+t[i])%10; // r always stores remainder
  r=(r+t[i])/10;   // b stores the result
 }     
}    // basic algorithms of b-m
int main() 
{ 
    int i,j,d_pos,n,a[MAX],b[MAX];
    string s;
    while (cin>>s>>n)
 {
  
  memset(b,0,sizeof(int)*MAX);
  memset(a,0,sizeof(int)*MAX);
  d_pos=getnum(s,a);
  getnum(s,b);
  
  for (i=0; i<n-1; i++)
   multi(a,b);  // a is a loop invariant
  
  for (i=254; !b[i]; i--); //find last non-zero  
  for (j=0; !b[j]; j++); // find first non-zero
  
  for (; i >= n*d_pos; i--) // loop n times
   cout<<b[i];
  if (n*d_pos >= j+1) cout<<"."; //pay attention
  for (i=n*d_pos-1; i>=j; i--)
   cout<<b[i];  //from back formating output
  
  cout<<endl;
 }
 return 0;
}

1. 计算复杂性  O
　　这是描述一种算法需要多少 Running time 的度量。（也有空间复杂性，但因为它们能相互转换，所以通常我们就说时间复杂性。对于大小为 n 的输入，我们用含 n 的简化式子来表达。（所谓简化式子，就是忽略系数、常数，仅保留最“大”的那部分）。
　　比如找出 n 个数中最大的一个，很简单，就是把第一个数和第二个比，其中大的那个再和第三个比，依次类推，总共要比 n-1 次，我们记作 O(n) (对于 n 可以是很大很大的情况下，-1可以忽略不计了）。
　　再比如从小到大排好的 n 个数，从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找，最好情况是第一个就是 x，最坏情况是比较了 n 次直最后一个，因此最坏情况下的计算复杂度也是 O(n)。还有一种方法：先取中间那个数和 x 比较，如偏大则在前一半数中找，如偏小则在后一半数中找，每次都是取中间的那个数进行比较，则最坏情况是 lg(n)/lg2。忽略系数lg2，算法复杂度是O(lgn)。
　　
2. 计算复杂性的排序
　　根据含 n 的表达式随 n 增大的增长速度，可以将它们排序：1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常数）< ... < 2^n （不用死记，想象它们的函数曲线，一看便明）。最后这个 2 的n 次方就是级数增长了，读过棋盘上放麦粒故事的人都知道这个增长速度有多快。而之前的那些都是 n 的多项式时间的复杂度。为什么我们在这里忽略所有的系数、常数，例如 2*n^3+9*n^2 可以被简化为 n^3？老师上课也没有说原因，所以我也不知道。但是如果对对 (2*n^3+9*n^2)/(n^3) 求导，结果是0，仔细想想，我也没有想出所以然来。
　　
3. P 问题

      对一个问题，凡是能找到计算复杂度可以表示为多项式的确定算法，这个问题就属于 P (polynomial) 问题。
　　
4. NP 问题
　　NP 中的 N 是指非确定的(non-deterministic）算法，这是这样一种算法：

（1）猜一个答案。（2）验证这个答案是否正确。（3）只要存在某次验证，答案是正确的，则该算法得解。
　　NP (non-deterministic polynomial)问题就是指，用这样的非确定的算法，验证步骤（2）有多项式时间的计算复杂度的算法。
　　
5. 问题的归约
　　想象一下函数的映射是怎么一回事吧。这个概念需要弄懂。
　　大致就是这样：找从问题1的所有输入到问题2的所有输入的对应，如果相应的，也能有问题2的所有输出到问题1的所有输出的对应，则若我们找到了问题2的解法，就能通过输入、输出的对应关系，得到问题1的解法。由此我们说问题1可归约到问题2。

　　再给一个我找到的高端解释：

问题归约是人求解问题常用的策略，其把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。只有当这些子问题全部解决时，问题才算解决，问题的解答就由子问题的解答联合构成。问题归约可以递归地进行，直到把问题变换为本原问题的集合。所谓本原问题就是不可或不需再通过变换化简的"原子"问题，本原问题的解可以直接得到或通过一个"黑箱"操作得到。 
　　
6. NP-Hard
　　有这样一种问题，所有 NP 问题都可以归约到这种问题，我们称之为 NP-hard 问题。
　　
7. NP完全问题 (NP-Complete)
　　如果一个问题既是 NP 问题又是 NP-Hard 问题，则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题，此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。