NOIP2015 推销员 解题报告

通过这道题,可以很好的学习和练习使用C++STL库中queuepair的使用。
之前一直使用纯粹的C,有需要的地方就自己使用struct写链表等数据结构,因此排序、极值、哈希搜索等操作不仅写起来费事,而且效率不高,这一题彻底让我从之前纯粹使用C的方式转换成了使用C++和STL。
题目地址:http://codevs.cn/problem/5126/
关于优先队列priority_queuepair,可以参考下面两篇比较全面的介绍:
优先队列priority_queue 详解
C++中pair的用法
值得注意的是,pair不光做好了泛型,还做了operator<的实现,因此可以默认通过priority_queue进行最大堆的操作,而不需要自己写比较函数。

解题思路:

构建数据结构,distance距离位置,和value疲劳值。
将所有数据分为两个序列,左部lq和右部rq,分割点就在当前推销员所在的坐标位置(一开始坐标点在0点处),动态维护其坐标的变化。左部序列是一个大顶堆的优先队列,初始时为空;右部元素不必单独开辟,直接使用左边界哨兵控制区域位置即可。

每次对左部和右部的最大值进行对比:
  • 如果左部最大值大一些,则此时选择左部元素(推销员已走过的房间),将左部元素的value值输出,并弹出这个元素。
  • 如果右部最大值大一些,则此时选择右部元素(推销员还没到过的坐标),将右部元素的(distance - nowDis) * 2 + value值输出,同时记录目标元素的distance值,并将右部元素中所有小于等于此distance值的节点全部压入左部队列,压入权值为每个元素的value值。
寻找最大值的方法:
  • 左部元素寻找最大值的方法:直接使用优先队列的特性,lq的top元素。

  • 右部元素寻找最大值的方法:在rq中依次遍历,寻找最大的(distance - nowDis) * 2 + value

直到左部和右部序列全部为空,解题结束。

实际编码中,我并没有每次对比左部和右部的最大值,而是在开始时将右部元素全部整理压入左部队列,然后将左部队列依次输出即可。整理和压入的方法是:寻找到右部(distance - nowDis) * 2 + value最大值后,将目标元素以(distance - nowDis) * 2 + value权值入栈,其余distance小于等于目标元素distance的节点以value值入栈。这样程序显得简洁一点。

代码:
/**
  * NOIP2015 推销员
  * 学习使用pair泛型进行组合,而不需要自己写struct
  * 学习使用priority_queue优先队列(默认为最大堆)
  */
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4.in","r",stdin);
    //freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4-dd.out","w",stdout);
    int N;
    scanf("%d", &N);
    pair<int, int> nodes[N];
    for(int i = 0; i < N; i++){
        scanf("%d", &nodes[i].second);      //读入dis数据
    }
    for(int i = 0; i < N; i++){
        scanf("%d", &nodes[i].first);       //读入value数据
    }

    priority_queue< pair<int, int> > lq;    //左部优先队列

    int nowPos = 0, nowDis = 0, nowResult = 0, tempPos, tempMXPos, tempResult, tempMXResult;

    //将nowPos不断向N逼近,迫使右部数据全部进入左部队列,最后整体输出左部队列
    while(nowPos < N){
        //找到本次登记的最大result和最大dis
        tempMXResult = 0;
        for(tempPos = nowPos; tempPos < N; tempPos++){
            tempResult = (nodes[tempPos].second - nowDis) * 2 + nodes[tempPos].first;
            if( tempResult >= tempMXResult ){
                tempMXResult = tempResult;
                tempMXPos = tempPos;
            }
        }
        nowDis = nodes[tempMXPos].second;
        //tempMXPos的权值为tempMXResult,其余小于nowDis的右部元素权值为first,将这些元素全部压入优先队列lq中
        for(tempPos = nowPos; nodes[tempPos].second <= nowDis && tempPos < N; tempPos++){
            if(tempPos == tempMXPos){
                nodes[tempPos].first = tempMXResult;
            }
            lq.push(nodes[tempPos]);
        }
        nowPos = tempPos;
    }

    while(!lq.empty()){
        nowResult += lq.top().first;
        printf("%d\n", nowResult);
        lq.pop();
    }

    return 0;
}

