Xavier's Blog

Linux下进程的安全性设置

| Comments

上一次我们讲过,如何用setrlimit限制进程的资源,并以时间和内存为例。这次我们来试试看更多的资源限制,以防止恶意代码的攻击,增加系统的安全性。

超时

超时上次不是讲过了吗?嗯,上次讲的是“忙”的超时,而这次是“sleep”的超时。通过实验发现,如果程序一直咋sleep,父进程是无法检测到子进程超时的,我想这应该是因为sleep的时间本身不算在进程的CPU时间内。那啥办呢?好办,加定时器(alarm)。例如:

signal(SIGALRM, my_alarm_handler);
alarm(timeLimit * 2);

这样,当进程流逝的时间超过alarm的限制时,父进程也会受到相应的信号。

例如对于这样的代码:

#include <unistd.h>

int main ()
{
    sleep(15);

    return 0;
}

运行结果如下:

quxiao@quxiao-laptop:~/judge$ ./linux_judge_svn/linux/judge.o /home/quxiao/judge/a_and_b.in /home/quxiao/judge/out.txt 1 64 /home/quxiao/judge/just_sleep.o input file: /home/quxiao/judge/a_and_b.in output file: /home/quxiao/judge/out.txt time limit: 1 memory limit: 67108864 cmd: /home/quxiao/judge/just_sleep.o ================parent process===================== child exit status: 14 exit abnormally. exit by signal: 14 | 14 parent process is finished. child process time: 0 ms maximum resident set size:    292

生成/打开文件

有时我们并不希望子进程有文件操作(当然,除了输入输出设备这些特殊文件),可以通过修改RLIMIT_NOFILE的值来达到此效果。

如果程序会生成一些文件,代码如下:

for (i = 0; i < 10; i ++)
{
    char template[] = "template-XXXXXX";
    fd = mkstemp(template);
    if ( fd == -1 )
    {
        printf("can't create file!\n");
    }
}

那么,修改过限制之后的代码运行结果就是:

quxiao@quxiao-laptop:~/judge$ ./linux_judge_svn/linux/judge.o /home/quxiao/judge/a_and_b.in /home/quxiao/judge/out.txt 1 64 /home/quxiao/judge/too_many_file.o input file: /home/quxiao/judge/a_and_b.in output file: /home/quxiao/judge/out.txt time limit: 1 memory limit: 67108864 cmd: /home/quxiao/judge/too_many_file.o ================parent process===================== child exit status: 0 exit normally. parent process is finished. child process time: 0 ms

maximum resident set size:    364

quxiao@quxiao-laptop:~/judge$ cat out.txt can’t create file! can’t create file! can’t create file! can’t create file! can’t create file! can’t create file! can’t create file! can’t create file! can’t create file!

不过,从例子中可以看出,表面上父进程并没有检测到子进程的任何异常,但我们可以从输出文件中看到子进程的生成文件是受到限制的。另外,还有一点值得考虑,那就是子进程还是生成了一个文件的,RLIMIT_NOFILE到底应该设置成多少,还要再研究研究。

生成子进程

同样,让进程可以任意地生成子进程也是很危险的。RLIMIT_NPROC可以限制生成子进程的数目。对于如下代码:

    for (i = 0; i < 3; i ++)
    {
        pid_t pid;
        if ( (pid=fork()) == -1 )
        {
            printf("error!\n");
        }
        else if ( pid == 0 )
        {
            printf("this is child process\n");
        }
        else
        {
            printf("this is parent process\n");
        }
    }

运行结果如下:

quxiao@quxiao-laptop:~/judge$ ./linux_judge_svn/linux/judge.o /home/quxiao/judge/a_and_b.in /home/quxiao/judge/out.txt 1 64 /home/quxiao/judge/too_many_child.o input file: /home/quxiao/judge/a_and_b.in output file: /home/quxiao/judge/out.txt time limit: 1 memory limit: 67108864 cmd: /home/quxiao/judge/too_many_child.o ================parent process===================== child exit status: 0 exit normally. parent process is finished. child process time: 0 ms

