0%

本文是mybatis框架一个初步的入门总结,最全的最好的资料应该参考这个

本文在Eclipse下搭建一个小程序可以测试mybatis对mysql数据库进行增删改查这几个基本功能。

1.首先建立数据库,我建立的数据库叫test,编码是UTF-8,里面有两张表,它们是这样的:

pic1

两张表的数据我填的是这样的,当然可以随便填,不过最好在person中有1个以上name相同的,后面会用到:

pic2

2.在ECLIPISE下建立DYNAMIC WEB PROJECT,别忘了在BUILD PATH下加入mybatis和mysql的jar包。这个工程的布局是这样的:

文件和类的用途后面解释

pic3

Main里面有程序的static void main函数。Test类封装了测试mybatis框架功能的函数。xml都是框架的配置文件。Person与Student是DTO数据传输对象。两个Mapper类都是接口类,用途后面讲。

3.配置Configuration.xml。在src文件夹下先建立这个文件。

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE configuration PUBLIC "-//mybatis.org//DTD Config 3.0//EN"
"http://mybatis.org/dtd/mybatis-3-config.dtd">
<configuration>
    <typeAliases> 
        <typeAlias alias="Person" type="com.ymy.mybatis.model.Person"/> 
        <typeAlias alias="Student" type="com.ymy.mybatis.model.Student"/> 
        <!-- short name of java classes -->
    </typeAliases> 

    <environments default="development">
        <environment id="development">
            <!--
            choose any name for default and id
              -->
        <transactionManager type="JDBC"/>
            <dataSource type="POOLED">
            <property name="driver" value="com.mysql.jdbc.Driver"/>
            <property name="url" value="jdbc:mysql://127.0.0.1:3306/test"/>
            <property name="username" value="root"/>
            <property name="password" value="31415926"/>
            <property name="driver.encoding" value="UTF8"/>
            <!--property name="PROPERTY NAME" value="${var name}"/-->
            </dataSource>
        </environment>
    </environments>
    
    <mappers>
        <mapper resource="com/ymy/mybatis/model/Person.xml"/>
        <mapper resource="com/ymy/mybatis/model/Student.xml"/>
        <!-- xml of mapper class -->
    </mappers>
</configuration>

标签解释:

<typeAliases> 定义的是别名,全名是type里的一大串,起个别名减少了后面的书写量。

<environments>和<environment>配置了数据库的信息,一个environments下可以配多个environment来访问多个数据库,这超出了本文讨论范围。这个文章:http://zhangbo-peipei-163-com.iteye.com/blog/2052924讲了多数据源配置。

<property name>和value改成自己的数据库的就行了

<mappers>下定义多个<mapper>每个mapper对应一个DTO类型,以及它们对应的数据库操作。mapper resource后面是对应DTO的xml文件的实际位置。

3.建立DTO类Student和Person。

Student类:

package com.ymy.mybatis.model;

public class Student {
    private int id;
    private String name;
    private int score;

    public Student() {
    }

    public int getID() {
        return id;
    }

    public void setID(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    public int getScore() {
        return score;
    }

    public void setScore(int score) {
        this.score = score;
    }
}

Person类:

package com.ymy.mybatis.model;

public class Person {
    private int id;
    private String name;
    private int age;
    private String address;

    public Person(String name, int age, String address) {
        this.name = name;
        this.age = age;
        this.address = address;
    }

    public Person(int id, String name, int age, String address) {
        this.id = id;
        this.name = name;
        this.age = age;
        this.address = address;
    }

    public Person() {
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getAddress() {
        return address;
    }

    public void setUserAddress(String userAddress) {
        this.address = userAddress;
    }
}

4.配置Student.xml

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" 
"http://mybatis.org/dtd/mybatis-3-mapper.dtd">

<mapper namespace="com.ymy.mybatis.model.StudentMapper">
  <select id="selectStudentByID" parameterType="int" resultType="Student">
     select * from student where id = #{id}
 </select>
</mapper>

解释:< mapper namespace >那句,相当于在命名空间com.ymy.mybatis.model.StudentMapper下定义了一个叫selectStudentByID的语句,它接收的参数类型(parameterType)为int,返回类型为Student。到后面我们定义了接口类StudentMapper,mybatis就会把接口中的函数和xml中的定义绑定。< select >标签说明这是查询类型的操作。

接口类StudentMapper:

package com.ymy.mybatis.model;

public interface StudentMapper {
    public Student selectStudentByID(int id);
}

配置Person.xml

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" 
"http://mybatis.org/dtd/mybatis-3-mapper.dtd">

<mapper namespace="com.ymy.mybatis.model.PersonMapper">
     <resultMap id="personResultMap" type="Person">
            <id property="id" column="id" />
             <result property="name" column="name"/>
             <result property="age" column="age"/>
             <result property="address" column="address"/>
    </resultMap>

