首页 > ACM题库 > HDU-杭电 > HDU 3577-Fast Arrangement[解题报告]HOJ
2014
11-27

HDU 3577-Fast Arrangement[解题报告]HOJ

Fast Arrangement

问题描述 :

Chinese always have the railway tickets problem because of its’ huge amount of passangers and stations. Now goverment need you to develop a new tickets query system.
One train can just take k passangers. And each passanger can just buy one ticket from station a to station b. Each train cannot take more passangers any time. The one who buy the ticket earlier which can be sold will always get the ticket.

输入:

The input contains servel test cases. The first line is the case number. In each test case:
The first line contains just one number k( 1 ≤ k ≤ 1000 ) and Q( 1 ≤ Q ≤ 100000 )
The following lines, each line contains two integers a and b, ( 1 ≤ a < b ≤ 1000000 ), indicate a query.
Huge Input, scanf recommanded.

输出:

The input contains servel test cases. The first line is the case number. In each test case:
The first line contains just one number k( 1 ≤ k ≤ 1000 ) and Q( 1 ≤ Q ≤ 100000 )
The following lines, each line contains two integers a and b, ( 1 ≤ a < b ≤ 1000000 ), indicate a query.
Huge Input, scanf recommanded.

样例输入:

1
3 6
1 6
1 6
3 4
1 5
1 2
2 4

样例输出:

Case 1:
1 2 3 5 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define lc rt << 1
#define rc rt << 1 | 1

using namespace std;

const int MAXN = 1000100;

struct node
{
    int l, r;
};

node D[MAXN];
int limit, Q;
int maxi[ MAXN << 2 ];
int lazy[ MAXN << 2 ];
int N;

void build( int l, int r, int rt )
{
    maxi[rt] = lazy[rt] = 0;
    if ( l == r ) return;
    int m = ( l + r ) >> 1;
    build( lson );
    build( rson );
    return;
}

void PushUp( int rt )
{
    maxi[rt] = max( maxi[lc], maxi[rc] );
    return;
}

void PushDown( int rt )
{
    if ( lazy[rt] )
    {
        lazy[lc] += lazy[rt];
        lazy[rc] += lazy[rt];
        maxi[lc] += lazy[rt];
        maxi[rc] += lazy[rt];
        lazy[rt] = 0;
    }
    return;
}

void update( int L, int R, int l, int r, int rt )
{
    if ( L <= l && r <= R )
    {
        lazy[rt] += 1;
        maxi[rt] += 1;
        return;
    }
    PushDown( rt );
    int m = ( l + r ) >> 1;
    if ( L <= m ) update( L, R, lson );
    if ( R > m )  update( L, R, rson );
    PushUp( rt );
    return;
}

int query( int L, int R, int l, int r, int rt )
{
    if ( L <= l && r <= R )
    {
        return maxi[rt];
    }
    PushDown( rt );
    int m = ( l + r ) >> 1;

    int res = -10;
    if ( L <= m ) res = max( res, query( L, R, lson ) );
    if ( R > m )  res = max( res, query( L, R, rson ) );
    PushUp( rt );
    return res;
}

int main()
{
    int T, cas = 0;
    scanf( "%d", &T );
    while ( T-- )
    {
        scanf( "%d%d", &limit, &Q );
        N = 0;
        for ( int i = 0; i < Q; ++i )
        {
            int u, v;
            scanf( "%d%d", &u, &v );
            N = max( N, v );
            --v;
            D[i].l = u, D[i].r = v;
        }

        build( 1, N, 1 );
        printf( "Case %d:\n", ++cas );
        for ( int i = 0; i < Q; ++i )
        {
            int ans = query( D[i].l, D[i].r, 1, N, 1 );
            if ( ans < limit )
            {
                printf( "%d ", i + 1 );
                update( D[i].l, D[i].r, 1, N, 1 );
            }
        }
        puts("\n");
    }
    return 0;
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