maximum resident set size:    340

quxiao@quxiao-laptop:~/judge$ cat out.txt error! error! error!

runtime error

当程序出现一些运行时错误的时候,父进程也可以通过信号检测到。这里其实跟资源限制没太大关系,但检测这方面的信息也是很重要的。举2个例子,1个是除0,1个是数组越界。

除0程序:

int main ()
{
    int a, b;
    a = 1;
    b = 0;
    a = a / b;

    return 0;
}

quxiao@quxiao-laptop:~/judge$ ./linux_judge_svn/linux/judge.o /home/quxiao/judge/a_and_b.in /home/quxiao/judge/out.txt 1 64 /home/quxiao/judge/divide0.o input file: /home/quxiao/judge/a_and_b.in output file: /home/quxiao/judge/out.txt time limit: 1 memory limit: 67108864 cmd: /home/quxiao/judge/divide0.o ================parent process===================== child exit status: 8 exit abnormally. exit by signal: 8 | 8 parent process is finished. child process time: 0 ms

maximum resident set size:    292

数组越界程序:

const int MAX = 100;

int main ()
{
    int array[MAX];
    int i;
    i = 0;
    while ( ++i )   /* so dangerous! */
    {
        array[i] = 0;
    }

    return 0;
}

quxiao@quxiao-laptop:~/judge$ ./linux_judge_svn/linux/judge.o /home/quxiao/judge/a_and_b.in /home/quxiao/judge/out.txt 1 64 /home/quxiao/judge/re.o input file: /home/quxiao/judge/a_and_b.in output file: /home/quxiao/judge/out.txt time limit: 1 memory limit: 67108864 cmd: /home/quxiao/judge/re.o ================parent process===================== child exit status: 11 exit abnormally. exit by signal: 11 | 11 parent process is finished. child process time: 0 ms

maximum resident set size:    288

USACO Section 3.3 Shopping Offers

| Comments

题目大意:

买N(0<=N<=5)类商品,每种买K(0<=K<=5)件,再给出S(0<=S<=99)个优惠价格列表,每种优惠给定一种商品及其数量的组合。

优惠列表如下:

1 7 3 5
2 7 1 8 2 10

表示第1种优惠包含1类商品:7号商品买3件,优惠价为5;第2种优惠包含2类商品:7号商品买1件,8号商品买2件,优惠价为10。

求买这N类商品,每种K件,购买的最低价格是多少?

思路:

题目中要求买的商品的种类和数量都很少(<=5),这很好,但S的数量级有点高,尽量避免枚举S很重要。商品最多5种,每种商品0~5个,那么商品类型和数目的组合状态就是65种。每种组合的最优解(即最低价格)是唯一的,而组合的种类又不多,则很容易想到把子问题的解保存起来,避免重复计算。

对于当前的商品类型价格组合,如果之前已计算出来,则直接返回。否则,枚举每一种优惠,如果可以使用该种优惠,计算优惠价格加上剩下的组合,返回所有可以使用优惠的价格以及不使用优惠的价格中的最小值,作为当前情况的最优解。这样,问题就可以解决了,提交之后发现效率还可以。

关键代码如下:

int getMinCost (int num[PRODUCT_NUM])
{
    int curState;
    curState = getState(num);
    if ( minCost[curState] != -1 )
        return minCost[curState];

    int i, j, minPrice = 0, curPrice, tmpNum[PRODUCT_NUM];
    bool check;
    for (i = 0; i < proNum; i ++)
        minPrice += num[i] * price[i];
    for (i = 0; i < offerNum; i ++)
    {
        curPrice = 0;
        check = true;
        for (j = 0; j < proNum; j ++)
        {
            if ( num[j] - offerProIdxNum[i][j] < 0 )
            {
                check = false;
                break;
            }
            tmpNum[j] = num[j] - offerProIdxNum[i][j];
        }
        if ( check )
        {
            curPrice = offerPrice[i] + getMinCost(tmpNum);
            if ( curPrice < minPrice )
                minPrice = curPrice;
        }
    }
    return (minCost[curState] = minPrice);
}

