内存检查工具

内存检测工具主要用于检测程序的堆栈错误。一般的检测方法是通过加magic number来表示正确的内存信息。如果magic number被写坏,那么就表示内存错乱了。

1编译选项:

-fstack-protector & -fstack-protector-all

-fstack-protector

在函数的stack上加一个magic number,如果buffer overflows的话,程序直接退出。

函数开始时加入,退出时检测。

*** stack smashing detected ***: ./test terminated

2环境变量

MALLOC_CHECK_检测堆错误。

若将MALLOC_CHECK_设置为0,则在检查到错误时不作任何提示。

若将MALLOC_CHECK_设置为1,则在检查到错误时打印一条信息到标准错误输出。

若将MALLOC_CHECK_设置为2,则在检查到错误时直接调用abort()中止程序。

3 lib :mcheck

在编译时链接 –lmcheck, 会起到和上诉边境变量相同的效果,不过,mcheck这个lib是线程不安全的。

如果出错,程序直接退出,并打印出:memory clobbered before allocated block

3: mudflap

http://gcc.gnu.org/wiki/Mudflap_Pointer_Debugging

使用方法:

1:添加编译选项:-fmudflap

2:添加lib: -lmudflap

3:环境变量export MUDFLAP_OPTIONS=’<options>

检查非常严格,任何读写越界都会报错。’

4:mtrace:用于查看内存泄露

使用方法:

1.设置环境变量 MALLOC_TRACE指定程序输出log文件

2.包含mcheck.h文件

3.程序开始时调用 mtrace()

4.运行程序

5.使用mtrace查看log文件

5:dmalloc

需要安装http://dmalloc.com/releases/dmalloc-5.5.2.tgz

使用方法:

1:设置环境变量:

在terminal输入export DMALLOC_OPTIONS=log=logfile, debug=0×3(in Bash)/export

2:在源文件中添加下面的C代码:

#include “dmalloc.h”

值得注意的是:要在每一个.C文件里面添加,而且必须添加在所包含的头文件最后一行!

3编译选项:-DDMALLOC -DDMALLOC_FUNC_CHECK

4:lib:-ldmalloc

6 memwatch:

用于检测内存泄露

memwatch不需要安装,只要下载包解压即可,有用的文件只有memwatch.c&memwatch.h,把这两个文件放入要检测的程序的文件夹中即可。编译的命令为:gcc -DMEMWATCH -DMW_STDIO test.c memwatch.c -o test

7:valgrind:

这个资料比较多。

【usaco】 checker

本题的要点在于位运算

!6>!n>!n>!if>!hint:>

Checker Challenge

Examine the 6x6 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal. (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.) 

          Column
    1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------



 The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6: 




ROW

1

2

3

4

5

6



COLUMN

2

4

6

1

3

5




This is one solution to the checker challenge. Write a program that finds all unique solution sequences to the Checker Challenge (with ever growing values of N). Print the solutions using the column notation described above. Print the the first three solutions in numerical order, as if the checker positions form the digits of a large number, and then a line with the total number of solutions. 

Special note: the larger values of N require your program to be especially efficient. Do not precalculate the value and print it (or even find a formula for it); that's cheating. Work on your program until it can solve the problem properly. If you insist on cheating, your login to the USACO training pages will be removed and you will be disqualified from all USACO competitions. YOU HAVE BEEN WARNED. 

TIME LIMIT: 1 CPU second

PROGRAM NAME: checker

INPUT FORMAT


A single line that contains a single integer N (6 <= N <= 13) that is the dimension of the N x N checkerboard. 

SAMPLE INPUT (file checker.in) 
6

 OUTPUT FORMAT

The first three lines show the first three solutions found, presented as N numbers with a single space between them. The fourth line shows the total number of solutions found. 

SAMPLE OUTPUT (file checker.out)
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

HINTS (use them carefully!)

我的解法:

/*
ID: yunleis2
PROG: checker
LANG: C++
*/

#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
 

typedef unsigned int uint;
uint limit;
int * result;
int N;
int total=0;
void search(uint row,uint ld,uint rd,int depth);
fstream fout("checker.out",ios::out);
int main()
{
 
 fstream fin("checker.in",ios::in);

 fin>>N;
 limit=(1<<N) -1;
 result=new int[N];
 search(0,0,0,N);
 delete []result;
 fout<<total<<endl;
 return 0;
}
void search(uint row,uint ld,uint rd,int depth)
{
 int i=0;
 if(depth==0||row==limit)
 {
  total++;
  if(total>3)
   return;
  for(i=0;i<N;i++)
  {
   fout<<result[i]+1;
   if(i<(N-1))
    fout<<" ";
  }
  fout<<endl;
  return;
 }
 uint unused=~(row|rd|ld);
 uint tmp=1;
 for(i=0;i<N;tmp=tmp<<1,i++)
 {
  if((unused&tmp)!=0)
  {
   result[N-depth]=i;
   search(row|tmp,(ld|tmp)<<1,(rd|tmp)>>1,depth-1);
  }
 }


}

 

测试:

USER: Ma yunlei [yunleis2]
TASK: checker
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3028 KB]
   Test 2: TEST OK [0.000 secs, 3028 KB]
   Test 3: TEST OK [0.000 secs, 3028 KB]
   Test 4: TEST OK [0.000 secs, 3028 KB]
   Test 5: TEST OK [0.000 secs, 3028 KB]
   Test 6: TEST OK [0.000 secs, 3028 KB]
   Test 7: TEST OK [0.054 secs, 3028 KB]
   Test 8: TEST OK [0.297 secs, 3028 KB]

All tests OK.
YOUR PROGRAM ('checker') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.

 Here are the test data inputs:
------- test 1 ----
6
------- test 2 ----
7
------- test 3 ----
8
------- test 4 ----
9
------- test 5 ----
10
------- test 6 ----
11
------- test 7 ----
12
------- test 8 ----
13
 Keep up the good work!



Thanks for your submission!

 

 

 

 

参考:http://blog.csdn.net/cmykrgb123/article/details/1854976

Java 序列化的高级认识

引言

将 Java 对象序列化为二进制文件的 Java 序列化技术是 Java 系列技术中一个较为重要的技术点,在大部分情况下,开发人员只需要了解被序列化的类需要实现 Serializable 接口,使用 ObjectInputStream 和 ObjectOutputStream 进行对象的读写。然而在有些情况下,光知道这些还远远不够,文章列举了笔者遇到的一些真实情境,它们与 Java 序列化相关,通过分析情境出现的原因,使读者轻松牢记 Java 序列化中的一些高级认识。

——————————————————————————–
回页首
文章结构

本文将逐一的介绍几个情境,顺序如下面的列表。

序列化 ID 的问题
静态变量序列化
父类的序列化与 Transient 关键字
对敏感字段加密
序列化存储规则
列表的每一部分讲述了一个单独的情境,读者可以分别查看。

——————————————————————————–
回页首
序列化 ID 问题

情境:两个客户端 A 和 B 试图通过网络传递对象数据,A 端将对象 C 序列化为二进制数据再传给 B,B 反序列化得到 C。

问题:C 对象的全类路径假设为 com.inout.Test,在 A 和 B 端都有这么一个类文件,功能代码完全一致。也都实现了 Serializable 接口,但是反序列化时总是提示不成功。

解决:虚拟机是否允许反序列化,不仅取决于类路径和功能代码是否一致,一个非常重要的一点是两个类的序列化 ID 是否一致(就是 private static final long serialVersionUID = 1L)。清单 1 中,虽然两个类的功能代码完全一致,但是序列化 ID 不同,他们无法相互序列化和反序列化。

清单 1. 相同功能代码不同序列化 ID 的类对比
    
 package com.inout;

 import java.io.Serializable;

 public class A implements Serializable {

  private static final long serialVersionUID = 1L;

  private String name;
 
  public String getName()
  {
   return name;
  }
 
  public void setName(String name)
  {
   this.name = name;
  }
 }

 package com.inout;

 import java.io.Serializable;

 public class A implements Serializable {

  private static final long serialVersionUID = 2L;
 
  private String name;
 
  public String getName()
  {
   return name;
  }
 
  public void setName(String name)
  {
   this.name = name;
  }
 }
 

序列化 ID 在 Eclipse 下提供了两种生成策略,一个是固定的 1L,一个是随机生成一个不重复的 long 类型数据(实际上是使用 JDK 工具生成),在这里有一个建议,如果没有特殊需求,就是用默认的 1L 就可以,这样可以确保代码一致时反序列化成功。那么随机生成的序列化 ID 有什么作用呢,有些时候,通过改变序列化 ID 可以用来限制某些用户的使用。

特性使用案例

读者应该听过 Fa?ade 模式,它是为应用程序提供统一的访问接口,案例程序中的 Client 客户端使用了该模式,案例程序结构图如图 1 所示。

图 1. 案例程序结构
 

Client 端通过 Fa?ade Object 才可以与业务逻辑对象进行交互。而客户端的 Fa?ade Object 不能直接由 Client 生成,而是需要 Server 端生成,然后序列化后通过网络将二进制对象数据传给 Client,Client 负责反序列化得到 Fa?ade 对象。该模式可以使得 Client 端程序的使用需要服务器端的许可,同时 Client 端和服务器端的 Fa?ade Object 类需要保持一致。当服务器端想要进行版本更新时,只要将服务器端的 Fa?ade Object
类的序列化 ID 再次生成,当 Client 端反序列化 Fa?ade Object 就会失败,也就是强制 Client 端从服务器端获取最新程序。

——————————————————————————–
回页首
静态变量序列化

情境:查看清单 2 的代码。

清单 2. 静态变量序列化问题代码
    
 public class Test implements Serializable {

 private static final long serialVersionUID = 1L;

 public static int staticVar = 5;

 public static void main(String[] args) {
  try {
   //初始时staticVar为5
   ObjectOutputStream out = new ObjectOutputStream(
     new FileOutputStream(“result.obj”));
   out.writeObject(new Test());
   out.close();

   //序列化后修改为10
   Test.staticVar = 10;

   ObjectInputStream oin = new ObjectInputStream(new FileInputStream(
     “result.obj”));
   Test t = (Test) oin.readObject();
   oin.close();
   
   //再读取,通过t.staticVar打印新的值
   System.out.println(t.staticVar);
   
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  } catch (ClassNotFoundException e) {
   e.printStackTrace();
  }
 }
}
 