NOIP2015子串问题解题报告

NOIP2015子串问题解题报告

本题来自NOIP2015,我第一次见它是在NUAA1012,这题是一条经典的动态规划(dynamic programming)。

做算法竞赛也有一段时间了,我所理解的动态规划就是用开数组的方式解决递归的时间复杂度。可能是还不熟练的原因,每次遇到动态规划我都要先写出递归函数,然后用循环和开数组的方式改造,记录递推中产生的过程解,这样在新的方程中递推到同样位置时不需要深入计算,直接用已经计算出来解即可,从而降低时间复杂度,但是因为开辟了数组记录过程解,因此是一种典型的「空间换时间」的思想。

这一题对我来说,同样需要先写出递归函数,再去改造。如果是练习的话,可以在OJ平台一步一步提交观察,现在一些流行的OJ平台不光会告诉你AC还是WA,还会告诉你A了几个测试用例,所以如果光写递归的话,能够通过大概40%,用上DP改造,可以通过90%,最后一道测试用例不出意外的话,你的空间会超,要想拿到100%AC,最后一个测试用例需要使用滚动数组降低空间复杂度。实际现场竞赛的话建议考虑周全后,再提交,毕竟会有惩罚机制在里面。

网上这道题的解题报告不胜枚举,但大多数作为算法的初级爱好者,我都看得云里雾里,看了一些报告,加上自己想了一个晚上,我力争用自然人类的语言来把这题讲明白。

题目大意就是给定两个字符串,A和B,其中A称之为主串,B称之为子串,和一个取串数K。

要求在主串A中找到K个连续的字符串,能够组成完整的子串B,求这种方案的个数。

样例分析

6 3 1
aabaab
aab
6 3 2
aabaab
aab
6 3 3
aabaab
aab

样例 1,将A串取一个子集,组成B串:
aab aab
aab aab
(两种方案)

样例 2,将A串取两个子集,组成B串:
a ab aab
a aba ab
a a ba ab
aab a ab
aa b aab
aa baa b
aab aa b
(七种方案)

样例 3:
a a b aab
a a baa b
a ab a a b
a aba a b
a a b a a b
a a ba a b
aab a a b
(七种方案)

我们设主串长度为N,子串长度为M,取子集个数为K,N >= M >= K,这是潜在的天然条件
乍一看,最终解法数与N,M,K之间应该存在着某种关系,这种关系应该还与A串和B串的实际内容相关。虽然这种关系暂时我们还看不出来,但隐约觉得应该可以通过层层往前递推,让N,M,K逐渐变小而得到。于是我们设f(i,j,k)表示在主串的0-i中,取k个子集组成子串的0-j的方法有f(i,j,k)种,我们最终就是要求f(N-1, M-1, K)。

推导f方程

有了方程f,我们就要求递推关系,假设,我们现在知道所有f([0,i), [0,j], [1,k])的任意值,现在试着推导f(i,j,k),A串B串还是用样例中的A=aabaab,B=aab,K=2来推理,那么我们现在知道所有的f([0,4],[0,2],[1,2]),求f(5,2,2)。
PS:k=0时,无视其他所有值,f直接等于0,因为无法将主串取出0个子集出来构成子串。
f(5,2,2) = ?
我们将目光聚焦到A[5]和B[2]上,也就是’b’和’b’。
咦?这两个字母一样诶,那我们是不是有且只有两种选择:
一种是取出来的子集带有A[5]
另一种是取出来的子集不带A[5]
我们先不忙着继续推导,先给这两种情况分别命名,组成结果数带有A串最后一个字母的叫做s(i,j,k),反之,不带有最后一个字母的叫做t(i,j,k),假设s和t函数都我们都能轻松求出来,我们现在试着给A串做一次修改,让他变成aabaabc,现在求f(6,2,2),好了,现在A[6]和B[2]分别是字母’c’和’b’,这两个字母不同,那我们只且只有一种情况,那就是刚刚定义的不取A[6]的t函数,我们再仔细观察一下,不取A[6]的话,那只能在A[0,5]中选择子集,那结果等同于f(5,2,2)啊,也就是f(6,2,2) = t(6,2,2) = f(5,2,2),好了,我们将t函数的定义取消掉,因为它可以直接用f(i-1,j,k)取代,本文中我们再也不会提到t这个函数了。
我们先归纳一下现在的分支:

if(A[i] == B[j]){    //取A[i]和不取A[i]
    f(i,j,k) = s(i,j,k) + f(i-1, j, k);
}else{                //不取A[i]
    f(i,j,k) = f(i-1, j, k);
}

大功告成,开始写递归?慢着,s是个什么鬼,好吧我们硬着头皮继续推导s吧:

推导s方程

s的定义是取A[i]这个字符时,从A[0,i]中取k个子集构成B[0-j]的方法数,也就是潜在的现状就是A[i] == B[j]
我们将A串回归到样例状态aabaab,这时候求s(5,2,2)就是默认要取A[5]了,也就是A串最后一个字符’b’必须参与子集的选择。
我们又遇到一个似曾相识的问题,前方的道路又产生了一个问题:我们的A[4] = B[1]呢,取还是不取A[4]?
No,No,No,取不取A[4]这个问题问得不好,会产生二义性,我们需要问一个更明确的问题:合并A[4,5]使其作为一个整体,还是不合并?
合并A[i-1]和A[i]:s(i,j,k) = s(i-1, j-1, k)
不合并A[i-1]和A[i]:,s(i,j,k) = f(i-1, j-1, k-1)
以上两个公式的推导过程咱就省略吧,对着aabaab和aab两个字符串比划比划就能的出来。
于是我们又有了下面这个分支:

if(A[i-1] == B[j-1]){    //合并+不合并
    s(i,j,k) = s(i-1, j-1, k) + f(i-1, j-1, k-1);
}else{                    //不合并
    s(i,j,k) = f(i-1, j-1, k-1);
}

以下就是整个递推方程的推导脑图:

f,s都有了,下面用递归函数AC这道题吧

咳咳咳,没说完,只能A掉40%哦,递归栈太深,会溢出的。
我贴代码有人愿意看吗?反正我看解题报告从来不看别人的代码,看也看不懂,每个人编码习惯还不同,有强迫症的话简直抓狂。

    //本来想贴代码的,想想只能A40%的代码也没人愿意看啊,还是算了。。。

动态规划改造之

动态规划天生就是用来解决递归的,使用开数组记录的方式空间换时间,递推时我们从f(i,j,k)一步一步向f(0,0,0)推理,DP时我们从f(0,0,0)一步一步向f(i,j,k)逼近,但这一题因为测试用例太极限,单纯动规也只能A掉90%的测试用例,第10组用例会报「空间超限」,128M的内存不够用,我算了一下,一个整型变量4个字节,也就是4Byte,如果第10组数据是1≤n≤1000,1≤m≤200,1≤k≤m这样一个等级的话,需要开两个[1000][200][200]这么大的数组,算下来就是2 * 1000 * 200 * 200 * 4B = 320,000,000B = 312,500KB = 305M,题目限制只有128M,显然不够了。

滚动数组

这时候我们引入滚动数组的概念,首先不要被陌生词汇唬住,先别看这个术语,我们来观察一下之前推导的s函数

if(A[i-1] == B[j-1]){    //合并+不合并
    s(i,j,k) = s(i-1, j-1, k) + f(i-1, j-1, k-1);
}else{                    //不合并
    s(i,j,k) = f(i-1, j-1, k-1);
}

我们发现s函数只会跟自身的s(i-1,j-1,k)发生关系,想象一下s[i][j][k]是一个三维的立方体,也就是每次求s[i][j][k]时,它都只需要知道同一层二维平面的之前推导出来的数据,而下面层那些数据都不需要了。而一旦使用动态规划,我们计算机内存中会保存s[0-i] [0-j][1,k]的所有数据,直到程序进程结束,这些数据才会被释放,辣么,会有很多数据白白的保存在内存中,而我们可以预计他们再也不会被以后的推导过程调用。
于是,我们第一步空间压缩,拿s函数(或者叫s数组)开刀吧,因为它只跟它同一层的s[i-1][j-1]发生关系。所以只需要开辟s[n][m]就行了,将一个三维立方体活生生地压缩成为一个二维平面,哈哈,有没有《三体》中二向箔的感觉。
然而,不幸的事情再次发生,当我们把原本需要开s[N][M][K]的数组换成了s[N][M],之后,还是会报「空间超限」。。。
逼着我们继续拿f函数动刀,继续观察推导出来的f函数,这时候要并入s函数一起观察:

if(A[i] == B[j]){    //取A[i]和不取A[i] f(i,j,k) = s(i,j,k) + f(i-1, j, k);
    if(A[i-1] == B[j-1]){    //合并+不合并
        f(i,j,k) = s(i-1, j-1, k) + f(i-1, j-1, k-1) + f(i-1, j, k);
    }else{            //不合并
        f(i,j,k) = f(i-1, j-1, k-1) + f(i-1, j, k);
    }
}else{                //不取A[i]
    f(i,j,k) = f(i-1, j, k);
}

f[N][M][K]同样看做一个立方体,那么它在层层往上搭建的过程中,不光用到了k层的二维平面,还用到了k-1层的二维平面,好说,只要他不是在立方体里到处乱跑就行,不就是用到下一层吗,那我们同样没必要开辟f[N][M][K],我们只需要开辟f[N][M][2]就行了,然后用一个flag从0到1,从1再到0,轮流交替使用f[i][j][flag]就OK了,滚动数组的技巧完美get。

最终编码

写到这里终于要上100%AC的代码了,不过我相信还是没人愿意看代码,所有ACMer包括我在内都只想看思路,自己实现代码对不对。
不过为了符合国际惯例,还是贴上代码吧:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

char *A, *B;

int main()
{
    int n,m,K;
    scanf("%d %d %d", &n, &m, &K);
    int f[n][m][2];
    int s[n][m];
    A = (char*)malloc( (n+1) * sizeof(n));
    B = (char*)malloc( (m+1) * sizeof(m));
    scanf("%s", A);
    scanf("%s", B);

    /*
     * ACM比赛中,1s对应的计算量大约是4*10^8
     * 因此O(n*m*K) = 1000 * 200 * 1000是可以接受的
     */
    int k,i,j;
    bool flag = false;
    for(k = 1; k<=K; k++){
        for(i = 0; i<n; i++)
            for(j = k-1; j<=i && j<m; j++){

                if(i < j || j < (k-1)){
                    f[i][j][flag?1:0] = 0;
                    s[i][j] = 0;
                    continue;
                }

                if(j == 0 && k ==1){
                    s[i][j] = A[i] == B[j] ? 1 : 0;
                    f[i][j][flag?1:0] = (long long)((long long)s[i][j] + ((k <= 0 || i<1 || j<0 || i<j || j<(k-1))?0:(long long)f[i-1][j][flag?1:0])) % 1000000007;
                    continue;
                }

                if(A[i] == B[j]){
                    if(i>0 && j>0){
                        if(A[i-1] == B[j-1])
                            s[i][j] = (long long)((j<k?0:s[i-1][j-1]) + ((k<=1)?0:f[i-1][j-1][flag?0:1])) % 1000000007;
                        else
                            s[i][j] = (k<=1)?0:f[i-1][j - 1][flag?0:1];
                    }
                    f[i][j][flag?1:0] = (long long)(s[i][j] + ((k <= 0 || i<1 || j<0 || i<=j || j<(k-1))?0:f[i-1][j][flag?1:0]) ) % 1000000007;
                }else{
                    f[i][j][flag?1:0] = i==0?0:f[i - 1][j][flag?1:0];
                }
            }
        flag = !flag;
    }

    printf("%d\n", f[n - 1][m - 1][flag?0:1]);

    return 0;
}

/**************************************************************
    Problem: 2241
    User: newflydd
    Language: C
    Result: 正确
    Time:396 ms
    Memory:3168 kb
****************************************************************/

八皇后极限编程