Linux API 实践:setjmp和longjmp

| Comments

我们在平时编程的过程中,编写异常处理的代码是常有的事。但有时,我们的函数调用的比较“深”,同时又想根据较深处的函数的异常处理,使较高层次的调用函数作出相应动作。举个例子吧,main()调用a(),a()调用b(),b()调用c(),如果c()中进行异常处理,要在main()中显示错误信息。我们一般的做法应该都是根据函数返回值将底层的错误返回给调用者,以此类推,直至main()。示意代码如下:

#include <stdio.h>

int a(int);     //-1 means error
int b(int);     //-1 means error
int c(int);     //-1 means error

int main ()
{
    int i;
    while ( scanf("%d", &i) != EOF )
    {
        if ( a(i) == -1 )
            printf("error!\n");
    }
}

int a (int n)
{
    //blablabla
    if ( b(n) == -1 )
        return -1;
}

int b (int n)
{
    //blablabla
    if ( c(n) == -1 )
                return -1;
}

int c (int n)
{
    //blablabla
    if ( n < 0 )
        return -1;
}

可以看到,a, b, c三个函数都需返回错误信息,有时a和b本来并不需要进行异常处理,而因为c要将异常信息传给main,a和b不得不加入更多的代码。

但是,当你知道有setjmp和longjmp这两个函数后,处理起来就会简单一些。它们可以进行跨函数的跳转,其内在的动作是直接改变程序调用栈的栈顶位置,而不用根据函数调用关系一层一层的返回。我们再来看看经过改进的代码:

#include <setjmp.h>
#include <stdio.h>

int a(int);
int b(int);
int c(int);

jmp_buf jmpbuffer;

int main ()
{
    int i;
    if ( setjmp(jmpbuffer) )
        printf("error!\n");
    while ( scanf("%d", &i) != EOF )
    {
        a(i);
    }
}

int a (int n)
{
    //blablabla
    b(n);
}

int b (int n)
{
    //blablabla
    c(n);
}

int c (int n)
{
    //blablabla
    if ( n < 0 )
        longjmp(jmpbuffer, 1);
}

在完成功能的情况下,少写了一些代码,结构也清晰了一些。

运行结果如下:

quxiao@quxiao-laptop:~/learnLinux/setjmp$ ./setjmp_ex.o 0 1 2 3 -1 error! -2 error! -3 error!

不过,对于这种加强版的”goto”,我还是觉得应该慎用。

Linux API 实践:限制进程资源

| Comments

上一篇文章,讲到了如何用getrlimit获取进程资源上限。既然能getrlimit,那当然我们也可以setrlimit,对进程的资源进行限制。我们就以进程的CPU时间和占用的内存为例,讲述如何限制进程相应的资源以及当资源上限超过时,是如何捕捉的。

一个对子进程的资源(时间和内存)进行限制的程序:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/resource.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>
#include <fcntl.h>
#include <signal.h>

#define SYSTEM_ERROR        10

#define MIN_TIME_LIMIT 1
#define MAX_TIME_LIMIT 100
#define MIN_MEM_LIMIT 4
#define MAX_MEM_LIMIT 1024

struct rlimit tLimit, mLimit;