清单 2 中的 main 方法,将对象序列化后,修改静态变量的数值,再将序列化对象读取出来,然后通过读取出来的对象获得静态变量的数值并打印出来。依照清单 2,这个 System.out.println(t.staticVar) 语句输出的是 10 还是 5 呢?

最后的输出是 10,对于无法理解的读者认为,打印的 staticVar 是从读取的对象里获得的,应该是保存时的状态才对。之所以打印 10 的原因在于序列化时,并不保存静态变量,这其实比较容易理解,序列化保存的是对象的状态,静态变量属于类的状态,因此 序列化并不保存静态变量。

——————————————————————————–
回页首
父类的序列化与 Transient 关键字

情境:一个子类实现了 Serializable 接口,它的父类都没有实现 Serializable 接口,序列化该子类对象,然后反序列化后输出父类定义的某变量的数值,该变量数值与序列化时的数值不同。

解决:要想将父类对象也序列化,就需要让父类也实现Serializable 接口。如果父类不实现的话的,就 需要有默认的无参的构造函数。在父类没有实现 Serializable 接口时,虚拟机是不会序列化父对象的,而一个 Java 对象的构造必须先有父对象,才有子对象,反序列化也不例外。所以反序列化时,为了构造父对象,只能调用父类的无参构造函数作为默认的父对象。因此当我们取父对象的变量值时,它的值是调用父类无参构造函数后的值。如果你考虑到这种序列化的情况,在父类无参构造函数中对变量进行初始化,否则的话,父类变量值都是默认声明的值,如
int 型的默认是 0,string 型的默认是 null。

Transient 关键字的作用是控制变量的序列化,在变量声明前加上该关键字,可以阻止该变量被序列化到文件中,在被反序列化后,transient 变量的值被设为初始值,如 int 型的是 0,对象型的是 null。

特性使用案例

我们熟悉使用 Transient 关键字可以使得字段不被序列化,那么还有别的方法吗?根据父类对象序列化的规则,我们可以将不需要被序列化的字段抽取出来放到父类中,子类实现 Serializable 接口,父类不实现,根据父类序列化规则,父类的字段数据将不被序列化,形成类图如图 2 所示。

图 2. 案例程序类图
 

上图中可以看出,attr1、attr2、attr3、attr5 都不会被序列化,放在父类中的好处在于当有另外一个 Child 类时,attr1、attr2、attr3 依然不会被序列化,不用重复抒写 transient,代码简洁。

——————————————————————————–
回页首
对敏感字段加密

情境:服务器端给客户端发送序列化对象数据,对象中有一些数据是敏感的,比如密码字符串等,希望对该密码字段在序列化时,进行加密,而客户端如果拥有解密的密钥,只有在客户端进行反序列化时,才可以对密码进行读取,这样可以一定程度保证序列化对象的数据安全。

解决:在序列化过程中,虚拟机会试图调用对象类里的 writeObject 和 readObject 方法,进行用户自定义的序列化和反序列化,如果没有这样的方法,则默认调用是 ObjectOutputStream 的 defaultWriteObject 方法以及 ObjectInputStream 的 defaultReadObject 方法。用户自定义的 writeObject 和 readObject 方法可以允许用户控制序列化的过程,比如可以在序列化的过程中动态改变序列化的数值。基于这个原理,可以在实际应用中得到使用,用于敏感字段的加密工作,清单
3 展示了这个过程。