    <select id="selectPersonByID" parameterType="int" resultType="Person">
         select * from person where id = #{id}
    </select>

    <select id="selectPersonByName" parameterType="String" resultMap="personResultMap">
         select * from person where name = #{name}
    </select>

    <select id="lastInsertId" resultType="int">
          select last_insert_id()
    </select>

    <insert id="addPerson" parameterType="Person">
            insert into person (id,name,age,address)
            values (NULL,#{name},#{age},#{address})
    </insert>

    <update id="updatePerson" parameterType="Person">
            update person set
            name = #{name},
            age = #{age},
            address= #{address}
            where id = #{id}
    </update>

    <delete id="deletePerson" parameterType="int">
         delete from person where id = #{id}
    </delete>
</mapper>

看sql语句就知道都是干啥的了,增删改查已经全了。重点是selectPersonByName。数据库里有重名的人,所以会查询到多个人。这时返回类型标签成了resultMap。值为personResultMap。文件最前面定义了personResultMap。result里面property是DTO里变量的名称。column和数据库里的名称对应。

接口类PersonMapper:

package com.ymy.mybatis.model;

import java.util.List;

public interface PersonMapper {
    public Person selectPersonByID(int id);
    public List<Person> selectPersonByName(String name);
    
    public void addPerson(Person person);
    public void deletePerson(int id);
    public void updatePerson(Person person);
    public int lastInsertId();
}

5.写测试代码:

Test类:

package com.ymy.mybatis.test;

import java.io.*;
import java.util.*;

import org.apache.ibatis.io.Resources;
import org.apache.ibatis.session.SqlSession;
import org.apache.ibatis.session.SqlSessionFactory;
import org.apache.ibatis.session.SqlSessionFactoryBuilder;

import com.ymy.mybatis.model.*;

public class Test {
    private static SqlSessionFactory sqlSessionFactory;
    // it should be static
    // every thread should have its own SqlSession instance
    private static Reader reader;
    static {
        try {
            reader = Resources.getResourceAsReader("Configuration.xml");
            sqlSessionFactory = new SqlSessionFactoryBuilder().build(reader);
            // every database should have its own SqlSessionFactory
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void getPersonList(String userName) {
        SqlSession session = sqlSessionFactory.openSession();
        try {
            PersonMapper mapper = session.getMapper(PersonMapper.class);
            List<Person> people = mapper.selectPersonByName(userName);
            for (Person person : people) {
                System.out.print("Name: " + person.getName() + "\t");
                System.out.print("Age: " + person.getAge() + "\t");
                System.out.println("Addr: " + person.getAddress());
            }
        } finally {
            session.close();
        }
    }

    public void addPerson() {
        @SuppressWarnings("resource")
        Scanner inputer = new Scanner(System.in);
        System.out.println("Input a person's name age and address");
        String name = inputer.next();
        int age = inputer.nextInt();
        String address = inputer.next();

        Person newPerson = new Person(name, age, address);
        SqlSession session = sqlSessionFactory.openSession();
        try {
            PersonMapper mapper = session.getMapper(PersonMapper.class);
            mapper.addPerson(newPerson);
            int last_id = mapper.lastInsertId();
            System.out.println("Insert id = " + last_id);
            session.commit();
        } finally {
            session.close();
        }
    }
    
    public void updatePerson() {
        @SuppressWarnings("resource")
        Scanner inputer = new Scanner(System.in);
        System.out.println("Input a person's id, name, age and address");
        int id = inputer.nextInt();
        String name = inputer.next();
        int age = inputer.nextInt();
        String address = inputer.next();

        Person person = new Person(id, name, age, address);
        SqlSession session = sqlSessionFactory.openSession();
        try {
            PersonMapper mapper = session.getMapper(PersonMapper.class);
            mapper.updatePerson(person);
            session.commit();
            System.out.println("OK!");
        } finally {
            session.close();
        }
    }

    public void deletePerson() {
        @SuppressWarnings("resource")
        Scanner inputer = new Scanner(System.in);
        System.out.println("Input an id to delete:");
        int id = inputer.nextInt();

        SqlSession session = sqlSessionFactory.openSession();
        try {
            PersonMapper mapper = session.getMapper(PersonMapper.class);
            mapper.deletePerson(id);
            session.commit();
        } finally {
            session.close();
        }
    }
    
    public void selectPersonById(){
        @SuppressWarnings("resource")
        Scanner inputer = new Scanner(System.in);
        System.out.println("Input an id to select:");
        int id = inputer.nextInt();
        
        SqlSession session = sqlSessionFactory.openSession();
        try {
            PersonMapper mapper = session.getMapper(PersonMapper.class);
            Person person = mapper.selectPersonByID(id);
            System.out.print("Name: " + person.getName() + "\t");
            System.out.print("Age: " + person.getAge() + "\t");
            System.out.println("Addr: " + person.getAddress());
        } finally {
            session.close();
        }
    }
    
    public void selectStudentById(){
        @SuppressWarnings("resource")
        Scanner inputer = new Scanner(System.in);
        System.out.println("Input an student id to select:");
        int id = inputer.nextInt();
        
        SqlSession session = sqlSessionFactory.openSession();
        try {
            StudentMapper mapper = session.getMapper(StudentMapper.class);
            Student student = mapper.selectStudentByID(id);
            System.out.print("Name: " + student.getName() + "\t");
            System.out.print("ID: " + student.getID() + "\t");
            System.out.println("Score: " + student.getScore());
        } finally {
            session.close();
        }
    }
    
}

解释:我们通过SqlSession类的对象获取映射(使用getMapper方法),通过映射调用Student和Person接口类里的函数。SqlSession参与数据库的管理事务。当执行了修改数据库内容的语句后调用commit()方法讲更改的内容写入数据库。完成后及时关闭SqlSession对象,调用close()方法。

最后写Main类,然后运行程序:

package com.ymy.mybatis.test;

public class Main {
    public static void main(String[] args) {
        Test t1 = new Test();
        t1.selectPersonById();
        t1.getPersonList("Bill");// find Bill
        t1.addPerson();
        t1.deletePerson();
        t1.updatePerson();
        
        t1.selectStudentById();
    }
}

这学期开始时本来打算写个自动生成迷宫的程序。但当时水平所限,写不出来。假期这两天把这个想法付诸实施,现在想想这个程序挺有意思的。

程序和道理都非常简单,有些类似于走迷宫。

思路是这样:

1.首先假设迷宫场地是充满墙壁没有道路的。我们的工作其实就是把迷宫“挖”出来。不妨把开始时的迷宫看成一些小的“房间”,每个“房间”四面都被墙壁包围。画迷宫的过程实际就是从一个房间随机走到另一个房间,走的过程中把墙壁“挖掉”。定义一个类,这个类的每个对象代表迷宫里的一个格子,里面存放了这块墙壁或房间是否被挖过,以及它是否是一个“房间”。选好一个房间作为起点(我选的左上角),然后开始随机挖。

2.到达一个房间时判断四周房间的情况。按照四个方向判断。如果其中一个方向的隔壁房间挖过了,就不要把这个方向记录下来。如果四周都不能挖了,就一路退回之前能挖的地方。再次随机一个新方向,继续挖。(有点类似走迷宫的过程)

程序中记录道路用了C++STL里的栈。

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <stack>
#include <vector>
#define M 25   //迷宫的规模
using namespace std;

class Grid{
public:
    bool cell, dig;
};
//迷宫格子类型,记录了是否被挖过
Grid maze[M][M];
stack<int> row_s, col_s;
//用来存放路径的栈
void Init(){
    for(int i=0; i<M; i++){
        for(int j=0; j<M; j++){
            maze[i][j].dig=false;
            if(i%2!=0 && j%2!=0)
                maze[i][j].cell=true;
        }
    }
    row_s.push(1);    col_s.push(1);
    srand(time(0));
}
//初始化迷宫格子
int DirRand(){
    vector <int> dirlist;        //用来记录可选择的方向
    int result=0;
    int row=row_s.top(), col=col_s.top();
    //0 up, 1 down, 2 left, 3 right
    if(row-2>0 && !maze[row-2][col].dig) dirlist.push_back(0);
    if(row+2<M-1 && !maze[row+2][col].dig) dirlist.push_back(1);
    if(col-2>0 && !maze[row][col-2].dig) dirlist.push_back(2);
    if(col+2<M-1 && !maze[row][col+2].dig) dirlist.push_back(3);
    if(dirlist.size()==0) result=-1;
    else result=dirlist[rand()%((int)dirlist.size())];
    return result;
}
//判断周围情况,没有可挖的格子时返回-1
void GenMaze(){
    while(!row_s.empty() && !col_s.empty()){
        int dir=DirRand();
        int row=row_s.top(), col=col_s.top();
        if(dir!=-1){     //前进
            if(dir==0){
                maze[row-2][col].dig=maze[row-1][col].dig=true;
                row_s.push(row-2);  col_s.push(col);
            }else if(dir==1){
                maze[row+2][col].dig=maze[row+1][col].dig=true;
                row_s.push(row+2);  col_s.push(col);
            }else if(dir==2){
                maze[row][col-2].dig=maze[row][col-1].dig=true;
                row_s.push(row);    col_s.push(col-2);
            }else if(dir==3){
                maze[row][col+2].dig=maze[row][col+1].dig=true;
                row_s.push(row);    col_s.push(col+2);
            }
        }else{
            row_s.pop();    col_s.pop();        //后退
        }
    }
}

void OutMaze(){      //输出迷宫
    for(int i=0; i<M; i++){
        for(int j=0; j<M; j++){
            if(maze[i][j].cell || maze[i][j].dig)
            cout<<"  ";
            else cout<<"##";        //为了保证对齐,墙壁和道路宽都是2个字符
        }
        cout<<endl;
    }
}

int main(){
    Init();
    GenMaze();
    OutMaze();
    return 0;
}

算法主要参考:http://en.wikipedia.org/wiki/Maze_generation_algorithm

每次升级内核都要重新编译网卡驱动,好麻烦(驱动是网上下的,BCM43142,系统自己没有)。刚好在学LINUX SHELLSCRIPT。写个SHELLSCRIPT,以后就成全自动安装了!

#########################################################################
# File Name: NetcardCompiler.sh
# Author: ymy
# Created Time: Tue 15 Jul 2014 09:58:37 AM CST
#########################################################################
#!/bin/bash

cd ~/Compile/hybrid-v35_64-nodebug-pcoem-6_30_223_141
make clean
make API=WEXT
if [ -f 'wl.ko' ] ; then
    cp wl.ko /lib/modules/`uname -r`/kernel/net/wireless
else
    echo 'Compile failed!'
    exit
fi
modprobe lib80211
modprobe lib80211_crypt_tkip
insmod wl.ko
depmod -a
echo modprobe wl>> /etc/rc.local

驱动的压缩包之前解压过了。如果要经常编译还是不要把解压后的文件夹删掉,最好把常用的软件解压到一个统一的地方。

两个问题,代表线段树中最基础的两类:1.更新数组里某个值然后查询。2.统一更新数组中一段区间的值然后查询。放假回来这两天也就看到了这里:)

为什么要学习线段树(个人之见):1.如果有上万甚至更多的数据反复查找并更新,用这个数据结构就比较高效了。2.高级的数据结构和算法多学些没坏处,尤其大一大二需要注重基础。3.想考这个证书的话需要学:)

第一类问题:

成电OJ 838 母仪天下

富庶的建业城中,有一条格格不入的长街,名曰跳蚤街,被战争所致的孤儿,聚集于此。全国的经济都在为战争服务之时,也无人顾得了这里了。

除了两位夫人。

大乔小乔每天都会带着一些食物来到跳蚤街,分给某一位孩子。为了避免分配不均,她们时常会询问一个区域内食物的总量,然后进行调整以保证每个孩子都有足够的食物。

Input

第一行两个整数n,m,表示跳蚤街住着n户孩子,大乔小乔一共分发或询问了m次。

第二行n个整数,第i个数ai表示第i户孩子已有ai的食物。

接下来m行,每行开始先读入一个整数si,指明这是一次询问还是一次分发。

si=0,表明这是一次询问,然后读入两个整数li,ri,表示询问[li,ri]区间中的孩子们一共有多少食物。

si=1,表明这是一次分发,然后读入两个整数xi,wi,表示对第xi户孩子分发了wi的食物。

1≤n,m≤100000,0≤ai≤100000,1≤xi≤n,0≤wi≤10000,1≤li≤ri≤n

Output

有多少询问就输出多少行,每行输出一个整数,作为对该询问的回答。

Sample Input

5 4

1 2 3 4 5

1 2 3

0 2 4

1 4 1

0 1 5

Sample Output

12

19

#include <iostream>
#include <cstdio>
using namespace std;

typedef struct{
    int l,r;
    int sum;
}SegTree;

int n,m,i,j,s;

void Build(SegTree trees[], int id, int l, int r){
    trees[id].l=l; trees[id].r=r;
    if (l==r){
        trees[id].sum=0;
    }else{
        int mid=(l+r)/2;
        Build(trees, 1+id*2, l, mid);
        Build(trees, id*2+2, mid+1, r);
        trees[id].sum=trees[id*2+2].sum+trees[id*2+1].sum;
    }
}

void Update(SegTree trees[], int id, int pos, int val){
    if (trees[id].l==trees[id].r){
        trees[id].sum=val;
    }else{
        int mid=(trees[id].l+trees[id].r)/2;
        if (pos<=mid) Update(trees, id*2+1, pos, val);
        else Update(trees, id*2+2, pos, val);
        trees[id].sum=trees[id*2+2].sum+trees[id*2+1].sum;
    }
}

int Query(SegTree trees[], int id, int l, int r){
    if (trees[id].l==l && trees[id].r==r)
        return trees[id].sum;
    else{
        int mid=(trees[id].l+trees[id].r)/2;
        if(r<=mid) return Query(trees, id*2+1, l, r);
        else if(l>mid) return Query(trees, id*2+2, l, r);
        else return Query(trees, id*2+1, l, mid)+Query(trees, id*2+2, mid+1, r);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    int a[n];
    SegTree *tree=new SegTree[4*n];
    Build(tree, 0, 0, n-1);
    for(i=0; i<n; i++){
        scanf("%d", &a[i]);
        Update(tree, 0, i, a[i]);
    }
    for(i=0; i<m; i++){
        int q, ll_x, rr_w;
        scanf("%d%d%d", &s, &ll_x, &rr_w);
        if(s==0){
            q=Query(tree, 0, ll_x-1, rr_w-1);
            printf("%d\n", q);
        }else{
            q=Query(tree, 0, ll_x-1, ll_x-1);
            Update(tree, 0, ll_x-1, rr_w+q );
        }
    }
    return 0;
}

我的数组下标是从0开始的。所以线段树的写法可能看上去和网上一些模板和伪代码不太一样。

第二类问题:

成电OJ 839 东风不与周郎便

“揽二乔于东南兮,乐朝夕之与共”

一首铜雀台赋,将愤怒与恐惧散播在了孙吴大军之中。

对抗曹军,万事俱备,只欠东风。

现在已经找到n个风眼,这些风眼的东风有强有弱,诸葛亮说他每次祈风都能够将一段风眼的东风增强,但需人去帮他布阵。同时他需要时刻掌控风眼的状况,以确定下一步的计划,所以还需要知道一段风眼的强度之和。

借东风,此乃逆天之术,施术者会折阳寿不说,布阵者更是会受十倍之伤。

“何人能当此任?”

“在下愿往,大都督。”

“你是?”

“在下一无名小卒,来自跳蚤街。”

Input

第一行两个整数n,m,表示有n个风眼,诸葛亮一共祈风或询问了m次。

第二行n个整数,第i个数ai表示第i个风眼已有东风的强度。

接下来m行,每行开始先读入一个整数si,指明这是一次询问还是一次祈风。

si=0,表明这是一次询问,然后读入两个整数li,ri,表示询问[li,ri]区间中风眼的东风强度之和。

si=1,表明这是一次祈风,然后读入三个整数li,ri,wi,表示把[li,ri]区间中每个风眼的东风强度提升wi。

1≤n,m≤100000,0≤ai≤10000,0≤wi≤10000,1≤li≤ri≤n

Output 有多少询问就输出多少行,每行输出一个整数,作为对该询问的回答。

Sample Input

5 4

1 2 3 4 5

1 2 3 2

0 3 4

1 4 5 3

0 2 4

Sample Output

9

16

手头没有一本书是讲线段树区间更新的,翻了无数博客,文档,而且网上所有资料里下标都是1开始的(很不习惯),终于写出了一个体现了C++面向对象风格的程序(其实就是把数据和操作封装了个对象-_-||)。

区间更新时并不是每个节点都更新,需要加一个标记,把要更新的数据放在标记里。等到需要修改子节点(比如更新或查询)的时候把这个标签里的信息传下去。如果你的查询或修改区间刚好和你二分处的区间相同,这个查询或修改操作就不再向下一层执行,而是直接返回结果。

#include<cstdio>
#include<cstring>
#define __int64 long long
#define MAX 100005
class Node{
public:
    int l,r;
    __int64 sum,add;
};
int num[MAX];

class SegTree{
private:
    Node *tree;
    void PushDown(int id){
        int j=id*2+1;
        int mid=(tree[id].l+tree[id].r)/2;
        tree[j].add+=tree[id].add;
        tree[j+1].add+=tree[id].add;
        tree[j].sum+=tree[id].add*(mid-tree[id].l+1);
        tree[j+1].sum+=tree[id].add*(tree[id].r-mid);
        tree[id].add=0;
    }
public:
    SegTree(int n){tree=new Node[4*n];}
    ~SegTree(){delete []tree;}

    void Build(int l,int r,int id){
        tree[id].l=l; tree[id].r=r; tree[id].add=0;
        if(l==r)tree[id].sum=num[l];
        else{
            int mid=(l+r)/2;
            Build(l,mid,id*2+1);
            Build(mid+1,r,id*2+2);
            tree[id].sum=tree[id*2+2].sum+tree[id*2+1].sum;
        }
    };

    void Update(int l,int r,int c,int id){
        if (tree[id].l>=l&&tree[id].r<=r){
            tree[id].sum+=(__int64)c*(tree[id].r-tree[id].l+1);
            tree[id].add+=c;
        }else{
            if (tree[id].add) PushDown(id);
            int mid=(tree[id].l+tree[id].r)/2;
            int j=id*2+1;
            if (l<=mid) Update(l,r,c,j);
            if (r>mid) Update(l,r,c,j+1);
            tree[id].sum=tree[j].sum+tree[j+1].sum;
        }
    };

    __int64 Query(int l,int r,int id){
        if (tree[id].l>=l && tree[id].r<=r)
            return tree[id].sum;
        else{
            if(tree[id].add) PushDown(id);
            int mid,j;
            __int64 ans=0;
            mid=(tree[id].l+tree[id].r)/2;
            j=id*2+1;
            if(l<=mid) ans+=Query(l,r,j);
            if(r>mid) ans+=Query(l,r,j+1);
            return ans;
        }
    }
};

int main(){
    int n,m,a,b,c;
    int cmd;
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) scanf("%d",num+i);

    SegTree tt(n);

    tt.Build(0,n-1,0);
    while(m--){
        scanf("%d%d%d",&cmd,&a,&b);
        if (cmd==1) scanf("%d",&c);
        if (cmd==0)
            printf("%lld\n", tt.Query(a-1, b-1, 0));
        else
            tt.Update(a-1, b-1, c, 0);
    }
    return 0;
}

一个多月前在成电OJ上看到一个并查集的问题,当时刚看完一些基础的数据结构,所以就试着做了。当然没有做出来。这题坑就在于:每组测试数据有10^5个,地图还是1000*1000的。挨着个每次都搜一遍不太可能。容易超时。

解决方法:潮水高度是递增的。所以想象一个退潮的过程,把每次退潮露出的岛屿记录下来,从最后最高的潮水高度算起。把露出的岛屿加入集合,每个测试数据对应的答案可以接着在下一组继续使用。

Islands

Deep in the Carribean, there is an island even stranger than the Monkey Island, dwelled by Horatio Torquemada Marley. Not only it has a rectangular shape, but is also divided into an n×m grid. Each grid field has a certain height. Unfortunately, the sea level started to raise and in year i, the level is i meters. Another strange feature of the island is that it is made of sponge, and the water can freely flow through it. Thus, a grid field whose height is at most the current sea level is considered flooded.Adjacent unflooded fields (i.e., sharing common edge) create unflooded areas. Sailors are interested in the number of unflooded areas in a given year.

An example of a 4×5 island is given below. Numbers denote the heights of respective fields in meters.Unflooded fields are darker; there are two unflooded areas in the first year and three areas in the second year.

Input

Multiple Test Cases

The input contains several test cases. The first line of the input contains a positive integer Z≤20,denoting the number of test cases. Then Z test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.

Single Instance Input

The first line contains two numbers n and m separated by a single space, the dimensions of the island, where 1≤n,m≤1000. Next n lines contain m integers from the range [1,10^9] separated by single spaces, denoting the heights of the respective fields. Next line contains an integer T (1≤T≤105). The last line contains T integers tj , separated by single spaces, such that 0≤t1≤t2≤⋯≤tT≤10^9

Output

Single Instance Output

Your program should output a single line consisting of T numbers rj , where rj is the number of unflooded areas in year tj . After every number ,you must output a single space

Sample Input

1

4 5

1 2 3 3 1

1 3 2 2 1

2 1 3 4 3

1 2 2 2 2

5

1 2 3 4 5

Sample Output

2 3 1 0 0

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
class Field{
public:
    int height, father;
    bool under;
};

int Z;  int row, col, T;
int res[100000];
vector<int> height_list[100000];
vector<int> t;
int i,j,result,temp;
Field field[1000][1000];
int Father(int a, int b){
    if (field[a][b].father!=a*col+b)
        field[a][b].father=Father(field[a][b].father/col, field[a][b].father%col);
    return field[a][b].father;
}

void Merge(int a, int b, int c, int d){
    int f1, f2, x, y;
    f1=Father(a, b);    f2=Father(c, d);
    if(f1==f2) return;
    else{
        result--;
        x=field[a][b].father/col;
        y=field[a][b].father%col;
        field[x][y].father=f2;
    }
}

void Check(int r, int c){
    if (r+1<row && !field[r+1][c].under) {Merge(r, c, r+1, c); }
    if (r-1>=0 && !field[r-1][c].under) {Merge(r, c, r-1, c); }
    if (c+1<col && !field[r][c+1].under) {Merge(r, c, r, c+1); }
    if (c-1>=0 && !field[r][c-1].under) {Merge(r, c, r, c-1); }
}

void Solve(){
    int x, y, m, n;
    result=0;
    for(m=t.size()-1; m>=0; m--){
        for(n=height_list[m].size()-1; n>=0; n--){
            x=height_list[m][n]/col;   y=height_list[m][n]%col;
            field[x][y].under=false;
            result++;   Check(x, y);
        }
        res[m]=result;
    }
}

int main(){
    scanf("%d", &Z);
    while(Z--){
        result=0;
        t.clear();
        for (i=0; i<100000; i++) height_list[i].clear();

        scanf("%d%d", &row, &col);
        for(i=0; i<row; i++){
            for(j=0; j<col; j++){
                scanf("%d", &field[i][j].height);
                field[i][j].under=true;
                field[i][j].father=i*col+j;
            }
        }

        scanf("%d", &T);
        for(i=0; i<T; i++){
            scanf("%d", &temp);
            t.push_back(temp);
        }

        for(i=0; i<row; i++){
            for(j=0; j<col; j++){
                temp=lower_bound(t.begin(), t.end(), field[i][j].height)-t.begin();
                if(temp>0) height_list[temp-1].push_back(i*col+j);
            }
        }
        Solve();
        for(i=0; i<(int)t.size(); i++) printf("%d ", res[i]);
        printf("\n");
    }
    return 0;
}

昨天C++课上留了三道题,除了C语言本身外都涉及了一些算法。其中第二个问题是这样的:

拦截导弹

某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹。拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹。

输入

第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),

第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。

输出

输出只有一行,包含一个整数,表示最多能拦截多少枚导弹。

样例输入

8

300 207 155 300 299 170 158 65

样例输出

6

课堂上没搞出来。老师说用到了动态规划。好吧,高中没学过信息学竞赛。不过没关系,回去翻了翻《算法导论》,基本算弄明白了。其实就是求一串数的最长递减子序列。

问题关键在于,可能的情况组合很多,不适合穷举。所以要利用动态规划(很适合这类问题)。动态规划把问题分成很多子问题,而子问题之间又有关系。子问题不是相互独立的,子问题可能有重叠,全局最优解由子问题的最优解构成(最优子结构性质)。这和分治法(典型的比如归并排序)不一样。

动态规划的基本想法在于:

  1. 描述最优解结构,就是说最优解是什么样子的,符合什么条件。
  2. 递归定义最优解的值。也就是写出状态方程。其中一般需要特别考虑初始条件。
  3. 自底向上计算最优解的值。
  4. 由计算的值构造最优解(在这题里没要求,到第三部求出序列长就行了)。

其中,问题设计时最关心的就是第二步。以下的步骤是必不可少的:

  • 阶段划分。
  • 确定状态变量。当前状态变量是由之前阶段的某个状态转移来的。当前状态是对之前所有状态的完整总结。当前这个状态之后的选择只受当前最优决策序列的影响(无后效性)。
  • 写状态转移方程。也就是确定如何从之前状态得到本阶段的状态。
  • 找边界条件(开始和终止的条件)。

比如说,这个问题中要拦第i个导弹。截止到第i个导弹的最长拦截序列肯定包含了前面i-1个导弹中最长的序列。如果不是这样,我们求出的截止到第i个导弹的拦截序列就不是最长的了。我们用数组D[i]把截止到第i个导弹的最长拦截序列长度存起来。最后计算完i=k(导弹总数)时,整个问题的答案就是数组D[i]的最大值。

如果用一个数组,把前一个最优解对应的导弹编号存下来,最后还可以把被击落的导弹高度按编号输出。

代码:

/*
    设数组A存放导弹高度,D[i]是高度为A[i]是的最优解,S用于记录最优解中导弹被击落的次序
    最优解结构:设在第k个数处的最优解为D(k)。设当前位于第i个数,则在第i个数处的
            最优解D(i)为:在i之前拦下导弹最多的方法的解D(j)加上1。(因为把第i
            个也打下来了,所以加上1)。当然还要保证A[i]<=A[j]
    递归解:D(i)=D(j)+1。j是数组A中位于A[i]左侧,且大于等于A[i]的所有数中D值最大的
            那个。如果A[i]左侧没有找到大于等于它的数,则D[i]=1。
    状态转移方程:D(i)=max{D(j)+1}  (0<=j<i<k)
                D(0)=1
    最终结果:找到数组D中最大的数,这个数就是结果。
*/
#include <cstdio>
int main(){
    int k;
    scanf("%d", &k);
    int A[k], D[k], S[k];

    for(int i=0; i<k; i++){
        scanf("%d", &A[i]);
        D[i]=0;
    }
    D[0]=1;

    for(int i=1; i<k; i++){
        bool found=false;   //是否找到i之前的最优解
        int last_good_solve=D[0];
        int good_position=0;//最优解的下标和值
        for(int j=0; j<i; j++)
            if(A[j]>=A[i] && D[j]>=D[good_position]){
                last_good_solve=D[j];
                good_position=j;
                found=true;
            }

        if(found){
            D[i]=1+D[good_position];
            S[i]=good_position;
        }
        else {
            D[i]=1;
            S[i]=good_position;
        }
    }

    int result=0;   int go_back;//用于向前找被击落的导弹
    for(int i=0; i<k; i++){
        if(D[i]>result){
            result=D[i];
            go_back=i;
        }
    }

    printf("%d\n", result);

    for(int i=0; i<result; i++){
        printf("%d  ", A[go_back]);
        go_back=S[go_back];
    }//逆序输出被击落导弹的高度
}
pic1

很讨厌不少教材上排序时两边向中间的扫描的方法,感觉很麻烦。看见《算法导论》上是单向扫描的分区方法,感觉实现起来很简单。这里和《算法导论》上的只有一点不同,基准数选了第一个数(其实没什么区别)。

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;

class QSorter{
    vector<int> data;