int main (int argc, char** argv)
{
    int timeLimit, memLimit, ret;
    pid_t pid;
    int s;
    struct rusage rUsage;
    double passTime;
    char** childCmd;

    if ( argc < 4 )
    {
        printf("argument number error!\n");
        printf("usage: timeLimt(%d~%ds) memoryLimit(%d~%dMb) commandLine\n",
                MIN_TIME_LIMIT, MAX_TIME_LIMIT, MIN_MEM_LIMIT, MAX_MEM_LIMIT);
        return SYSTEM_ERROR;
    }
    //获取时间限制和内存限制
    if ( isdigit(argv[1][0]) )
        timeLimit = atoi(argv[1]);
    if ( isdigit(argv[2][0]) )
        memLimit = atoi(argv[2]);
    if ( timeLimit < MIN_TIME_LIMIT || timeLimit > MAX_TIME_LIMIT )
    {
        printf("time limit argument error!(%d~%ds)\n", MIN_TIME_LIMIT, MAX_TIME_LIMIT);
        return SYSTEM_ERROR;
    }
    if ( memLimit < MIN_MEM_LIMIT || memLimit > MAX_MEM_LIMIT )
    {
        printf("memory limit argument error!(%d~%dMb)\n", MIN_MEM_LIMIT, MAX_MEM_LIMIT);
        return SYSTEM_ERROR;
    }
    memLimit = memLimit * 1024 * 1024;

    if ( (pid=fork()) < 0 )
    {
        printf("fork error!\n");
        return SYSTEM_ERROR;
    }
    else if ( pid == 0 )        /*child process*/
    {
        getrlimit(RLIMIT_CPU, &tLimit);
        getrlimit(RLIMIT_AS, &mLimit);

        tLimit.rlim_cur = timeLimit;
        mLimit.rlim_cur = memLimit;

        if ( setrlimit(RLIMIT_CPU, &tLimit) == -1 )     /*设置时间限制*/
            printf("setrlimit time limit error!\n");
        if ( setrlimit(RLIMIT_AS, &mLimit) == -1 )      /*设置内存限制*/
            printf("setrlimit memory limit error!\n");

        childCmd = argv + 3;
        execvp(childCmd[0], childCmd);
    }
    else
    {
        waitpid(pid, &s, 0);        //等待子进程结束,并获取信号
        printf("================parent process=====================\n");
        printf("child exit status: %d\n", s);
        if ( WIFEXITED(s) )
            printf("exit normally.\n");
        else
            printf("exit abnormally.\n");
        if ( WIFSIGNALED(s) )
            printf("exit by signal: %d | %d\n", s, WTERMSIG(s));
        printf("parent process is finished.\n");
        getrusage(RUSAGE_CHILDREN, &rUsage);
        passTime = (rUsage.ru_utime.tv_sec + rUsage.ru_stime.tv_sec) * 1000 + (float)(rUsage.ru_stime.tv_usec + rUsage.ru_utime.tv_usec) / 1000;
        printf("child process time: %d ms\n", (int)passTime);
        printf("===================================================\n\n");
        return 0;
    }
}

好了,下面我们写几个测试程序。

第一个,写个占用CPU时间很长的程序:

#include <stdio.h>
#include <unistd.h>

const int MAX = 50000;

int main ()
{
    int i, j, k;
    for (i = 0; i < MAX; i ++)
        for (j = 0; j < MAX; j ++)
            k = i * j;
    return 0;
}

测试运行结果:

> quxiao@quxiao-laptop:~/learnLinux/setrlimit$ ./setrlimit_ex.o 1 64 ./run_so_long.o

================parent process=====================

child exit status: 24

exit abnormally.

exit by signal: 24 | 24

parent process is finished.

child process time: 1000 ms

===================================================

信号24是SIGXCPU信号,表示超出CPU时间上限(我们的程序中为1s)。

好,再写个申请过多内存空间的程序:

#define MAX 10000

int arr[MAX][MAX];

int main ()
{
    return 0;
}

测试运行结果:

> quxiao@quxiao-laptop:~/learnLinux/setrlimit$ ./setrlimit_ex.o 1 64 ./so_long_array.o

================parent process=====================

child exit status: 9

exit abnormally.

exit by signal: 9 | 9

parent process is finished.

child process time: 0 ms

===================================================

信号9表示SIGKILL,申请过多内存空间时会产生该信号。(还有哪些情况会产生这个信号?)

