/*终于又开始写了，本来打算按上课的顺序写，但是发现不够有条理，于是先写基础算法*/
一、分治；
  将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
  //子问题如果有交集且无后效性就是动态规划了；
  问题：给定两个数a、b，计算'1'在a、b之间出现的次数。0 0 为结束标记（范围0<a,b<100,000,000）
input:
1 10
44 497
346 542
1199 1748
1496 1403
0 0
output:
2
185
40
666
113
代码:
#include <fstream>
using namespace std;
ifstream cin("1_1.in");
ofstream cout("1_1.out");
int d[11];
int value，i;
void deal(int n)
{
    if(n<=0)return;
    int one,ten;
    one=n%10;
    n/=10;
    ten=n;
    for(i=0;i<one;i++)d[i]+=value;
    while(ten)
    {
        d[ten%10]+=(one+1)*value;
        ten/=10;
    }
    for(i=0;i<10;i++)d[i]+=value*n;
    d[0]-=value;
    value*=10;
    deal(n-1);
}
int main()
{
    int i;
    int a,b;
    while(cin>>a>>b)
    {
        if(a==0&&b==0)break;
        if(a<b)swap(a,b);
        for(i=0;i<10;i++)d[i]=0;
        value=1;
        deal(a);
        value=-1;
        deal(b-1);
        cout<<d[1]<<endl;
    }
    //system ("pause");
    return 0;
}
//当然把最后的d[1]改一下也可以记录随便某数的出现次数；重点是void deal(int n);

二、递归（调用自身）；
经典问题：Hanoi塔；
input : 3
output:
move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c
代码：
#include <fstream>
using namespace std;
ifstream cin("hanoi.in");
ofstream cout("hanoi.out");
void move(int n,char x,char y)
{
    cout<<"move "<<n<<" from "<<x<<" to "<<y<<endl;
}
void hanoi(int n,char a,char b,char c)
{
    if(n==1)move(1,a,c);
    else
    {
        hanoi(n-1,a,c,b);
        move(n,a,c);
        hanoi(n-1,b,a,c);
    }
}
int main()
{
    int n;
    cin>>n;
    hanoi(n,'a','b','c');
    //system ("pause");
    return 0;
}
  
三、枚举（遍历所有可能解再排除错误）；
题目：木棒三角形；
      输入木棒总数和长度，挑三根组成直角三角形，输出最大面积。组不成输出"error";
input:
4
1 2 3 4
5
2 3 4 5 6
6
3 4 5 6 8 10
2
1 1
output:
error
6
24
error
代码：
#include <fstream>
using namespace std;
ifstream cin("1_3.in");
ofstream cout("1_3.out");
int main()
{
    int i,j,k,n;
    double ans;
    int len[110];
    while(cin>>n)
    {
        for(i=1;i<=n;i++)cin>>len[i];
        ans=-1;
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
                for(k=j+1;k<=n;k++)
                    if(len[i]*len[i]+len[j]*len[j]==len[k]*len[k])
                        if(0.5*len[i]*len[j]>ans)ans=0.5*len[i]*len[j];
    if(ans==-1)cout<<"error"<<endl;
    else cout<<ans<<endl;
    }
    //system ("pause");
    return 0;
}

四、贪心（每步只找一个最优解）；
问题：
A公司的电脑管理系统受到了千年虫病毒的攻击，A公司因此丢失了向MS公司做年终汇报的数据。
A公司目前掌握的数据是MS公司每次公布的公司盈亏报表，而MS公司公布盈亏的方式与众不同，它每次都是将连续5个月的盈或亏得总和做一次性的公布，因此A公司不知道每个月具体的盈亏状况。已知的情况是所有盈利月盈利固定为s，而亏损月亏损固定为d。
写一个程序，确定MS公司是否盈利，若盈利的话，那么可能的盈利最大值是多少。
Input
输入为两个正整数s和d。
Output
对于每一组的输入数据，若盈利的话，那么输出可能的盈利最大值是多少；若亏损的话，输出Deficit。
input:
59 237
375 743
200000 849694
2500000 8000000
output:
116
28
300612
Deficit
代码:
#include <fstream>
using namespace std;
ifstream cin("1_4.in");
ofstream cout("1_4.out");
int main()
{
    int i,ans;
    int s,d;
    while(cin>>s>>d)
    {
        for(i=1;i<=5;i++)
            if(s*(5-i)-d*i<0)break;
        if(i==4)ans=3*s-9*d;
        else ans=s*(12-2*i)-d*2*i;
        if(i==5||ans<0)cout<<"Deficit"<<endl;
        else cout<<ans<<endl;
    }
    //system ("pause");
    return 0;
}
//另有一普及组题目；
排座椅（seat.pas/c/cpp）
【问题描述】
上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。
【输入】
输入文件seat.in的第一行，有5各用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。
接下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。
输入数据保证最优方案的唯一性。
【输出】
输出文件seat.out共两行。
第一行包含K个整数，a1a2……aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道，其中ai< ai+1，每两个整数之间用空格隔开（行尾没有空格）。
第二行包含L个整数，b1b2……bk，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、…、第bL列和第bL+1列之间要开辟通道，其中bi< bi+1，每两个整数之间用空格隔开（行尾没有空格）。
【输入输出样例】
seat.in 
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4 
seat.out
2
2 4

上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。
代码：
#include <fstream>
using namespace std;
ifstream cin("seat.in");
ofstream cout("seat.out");
int main()
{
  int y[1010],x[1010],w[1010];
  int m,n,k,l,d;
  int x1,y1,x2,y2;
  int i,j;
  cin>>m>>n>>k>>l>>d;
  for(i=1;i<=m;i++)y[i]=0;
  for(i=1;i<=n;i++)x[i]=0;
  for(i=0;i<d;i++)
  {
    cin>>y1>>x1>>y2>>x2;
    if(x1==x2)
    {
      if(y1>y2)swap(y1,y2);
      y[y1]++;
    }
    else
      if(y1==y2)
      {
        if(x1>x2)swap(x1,x2);
        x[x1]++;
      }
  }
  //y
  for(i=0;i<=m;i++)
    w[i]=i;
  for(i=1;i<m;i++)
    for(j=i+1;j<=m;j++)
      if(y[i]<y[j])
      {
        swap(y[i],y[j]);
        swap(w[i],w[j]);
      }
  for(i=1;i<k;i++)
    for(j=i+1;j<=k;j++)
      if(w[i]>w[j])
        swap(w[i],w[j]);
  cout<<w[1];
  for(i=2;i<=k;i++)cout<<" "<<w[i];
  cout<<endl;
  //x
  for(i=0;i<=n;i++)w[i]=i;
  for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
      if(x[i]<x[j])
      {
        swap(x[i],x[j]);
        swap(w[i],w[j]);
      }
  for(i=1;i<l;i++)
    for(j=i+1;j<=l;j++)
      if(w[i]>w[j])swap(w[i],w[j]);
  cout<<w[1];
  for(i=2;i<=l;i++)cout<<" "<<w[i];
  cout << endl;
  //system ("pause");
  return 0;
} 
//在marcool上评测终于通过了！！！
return 0;