C++博客-SunKai's Blog

数独推理解答程序代码

SunKai — Sat, 05 Apr 2008 10:52:00 GMT

摘要: 解答程序介绍及编译后的程序下载:http://www.cppblog.com/sunkai/archive/2008/04/04/46250.htmlGCC下编译测试通过 /* Author: Sun Kai (S.K) E-mail: sunkai [at] msn [dot]&n... 阅读全文

SunKai 2008-04-05 18:52 发表评论

数独推理解答程序

SunKai — Fri, 04 Apr 2008 03:55:00 GMT

下载地址:http://www.cppblog.com/Files/sunkai/sudoku.rar
由于只是为了描述算法并进行科学计算,我并没有编写很友好的GUI,只是在控制台下工作,不过算法为推理算法,它将模拟人解数独的思维进行推理,如果推理失败还可以用搜索算法解答,因此,只要输入的数独有解,那么就一定可以在较短时间内解出
RAR包内有两个程序,二者核心相同,只是表示方法不同,它们都只需要输入一个用数字描述的数独问题
数独中未知数用0表示,例如:
302008000000005001000000320840290000190000062000063049051000000900700000000500706
输入后其中一个名为sudoku_单步跟踪.exe程序在输入一个数独问题后按两次回车后开始推理过程,每推出一步输出一次并暂停,按回车可以继续进行下一步推理,直到出结果
另一个名为sudoku_非单步跟踪.exe的程序在输入一个数独问题后按一次回车后就自动推理(不暂停),同样显示每步推理信息,直到输出结果
以下提供多组数据供测试:
302008000000005001000000320840290000190000062000063049051000000900700000000500706

002000000105042000090005801040160000500000008000039040704900050000250104000000300

900007000080000602005102400000009516000000000651400000003908100408000060000200009

008000000000006070302700045000520060070000010050098000680001207010300000000000300

020090300000005000400600120900106078000000000170908006054009001000500000007030090

000000000040026009930008100003009074700000008890100300008700036300280040000000000

900104007480000020000205400102306709000000000508407306009508000010000040300609002

004003000700000000091607043000780069900000007210096000180305670000000008000900300

000090008010003650000100230170800000900246001000007082023001000081300040500060000

000040020000006010000810576730002100500000007009500082952038000060200000070050000

090003000000070600080000420010602500500000008003801060036000070005020000000300080

100004000000900080830050200300009070760305019080400006006010038070003000000600005

060000007000306090000010650008700560047000230051002400023050000090607000800000020

005000300000300904000054617010080000400501003000030070358760000204005000001000700
程序代码可能在日后公开

SunKai 2008-04-04 11:55 发表评论

习题 46：Monkey And Banana ★★★★

SunKai — Fri, 04 Apr 2008 03:20:00 GMT

习题 46：Monkey And Banana ★★★★


问题描述：
有一班科学家正在设计一个测试猴子IQ的试验。他们 把一只“banana”吊在天花板，而且同时给猴子一些箱子。如果猴子聪明的话，它们会把箱子一个个叠起来做成一个塔子来取得食物。科学家有n种箱子，而且每一种箱子都有好多个。第 i 种箱子有三维（xi,yi,zi)。箱子可以用它的任意一面作底面来摆放，也就是它的三维之中可以任选两条来做它的底面长和宽。科学家想确定箱子叠到最高的时候是可以到达天花板的。现在问题是，要叠起一个塔子，上下摆放的两个箱子，在上的箱子的底面长宽必须严格小于在下的箱子的底面长宽,留下些地方让猴子落脚来爬上去。也就是说，底面面积相等的箱子不能叠放。现在你的任务是利用所给定的箱子，决定塔子最高能达到的高度

输入：
输入数据有多组测试数据。
每一组测试数据的第一行是一个整数n，表示不同三维的箱子的总数。n最大为30。
以下的n行每一行有三个正整数，表示该箱子的三维xi,yi和zi。
当n=0的时候输入结束。

输出：
对应每组测试数据，输出一行包括数据组号case（从1开始）和塔子最高高度height，
并按照一下格式： "Case case: maximum height = height" 

样例输入
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

样例输出
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342 

难度：Difficult