这样,我们就可以对进程的行为进行限制,并测量进程的各项资源了。(这也是我们的OJ所需要的 :) )

具体所有信号所表示的含义,可以查看这里

Linux API 实践:获取进程资源限制

| Comments

进程在运行时,会占用计算机的各种资源,比如CPU时间、内存、文件等等。但是,进程是不可以占用无限多的资源的,操作系统会给进程设定所使用资源的上限。想获取这些资源的上限值,是需要调用getrlimit()即可。

int getrlimit(int resource, struct rlimit *rlptr);

第一个参数是资源,有哪些资源呢?

资源

粗略含义

RLIMIT_AS

进程可使用的内存的最大值

RLIMIT_CORE

核心文件(core file)的最大值

RLIMIT_CPU

CPU时间最大值

RLIMIT_DATA

数据段(已初始化数据+未初始化数据+堆)的最大值

RLIMIT_FSIZE

新建文件的最大字节数

RLIMIT_LOCKS

持有的锁的最大数

RLIMIT_MEMLOCK

锁定内存的最大字节数

RLIMIT_NOFILE

打开文件的最大数目

RLIMIT_NPROC

每个实际用户(real user)的最大子进程数目

RLIMIT_RSS

RSS(Resident Set Size)的最大字节数

RLIMIT_SBSIZE

socket buffer的最大字节数

RLIMIT_STACK

进程栈的最大字节数

RLIMIT_VMEM

与RLIMIT_AS含义一致

第二个参数是rlimit,rlimit结构是这样的:

struct rlimit

{

rlim_t rlim_cur; /* soft limit: current limit */

rlim_t rlim_max; /* hard limit: maximum value for rlim_cur */

};

其中含有软限制和硬限制。超级用户可以增加硬限制;一般用户可以降低硬限制,但不能增加硬限制,一般用户还可修改软限制,但修改的软限制不能超过硬限制。

实际运行的效果如何呢?实践一下吧!

#include <stdio.h>
#include <sys/resource.h>

#define doit(name) pr_limit(#name, name)

void pr_limit(char* name, int resource);

int main ()
{
    printf("resource name  soft\thard \n");
#ifdef  RLIMIT_AS
    doit(RLIMIT_AS);
#endif
    doit(RLIMIT_CORE);
    doit(RLIMIT_CPU);
    doit(RLIMIT_DATA);
    doit(RLIMIT_FSIZE);
#ifdef  RLIMIT_LOCKS
    doit(RLIMIT_LOCKS);
#endif
#ifdef  RLIMIT_MEMLOCK
    doit(RLIMIT_MEMLOCK);
#endif
    doit(RLIMIT_NOFILE);
#ifdef  RLIMIT_NPROC
    doit(RLIMIT_NPROC);
#endif
#ifdef  RLIMIT_RSS
    doit(RLIMIT_RSS);
#endif
#ifdef  RLIMIT_SBSIZE
    doit(RLIMIT_SBSIZE);
#endif
    doit(RLIMIT_STACK);
#ifdef  RLIMIT_VMEM
    doit(RLIMIT_VMEM);
#endif

    return 0;
}

void pr_limit(char* name, int resource)
{
    struct rlimit limit;
    if ( getrlimit(resource, &limit) < 0 )
    {
        printf("getrlimit error!\n");
        return;
    }
    printf("%-14s ", name);
    if ( limit.rlim_cur == RLIM_INFINITY )
        printf("infinite ");
    else
        printf("%8ld ", limit.rlim_cur);

    if ( limit.rlim_max == RLIM_INFINITY )
        printf("infinite ");
    else
        printf("%8ld ", limit.rlim_max);
    putchar('\n');
}

运行的结果:

resource name  soft hard
RLIMIT_AS      infinite infinite
RLIMIT_CORE           0 infinite
RLIMIT_CPU     infinite infinite
RLIMIT_DATA    infinite infinite
RLIMIT_FSIZE   infinite infinite
RLIMIT_LOCKS   infinite infinite
RLIMIT_MEMLOCK    65536    65536
RLIMIT_NOFILE      1024     1024
RLIMIT_NPROC   infinite infinite
RLIMIT_RSS     infinite infinite
RLIMIT_STACK    8388608 infinite