    void QS(vector<int>&, int, int);
    int Partition(vector<int>&, int, int);
public:
    void QSort_DM();
    void GenNum(int);
    QSorter(){ srand(time(NULL)); }
    QSorter(int n){ srand(time(NULL)); GenNum(n); }
    void OutData();
};

void QSorter::OutData(){
    cout<<"Data:";
    for(int i=0; i<(int)data.size(); i++)
        cout<<data[i]<<" ";
    cout<<endl;
}

void QSorter::GenNum(int n){
    for(int i=0; i<n; i++)
        data.push_back(rand()%200);
}

void QSorter::QS(vector<int>& v, int low, int high){
    if(low<high){
        int pivot=Partition(v, low, high);
        QS(v, low, pivot-1);
        QS(v, pivot+1, high);
    }
}

int QSorter::Partition(vector<int>& v, int low, int high){
    int x=v[low];   //第一个数是枢轴
    int i=low;      //比枢轴小的左部分最后一个数的下标

    for(int j=low+1; j<=high; j++)
        if(v[j]<x){
            i++;
            swap(v[i], v[j]);
        }
    //找到比枢轴小的数就把它放第i个数后,i+1扩大左部分
    //循环结束时是中左右结构
    swap(v[i], v[low]);
    return i;//和左区第一个数换位,形成左中右结构
}

void QSorter::QSort_DM(){
    QS(data, 0, data.size()-1);
}

int main()
{
    QSorter s1(10);
    s1.OutData();
    s1.QSort_DM();
    s1.OutData();
    return 0;
}

快排的思想也很好理解,每次把比基准数小的放左边,大的放右边,每次分割区间都形成左(小于基准)中(基准数)右(大于基准)的结构。最后传给递归函数的子区间大小为1时,排序结束。

两侧扫描的分区法有一个大神讲的非常棒。

1.下载MINGW4.9。先从网站http://www.mingw.org/上下载在线安装器(页面右边有DOWNLOAD INSTALLER按钮)。

2.我是WIN7的64位机子,选择下面这种配置:(如果不用POSIX而选WIN32反而用不了)

pic1

3.装好后配置CODEBLOCKS:

pic2
pic3

4.写个程序运行一下:

    #include <thread>
    #include <iostream>
    using namespace std;
    void hello()
    {
        cout<<"Hello from thread"<<endl;
    }
    
    int main()
    {
        thread t1(hello);
        t1.join();
        cout<<"Main Thread"<<endl;
        return 0;
    }
    
pic4