清单 3. 静态变量序列化问题代码
    
 private static final long serialVersionUID = 1L;

 private String password = “pass”;

 public String getPassword() {
  return password;
 }

 public void setPassword(String password) {
  this.password = password;
 }

 private void writeObject(ObjectOutputStream out) {
  try {
   PutField putFields = out.putFields();
   System.out.println(“原密码:” + password);
   password = “encryption”;//模拟加密
   putFields.put(“password”, password);
   System.out.println(“加密后的密码” + password);
   out.writeFields();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

 private void readObject(ObjectInputStream in) {
  try {
   GetField readFields = in.readFields();
   Object object = readFields.get(“password”, “”);
   System.out.println(“要解密的字符串:” + object.toString());
   password = “pass”;//模拟解密,需要获得本地的密钥
  } catch (IOException e) {
   e.printStackTrace();
  } catch (ClassNotFoundException e) {
   e.printStackTrace();
  }

 }

 public static void main(String[] args) {
  try {
   ObjectOutputStream out = new ObjectOutputStream(
     new FileOutputStream(“result.obj”));
   out.writeObject(new Test());
   out.close();

   ObjectInputStream oin = new ObjectInputStream(new FileInputStream(
     “result.obj”));
   Test t = (Test) oin.readObject();
   System.out.println(“解密后的字符串:” + t.getPassword());
   oin.close();
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  } catch (ClassNotFoundException e) {
   e.printStackTrace();
  }
 }
 

在清单 3 的 writeObject 方法中,对密码进行了加密,在 readObject 中则对 password 进行解密,只有拥有密钥的客户端,才可以正确的解析出密码,确保了数据的安全。执行清单 3 后控制台输出如图 3 所示。

图 3. 数据加密演示
 

特性使用案例

RMI 技术是完全基于 Java 序列化技术的,服务器端接口调用所需要的参数对象来至于客户端,它们通过网络相互传输。这就涉及 RMI 的安全传输的问题。一些敏感的字段,如用户名密码(用户登录时需要对密码进行传输),我们希望对其进行加密,这时,就可以采用本节介绍的方法在客户端对密码进行加密,服务器端进行解密,确保数据传输的安全性。

——————————————————————————–
回页首
序列化存储规则

情境:问题代码如清单 4 所示。

清单 4. 存储规则问题代码
    
 ObjectOutputStream out = new ObjectOutputStream(
     new FileOutputStream(“result.obj”));
 Test test = new Test();
 //试图将对象两次写入文件
 out.writeObject(test);
 out.flush();
 System.out.println(new File(“result.obj”).length());
 out.writeObject(test);
 out.close();
 System.out.println(new File(“result.obj”).length());

 ObjectInputStream oin = new ObjectInputStream(new FileInputStream(
   “result.obj”));
 //从文件依次读出两个文件
 Test t1 = (Test) oin.readObject();
 Test t2 = (Test) oin.readObject();
 oin.close();
   
 //判断两个引用是否指向同一个对象
 System.out.println(t1 == t2);
 

清单 3 中对同一对象两次写入文件,打印出写入一次对象后的存储大小和写入两次后的存储大小,然后从文件中反序列化出两个对象,比较这两个对象是否为同一对象。一般的思维是,两次写入对象,文件大小会变为两倍的大小,反序列化时,由于从文件读取,生成了两个对象,判断相等时应该是输入 false 才对,但是最后结果输出如图 4 所示。

图 4. 示例程序输出
 

我们看到,第二次写入对象时文件只增加了 5 字节,并且两个对象是相等的,这是为什么呢?

解答:Java 序列化机制为了节省磁盘空间,具有特定的存储规则,当写入文件的为同一对象时,并不会再将对象的内容进行存储,而只是再次存储一份引用,上面增加的 5 字节的存储空间就是新增引用和一些控制信息的空间。反序列化时,恢复引用关系,使得清单 3 中的 t1 和 t2 指向唯一的对象,二者相等,输出 true。该存储规则极大的节省了存储空间。

特性案例分析

查看清单 5 的代码。

清单 5. 案例代码
    
ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream(“result.obj”));
Test test = new Test();
test.i = 1;
out.writeObject(test);
out.flush();
test.i = 2;
out.writeObject(test);
out.close();
ObjectInputStream oin = new ObjectInputStream(new FileInputStream(
     “result.obj”));
Test t1 = (Test) oin.readObject();
Test t2 = (Test) oin.readObject();
System.out.println(t1.i);
System.out.println(t2.i);
 

清单 4 的目的是希望将 test 对象两次保存到 result.obj 文件中,写入一次以后修改对象属性值再次保存第二次,然后从 result.obj 中再依次读出两个对象,输出这两个对象的 i 属性值。案例代码的目的原本是希望一次性传输对象修改前后的状态。

结果两个输出的都是 1, 原因就是第一次写入对象以后,第二次再试图写的时候,虚拟机根据引用关系知道已经有一个相同对象已经写入文件,因此只保存第二次写的引用,所以读取时,都是第一次保存的对象。读者在使用一个文件多次 writeObject 需要特别注意这个问题。

——————————————————————————–
回页首
小结

本文通过几个具体的情景,介绍了 Java 序列化的一些高级知识,虽说高级,并不是说读者们都不了解,希望用笔者介绍的情景让读者加深印象,能够更加合理的利用 Java 序列化技术,在未来开发之路上遇到序列化问题时,可以及时的解决。由于本人知识水平有限,文章中倘若有错误的地方,欢迎联系我批评指正。

 

[ssh ][异常]The type org.springframework.dao.support.DaoSupport cannot be resolved……..

写spring的时候,使用SqlMapClientDaoSupport,结果报出异常:

The type org.springframework.dao.support.DaoSupport cannot be resolved. It is indirectly referenced from required .class files

 

上网搜索了一下:发现有些地方说,把spring-core-xx.jar换成 spring.jar。可是spring包里边没有这个jar。

后来发现,要添加一个

org.springframework.transaction-3.0.5.RELEASE.jar,就可以了。

minix添加系统调用

环境minix3.1.8

打印进程的vm信息:

添加系统调用分为三个部分:

1,库函数向用户提供接口;

2,pm接受消息处理信息;

3,vm接收消息处理信息。

 

1库函数添加:

  1.1 posix/下添加print_vmmap函数,文件名命名为_print_vmmap.c:

#include<lib.h>
#define print_vmmap _print_vmmap
#include<unistd.h>
PUBLIC int print_vmmap()
{
 message m;
 return(_syscall(PM_PROC_NR, PM_PRINTVMMAP, &m));
}

  1.2 修改posix下边的makefile.inc文件,按照格式添加

  1.3在include/unistd.h下添加函数原型:_PROTOTYPE( int  print_vmmap, (void));

  1.4libc/syscall下添加print_vmmap.s文件:

#include <machine/asm.h>

IMPORT(_print_vmmap)
ENTRY(print_vmmap)
 jmp _C_LABEL(_print_vmmap)

  1.5修改syscall下边的makefile

 

2:pm的处理

    2.1修改callnr.h:

          把NCALLS加1;

          添加#define PM_PRINTVMMAP 113;

   2.2修改pm/proto.h

          添加do_pmprintvmmap的原型:_PROTOTYPE( int do_pmprintvmap, (void)      );

   2.3在pm/getset.c(也可以是其他的c文件)中添加处理函数:

  int do_pmprintvmap()
{
 int result;
 message m;
 printf(“pm debug/n”);
 result=1;
 m.m1_i1=mp->mp_endpoint;
 result=_taskcall(VM_PROC_NR, VM_PM_PRINTMAP,&m);
 return result;
}

   2.4修改pm/table.c添加消息处理函数:do_pmprintvmap,/*113= print vmmap*/

   2.5修改vfs/table.c:no_sys,   /*113= print vm map*/(此处必须添加。)

 

 

3vm的处理:

 3.1修改include/minix/com.h定义vm的新消息。

        #define VM_PM_PRINTMAP     (VM_RQ_BASE+43)

        /* Total. */
        #define NR_VM_CALLS    44

 3.2在mmap.c(也可以是其他的c文件)中添加函数:

      PUBLIC int do_printvmmap(message *m)
{
 int result=1;
 int proc;
 struct vmproc * vmp;
 struct vir_region * vir_r;
 printf(“start-addr end-addr permission /n”);
 if(vm_isokendpt(m->m1_i1, &proc) != OK) {
     printf(“VM: bogus endpoint VM_print vm map %d/n”, m->m1_i1);
  
  return EINVAL;
   }
 vmp=&vmproc[proc];
 vir_r=vmp->vm_regions;
 
 while(vir_r!=NULL){
  printf(“%lu %lu r”,vir_r->vaddr,vir_r->length+vir_r->vaddr);
  if(vir_r->flags&VR_WRITABLE)
   printf(“w”);
  else
   printf(“-“);
  printf(“/n”);
  vir_r=vir_r->next;
 }
 return result; 
}
 3.3在vm/proto.h中添加声明:

      _PROTOTYPE(int do_printvmmap, (message *m)                            );
  3.4在vm/main.c中添加CALLMAP处理消息:

            CALLMAP(VM_PM_PRINTMAP,do_printvmmap);

  3.5在vm/main.c中做处理,躲避权限检查:

          if (msg.m_type == VM_PAGEFAULT) {
  if (!IPC_STATUS_FLAGS_TEST(rcv_sts, IPC_FLG_MSG_FROM_KERNEL)) {
    }
 } else if(c < 0 || !vm_calls[c].vmc_func) {
   } else {
  if (msg.m_type != VM_PM_PRINTMAP &&
   vm_acl_ok(who_e, c) != OK) {
  } else {
  }
 }

 

4编译和安装新的内核。

  4.1在是src/lib文件夹make install;

  4.2在src/servers下边make install;

  4.3在src/tools文件夹make install

  4.4重启系统

5编写测试文件:

#include<stdio.h>

#include<unistd.h>
int main()
{
  print_vmmap();
 }

用cc命令编译该文件,注意不能用gcc命令。

 

[usaco] Cow Pedigrees

Cow Pedigrees
Silviu Ganceanu — 2003

Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees
have these properties:

The degree of each node is 0 or 2. The degree is the count of the node’s immediate children.
The height of the tree is equal to K (1 < K <100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.
How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

PROGRAM NAME: nocows
INPUT FORMAT
Line 1: Two space-separated integers, N and K.
SAMPLE INPUT (file nocows.in)
5 3

OUTPUT FORMAT
Line 1: One single integer number representing the number of possible pedigrees MODULO 9901.
SAMPLE OUTPUT (file nocows.out)
2

OUTPUT DETAILS
Two possible pedigrees have 5 nodes and height equal to 3:
           @                   @     
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

——————————————————————————————————–
这是个典型的动态规划的问题:
欲求一个高度为K的二叉树,要从一个等于K-1,一个小于等于K-1的两个二叉树构造而来。
关键之处在于,用哈希映射来快速的查找。
还有,是自底向上构造二叉树,还是自上向下的构造二叉树。根据动态规划,类似于斐波纳旗公式,存在很多重复计算的问题,
因此自底向上计算的,可以减少重复。

还有减枝的问题。对于高度为K的二叉树,节点数是2×K-1 -》2^k-1;对于超过N的节点,就不必计算了。
这会减少很多计算。
还有,节点数不再这个范围内的数,直接返回0就不必计算。

我的解法:
——————————————————————————————————–

/*
ID: yunleis2
PROG: nocows
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

int ind[203]; 
 
class unit
{
public:
	int c;
	int h;
	int n;
	unit(int c,int h,int n)
	{
		this->c=c;
		this->h=h;
		this->n=n;
	}
	unit(){}
	friend ostream & operator <<(ostream & out,unit u)
	{
		out<<u.c<<"\t"<<u.h<<"\t"<<u.n<<endl;
		return out;
	}
};
vector<unit> v; 
#define max(x,y)  (x>y?x:y)

int main()
{
	fstream fin("nocows.in",ios::in);
	int N,K;
	fin>>N>>K;
	unit u(1,1,1);
	v.push_back(u);

	for(int i=0;i<203;i++)
		ind[i]=-1;
	int total=0;
	int ptr=0;
	vector<unit> v1;
	
	 

	bool flag=false;
	if((N<(2*K-1))||(N>(pow((double)2,K)-1)))
		flag=true;
	while(!flag)
	{ 

		int i;
		for(i=ptr;i<v.size()&&!flag;i++)
		{
			
			unit u1=v.at(i);
			 
			if((u1.h)>=K)
			{
				flag=true;
				break;
			}
			for(int j=0;j<=i;j++)
			{
				unit u2=v.at(j);
				
				int c=1+u1.c+u2.c;
				if(c>N)
					continue;
				int h=max(u1.h,u2.h)+1;
				int n=u1.n*u2.n%9901;
				if(i!=j)
					n=2*n;
				unit u(c,h,n);
				//v.push_back(u);
				//add to the temp vec
				if(ind[u.c]==-1){
					v1.push_back(u);
					ind[u.c]=v1.size()-1;//ind[u.c]=v1.size()-1;
				}
				else
				{
					v1.at(ind[u.c]).n+=u.n;
				}
			}
		}
		for(int s=0;s<v1.size();s++)
		{
			v1.at(s).n=v1.at(s).n%9901;
			v.push_back(v1.at(s));
			ind[v1.at(s).c]=-1;
			cout<<v1.at(s);
			if(v1.at(s).c==N&&v1.at(s).h==K)
			{
				flag=true;
				total=v1.at(s).n;
				break;
			}
			
		}
		
		v1.clear(); 
		ptr=i;
		
	}
	
	
	 
	 
	fstream fout("nocows.out",ios::out);
	fout<<total<<endl;
	 
	 
  return 0;

 }


 

do while 循环的执行逻辑

do while 相对于while循环而言,平时用的非常少,因此有一些问题也非常的容易出错。

比如,在do while的循环体中,假如有一个continue,那么你觉得这个continue会跳转到do呢?还是条传到while呢?

答案是跳转到while,直接执行while里边的判断条件

[usaco] Number Triangles

Number Triangles

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

PROGRAM NAME: numtri

INPUT FORMAT

The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

SAMPLE INPUT (file numtri.in)

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

OUTPUT FORMAT

A single line containing the largest sum using the traversal specified.

SAMPLE OUTPUT (file numtri.out)

30

 

解体的要点在于,把数据转化成二叉树。然后自底向上计算每个节点的高度。但是注意,由于每个节点同时作为两个节点的子节点(一个是左子节点,一个是右子节点)。

这样可能会造成每个节点计算两次,于是设计每个几点的高度初始值为-1. 当判断高度不会-1时,就不必在计算该节点的高度了。之所以初始值不为0,是因为某个test case全为0.

这样还是会造成重复的递归。

我的解法:

/*
ID: yunleis2
PROG: numtri
LANG: C++
*/

#include<iostream>
#include<fstream>
#include<queue>
using namespace std;

#define max(a,b) (a>b?a:b)

class node
{
public:
 node * left;
 node * right;
 int value;
 int length;
 node(node * l,node * r)
 {
  left=l;
  right=r;
 }
 node ()
 {left=NULL;right=NULL;value=0;length=-1;}

};
int  search( node *root);
void print(node *);
int main()
{
 fstream fin(“numtri.in”,ios::in);
 int line;
 fin>>line;
 int size=(line+1)*line/2;
 node * root=new node();

 queue<node *> q;
 fin>>root->value;
 q.push(root);
 for(int i=1;i<line;i++)
 {
  node * last=NULL;
  for(int j=1;j<=i;j++)
  {
   node * ptr=q.front();
   q.pop();
   if(j==1)
   {
    ptr->left=new node();
    fin>>ptr->left->value;
    q.push(ptr->left);
   }
   else
   {
    ptr->left=last->right;
   }
   ptr->right=new node();
   fin>>(ptr->right)->value;
   last=ptr;
   
   q.push(ptr->right);
  }
 }
 while(!q.empty())
  q.pop();
 //print(root);
 int length=search(root);
 fstream fout(“numtri.out”,ios::out);
 fout<<root->length<<endl;
 //system(“pause”);
 
}
void print(node * root)
{
 if(root!=NULL)
 {
  cout<<root->value;
  print(root->left);
  print(root->right);
 }
}
int  search( node *root)
{
 if(root==NULL)
  return 0;
 if(root->length!=-1)
  return root->length;
 root->length=max(search(root->right),search(root->left))+root->value;
 return root->length;
}

—————————————————————————————————————————————————————————————————————————————

usaco的解法
Number Triangles
Russ Cox

We keep track (in the “best” array) of total for the best path ending in a given column of the triangle. Viewing the input, a path through the triangle always goes down or down and to the right. To process a new row, the best path total ending at a given column is the maximum of the best path total ending at that column or the one to its left, plus the number in the new row at that column. We keep only the best totals for the current row (in “best”) and the previous row (in “oldbest”).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXR 1000
int
max(int a, int b)
{
	return a > b ? a : b;
}
void
main(void){
	int best[MAXR], oldbest[MAXR];
	int i, j, r, n, m;
	FILE *fin, *fout;
	fin = fopen("numtri.in", "r");
	assert(fin != NULL);
	fout = fopen("numtri.out", "w");
	assert(fout != NULL);
	fscanf(fin, "%d", &r);

	for(i=0; i<MAXR; i++)
		best[i] = 0;

	for(i=1; i<=r; i++) {
		memmove(oldbest, best, sizeof oldbest);
		for(j=0; j<i; j++) {
			fscanf(fin, "%d", &n);
			if(j == 0)
				best[j] = oldbest[j] + n;
			else
				best[j] = max(oldbest[j], oldbest[j-1]) + n;
		}
	}
	m = 0;
	for(i=0; i<r; i++)
		if(best[i] > m)
			m = best[i];

	fprintf(fout, "%d\n", m);
	exit(0);
}

 

 

 

[usaco]超级素数 superprime

偶也,纪念一次成功,首先发测试结果

USER: Ma yunlei [yunleis2]
TASK: sprime
LANG: C++

Compiling…
Compile: OK

Executing…
   Test 1: TEST OK [0.000 secs, 3028 KB]
   Test 2: TEST OK [0.000 secs, 3028 KB]
   Test 3: TEST OK [0.000 secs, 3028 KB]
   Test 4: TEST OK [0.000 secs, 3028 KB]
   Test 5: TEST OK [0.000 secs, 3028 KB]

All tests OK.
YOUR PROGRAM (‘sprime’) WORKED FIRST TIME!  That’s fantastic
— and a rare thing.  Please accept these special automated
congratulations.

Here are the test data inputs:

——- test 1 —-
4
——- test 2 —-
5
——- test 3 —-
6
——- test 4 —-
7
——- test 5 —-
8

Keep up the good work!

Thanks for your submission!

问题:
Superprime Rib
Butchering Farmer John’s cows always yields the best prime rib. You can tell prime ribs by looking at the digits lovingly stamped across them, one by one, by FJ and the USDA. Farmer John ensures that a purchaser of his prime ribs gets really prime ribs because when sliced from the right, the numbers on the ribs continue to stay prime right down to the last rib, e.g.:

     7  3  3  1

The set of ribs denoted by 7331 is prime; the three ribs 733 are prime; the two ribs 73 are prime, and, of course, the last rib, 7, is prime. The number 7331 is called a superprime of length 4.

Write a program that accepts a number N 1 <=N<=8 of ribs and prints all the superprimes of that length.

The number 1 (by itself) is not a prime number.

PROGRAM NAME: sprime
INPUT FORMAT
A single line with the number N.
SAMPLE INPUT (file sprime.in)
4

OUTPUT FORMAT
The superprime ribs of length N, printed in ascending order one per line.
SAMPLE OUTPUT (file sprime.out)
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

我的程序:
/*
ID: yunleis2
PROG: sprime
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int single[]={
 1,3,5,7,9
};
vector<int > v;
void check(int depth,int num);
bool isprime(int num);
void quicksort(int * a,int p,int r);
int main()
{
 fstream fin(“sprime.in”,ios::in);
 int N;
 fin>>N;
 int num;
 check(N,0);
 int *result=new int[v.size()];
 for(int i=0;i<v.size();i++)
 {
  result[i]=v.at(i);
 }
 quicksort(result,0,v.size()-1);
 fstream fout(“sprime.out”,ios::out);
 for(int i=0;i<v.size();i++)
  fout<<result[i]<<endl;
 

}
bool isprime(int num)
{
 if(num==1)
  return false;
 if(num==2)
  return true;
 for(int i=2;i*i<=num;i++)
 {
  if(num%i==0)
   return false;
 }
 return true;
}
void check(int depth,int num)
{
  if(depth==0)
 {
  v.push_back(num);
  return;
 }
 for(int i=0;i<(sizeof(single)/sizeof(int));i++)
 {
  int newnum=num*10+single[i];
  if(isprime(newnum))
   check(depth-1,newnum);
 }
 if(num==0)
  check(depth-1,2);
}

void swap(int * x,int * y)
{
 int t=*x;
 *x=*y;
 *y=t;
}
int partition(int* a,int p,int r)
{
 int i=p-1;
 int x=a[r];
 for(int j=p;j<r;j++)
 {
  if(a[j]<=x)
  {
   i++;
   swap(a+j,a+i);
  }
 }
 swap(a+i+1,a+r);return i+1;
}
void quicksort(int * a,int p,int r)
{
 if(p<r)
 {
  int q=partition(a,p,r);
  quicksort(a,p,q-1);
  quicksort(a,q+1,r);
 }
}

usaco的解法:
We use a recursive search to build superprimes of length n from superprimes of length n-1 by adding a 1, 3, 7, or 9. (Numbers ending in any other digit are divisible by 2 or 5.) Since there are so few numbers being tested, a simple primality test suffices.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

FILE *fout;

int
isprime(int n)
{
 int i;

 if(n == 2)
  return 1;

 if(n%2 == 0)
  return 0;

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

 return 1;
}

/* print all sprimes possible by adding ndigit digits to the number n */
void
sprime(int n, int ndigit)
{
 if(ndigit == 0) {
  fprintf(fout, “%d\n”, n);
  return;
 }

 n *= 10;
 if(isprime(n+1))
  sprime(n+1, ndigit-1);
 if(isprime(n+3))
  sprime(n+3, ndigit-1);
 if(isprime(n+7))
  sprime(n+7, ndigit-1);
 if(isprime(n+9))
  sprime(n+9, ndigit-1);
}

void
main(void)
{
 int n;
 FILE *fin;

 fin = fopen(“sprime.in”, “r”);
 assert(fin != NULL);
 fout = fopen(“sprime.out”, “w”);
 assert(fout != NULL);

 fscanf(fin, “%d”, &n);

 sprime(2, n-1);
 sprime(3, n-1);
 sprime(5, n-1);
 sprime(7, n-1);
 exit (0);
}

 

 

 

[usaco]4.1.3 Fence Rails 多维背包问题,dfsid

 Fence Rails
Burch, Kolstad, and Schrijvers
Farmer John is trying to erect a fence around part of his field. He has decided on the shape of the fence and has even already installed the posts, but he’s having a problem with the rails. The local lumber store has dropped off boards of varying lengths; Farmer
John must create as many of the rails he needs from the supplied boards.

Of course, Farmer John can cut the boards, so a 9 foot board can be cut into a 5 foot rail and a 4 foot rail (or three 3 foot rails, etc.). Farmer John has an `ideal saw’, so ignore the `kerf’ (distance lost during sawing); presume that perfect cuts can
be made.

The lengths required for the rails might or might not include duplicates (e.g., a three foot rail and also another three foot rail might both be required). There is no need to manufacture more rails (or more of any kind of rail) than called for the list
of required rails.

PROGRAM NAME: fence8
INPUT FORMAT
Line 1:  N (1 <= N <= 50), the number of boards 
Line 2..N+1:  N lines, each containing a single integer that represents the length of one supplied board 

Line N+2:  R (1 <= R <= 1023), the number of rails 
Line N+3..N+R+1:  R lines, each containing a single integer (1 <= ri <= 128) that represents the length of a single required fence rail 

SAMPLE INPUT (file fence8.in)
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

OUTPUT FORMAT
A single integer on a line that is the total number of fence rails that can be cut from the supplied boards. Of course, it might not be possible to cut all the possible rails from the given boards.

SAMPLE OUTPUT (file fence8.out)
7

HINTS (use them carefully!)
Fence Rails: Hint 1
This is a high dimensionality multiple knapsack problem, so we just have to test the cases. Given that the search space has a high out-degree, we will use depth first search with iterative deepening in order to limit the depth of the tree. However, straight
DFSID will be too slow, so some tree-pruning is necessary.

———————————————————
多维背包问题
使用dfs遍历,
首先把rails排序,然后,从最大的rail开始遍历。
对于第k个rail,遍历所有的板子,然后遍历地k-1个rail。如果所有的rail都有解法,则输出最开始rail。
usaco称之为DFSID

/*
ID:yunleis2
PROG:fence8
LANG:C++
*/


#include<iostream>
#include<fstream>

using namespace std;
const int MAXB=50;
const int MAXR=1024;
int boards[MAXB];
int remains[MAXB];
int rails[MAXR];
int b;
int r;
int board_sum=0;
int result=0;
int waste_max=0;
int from[MAXR];
fstream fout("fence8.out",ios::out);
inline void swap(int * a,int * b){
	int t=*a;
	*a=*b;
	*b=t;
//	*a=*a+*b;
//	*b=*a-*b;
//	*a=*a-*b;
}
int partiton(int * a,int p,int r)
{
	int x=a[r];
	int i=p-1;
	for(int j=p;j<r;j++){
		if(a[j]<x){
			++i;
			swap(a+j,a+i);
		}
	}
	swap(a+i+1,a+r);
	return i+1;
}
void quicksort(int * a,int p,int r)
{
	if(p<r)
	{
		int q=partiton(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
void dfs(int k,int waste){
	if(k<0){
		fout<<result+1<<endl;
		exit(0);
	}
	int i=0;
	if(k!=result&&rails[k]==rails[k+1])
		i=from[k+1];
	for(;i<b;i++){
		if(remains[i]>=rails[k]){
			from[k]=i;
			remains[i]-=rails[k];
			if(remains[i]<rails[0])waste+=remains[i];
			if(waste>waste_max){
				remains[i]+=rails[k];
				waste-=remains[i];
				continue;
			}
			dfs(k-1,waste);
			remains[i]+=rails[k];
		}
	}
}
int main()
{

	fstream fin("fence8.in",ios::in );
	fin>>b;
	for(int i=0;i<b;i++)
	{
		fin>>boards[i];
		board_sum+=boards[i];
		remains[i]=boards[i];
	}
	fin>>r;
	for(int i=0;i<r;i++)
		fin>>rails[i];
	quicksort(boards,0,b-1);
	quicksort(rails,0,r-1);
	int rail_sum=0;
	for(int i=0;i<r;i++){
		rail_sum+=rails[i];
		if(rail_sum>board_sum)
		{
			rail_sum-=rails[i];
			r=i;
			break;
		}
	}

	for(int i=r-1;i>=0;--i){
		result=i;
		waste_max = board_sum - rail_sum;
		rail_sum -= rails[i];
		dfs(i,0);
	}
	fout<<0<<endl;
	return 0;
}