Linux API 实践:输入输出重定向

| Comments

在shell中对程序进行重定向很简单,用<和>符号就可以了,但在自己的程序中怎么实现输入输出重定向呢?

先来看看Linux内核中,文件(还是设备)是通过哪些数据结构保存的:

image

每个进程都保存一份文件描述符的表格,每一行又指向file table,然后file table再指向v-node table。v-node table我们可以暂不考虑,暂且把它当作文件的内容。而从process table entry中的file pointer可以指向不同或者相同的file table。原本标准输入输出是指向“键盘”和“屏幕”这两个设备的,如果可以将它们指向我们指定的文件,就可以实现重定向了。

先用open()打开需要重定向到的文件,获取去文件描述符fd,在用dup2()把进程中原先的输入输出文件描述符STDIN_FILENO和STDOUT_FILENO重定向至fd,这样就可以实现输入输出重定向了。我想,shell实现重定向也应该是类似的思想,关键代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/resource.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>
#include <fcntl.h>
#include <signal.h>

int main (int argc, char** argv)
{
    if ( argc != 3 )
    {
        printf("usage: inputFile outputFilen");
        return 1;
    }
    int inFd, outFd;

    inFd = open(argv[1], O_RDONLY);
    if ( inFd < 0 )
    {
        printf("inFd open error!n%sn",strerror(errno));
        return 1;
    }
    outFd = open(argv[2], O_CREAT | O_TRUNC | O_RDWR, S_IRWXU | S_IRGRP | S_IROTH);
    if ( outFd < 0 )
    {
        printf("outFd open error!n%sn", strerror(errno));
        return 1;
    }

    if ( dup2(inFd, STDIN_FILENO) < 0 )
    {
        printf("inFd dup2 error!n");
        return 1;
    }
    if ( dup2(outFd, STDOUT_FILENO) < 0 )
    {
        printf("outFd dup2 error!n");
        return 1;
    }       

    char line[128];
    while ( scanf("%s", &line) != EOF )
    {
        printf("%sn", line);
    }

    return 0;
}

USACO Section 3.2 Stringsobits

| Comments

有这样一种集合,集合元素为长度N(1~31)的二进制串,并且每个二进制串中1的个数小于等于L,求这个集合中第I大的元素是多少?

最开始很天真的想枚举每个数,计算其中1的个数,结果第8组测试数据开始就超时的不行了。

枚举不行,来试试构造可不可以,假设我们有一个长度为n,1个数<=l的二进制串的集合,那么怎么把它们从大到小区分呢?我们一位一位来,根据第n位,可以将集合划为2部分:第n位是0的,第n为是1的。好了,递推式突然就变得很明显了。如何设num[N][L]为长度为N,1个数小于等于L的二进制串的个数,那么:

num[N][L] = num[N-1][L] + num[N-1][L-1]
(第n位是0) (第n位是1)

个数有了,那么第I个数是多少怎么求呢?说来也简单,就是用递归的思想,看I落在num[N-1][L]和num[N-1][L-1]的哪一部分,看下面的代码应该就明白了:

<span style="color: #0000ff">void</span> Print (<span style="color: #0000ff">int</span> len, <span style="color: #0000ff">int</span> num1, <span style="color: #0000ff">long</span> <span style="color: #0000ff">long</span> idx)
{
     <span style="color: #0000ff">if</span> ( len == 0 )
          <span style="color: #0000ff">return</span>;
     <span style="color: #0000ff">if</span> ( num[len-1][num1] >= idx )
     {
          putchar('0');
          Print(len-1, num1, idx);
     }
     <span style="color: #0000ff">else</span>
     {
          putchar('1');
          Print(len-1, num1-1, idx-num[len-1][num1]);
     }
}