这几天,准确来说是连续4天了
真的能称之为极限编程了
关于N皇后算法的极限挑战,最终很满意
代码使用了“一维棋盘”,“对称剪枝”,“递归回溯”,“多线程”等特色
最终结果:
15皇后,用时:4903毫秒,计算结果:2279184
16皇后,用时:33265毫秒,计算结果:14772512
17皇后,用时:267460毫秒,计算结果:95815104

比起我第一天写N皇后,14皇后用时87秒的成绩,提高太多了!!!
说好的一定要在100秒内解16皇后,终于解脱了
啥都不说了,贴上代码和运算成绩

package com.newflypig.eightqueen;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;


public class EightQueen7 {
    private static final short K=8;     //使用常量来定义,方便之后解N皇后问题
    private static short N=0;

    public static void main(String[] args) throws Exception {
        for(N=9;N<=17;N++){
            long count=0;
            Date begin =new Date();
            /**
             * 初始化棋盘,使用一维数组存放棋盘信息
             * chess[n]=X:表示第n行X列有一个皇后
             */

            List<short[]> chessList=new ArrayList<short[]>(N);
            for(short i=0;i<N;i++){
                short chess[]=new short[N];
                chess[0]=i;
                chessList.add(chess);
            }

            short taskSize =(short)( N/2+(N%2==1?1:0) );
            // 创建一个线程池
            ExecutorService pool = Executors.newFixedThreadPool(taskSize);
            // 创建多个有返回值的任务
            List<Future<Long>> futureList = new ArrayList<Future<Long>>(taskSize);
            for (int i = 0; i < taskSize; i++) {
                Callable<Long> c = new EightQueenThread(chessList.get(i));
                // 执行任务并获取Future对象
                Future<Long> f = pool.submit(c);
                futureList.add(f);
            }
            // 关闭线程池
            pool.shutdown();

            for(short i=0; i<(short) (taskSize - (N%2==1?1:0)); i++){              
                count+=futureList.get(i).get();
            }
            count=count*2;
            if(N%2==1)
                count+=futureList.get(N/2).get();

            Date end =new Date();
            System.out.println("解决 " +N+ "皇后问题,用时:" +String.valueOf(end.getTime()-begin.getTime())+ "毫秒,计算结果:"+count);
        }
    }
}

class EightQueenThread implements Callable<Long>{
    private short[] chess;
    private short N;

    public EightQueenThread(short[] chess){
        this.chess=chess;
        this.N=(short) chess.length;
    }


    @Override
    public Long call() throws Exception {
        return putQueenAtRow(chess, (short)1) ;
    }


    private Long putQueenAtRow(short[] chess, short row) {
        if(row==N){
            return (long) 1;
        }

        short[] chessTemp=chess.clone();
        long sum=0;
        /**
         * 向这一行的每一个位置尝试排放皇后
         * 然后检测状态,如果安全则继续执行递归函数摆放下一行皇后
         */
        for(short i=0;i<N;i++){
            //摆放这一行的皇后
            chessTemp[row]=i;

            if( isSafety( chessTemp,row,i) ){
                sum+=putQueenAtRow(chessTemp,(short) (row+1));
            }
        }

        return sum;
    }

    private static boolean isSafety(short[] chess,short row,short col) {
        //判断中上、左上、右上是否安全
        short step=1;
        for(short i=(short) (row-1);i>=0;i--){
            if(chess[i]==col)   //中上
                return false;
            if(chess[i]==col-step)  //左上
                return false;
            if(chess[i]==col+step)  //右上
                return false;

            step++;
        }

        return true;
    }
}


这是四天前的成绩:

确实有了很大的提升!

丁丁生于 1987.07.01 ,30岁,英文ID:newflydd

  • 现居住地 江苏 ● 泰州 ● 姜堰
  • 创建了 Jblog 开源博客系统
  • 坚持十余年的 独立博客 作者
  • 大学本科毕业后就职于 中国电信江苏泰州分公司,前两年从事Oracle数据库DBA工作,两年后公司精简技术人员,被安排到农村担任支局长(其本质是搞销售),于2016年因志向不合从国企辞职,在小城镇找了一份程序员的工作。
  • Git OSChina 上积极参与开源社区