#include
#include
typedef struct
{
        int a,b,c;
} data;
data x[90];
int d[90];
int n;
int dfs(int q)
{
    int i,best=0;
    if(d[q]) return d[q];
    for(i=0;i{
      if(x[i].a{
        if(best<dfs(i)) best=dfs(i);
      }
    }
    d[q]=x[q].c+best;
    return d[q];
}
int main(void)
{
    int i,k=1,a,b,c;
    int best;
    while(scanf("%d",&n),n!=0)
    {
      n*=3;
      best=0;
      memset(d,0,sizeof(d));
      for(i=0;i{
        scanf("%d%d%d",&a,&b,&c);
        x[i].a=a; x[i].b=b; x[i].c=c;
        if(x[i].a>x[i].b) x[i].a^=x[i].b^=x[i].a^=x[i].b;
        i++; x[i].a=a; x[i].b=c; x[i].c=b;
        if(x[i].a>x[i].b) x[i].a^=x[i].b^=x[i].a^=x[i].b;
        i++; x[i].a=b; x[i].b=c; x[i].c=a;
        if(x[i].a>x[i].b) x[i].a^=x[i].b^=x[i].a^=x[i].b;
      }
      for(i=0;i{
        if(best<dfs(i)) best=dfs(i);
      }
      printf("Case %d: maximum height = %d\n",k++,best);
    }
    return 0;
}

SunKai 2008-04-04 11:20 发表评论

整数分解问题

SunKai — Fri, 04 Apr 2008 03:15:00 GMT

/*
问题描述：
大于1的正整数n可以分解为n=x1 * x2 * ... * xn
例如n=12时
12=12
12=6*2
12=4*3
12=3*4
12=3*2*2
12=2*6
12=2*3*2
12=2*2*3

1<=n<=2000000000
*/
/*
分析：
DP之记忆化搜索
状态若用d[2000000000]则内存不足
因此采用结构体记录状态
经过简单数学推理，对于一个数N,它的因子数不超过N^(1/2)+1
使用二分法查找
时间复杂度最终为O(N^1.5logN)
*/
#include
#include
struct DP
{
    int num;
    int sum;
} d[50000]={0};
int max=0;
void qsort(int low,int high,struct DP key[])
{
     int i=low,j=high;
     struct DP tag=key[i];
     if(i     {
            do
            {
              while(tag.num              if(i              {
                key[i]=key[j];
                i++;
                while(tag.num>=key[i].num && i                if(i                {
                  key[j]=key[i];
                  j--;
                }
              }
            }while(i            key[i]=tag;
            qsort(low,j-1,key);
            qsort(i+1,high,key);
     }
}
int dfs(int left)
{
    int i,p;
    int l,r,m;
    int count=0;
    l=0; r=max;
    while(l<=r)
    {
      m=(l+r)>>1;
      if(d[m].num    }
    p=l; if(d[p].sum) return d[p].sum;
    for(i=1;i<=d[i].num;i++)
    {
      if(left%d[i].num==0) count+=dfs(left/d[i].num);
    }
    d[p].sum=count;
    return count;
}
int main(void)
{
    int i,j,tmp;
    int n;
    scanf("%d",&n); tmp=sqrt(n);
    for(i=1;i<=tmp;i++)
    {
      if(n%i==0)
      {
        d[max].num=i; max++;
        d[max].num=n/i; max++;
      }
    } max--;
    qsort(0,max,d);
    d[0].sum=1;
    printf("%d\n",dfs(n));
    return 0;
}

SunKai 2008-04-04 11:15 发表评论

习题69：数素数★★

SunKai — Fri, 04 Apr 2008 03:10:00 GMT

习题69：数素数★★

题目描述：
素数是的只能被1和它本身整除的自然数。
判断一个数是素数的方法是使用2到小于该数的数除它，
若有能整除的则该数不是素数。

输入：
多组测试数据，每组一行，每行是两个整数m,n(1<= m,n <=4000000)，
遇到EOF标志结束程序

输出：
输出一个整数，表示介于m,n之间（包括m,n）的素数的数量

样例输入：
5 10
1 3
6 8

样例输出：
2
2
1

提示：
虽然内存限制有64M大小，但也要节约空间~~

难度：Easy

*/
#include
#include
int S[2000]={
0,309,255,237,227,226,215,212,219,210,202,205,208,193,206,190,198,204,192,190,190,
207,183,180,193,188,193,184,198,189,176,184,179,192,172,189,186,184,184,175,185,
178,176,185,179,172,188,184,168,179,187,166,180,173,175,175,172,175,175,175,183,
175,171,179,172,174,164,188,164,184,164,163,179,176,175,177,168,170,165,173,164,
168,167,161,175,173,160,170,184,162,171,179,163,168,169,167,168,173,161,167,162,
168,175,179,156,168,157,171,168,167,167,163,173,173,157,161,152,169,168,168,168,
164,172,165,162,167,153,167,155,168,164,177,163,169,151,170,156,159,174,161,161,
147,173,161,153,161,151,167,162,176,164,153,158,164,160,170,173,164,161,166,166,
161,162,163,156,167,149,162,161,160,164,162,162,165,163,152,157,159,159,162,162,
146,148,159,171,151,160,154,163,161,151,168,172,163,149,160,154,150,151,152,165,
162,150,169,153,168,150,162,158,154,163,161,164,170,146,155,162,171,153,141,166,
157,143,162,149,148,150,161,153,171,160,153,163,165,157,159,156,142,152,166,159,
152,167,155,162,155,143,166,149,156,157,151,149,174,154,164,153,158,155,157,151,
153,155,155,148,156,152,148,157,158,151,160,154,144,168,150,143,151,155,163,156,
151,162,154,156,158,149,174,148,142,158,160,154,147,157,156,155,150,159,159,148,
160,160,148,152,153,143,144,147,160,157,154,136,152,146,161,151,154,152,153,160,
143,149,164,144,167,146,145,153,161,148,144,164,159,147,153,157,153,144,153,155,
155,144,152,156,157,164,151,154,139,159,138,150,157,164,150,153,145,154,156,148,
156,148,151,128,147,156,148,152,160,138,159,158,149,159,150,155,155,152,142,150,
151,161,146,152,154,147,155,158,147,157,156,142,145,152,142,160,146,150,153,138,
163,157,158,152,141,151,163,137,149,148,146,153,146,151,147,153,141,148,157,147,
155,151,156,152,156,148,136,161,142,159,149,148,153,152,138,155,150,148,152,140,
144,153,152,165,152,139,137,148,155,146,156,162,143,151,137,150,156,143,145,158,
146,145,142,146,152,144,148,135,145,158,154,150,144,143,164,143,148,143,134,146,
147,158,131,154,144,142,159,146,153,156,145,149,167,138,151,148,151,150,152,145,
153,145,152,129,159,147,147,135,155,150,143,145,149,140,146,144,149,141,132,158,
142,152,149,145,152,149,140,166,144,142,142,146,149,149,160,146,142,147,149,157,
146,154,153,151,145,153,127,156,139,140,148,153,150,154,150,136,144,144,143,144,
139,157,144,145,153,155,142,171,149,143,146,145,139,145,150,160,155,147,154,145,
151,144,153,140,146,143,142,145,134,139,135,156,157,141,155,141,141,142,155,138,
142,149,130,136,153,147,139,153,146,157,144,133,159,144,151,144,150,147,151,148,
151,149,132,141,150,141,147,147,158,146,134,144,140,148,143,147,147,141,142,151,
143,137,143,152,134,168,143,147,137,132,153,137,147,149,147,154,138,141,132,150,
142,148,144,144,148,147,139,144,152,140,138,151,157,151,147,129,153,142,139,140,
149,156,163,146,137,138,136,148,148,154,123,130,142,145,140,150,156,136,154,148,
159,141,149,143,139,142,152,141,139,149,160,135,140,152,147,148,128,147,141,147,
128,157,154,142,150,137,140,157,146,153,140,133,146,144,162,148,143,149,144,137,
147,142,138,142,148,134,143,133,137,147,146,143,147,131,142,149,147,137,146,148,
143,152,132,141,146,139,140,155,140,145,133,147,135,146,132,144,145,134,150,136,
142,144,160,149,143,134,152,127,146,135,151,144,140,146,154,143,142,156,147,131,
130,136,148,148,137,150,128,154,152,137,138,146,127,153,154,150,133,149,145,155,
142,133,137,142,135,146,146,137,147,154,152,131,141,143,144,140,136,145,137,150,
140,127,148,145,136,141,141,139,140,154,134,141,145,146,158,152,137,136,136,124,
134,144,143,147,143,130,154,136,155,145,146,139,143,126,151,145,148,132,156,141,
131,152,145,150,141,136,149,130,139,139,154,149,148,142,146,146,123,131,138,153,
143,138,150,130,145,156,145,147,140,145,150,144,141,142,136,139,146,138,153,133,
145,143,145,141,152,138,137,140,132,138,137,148,145,148,143,148,143,136,133,142,
154,148,140,142,139,135,145,150,142,141,150,131,139,140,154,131,135,150,135,140,
132,130,134,138,128,148,151,139,152,132,147,136,142,143,150,151,135,142,141,141,
156,139,137,156,137,142,140,147,127,145,147,138,155,140,138,132,138,151,133,137,
134,140,140,132,156,145,134,151,136,139,148,140,134,133,136,149,129,137,149,150,
132,145,131,139,139,149,140,141,149,138,140,135,146,144,136,131,143,139,144,155,
129,141,133,150,137,145,144,146,134,133,145,140,148,154,146,139,136,129,146,138,
146,132,148,142,133,128,148,138,145,140,140,140,140,123,140,137,143,147,142,143,
135,132,137,132,132,145,139,158,140,134,145,148,132,135,137,135,151,144,122,135,
146,154,147,146,127,151,142,145,146,151,147,128,144,132,122,137,144,136,143,140,
139,135,145,153,133,130,142,147,141,130,133,133,138,138,137,134,151,126,137,146,
141,137,140,140,136,126,145,141,131,144,131,150,135,146,148,137,142,130,149,120,
144,138,148,141,128,155,147,139,133,126,153,148,124,147,134,135,128,140,151,139,
146,134,152,123,145,139,131,134,143,135,130,151,130,146,137,143,136,158,131,134,
145,144,133,150,129,130,145,138,131,141,137,138,133,145,153,131,134,138,138,143,
132,150,140,141,136,134,146,139,131,133,141,138,160,140,133,151,140,135,126,147,
127,134,143,128,150,124,148,146,129,139,150,139,125,147,132,147,136,147,152,129,
157,142,132,142,139,133,138,144,139,137,133,136,130,135,141,141,143,148,134,126,
144,138,132,132,156,156,120,140,128,150,137,152,132,141,145,129,146,147,138,134,
139,143,133,122,137,136,148,127,145,133,139,139,143,147,134,144,138,139,143,127,
150,138,142,137,140,143,141,155,118,142,128,125,144,141,130,127,130,147,142,141,
132,144,126,143,131,135,138,141,147,135,141,142,128,139,145,130,137,137,136,147,
139,127,127,149,136,131,145,140,145,146,126,158,145,150,131,142,141,145,143,135,
116,143,141,154,139,151,135,133,141,121,153,139,133,138,127,140,132,140,134,150,
135,131,137,136,132,128,142,136,139,135,141,139,132,130,134,142,138,133,143,141,
144,126,140,134,135,151,132,142,140,126,139,135,130,146,147,135,119,141,131,136,
146,141,128,124,130,143,149,141,143,135,138,134,134,133,138,147,141,145,131,126,
139,143,135,149,133,132,154,128,139,133,154,131,127,138,130,134,133,142,142,129,
137,138,119,144,131,147,137,138,128,131,144,132,132,141,136,134,124,137,143,148,
138,145,140,139,141,129,143,144,146,138,138,140,121,124,135,147,138,144,137,128,
139,144,150,132,137,133,130,141,150,126,139,128,137,134,134,137,133,138,145,145,
135,147,127,122,139,149,138,132,150,138,130,137,120,148,148,131,139,143,139,139,
138,140,147,149,131,139,139,140,138,138,142,136,136,135,138,130,148,129,144,142,
143,139,131,129,133,144,130,136,133,134,137,145,139,130,146,136,134,129,136,146,
156,119,129,142,136,138,139,137,125,140,138,117,135,137,140,146,133,140,139,134,
130,131,133,152,133,142,128,132,127,139,136,152,131,130,138,138,129,134,128,124,
131,126,139,152,142,147,126,133,139,147,131,132,142,137,140,136,129,137,147,127,
136,148,137,131,143,147,137,134,138,126,140,133,137,143,128,143,144,135,145,140,
133,145,135,132,149,117,140,132,135,125,132,130,135,141,125,141,134,121,130,142,
121,128,133,129,141,140,135,124,145,118,151,141,120,132,149,136,135,122,139,133,
130,124,135,127,146,135,139,123,129,136,131,143,139,126,136,137,136,139,133,137,
141,135,141,141,125,125,136,134,137,135,132,152,129,123,134,144,142,133,143,133,
141,148,147,137,144,134,142,125,158,138,135,135,142,137,128,129,131,135,132,134,
135,126,121,127,132,152,131,125,142,141,126,144,137,140,140,152,144,123,130,135,
134,131,150,130,148,132,137,141,139,123,142,120,145,137,134,139,142,129,146,146,
140,141,140,127,142,132,123,140,124,132,144,147,140,126,139,135,114,123,136,139,
134,122,136,133,143,138,139,131,144,126,126,141,118,139,145,132,134,149,127,122,
156,127,145,143,138,137,146,136,119,144,139,127,132,137,132,148,131,135,134,143,
128,137,128,136,142,134,128,125,143,129,123,143,129,134,140,132,130,144,128,143,
147,142,135,134,127,127,133,138,142,143,126,133,130,143,126,136,144,140,141,138,
129,131,137,138,131,144,135,139,141,136,117,136,133,130,132,136,116,135,139,134,
144,139,142,124,131,123,136,129,120,149,130,119,139};
int m=0;
int n1,n2;
int i,k;
void sumx(int n1,int n2)
{
     for(i=n1;i     {
       m++;
       for(k=2;k<=sqrt(i);k++)
       if(i%k==0)
       {
         m--;
         break;
       }
     }
}
int main(void)
{
while(scanf("%ld%ld",&n1,&n2)!=EOF)
{
    m=0;
    if(n1>n2) n1^=n2^=n1^=n2;
    if(n1>>11!=n2>>11)
    {
      for(i=(n1>>11)+2;i<=n2>>11;i++) m+=S[i];
      sumx(n1,((n1>>11)+1)<<11);
      sumx((n2>>11)<<11,n2+1);
    }
    else
      sumx(n1,n2+1);
    if(n1==1) m--;
    printf("%ld\n",m);
}
return 0;
}

SunKai 2008-04-04 11:10 发表评论

习题 59：马的周游问题★★★★★- Special Judged

SunKai — Fri, 04 Apr 2008 03:07:00 GMT

/*
习题 59：马的周游问题★★★★★- Special Judged
题目描述：
这样一个8 * 8的国际象棋棋盘用以下的方法编号如下：
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

输入：
有多个测试，每个测试一行，
每行一个整数N(1<=N<=64)，表示马的起点。
最后一行用-1表示结束，不用处理。

输出：
对输入的每一个起点，求一条周游线路。对应地输出一行，
有64个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。
相邻的数字用一个空格分开。

样例输入：
4
-1

样例输出：
（无样例输出）

其它：
如果起点和输入给定的不同，重复多次经过同一方格或者有的方格没有被经过，都会被认为是错误的。

题目提供：
ailyanlu

Special Judged
难度：Very Difficult
*/

AC程序:
#include
int main()
{
    int i,n;
    int x[]={10,20,30,40,46,56,62,52,58,43,53,63,48,54,64,47,37,31,21,27,33,50,60,45,55,61,51,57,42,36,26,41,35,25,19,9,3,13,28,38,32,15,5,11,1,18,12,2,17,34,49,59,44,29,39,24,7,22,16,6,23,8,14,4};
    while(scanf("%d",&n),n!=-1)
    {
      i=0; while(x[i]!=n) i++; do printf("%d ",x[i++]); while(i<64);
      i=0; while(x[i]!=n) printf("%d ",x[i++]); printf("\n");
    }
}

附程序: 预先计算特殊表(循环表) 经过测试,输入10后可以得到以上AC程序中的特殊循环表
#include
#include
int map[65];
int line[65];
int dfs(int now,int time)
{
    int next;
    int i;
    int flag=0;
    if(time==65) return 1;
    map[now]=0;
    for(i=1;i<65;i++)
    {
      flag=0;
      {
      if(!map[i])
      {
        next=i+10;
        {
        if((i-1)%8<6 && next<65 && !map[next]) flag=1;
        else {
          next=i+6;
          {
          if((i-1)%8>1 && next<65 && !map[next]) flag=2;
          else {
            next=i+17;
            {
            if((i-1)%8<7 && next<65 && !map[next]) flag=3;
            else {
              next=i+15;
              {
              if((i-1)%8>0 && next<65 && !map[next]) flag=4;
              else {
                next=i-6;
                {
                if((i-1)%8<6 && next>0 && !map[next]) flag=5;
                else {
                  next=i-10;
                  {
                  if((i-1)%8>1 && next>0 && !map[next]) flag=6;
                  else {
                    next=i-15;
                    {
                    if((i-1)%8<7 && next>0 && !map[next]) flag=7;
                    else {
                      next=i-17;
                      if((i-1)%8>0 && next>0 && !map[next]) flag=8;
                    }
                    }
                  }
                  }
                }
                }
              }
              }
            }
            }
          }
          }
        }
        }
        if(!flag) return 0;
      }
      }
    }
    map[now]=1;
    next=now+10;
    if((now-1)%8<6 && next<65 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    next=now+6;
    if((now-1)%8>1 && next<65 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    next=now+17;
    if((now-1)%8<7 && next<65 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    next=now+15;
    if((now-1)%8>0 && next<65 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    next=now-6;
    if((now-1)%8<6 && next>0 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    next=now-10;
    if((now-1)%8>1 && next>0 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    next=now-15;
    if((now-1)%8<7 && next>0 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    next=now-17;
    if((now-1)%8>0 && next>0 && !map[next])
    {
      line[time]=next;
      map[next]=1;
      if(dfs(next,time+1)) return 1;
      map[next]=0;
    }
    return 0;
}
int main(void)
{
    int i,j,k;
    int n;
    while(scanf("%d",&n)!=-1)
    {
      memset(map,0,sizeof(map));
      map[n]=1; line[1]=n;
      dfs(n,2);
      for(i=1;i<65;i++) printf("%d ",line[i]);
      printf("\n");
    }
    return 0;
}

SunKai 2008-04-04 11:07 发表评论

习题 41：二进制环★★

SunKai — Fri, 04 Apr 2008 03:03:00 GMT

/*
E-mail: sunkai [at] msn [dot] com
Author: Sun Kai
2008.4.4

习题 41：二进制环★★

问题描述：
一个数，把它化成二进制后，例如3，转为0011后，串长为2^2，把它看成一个环0->0->1->1->0
两个相邻的数取出分别得到00 01 11 10，刚好把4以内的所有数都有且仅有一次表示了出来
又例如29，化为00011101后，串长为2^3，三个三个地取可得到
000 001 011 111 110 101 010 100，也刚好把8以内所有数有且仅有一次表示了出来

输入：
多组测试数据，输入一个数n(0<=n<=12)，找出串长为2^n的一个以0,1组成的字符串，
把它n个n个地取要能得到2^n以内所有的数，并且这个字符串所代表的数值要最小

输出：
对每组测试数据输出这样的一个串长为2^n的一个以0,1组成的字符串

样例输入：
1
3
0
2

样例输出：
01
00010111
ERROR
0011

其它提示：
输入为2的时候，不但0011可以，0110，1100，1001都可以，因为它是一个环。
但你不能输出1100，因为1100是10进制的12，比3(0011)要大，要输出最小的那个

难度：easy
*/
#include
#include
#include
char ok[4096];
char q[8192];
int n;
int size;
int dfs(int now) /* now : 当前待填数(0/1)下标 */
{
    int tmp;
    int sum;
    int i,j;
    if(now==size+n-1) return 1;
    if(now==size)
      for(i=now,j=0;j      {
        q[i]=q[j];
      }
    if(now>=n-1)
    {
      if(now      sum=0;
      tmp=n;
      for(i=now-n+1;i<=now;i++)
      {
          tmp--;
          if(q[i])
            sum+=pow(2,tmp);
      }
      if(!ok[sum])
      {
          ok[sum]=1;
          tmp=dfs(now+1);
          ok[sum]=0;
          if(tmp) return 1;
      }
      if(now      sum++;
      if(!ok[sum])
      {
          ok[sum]=1;
          tmp=dfs(now+1);
          ok[sum]=0;
          if(tmp) return 1;
      }
      q[now]=0;
    }
    else
    {
        q[now]=0;
        tmp=dfs(now+1);
        if(tmp) return 1;
        q[now]=1;
        tmp=dfs(now+1);
        if(tmp) return 1;
        q[now]=0;
    }
    return 0;
}
int main(void)
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
      if(n==0) { printf("ERROR\n"); continue; }
      memset(ok,0,sizeof(ok));
      size=pow(2,n);
      dfs(0);
      for(i=0;i      printf("\n");
    }
    return 0;
}

SunKai 2008-04-04 11:03 发表评论

习题 95：恶魔岛救公主(3)★★★★★

SunKai — Sat, 08 Mar 2008 10:42:00 GMT

/*
习题 95：恶魔岛救公主(3)★★★★★(Contest 12)
题目描述：
Goldfisher为了解救被绑架的未婚妻而来到了恶魔岛。
上岛前，一个神秘的印度人Yingnan告诉他恶魔岛处处布满陷阱，
给Goldfisher画了一个草图，如一个4*4的房间布局如下：
1 6 2 4
2 3 1 2
1 5 9 3
9 1 2 1
每前进一步，只能选择进入上下左右任一房间。
而Goldfisher首先将站在左上方的格子，
数字表示那个房间里藏着的魔法豆的数目，
Goldfisher每进入一个房间就要把那个房间里的所有魔法豆取走。
而他的未婚妻就在最右下方的房间中。
Goldfisher必须以最短的路线救走他的未婚妻并返回出发点，
并把他手上所有的魔法豆倒进时空机器，当有足够多的魔法豆，
时空机才会送他们回去。这时Goldfisher犯难了，
因为他不知道需要多少魔法豆才足够，所以希望尽可能多拿，
但问题又必须以最短的路线，否则被敌人发现的话，
就连自己也逃不掉了。他希望找出这样一条路线，
尽可能地短，并且能尽可能多取得魔法豆。
如上图应该走1-6-3-5-9-3-1(返回)-2-1-9-1-2-1
一共有1+6+3+5+9+3+1+2+1+9+1+2=43个魔法豆。
你能帮助Goldfisher找到正确的道路解救他的未婚妻吗？

输入：
有多个测试，每个测试第一行分别是两个整数m,n(2<=m,n<=100)，
接下来的m行n列按顺序地描述了这个地图上相应房间里的魔法豆的数目。
数目在0到10000之间（包括两端）。
最后当输入的m=n=0表示结束。

输出：
对于每个测试，输出当路线最短时，
最多可以得到的魔法豆的数目

样例输入：
4 4
1 6 2 4
2 3 1 2
1 5 9 3
9 1 2 1
3 4
0 1 1 0
1 0 1 0
0 1 1 0
0 0

样例输出：
43
6

其它信息：

难度：Very Difficult
*/
#include
#include
int map[256][256];
int d[2][256][256];
/* 阶段,X1,X2 */
int max(int a,int b)
{
    return a>b ? a : b;
}
int min(int a,int b)
{
    return a>b ? b : a;
}
int main(void)
{
    int m,n;
    int t;
    int x;
    int i,j,k;
    int *dst,*src,*temp;
    dst=&d[0][0][0];
    src=&d[1][0][0];
    while(1)
    {
      scanf("%d%d",&m,&n);
      if(m==0 && n==0) break;
      x=m+n-1;
      t=max(m,n);
      for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
          scanf("%d",&map[i][j]);
      memset(d,0,sizeof(d));
      for(i=1;i<=x;i++) /*i:阶段*/
      {
        temp=dst; dst=src; src=temp;
        for(j=1;j<=min(i,n);j++) /* X1 */
          for(k=1;k<=j;k++) /* X2 */
          {
            dst[j*256+k]=max(max(src[(j-1)*256+k-1],src[j*256+k-1]),
            max(src[(j-1)*256+k],src[j*256+k]));
            if(j==k) dst[j*256+k]+=map[i-k+1][k];
            else dst[j*256+k]+=map[i-j+1][j]+map[i-k+1][k];
          }
      }
      printf("%d\n",dst[n*256+n]);
    }
    return 0;
}

SunKai 2008-03-08 18:42 发表评论

习题 94：天神的羊群★★★

SunKai — Sat, 08 Mar 2008 10:40:00 GMT

/*
习题 94：天神的羊群★★★(Contest 12)
题目描述：
天神有一群羊，一共k只，要带它们去放牧。
草地上有一排距离不等的木桩，共有n个，n>=k。
现在天神需要把羊都拴在木桩上，一羊一桩，让羊在木桩周围吃草。
不过，天神的羊和普通的羊也很不一样，它们很聪明，并且很贪心，
还不喜欢看到别的羊比自己多占便宜。
为了能每只羊都能吃到一样多的草，拴羊的绳子都必须一样的长。
天神也知道它们的贪心，所以也想办法尽可能满足它们，
希望绳子能尽可能地长。但同时，不能让同一地方的草，
能同时被两只以上的羊吃到，这样它们会打架抢地盘的，
并且那样就会不公平了，就会有羊吃的比其它的羊要少。

输入：
第一行依次有两个整数n,k，其中2<=k<=n<=100000，
接下来一行有n个整数，代表木桩的位置，范围从-1e9到+1e9

输出：
输出距离最近的两只羊之间的最大距离

样例输入：
5 3
2 5 1 10 7

样例输出：
4

其它信息：
把这三只羊安排在1,5,10三根桩上，距离最近的两只羊之间
的距离是5-1=4，而其它的安排方法没有比4更大的，
所以4就是结果。

难度：Normal
*/
#include
int n,k;
int l[100001];
void qsort(int low,int high,int key[])
{
     int i=low,j=high,tag=key[i];
     if(i     {
            do
            {
              while(tag              if(i              {
                key[i]=key[j];
                i++;
                while(tag>=key[i] && i                if(i                {
                  key[j]=key[i];
                  j--;
                }
              }
            }while(i            key[i]=tag;
            qsort(low,j-1,key);
            qsort(i+1,high,key);
     }
}
int main(void)
{
    int i,j,t,count;
    int mid,max,min=0;
    scanf("%d%d",&n,&k); t=k-1;
    for(i=1;i<=n;i++) scanf("%d",&l[i]);
    qsort(1,n,l);
    for(i=2;i<=n;i++) if(l[i]-l[i-1]>min) min=l[i]-l[i-1];
    max=(l[n]-l[1])/t; mid=(max+min)/2;
    while(max>=min)
    {
      count=t,j=l[1];
      for(i=2;i<=n;i++)
      {
        if(!count) break;
        if(l[n]-l[i]<(count-1)*mid) break;
        if(l[i]-j>=mid)
        {
          j=l[i];
          count--;
        }
      }
      if(count) max=mid-1; else min=mid+1;
      mid=(max+min)>>1;
    }
    printf("%d\n",mid);
    return 0;
}

SunKai 2008-03-08 18:40 发表评论

习题 92：高精度算阶乘★★

SunKai — Sat, 08 Mar 2008 10:30:00 GMT

/*
习题 92：高精度算阶乘★★
题目描述：
算出n!的完整结果，其中n!=1*2*3*...*n

输入：
多组测试数据，一行一组，每行仅一个数n
其中0<=n<=10000

输出：
输出相应的n!的结果，必须精确到个位

样例输入：
10
20
100

样例输出：
3628800
2432902008176640000
933262154439441526816992388562667004907159682643816214685929
638952175999932299156089414639761565182862536979208272237582
51185210916864000000000000000000000000

其它信息：
最后一个100!的结果由于过长，故拆分成三行，每行60字符，请见谅

难度：Easy
*/
#include
#define SIZE 8000
#define DS 7998
unsigned x[SIZE],n,p,i,j,t;
int main(void)
{
    while(scanf("%d",&n)!=EOF)
    {
      p=DS; x[DS]=1; x[DS+1]=0;
      for(i=1;i<=n;i++)
      {
        p--; x[p]=0; p--; x[p]=0;
        for(j=DS;j>p;j--)
        {
          x[j]*=i; t=j+1;
          x[j]+=x[t]/100000;
          x[t]%=100000;
        }
        while(!x[p]) p++;
      }
      printf("%u",x[p]); p++;
      for(;p        printf("%05u",x[p]);
      printf("\n");
    }
    return 0;
}

SunKai 2008-03-08 18:30 发表评论

我的OI之路&NOIP2007记

SunKai — Sat, 08 Mar 2008 00:58:00 GMT

我与OI的接触最早应该是在小学四年级，那时我十分喜欢摆弄家里的电脑，由于偶然的经历买了一本《电脑爱好者》杂志，结果从此它成为我至尽仍旧购买的一本杂志之一，它可以说是我的启蒙老师。我不断的从中学到许许多多的电脑技巧，同时了解了Flash动画和编程。可能是由于天赋，可能是由于兴趣，我的电脑水平与日俱增，最后自己的小学班主任都了解到了，因而——
那时小学可以说是实行素质教育，我们的业余丰富多采，学校为了计算机比赛开设了一个“微机兴趣小组”，本来我是不知道这件事的，但是由于班主任知道，经她的推荐，我进入了那小组中，从此开始了我的编程之路。
那时的编程我至今记忆尤新，因为那就是logo，小乌龟，输入repeat 360[fd 1 rt 1]就可以一个画圆fd 100 lt 100 fd 100 lt 100 fd 100 lt 100 fd 100就可以画一个正方形。我去小组时，小组中的其他同学已经学了好几次了，但是几次课后，我发现我已经在logo方面赶了上来（因为不只是logo,我们的比赛中还有打字速度测试），并且甚至超过了别的同学。不过我的打字速度不是最快的，而且总是出现错误，但是最后我还是练习到可以一分钟打300多个字的速度，用我们比赛专用的软件测可以到300分。那时我们总是在老师背后找到学校电脑中隐藏的CS(那是中午在学校午休的老师消遣用的)，并且总是背着老师联网玩CS。渐渐的，我学习了“过程”，绘出美丽图形用的第归等，那时还不知道，这些分别就是函数和算法。一个多月后，我们小组中选拔3人代表全校参赛，虽然我的打字速度在几人中不突出，但我的logo却名列第一。最后我们三人中我和另一女同学获得了一等奖，另一人获得了二等奖。比赛后我才知道，我的打字才得了70多分，而那个得二等奖的得了200多分，我的成绩全考的是logo提高上去的。
后来，我们小组中由于我会Flash，所以我又被老师单独辅导，制作flash动画，最后到录音的每个细节都是我们那经验丰富的老师亲自找人帮助我录的。最后众望所归，我顺利的进入了市里的比赛，又顺利的进入了山东省的比赛，最后获得了一等奖。这一切，归功于我的班主任和计算机老师，再就是启蒙我的那本《电脑爱好者》杂志。
当时我除了知道有数学奥赛，其它的什么都不知道，更不知道有信息学奥赛（OI）。（直到几月前我才知道，小学参加的logo比赛就是计算机奥赛），我的计算机路到了初中又遇到了一位指路人，没有她，就没有我的今天。
那日，我们的计算机老师有事，所以找了一名女老师帮助他代客。当天学的是无聊的Word，上机课。由于旁边的一名同学的word有问题，所以请求那个女老师帮助修复一下，但是那个女老师搞了半天也没搞出来。由于以前我遇到过这种情况，所以最后我用了几步就帮助那同学搞出来了。那女老师看了我一下，思索片刻问我是不是参加过全国中小学生电脑作品大赛，她说她好象在区里的比赛中见过我。我说是，然后我问她我能否代表学校参加今年的比赛，她说可以。
初中的那次比赛我准备的很不充分，因为初中很忙，寒假去掉写作业和到爷爷家过年就没几天了，同时由于当时我缺少素材，动画做的不太好，比赛过后，老师告诉我的作品没能进入省里的比赛，只是一个市二等奖，不过她鼓励我让我继续努力，同时给了我一本厚重的老书——《Pascal程序设计》。
在此之前，我在《电脑爱好者》杂志上看到VB编写出的应用程序，并曾买过基本VB的数，但由于当时英语还没怎么学，看了不到一半就不再看了，因为那些需要记忆的太多了，而我是一个一个字母的记忆。例如caption我就C,A,P,T,I,O,N的背。
老师给我那本书同时说，我们学校可以参加信息学奥赛，奥赛就考这个，回家好好看，下学期你就参加奥赛吧！
计算机奥赛？太好了，不过这本书好厚，我看了前面的几页就不再看了。那本书一直躺在电脑桌旁。到了初一的暑假前，那位女老师又给我了几本《奥赛经典》和其它的许许多多的信息学奥赛书，可是我没有看它们，只是在老师的嘱咐下于暑假看了那本《Pascal程序设计》的前五章。假期中才发现程序设计是如此的有意思，我用那所学的五章内容自己编写一个井字棋，还编写中文编程等若干个小程序。但是我看那本书看的太晚了。开学后，老师问我看的情况，我只好如实照答，老师没有批我，只是说今年报个名先试试，今年不好还有明年。11月的信息学奥赛开始了，我在考试前翻阅了一些前几年的考题，然后胸有成竹的去考试了，初赛是笔试。结果我发现考试比我想象的难多了，什么栈，图，二叉树，我根本不知道是什么,许多的函数我都不知道它的意思。我尽可能的答了，回家在网上对答案，发现：我的进制转换等十分基础的题竟然都错了（当时我还没掌握进制转换）。我的阅读程序和完成程序等还算可以，当时根本没学什么算法，当时我认为“以不变应万变”，我用的算法都是我自己创造的。最后老师告诉我，我是全区没有进复赛的第一名！（全区一共近100个人参赛，选拔2个，我是第三名），如果暑假我多看看那本数，或许...没有或许，比赛就是这样，残酷，毫不留情！
由于一直仰慕C语言，暑假期间我同时买了一本C二极教程，准备去考计算机二级（我没考一级，当时觉的考一级太容易了），但是考试大纲正直在那年变了，将windows/dos基础的30分改成了公共基础知识...什么内聚等，我哪里知道？机试更惨，考了一个三次方程，结果那年的计算机考试我以三次全部落败（动画，信息学奥赛，C二级）而收场。
后来，那个女老师也由于学校的原因去教初一的了，我换了一个女老师（受原来那个女老师委托）。再后来，我的那几本根本没看的书被学校要回了（因为那是学校出资的），我通过新换的那个女老师自己掏腰包买了2本书。
第二年，我总结的经验，在暑假期间猛学。那时我每天几乎都在学习计算机，既学C二级，又学OI，我每天都学习到夜里12点之后，白天就在家中编写我的人机对战的象棋程序。就这样，我度过了这一个我现在一生中最忙碌而充实的暑假，我的进步无与伦比。同时在假期中我做出了一个艰难的选择，经过2天的思想斗争，我决定彻底放弃Pascal，用C冲击OI(我之前不了解OI还可以用C,假期我上网知道后，感觉虽然pascal适合OI,但日后真正强大有用的是C，虽然C参加OI的难度大于同情况下使用pascal).
　11月又来了，我成熟了许多，比当年的稚嫩，我比赛中更为沉着老练，以67分，区第一的成绩进入烟台加试。加试比赛（机试）其实只要不是0（满分300）就可以进复赛，不过我还是尽力做，最后得了110分。
中间我又考了一次C二级，这次比上次好许多，机试的1小时时间我用了五分钟就全部答完，检查后就离开了，虽然不知道具体得分，估计应该是100
12月，我来到了寿光，我的复赛地——寿光现代中学。那里，我认识了许多OIers,但是我又失败了，考试前的一天晚上11点多我才入睡，使我在第二天下午的比赛中发挥失常，其实，我绝对应该是一等奖(因为去年的普及组题特别简单），但是最终只AC了一个弱智题，二等奖，与一等擦肩而过。
赛后我总结的比赛教训，虽然有客观原因，但是比赛失利的主观原因是有的，假期中我虽然看了一些算法，但是大部分并未上机实践，使我形成书写空洞，并且我的动态规划并未懂得（我没有辅导老师教我，我只能自学，对于许多长的求和公式，我根本看不懂）
自学虽然慢，但一旦学会，那是不易忘记的，我在比赛后于网上大量找动态规划资料并自学，终于对其有所领悟，并且在今年的暑假，我对许许多多的算法进行实地编程，上机实践，DFS,BFS已熟练掌握，对DP可以把握，贪心，高精度等已烂熟于胸，我在vijos上做题，改题，就这样，我度过了这个假期,假期中我参加了一个模拟赛，同时在假期后的十一，和各周末，我都到OIBH或RQNOJ上参加各种模拟...
今年的比赛又来了，NOIP2007的初赛已经结束，我又以区第一，加试180的资格进入复赛，初中的最后一年，我所面对的是又一次Challenge。NOIP2007，天道酬勤，我会成功！

上文完２００７．１１．３　晚

NOIP2007的复赛在日照一中举办，这次由我们主任（他是一名计算机教师）亲自出马与我一同去日照。由于有了经验，之前先拿着一包咖啡，防止由于睡的太晚而导致第二天打瞌睡。这次去，我的目标就是一等奖，没有第二种选择，同时希望与一些高中的高手交流一下，提高一下自己。
车上，我又遇到了许多与去年相同的面孔，是的，他们和我一样，在又一次的奋斗中。在我们主任的介绍下，我与烟台三中的带队老师姜涛老师相识，同时进行过交流。同时，我又看到了去年的与我比较熟悉的九中带队老师，我本以为今年可以再次在复赛见到去年代表九中参赛的曲凯，结果这次九中的那个人告诉我他这次没有进入复赛。他名叫王振宇，与他交谈中，我感觉他比较沉稳老师，从言语中我了解到一些关于他们学校的事情，也拉近我们间的关系。
到了日照的时候已经过了中午了，有条不紊的报完名后，安顿好我们的宿舍，我们与九中的老师，学生一同去餐厅吃午饭，在午饭时我们遇到了十三中的带队老师，好象从小学去参加flash比赛时到现在，我已经见过他多次了。
餐后，我与王振宇记下了彼此间的宿舍号，如果有问题，可以相互照应。下午，我的宿舍中起初空无一人，于是到了他的宿舍，没想到他很幸运，他与烟台三中的选手在一个宿舍。于是我也过去交流，同时与他一同去逛逛校园，找一下自己的考场，记得去年与曲凯也是这样度过一个下午的。日照一中的校园也很大，但是我感觉没有寿光一中漂亮。回宿舍后看到宿舍中来了人，是十三中的，几句交谈中我就对他产生了很强烈的鄙视，他没有信念，没有追求，一切好象无所谓，虽然王振宇算法能力也稍显不足，但是他为人真诚正直，完全强于那个十三中的家伙。晚上来的几个开发区高中的也沉默寡言，所以我那天几乎全部在王振宇的那个宿舍与三中的人来往。听说任青下午将来，我很高兴，希望与他相见。三中的人说他来就是来冲击山东前三名的，最终他带着个笔记本来了，我试探一下他的算法能力，我与他差不多。
晚上，三中的选手去参加提高组试机了，我与王振宇独在宿舍里，无聊，出去买了盘象棋下，晚上比较早时就睡了。第二天提高组比赛时，我把自己的一些经验告诉王振宇，毕竟他没有参加过复赛，同时我还教他了一点算法。上午三中的回来后我马上与他们要了份题——因为去年提高组的题中暗示了普及组要考背包问题，今年或许也如此。提高的题不难，第一题nlogn的qsort直接过，第二题仔细一点，模拟可过，第三题dp，由于我当时非经典dp还是相当不好，于是我决定如果实在遇到这个题就搜索，毕竟我不会，别人也可能不会。第四题一看到是图就没看——普及组不考图论
下午就考了，带的coffee没有喝，因为不方便冲，于是去买了两瓶现成的喝了，上午喝了一罐，考前喝了一罐。进入考场后刚做稳准备打qsort，一个女的来了，问我是否找错了考号，这时我才知道我与人重考号了。我担心可能会影响到自己的成绩，于是与在外等候的老师示意，工作人员让我还在我的考号的那台机器上考，让那个女的去了备用机。拿到考题，一看不难，第一题多关键字排序，第二题贪心，第四题递推+高精度，就是第三题有点乱，但最后想到了一个线形的算法。
考完试就依依不舍的与老师和找专车来接我的父母在夜晚踏上归途，因为第二天我还要参加全国英语能力竞赛初赛。因此本来准备去找sd.yy要sd.yy比赛的奖品顺便见一下大牛的机会也没有了
还是要感谢我们的主任，与我父母时刻保持联系，同时让我母亲与烟台市计算机教研员相识并记录了联系方式，他安排的很细心，很周到。
成绩是后来才知道的，虽然现场就出了，但是出成绩的时候我已经在英语竞赛的考场上。
300分，不太理想，因为我可以是400，最起码是350以上，记得考试后我层自信的说是400~
现在分析可能的原因是出在最简单的第一题上。当时的多关键字的qsort写错了。
noip2007还算圆满。山东一等分数线是180，无悬念，我是1等奖

我还要努力，现在要中考了，这方面的学习暂且停一停，中考完后我要参加山东的夏令营，努力提高自己。因为noip2008时，我将第一次在提高组展现我自己的风采！

全文完 2008.3.8

SunKai 2008-03-08 08:58 发表评论

我的新博客

SunKai — Fri, 07 Mar 2008 13:53:00 GMT

以前的那个博客不适合作为技术博客.从今天开始,这个博客作为我的新博客.
以前博客中的内容将陆续选择后转过来.
要中考了,对于算法的学习暂时停止,中考完后去参加山东的夏令营,那时将算法水平努力提高一个水平
在这个blog中,我将发一些我做的算法习题的原创AC代码和部分题目我写的题解,分享出来,同时作为一个记录,一些美好的记忆...

SunKai 2008-03-07 21:53 发表评论

习题 89：Coupons ★★★★

SunKai — Fri, 07 Mar 2008 11:09:00 GMT

/*
习题 89：Coupons ★★★★
题目描述：
FireDancer最近迷上了一个填数的游戏：一个n*n的正方形棋盘，要把从1到n2的整数填入到这个棋盘的每一个格子里（随意）。玩了很多次后，FireDancer发现了很多有趣的性质，他现在想考考你。他希望你得到一种棋盘的填法，使得任意相邻的两个格子里的数相加的最大值最小。这里的相邻指的是四个方向上的有公共边的相邻，而不是八个方向上的相邻。

输入：
有且只有一个整数n（2<=n<=50）。

输出：
一个整数，为最小的那个值。

样例输入：
2

样例输出：
6

其它信息：
一种最优填数方案为
1 4
3 2
此时，所有相邻的格子中4+2的和最大，为6。
若按以下方法填数
1 3
2 4
则，4+3的和最大，为7，没有6来得优。

题目提供：
ailyanlu

难度：Hard
*/
#include
int x[52][52]={0};
int m(int a,int b)
{
    if(a>b) return a; else return b;
}
int main(void)
{
    int i,j,k,t;
    int n;
    int n2;
    int flag;
    int maxi[2],maxj[2],max;
    int si,sj;
    int ri,rj;
    int temp;
    scanf("%d",&n);
    n2=n*n;
    k=(n2+1)/2;
    if(n2%2==0) k++;
    t=1;
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
      {
        if(i%2==j%2)
        {
          x[i][j]=k;
          k++;
        }
        else
        {
          x[i][j]=t;
          t++;
        }
      }

    flag=1;
    while(flag)
    {
      maxi[1]=maxi[2]=maxj[1]=maxj[2]=0;
      max=0;
      for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
          if((temp=x[i][j]+x[i][j+1])>max)
          {
            max=temp;
            maxi[1]=maxi[2]=i;
            maxj[1]=j;
            maxj[2]=j+1;
          }
          if((temp=x[i][j]+x[i+1][j])>max)
          {
            max=temp;
            maxi[1]=i;
            maxi[2]=i+1;
            maxj[1]=maxj[2]=j;
          }
        }
      if(maxi[1]%2!=maxj[1]%2)
      {
        si=maxi[1];
        sj=maxj[1];
        ri=maxi[2];
        rj=maxj[2];
      }
      else
      {
        si=maxi[2];
        sj=maxj[2];
        ri=maxi[1];
        rj=maxj[1];
      }
      flag=0;
      for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
          if(i%2!=j%2)
          {
            if(m(m(m(x[si][sj]+x[i][j-1],x[si][sj]+x[i][j+1]),
                 m(x[si][sj]+x[i-1][j],x[si][sj]+x[i+1][j])),
               x[i][j]+x[ri][rj])            {
              temp=x[i][j];
              x[i][j]=x[si][sj];
              x[si][sj]=temp;
              flag=1;
              goto next;
            }
          }
        }
        next: ;
    }
    /*
    for(i=1;i<=n;i++)
    {
      for(j=1;j<=n;j++)
      {
        printf("%d ",x[i][j]);
      }
      printf("\n");
    }*/
    printf("%d",max);
    /*
    while(1);
    */
    return 0;
}

SunKai 2008-03-07 19:09 发表评论

习题75：石子合并★★★★

SunKai — Fri, 07 Mar 2008 11:08:00 GMT

/*
75：石子合并★★★★
题目描述：
有n堆石子，每次可以将任意两堆合并为一堆，这次操作消耗的体力是这两堆石子数之和。最终需要将n堆石子合并为一堆，问最少要多少体力？
这些石子十分特殊：一开始的时候第i堆石子有i个石子，i=1,2,...,n

输入：
有多组测试数据，每行一个正整数n，n<=5e8
以EOF标志结束程序。

输出：
对于每组测试，每行输出一个数，
表示最少所需要的体力

样例输入：
2
3

样例输出：
3
9

其它：
题目提供：FancyMouse

难度：Hard
*/
#include
typedef struct
{
long long i,x1,x2,x3,x,c;
} data;
data s[101]=
{
{4ll,9ll,6ll,4ll,3ll,4ll},
{5000000ll,275139846620928ll,113708544ll,24ll,3145728ll,1291457ll},
{10000000ll,1150559277775168ll,237417088ll,25ll,6291456ll,2582913ll},
{15000000ll,2653065938683584ll,364834176ll,26ll,12582912ll,10165825ll},
{20000000ll,4802236883683584ll,494834176ll,26ll,12582912ll,5165825ll},
{25000000ll,7601407828683584ll,624834176ll,26ll,12582912ll,165825ll},
{30000000ll,11062263404900160ll,759668352ll,27ll,25165824ll,20331649ll},
{35000000ll,15198105232400160ll,894668352ll,27ll,25165824ll,15331649ll},
{40000000ll,20008947059900160ll,1029668352ll,27ll,25165824ll,10331649ll},
{45000000ll,25494788887400160ll,1164668352ll,27ll,25165824ll,5331649ll},
{50000000ll,31655630714900160ll,1299668352ll,27ll,25165824ll,331649ll},
{55000000ll,38502369299932288ll,1439336704ll,28ll,50331648ll,45663297ll},
{60000000ll,46049052889932288ll,1579336704ll,28ll,50331648ll,40663297ll},
{65000000ll,54295736479932288ll,1719336704ll,28ll,50331648ll,35663297ll},
{70000000ll,63242420069932288ll,1859336704ll,28ll,50331648ll,30663297ll},
{75000000ll,72889103659932288ll,1999336704ll,28ll,50331648ll,25663297ll},
{80000000ll,83235787249932288ll,2139336704ll,28ll,50331648ll,20663297ll},
{85000000ll,94282470839932288ll,2279336704ll,28ll,50331648ll,15663297ll},
{90000000ll,106029154429932288ll,2419336704ll,28ll,50331648ll,10663297ll},
{95000000ll,118475838019932288ll,2559336704ll,28ll,50331648ll,5663297ll},
{100000000ll,131622521609932288ll,2699336704ll,28ll,50331648ll,663297ll},
{105000000ll,145478608702892448ll,2843673408ll,29ll,100663296ll,96326593ll},
{110000000ll,160059475815392448ll,2988673408ll,29ll,100663296ll,91326593ll},
{115000000ll,175365342927892448ll,3133673408ll,29ll,100663296ll,86326593ll},
{120000000ll,191396210040392448ll,3278673408ll,29ll,100663296ll,81326593ll},
{125000000ll,208152077152892448ll,3423673408ll,29ll,100663296ll,76326593ll},
{130000000ll,225632944265392448ll,3568673408ll,29ll,100663296ll,71326593ll},
{135000000ll,243838811377892448ll,3713673408ll,29ll,100663296ll,66326593ll},
{140000000ll,262769678490392448ll,3858673408ll,29ll,100663296ll,61326593ll},
{145000000ll,282425545602892448ll,4003673408ll,29ll,100663296ll,56326593ll},
{150000000ll,302806412715392448ll,4148673408ll,29ll,100663296ll,51326593ll},
{155000000ll,323912279827892448ll,4293673408ll,29ll,100663296ll,46326593ll},
{160000000ll,345743146940392448ll,4438673408ll,29ll,100663296ll,41326593ll},
{165000000ll,368299014052892448ll,4583673408ll,29ll,100663296ll,36326593ll},
{170000000ll,391579881165392448ll,4728673408ll,29ll,100663296ll,31326593ll},
{175000000ll,415585748277892448ll,4873673408ll,29ll,100663296ll,26326593ll},
{180000000ll,440316615390392448ll,5018673408ll,29ll,100663296ll,21326593ll},
{185000000ll,465772482502892448ll,5163673408ll,29ll,100663296ll,16326593ll},
{190000000ll,491953349615392448ll,5308673408ll,29ll,100663296ll,11326593ll},
{195000000ll,518859216727892448ll,5453673408ll,29ll,100663296ll,6326593ll},
{200000000ll,546490083840392448ll,5598673408ll,29ll,100663296ll,1326593ll},
{205000000ll,574852697917896384ll,5747346816ll,30ll,201326592ll,197653185ll},
{210000000ll,603964432072896384ll,5897346816ll,30ll,201326592ll,192653185ll},
{215000000ll,633826166227896384ll,6047346816ll,30ll,201326592ll,187653185ll},
{220000000ll,664437900382896384ll,6197346816ll,30ll,201326592ll,182653185ll},
{225000000ll,695799634537896384ll,6347346816ll,30ll,201326592ll,177653185ll},
{230000000ll,727911368692896384ll,6497346816ll,30ll,201326592ll,172653185ll},
{235000000ll,760773102847896384ll,6647346816ll,30ll,201326592ll,167653185ll},
{240000000ll,794384837002896384ll,6797346816ll,30ll,201326592ll,162653185ll},
{245000000ll,828746571157896384ll,6947346816ll,30ll,201326592ll,157653185ll},
{250000000ll,863858305312896384ll,7097346816ll,30ll,201326592ll,152653185ll},
{255000000ll,899720039467896384ll,7247346816ll,30ll,201326592ll,147653185ll},
{260000000ll,936331773622896384ll,7397346816ll,30ll,201326592ll,142653185ll},
{265000000ll,973693507777896384ll,7547346816ll,30ll,201326592ll,137653185ll},
{270000000ll,1011805241932896384ll,7697346816ll,30ll,201326592ll,132653185ll},
{275000000ll,1050666976087896384ll,7847346816ll,30ll,201326592ll,127653185ll},
{280000000ll,1090278710242896384ll,7997346816ll,30ll,201326592ll,122653185ll},
{285000000ll,1130640444397896384ll,8147346816ll,30ll,201326592ll,117653185ll},
{290000000ll,1171752178552896384ll,8297346816ll,30ll,201326592ll,112653185ll},
{295000000ll,1213613912707896384ll,8447346816ll,30ll,201326592ll,107653185ll},
{300000000ll,1256225646862896384ll,8597346816ll,30ll,201326592ll,102653185ll},
{305000000ll,1299587381017896384ll,8747346816ll,30ll,201326592ll,97653185ll},
{310000000ll,1343699115172896384ll,8897346816ll,30ll,201326592ll,92653185ll},
{315000000ll,1388560849327896384ll,9047346816ll,30ll,201326592ll,87653185ll},
{320000000ll,1434172583482896384ll,9197346816ll,30ll,201326592ll,82653185ll},
{325000000ll,1480534317637896384ll,9347346816ll,30ll,201326592ll,77653185ll},
{330000000ll,1527646051792896384ll,9497346816ll,30ll,201326592ll,72653185ll},
{335000000ll,1575507785947896384ll,9647346816ll,30ll,201326592ll,67653185ll},
{340000000ll,1624119520102896384ll,9797346816ll,30ll,201326592ll,62653185ll},
{345000000ll,1673481254257896384ll,9947346816ll,30ll,201326592ll,57653185ll},
{350000000ll,1723592988412896384ll,10097346816ll,30ll,201326592ll,52653185ll},
{355000000ll,1774454722567896384ll,10247346816ll,30ll,201326592ll,47653185ll},
{360000000ll,1826066456722896384ll,10397346816ll,30ll,201326592ll,42653185ll},
{365000000ll,1878428190877896384ll,10547346816ll,30ll,201326592ll,37653185ll},
{370000000ll,1931539925032896384ll,10697346816ll,30ll,201326592ll,32653185ll},
{375000000ll,1985401659187896384ll,10847346816ll,30ll,201326592ll,27653185ll},
{380000000ll,2040013393342896384ll,10997346816ll,30ll,201326592ll,22653185ll},
{385000000ll,2095375127497896384ll,11147346816ll,30ll,201326592ll,17653185ll},
{390000000ll,2151486861652896384ll,11297346816ll,30ll,201326592ll,12653185ll},
{395000000ll,2208348595807896384ll,11447346816ll,30ll,201326592ll,7653185ll},
{400000000ll,2265960329962896384ll,11597346816ll,30ll,201326592ll,2653185ll},
{405000000ll,2324324817891738720ll,11749693632ll,31ll,402653184ll,400306369ll},
{410000000ll,2383460786129238720ll,11904693632ll,31ll,402653184ll,395306369ll},
{415000000ll,2443371754366738720ll,12059693632ll,31ll,402653184ll,390306369ll},
{420000000ll,2504057722604238720ll,12214693632ll,31ll,402653184ll,385306369ll},
{425000000ll,2565518690841738720ll,12369693632ll,31ll,402653184ll,380306369ll},
{430000000ll,2627754659079238720ll,12524693632ll,31ll,402653184ll,375306369ll},
{435000000ll,2690765627316738720ll,12679693632ll,31ll,402653184ll,370306369ll},
{440000000ll,2754551595554238720ll,12834693632ll,31ll,402653184ll,365306369ll},
{445000000ll,2819112563791738720ll,12989693632ll,31ll,402653184ll,360306369ll},
{450000000ll,2884448532029238720ll,13144693632ll,31ll,402653184ll,355306369ll},
{455000000ll,2950559500266738720ll,13299693632ll,31ll,402653184ll,350306369ll},
{460000000ll,3017445468504238720ll,13454693632ll,31ll,402653184ll,345306369ll},
{465000000ll,3085106436741738720ll,13609693632ll,31ll,402653184ll,340306369ll},
{470000000ll,3153542404979238720ll,13764693632ll,31ll,402653184ll,335306369ll},
{475000000ll,3222753373216738720ll,13919693632ll,31ll,402653184ll,330306369ll},
{480000000ll,3292739341454238720ll,14074693632ll,31ll,402653184ll,325306369ll},
{485000000ll,3363500309691738720ll,14229693632ll,31ll,402653184ll,320306369ll},
{490000000ll,3435036277929238720ll,14384693632ll,31ll,402653184ll,315306369ll},
{495000000ll,3507347246166738720ll,14539693632ll,31ll,402653184ll,310306369ll},
{500000000ll,3580433214404238720ll,14694693632ll,31ll,402653184ll,305306369}
};

int main(void)
{
    long long i,x1,x2,x3,n,x,c,p;
    while(scanf("%I64d",&n)!=EOF)
    {
      if(n==1) printf("0\n");
      else if(n==2) printf("3\n");
      else if(n==3) printf("9\n");
      else
      {
        p=0;
        for(i=0;i<99;i++) if(s[i].i        if(p>0) s[p].i++;
        x1=s[p].x1;
        x2=s[p].x2; x3=s[p].x3;
        x=s[p].x; c=s[p].c;
      for(i=s[p].i;i<=n;i++)
      {
        c--;
        if(!c) { x*=2; x3++; c=x;}
        x2=x2+x3;
        x1=x2+x1;
      }
      printf("%I64d\n",x1);
      }
    }
    return 0;
}

SunKai 2008-03-07 19:08 发表评论

习题67：The 3n+1 Problem(2) ★★★★

SunKai — Fri, 07 Mar 2008 11:06:00 GMT

/*
67：The 3n+1 Problem(2) ★★★★
题目描述：
这是一个古老的猜想：给定任何一个正整数n，对它进行以下操作：
n是偶数：n=n/2
n是奇数：n=3*n+1
这样经过多步操作后，最后必定变为1
如对13进行操作： 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
一共经历了9次操作，则称13这个数的周期是9

输入：
多组测试数据，每组一行，一行里有两个数m和n，
请你找出m和n之间（包括m,n）的周期最大的数的周期
其中m,n均为小于或者等于2e6的正整数

输出：
m,n之间周期最大的数的周期，一个结果单独占一行

样例输入：
1 10
2 3
30 100

样例输出：
19
7
118

难度：Hard
*/
#ifdef TEST
#include
#endif
#include
#include
#define SIZE 2000001
#define DIS 1000
int x[SIZE];
int hash[2001];
int dfs(long long now) /*记忆化搜索*/
{
    int c;
    if(now    if(now & 1)
    {
      c=dfs(now*3+1)+1;
    }
    else
    {
      c=dfs(now>>1)+1;
    }
    if(now    return c;
}
int main(void)
{
    int i,t,j;
    int m,n,max;
    #ifdef TEST
    long time=clock();
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    #endif
    memset(x,0,sizeof(x));
    x[1]=1;
    max=0;
    for(i=1;i    {
      if(dfs(i)>max) max=x[i];
      if(i%DIS==0)
      {
        hash[i/DIS-1]=max;
        max=0;
      }
    }
    #ifdef TEST
    printf("Total time:%dms\n",clock()-time);
    #endif
    while(scanf("%d%d",&m,&n)!=EOF)
    {
      if(m>n) m^=n^=m^=n;

      max=0;
      t=((m-1)/DIS+1)*DIS;
      if(t>n) t=n;
      for(i=(m-1)/DIS+1,j=n/DIS;i      for(i=m;i<=t;i++) if(x[i]>max) max=x[i];
      t=(n/DIS)*DIS;
      if(t      for(i=t;i<=n;i++) if(x[i]>max) max=x[i];

      printf("%d\n",max-1);
    }
    #ifdef TEST
    printf("Total time:%dms\n",clock()-time);
    #endif
    return 0;
}

SunKai 2008-03-07 19:06 发表评论

习题 36：The 3n+1 Problem ★★

SunKai — Fri, 07 Mar 2008 11:05:00 GMT

/*
习题 36：The 3n+1 Problem ★★

问题描述：
这是一个古老的猜想：给定任何一个正整数n，对它进行以下操作：
n是偶数：n=n/2
n是奇数：n=3*n+1
这样经过多步操作后，最后必定变为1
如对13进行操作： 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
一共经历了9次操作，则称13这个数的周期是9

输入：
多组测试数据，每组一行，一行里有两个数m和n，
请你找出m和n之间（包括m,n）的周期最大的数的周期
其中m,n均为小于或者等于1e5的正整数

输出：
m,n之间周期最大的数的周期，一个结果单独占一行

样例输入：
1 10
2 3
30 100

样例输出：
19
7
118

难度：Easy
*/
#include
/*
#include
*/
int hash[100001]={0};
int main(void)
{
    int m,n;
    int i,j,k,t;
    int max;
    /*
    int time;
    time=clock();
    */
    for(i=1;i<100001;i++)
    {
      if(!hash[i])
      {
        t=i;
        while(t!=1)
        {
          if(t%2) t=t*3+1;
          else t>>=1;
          hash[i]++;
        }
        for(j=i,k=hash[i],t=i;j<100001;j+=t,k++,t*=2) hash[j]=k;
      }
    }
    /*
    printf("%d",clock()-time);
    for(i=1;i<101;i++) printf("%3d ",hash[i]);
    */
    while(scanf("%d%d",&m,&n)!=EOF)
    {
      if(m>n) m^=n^=m^=n; max=0;
      for(i=m;i<=n;i++) if(hash[i]>max) max=hash[i];
      printf("%d\n",max);
    }
    return 0;
}

SunKai 2008-03-07 19:05 发表评论

习题 32：最大数字子串之和★★

SunKai — Fri, 07 Mar 2008 11:04:00 GMT

/*
注意数据中有负值
*/
/*
习题 32：最大数字子串之和★★

输入n(1<=n<=1e6)和n个整数，这n个整数的绝对值均小于1000，求最大数字子串之和

样例输入：
9
-3 4 9 2 -10 -7 11 3 -8
13
-1 2 6 -3 5 -7 14 -5 -15 1 8 -4 9

样例输出：
15
17

提示：
在第一组中，最大的数字子串是4 9 2的和
在第二组中，最大的数字子串是2 6 -3 5 -7 14的和

难度：easy
*/
#include
int main(void)
{
    int n,t,i;
    int sum,max;
    while(scanf("%d",&n)!=EOF)
    {
      sum=0; max=-10000;
      for(i=0;i      {
        scanf("%d",&t);
        if(sum>0) sum=sum+t;
        else sum=t;
        if(sum>max) max=sum;
      }
      printf("%d\n",max);
    }
    return 0;
}

SunKai 2008-03-07 19:04 发表评论

习题 26：滑雪★★★★

SunKai — Fri, 07 Mar 2008 11:02:00 GMT

/*
习题 26：滑雪★★★★

Description
Michael喜欢滑雪但这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input
多组测试数据。输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output
输出最长区域的长度。

Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Sample Output

难度：Hard
*/

#include
#include
int map[101][101]={0};
int d[101][101]={0};
int to[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int r,c;
int ok(int x,int y)
{
    if(x>0 && x<=r && y>0 && y<=c) return 1;
    return 0;
}
int dfs(int x,int y)
{
    int k,t;
    if(d[x][y]) return d[x][y];
    for(k=0;k<4;k++)
      if(ok(x+to[k][0],y+to[k][1]))
        if(map[x+to[k][0]][y+to[k][1]]          if((t=dfs(x+to[k][0],y+to[k][1])+1)>d[x][y]) d[x][y]=t;
    return d[x][y];
}
int main(void)
{
    int i,j;
    int max;
    while(scanf("%d%d",&r,&c)!=EOF)
    {
      max=0;
      memset(d,0,sizeof(d));
      for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
          scanf("%d",&map[i][j]);
      for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
          if(max      printf("%d\n",max+1);
    }
    return 0;
}

SunKai 2008-03-07 19:02 发表评论

习题 23：恶魔岛救公主★★

SunKai — Fri, 07 Mar 2008 11:01:00 GMT

/*
习题 23：恶魔岛救公主★★

goldfisher为了解救被绑架的未婚妻而来到了恶魔岛。上岛前，一个神秘的印度人yingnan告诉他恶魔岛处处布满陷阱，只有沿着地上标记数字和为最大的路径才能找到公主。为此他给goldfisher画了一个草图，假使地上标记的数字如下：
1
2 3
1 5 9
9 1 1 1
其中的最大路径是1-3-9-1，最大的和是14，只有沿着这条路径走，才能找到公主。goldfisher犯难了，因为现实中标记的数字更多，难度更大。你能帮助goldfisher找到正确的道路解救他的未婚妻吗？

注:地图为等腰三角形，必须置顶向下，且每次仅能访问相邻两个子路径。本例中：
第一层 1 可达 2、3 两点
第二层 2 可达 1、5 两点 ; 3 可达 5、9 两点，以此类推

输入：
        本题包含多组测试数据，其中第一行为N(1 <= N <= 100)，表示将要进过的关卡数。
        接下来N行为通往目的地图。
        通过判断End Of File结束程序
输出：
        输出 It will take him s steps!
其中 s为对应地图最长路径值。
输入样例：
4
1
2 3
1 5 9
9 1 1 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例：
It will take him 14 steps!
It will take him 30 steps!

难度：easy
*/
#include
#include
int max(int r,int t)
{
    if(r>t) return r;
    else return t;
}
int main(void)
{
    int i,j;
    int n;
    int temp;
    int line[101]={0};
    while(scanf("%d",&n)!=EOF)
    {
      memset(line,0,sizeof(line));
      for(i=1;i<=n;i++)
        for(j=i;j>0;j--)
        {
          scanf("%d",&temp);
          line[j]=max(line[j],line[j-1])+temp;
        }
      temp=0;
      for(i=1;i<=n;i++) if(temp      printf("It will take him %d steps!\n",temp);
    }
    return 0;
}

SunKai 2008-03-07 19:01 发表评论

习题 9：上阶梯★★

SunKai — Fri, 07 Mar 2008 10:59:00 GMT

/*
习题 9：上阶梯★★

上阶梯，你可以一个一个阶梯上，也可以两个两个地来，
也可以一个和二个间隔着上，甚至可以一次k个阶梯
问题是，上一个阶梯数为n，每步能上1至k个阶的话，
你有多少种方法走完它？

如 n = 5 , k = 2，可以
1,1,1,1,1
2,1,1,1
1,2,1,1
1,1,2,1
1,1,1,2
2,2,1
2,1,2
1,2,2
共8种

输入阶梯数n(1 <= n <= 30)和每步最大阶数k(1<=k<=n)：
5 2
5 3

输出：
8
13

难度：Easy
*/
#include
#include
int d[31][31];
int dfs(int left,int k)
{
    int i;
    if(d[left][k]!=-1) return d[left][k];
    if(!left) return 1;
    d[left][k]=0;
    for(i=1;i<=((left      d[left][k]+=dfs(left-i,k);
    return d[left][k];
}
int main(void)
{
    int n,k;
    memset(d,-1,sizeof(d));
    while(scanf("%d%d",&n,&k)!=EOF)
      printf("%d\n",dfs(n,k));
    return 0;
}

SunKai 2008-03-07 18:59 发表评论