USACO Section 3.2 Factorials

| Comments

问你N阶乘的最低非零位上是什么数字。(0 <= N <= 4220)

从1一直乘到N,如果能整除10,就除以10,可以吗?不行,因为即使去掉低位的0,高位的非0位仍然很大,无法保存下来。

可以将N!这样表示:
N! = 2K * 5L * V(N)
= 2K-L * V(N) * 10L ( K >= L 如何证明呢?)

10L不影响N!最低非零位,这个数由(K-L)以及V(N)的个位数所决定。K和L容易得到,V(N)的个位数也好得到,只要枚举i(从1到N),去除因子2和5(因子个数加到K和L),将其个位数乘以中间结果就可以了。

关键代码如下:

<span style="color: #0000ff">const</span> <span style="color: #0000ff">int</span> f2 [] = {6, 2, 4, 8};

<span style="color: #0000ff">int</span> i, tmp, n2, n5;
<span style="color: #0000ff">int</span> ans = 1;
n2 = n5 = 0;
<span style="color: #0000ff">for</span> ( i = 1; i <= n; i ++)
{
    tmp = i;
    <span style="color: #0000ff">while</span> ( tmp % 2 == 0 )
    {
        n2 ++;
        tmp /= 2;
    }
    <span style="color: #0000ff">while</span> ( tmp % 5 == 0 )
    {
        n5 ++;
        tmp /= 5;
    }
    ans = (( tmp % 10) * ans) % 10;
}
ans = ( ans * f2[( n2- n5)%4] ) % 10;
printf( "<span style="color: #8b0000">%d\n</span>", ans);

USACO Section 3.1 Stamps

| Comments

有N(1<=N<=50)种不同面值邮票,由这些邮票组成面值1~M,1、2、……、M每种面值均由不超过K(1<=K<=200)数目的邮票组成,求最大的M为多少?邮票最大面值为10000

一开始想到DP,数组canComprise[10000*200][200],canComprise[i][j]表示用j张邮票是否可以组成面值i,但数组太大,放弃。

后来改用深搜,优化了许久,最后几组数组仍然超时,放弃。

又回头想DP,如果canComprise[i][j1]和canComprise[i][j2]均为true,j1 < j2,那么canComprise[i][j1]肯定是更优的解,因为j1可以扩展更多i+stamps[x]。所以,只要用一维数组保存答案就可以了,比如minStamp[i] = j就表示组成i所用到的最少邮票数为j,递推式很容易想到:

minStamp[i] = Min{ minStamp[i-stamp[x]] + 1 } ( i – stamp[x] >= 0 )

同一种情况,表达解的方式可能有多种,尽量使用最精简的方式,已达到降维的效果。

USACO Section 3.1 Shaping Regions

| Comments

一道几何题,解决方法很容易想到,不过要细心。

随着输入的顺序,将矩形一个个放入集合,如果新的矩形与集合中的旧矩形相交,就将旧矩形分解,删除旧矩形,放入新矩形和分解的矩形。

设矩形R1、R2,宽和高分别为(W1, H1)和(W2, H2),两矩形中心坐标分别为(X1, Y1)以及(X2, Y2)。判断两矩形是否相交(也就是是否有面积相重合),就看两矩形中心坐标的竖直和水平距离是否小于两矩形高的和的一半以及两矩形宽的和的一半。即:

( |X1 – X2| < (W1 + W2) / 2 ) && ( |Y1 – Y2| < (H1 + H2) / 2 )

如果条件满足,R1和R2即相交。

那相交会有几种情况呢?我想到了16种:

image

根据不同的情况,可以将原来的矩形分解为0~4个小矩形,这样就可以解出来了。

(做几何题可真费草稿纸啊,看来以后得学学matlab了,低碳、环保!)

另外,USACO还有一种解法,就是将矩形的四条边进行离散化处理,将线段排序,然后再依次扫描,大体思路是这样的,具体细节没怎么看。