首页 > 搜索 > BFS搜索 > HDU 3860-Circuit Board-高精度-[解题报告]HOJ
2015
04-13

HDU 3860-Circuit Board-高精度-[解题报告]HOJ

Circuit Board

问题描述 :

Recently Silence has got a new circuit board with which he will do a new experiment.

Now we can assume that the circuit board is made of R lines and each line has C holes. And we can only put a wire between the adjacent holes. We say a hole is adjacent to another one if and only if it is at the up, down, left or right side of the other one.

Inverting Cups

This is a circuit board and we can add wires like this.

Now P holes on the left side of the board are power sources and each one can afford a specific amount of electric current. And O holes on the right side of the board are output interfaces and each one needs a specific amount of electric current.

In order to complete the experiment we should put some wires on the board so that we can meet every output interface on the board (we don’t have to use up all the power). But the circuit board is a little old so between some adjacent holes we can only put a wire whose capacity is not greater than a specific value. And what’s more, some of the holes are fault holes which means the fault hole can’t be connect to any adjacent holes, we assume no power sources or output interfaces are fault holes.

Now we have several different kinds of wires and each kind of wire has a specific capacity. And we can use as many wires as we want of each kind. But as we know the wire which has a higher capacity is much more expensive than the one which has a lower capacity. So we should make the highest capacity of the wires we use as low as possible.

Now it is your turn to write a program to get the best solution whose highest capacity of all the wires is as low as possible. You can just output the highest capacity of the best solution.

输入:

There are several test cases in this problem. The first line of the input is an integer T(1 <= T <= 10), which means there are T test cases in the input.
  
The first line of each test case is two integers R and C (2 <= R, C <= 200), which means the circuit board has R lines and each line has C holes. And the coordinate of the upper left corner is always (1, 1).

Then there is an integer P(1 <= P <= R) means P holes of the left side is power sources. And each of the next P lines has two integers Ai, Si (1 <= Ai <= R, 0 < Si <= 1000), which indicates the i-th power source is located at (Ai, 1) and can afford Si amount of electric current. Then there is an integer O (1 <= O <= R) means O holes of the right side is Output interfaces. And each of the next O lines has two integer Bi, Ti, (1 <= Bi <= R, 0 < Ti <= 1000), which indicates the i-th output source is located at (Bi, C) and needs Ti amount of electric current.

Then there is an integer Q (0 <= Q <= R*(C-1) + C*(R-1)), and the next Q lines each one has 5 integers x1, y1, x2, y2, m (0 < x1,x2 <= R, 0 < y1, y2 <= C, 0 < m <= 1000). That indicates between the holes at (x1, y1) and (x2, y2) we can only put a wire whose capacity is not greater than m. we assume that (x1, y1) and (x2, y2) are adjacent holes.

And then there is an integer K (0 <= K <= R * C �C P – O). And each of the next K lines has two integers xi, yi, means there are k fault holes on the board and the i-th hole’s coordinate is (xi, yi).

Then there is an integer W (1 <= W <= 10000), means there are W kinds of wire we can choose. And the followed line has W integers u1, u2, …, uw. ui means the i-th kind of wire’s capacity is ui (0 < ui <= 100000).

输出:

There are several test cases in this problem. The first line of the input is an integer T(1 <= T <= 10), which means there are T test cases in the input.
  
The first line of each test case is two integers R and C (2 <= R, C <= 200), which means the circuit board has R lines and each line has C holes. And the coordinate of the upper left corner is always (1, 1).

Then there is an integer P(1 <= P <= R) means P holes of the left side is power sources. And each of the next P lines has two integers Ai, Si (1 <= Ai <= R, 0 < Si <= 1000), which indicates the i-th power source is located at (Ai, 1) and can afford Si amount of electric current. Then there is an integer O (1 <= O <= R) means O holes of the right side is Output interfaces. And each of the next O lines has two integer Bi, Ti, (1 <= Bi <= R, 0 < Ti <= 1000), which indicates the i-th output source is located at (Bi, C) and needs Ti amount of electric current.

Then there is an integer Q (0 <= Q <= R*(C-1) + C*(R-1)), and the next Q lines each one has 5 integers x1, y1, x2, y2, m (0 < x1,x2 <= R, 0 < y1, y2 <= C, 0 < m <= 1000). That indicates between the holes at (x1, y1) and (x2, y2) we can only put a wire whose capacity is not greater than m. we assume that (x1, y1) and (x2, y2) are adjacent holes.

And then there is an integer K (0 <= K <= R * C �C P – O). And each of the next K lines has two integers xi, yi, means there are k fault holes on the board and the i-th hole’s coordinate is (xi, yi).

Then there is an integer W (1 <= W <= 10000), means there are W kinds of wire we can choose. And the followed line has W integers u1, u2, …, uw. ui means the i-th kind of wire’s capacity is ui (0 < ui <= 100000).

样例输入:

1
2 3
1
1 4
1
2 4
1
1 1 1 2 1
0
4
1 2 3 4

样例输出:

3

Hint
Inverting Cups
This is one of the solution of the sample input, so the answer is 3.

  这道题,首先想到的就是BFS,但是因为数据太大,BFS不仅TLE而且MLE。

我是这么思考的:

如果n >= m 显然只能是1步1步减,输出n-m即可。

如果m > n ,也就是说m经过若干步骤后变成了n。

我们假设m的变化中第2次变化有*2操作,那么在下面的情况里不可能出现相邻连续+1+1或者-1-1,如果出现,只要先+1或-1再*2即可。

eg. 6 ->14
6 * 2 = 12   12 + 1 + 1 = 14 ; 3步

6 + 1 = 7
7 * 2 = 14 ; 2步

有了这一点,不难想到此题我们考虑从n到m,一开始只有1个偶数(或者奇数)扩展相邻项后最多每层只有2个偶数,那么一共有log(2,1e500)层(不到2000层),

每层2个数,那就没压力了。然后记下每层的到达这个数的最小步数(相邻则进行更新)。

eg.
m = 801               n = 5

第一层    800  801  802

步数  1 0  1           更新ans = 801 -5=796

第二层
 400  402     更新ans

……

交后的测试期望时间是78MS

<pre name="code" class="cpp">/*
 *    Author:
 *        OpenPandora 
 *     Date:
 *          2014.08.26
 */ 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define cls(a) memset(a,0,sizeof(a))
#define rise(i,a,b) for(int i=a;i<=b;i++)
#define fall(i,a,b) for(int i=a;i>=b;i--)
const int base = 1e9;
char a[600];
bool ined, flag;
int cnt, cntt, ep;
void init()
{
    ined = false; cnt = 0;    
    while( true )
    {
        a[cnt] = getchar();
        if( a[cnt] >= '0' && a[cnt] <= '9' ) 
        {
            ined = true;
            cnt ++;    
        }
        else if( ined ) break;
    }
    a[cnt] = '\0';
    cnt --;
}
struct point
{
    int num[60], len;
    point() { clear(); }
    void clear(){ len = 1 ; cls(num); }
    void out( int x ) 
    { 
        printf( "%d" , num[len] );
        fall( i , len - 1 , 1 ) printf( "%09d" , num[i] );
        if( x )putchar('\n');
        else putchar( ' ' );
    }
    void in()
    {
        init(); cntt = 0; ep = 1; clear();
        fall( i , cnt , 0 )
        {
            if( cntt == 9 )
            {
                cntt = 0;
                len ++;
                ep = 1;
            }
            cntt ++;
            num[len] += (int) ( a[i] - '0' ) * ep;
            ep *= 10;
        }
        while( len > 1 && num[len] == 0 ) len --; 
    }
    void inc()
    {
        num[1] ++;
        rise( i , 1 , len )
        {
            if( num[i] >= base )
            {
                num[i+1] ++;
                num[i] -= base;
            }
            else break;
        }
        if( num[len+1] == 1 ) len ++;
    }
    void dec( int x )
    {
        num[1] -=x;
        rise( i , 1 , len )
        {
            if( num[i] < 0 )
            {
                num[i+1] --;
                num[i] += base;
            }
            else break;
        }
        if( num[len] == 0 ) len --;
    }
    void divid()
    {
        fall( i , len , 1 )
        {
            num[i-1] += ( num[i] & 1 ) * base;
            num[i] >>= 1;
        }
        if( num[len] == 0 ) len --;
    }
    point &operator = ( const point& ); 
    point operator - ( const point& )const; 
    point operator + ( const point& )const;
    point(const int);
    bool operator>(const point &p )const;
    bool operator<(const point &p )const;
    bool operator==(const point &p )const;
}n, m, one, zero, two, now[3], tmp[5], nv[3], tv[5], ans;
point & point :: operator=(const point &p)
{
    clear();
    len = p.len;
    rise( i , 1 , len ) num[i] = p.num[i];
    return *this;
}
point point ::operator+(const point &p)const
{
    point ret = *this;
    int l = max( ret.len , p.len );
    rise( i , 1 , l )
    {
        ret.num[i] += p.num[i];
        if( ret.num[i] >= base ) 
        {
            ret.num[i+1] ++;
            ret.num[i] -= base;
        }
    }
    if( ret.num[l+1] > 0 ) l ++;
    ret.len = l;
    return ret;
}
point point ::operator-(const point &p)const
{
    point ret = *this;
    if( ret > p )
    {
        rise( i , 1 , ret.len )        
        {
            ret.num[i] -= p.num[i];
            if( ret.num[i] < 0 ) 
            {
                ret.num[i] += base;
                ret.num[i+1] --;
            }
        }
        while( ret.len > 1 )
        if( ret.num[ret.len] == 0 ) ret.len --;
        else break;
        return ret;
    }
    if( ret == p )
    return zero;
    if( ret < p )
    {
        point tmp = ret;
        ret = p;
        rise( i , 1 , ret.len )        
        {
            ret.num[i] -= tmp.num[i];
            if( ret.num[i] < 0 ) 
            {
                ret.num[i] += base;
                ret.num[i+1] --;
            }
        }
        while( ret.len > 1 )
        if( ret.num[ret.len] == 0 ) ret.len --;
        else break;
        return ret;
    }
}
point::point( const int b )
{
    clear();
    num[1] = b;
}
bool point::operator==(const point &p)const
{
    if( len != p.len ) return false;
    fall( i , len , 1 ) if( num[i] != p.num[i] ) return false;
    return true;
}
bool point::operator>(const point &p)const
{
    if( len > p.len ) return true;
    if( len < p.len ) return false;
    fall( i , len , 1 ) 
    {
        if( num[i] > p.num[i] ) return true;
        if( num[i] < p.num[i] ) return false;
    }
    return false;
}
bool point::operator<(const point &p)const
{
    if( len < p.len ) return true;
    if( len > p.len ) return false;
    fall( i , len , 1 ) 
    {
        if( num[i] < p.num[i] ) return true;
        if( num[i] > p.num[i] ) return false;
    }
    return false;
}

int main()
{    
    one = point(1);
    zero = point(0);
    two = point(2);
    int cnt = 1;
    while( true )
    {
        m.in();
        n.in();
        if( n == zero && m == zero ) break;
        if( n > m || n == m )
        {
            ( n - m ).out(1);
            continue;
        }
        now[1] = m;
        ans = m - n;
        cnt = 1;cntt=0;
        while( cnt )
        {
            rise( i , 1 , cnt )
            {
                if( ans > now[i] - n + nv[i] ) ans = now[i] - n + nv[i];
                if( now[i].num[1] % 2 == 0 )
                {
                    flag = 0;
                    rise( j , 1 , cntt )
                    if( now[i] == tmp[j] )
                    {
                        if( nv[i] < tv[j] )
                        tv[j] = nv[i];
                        flag = true;
                    }
                    if( !flag )
                    {
                        tmp[++cntt] = now[i];
                        tv[cntt] = nv[i];
                    }
                }
                else
                {
                    nv[i].inc();
                    flag = false;
                    now[i].inc();
                    rise( j , 1 , cntt )
                    if( now[i] == tmp[j] )
                    {
                        if( nv[i] < tv[j] )
                        tv[j] = nv[i];
                        flag = true;
                    }
                    if( !flag )
                    {
                        tmp[++cntt] = now[i];
                        tv[cntt] = nv[i];
                    }
                    
                    if( now[i] > two ) 
                    {
                        flag = false;
                        now[i].dec(2);
                        rise( j , 1 , cntt )
                        if( now[i] == tmp[j] )
                        {
                            if( nv[i] < tv[j] )
                            tv[j] = nv[i];
                            flag = true;
                        }
                        if( !flag )
                        {
                            tmp[++cntt] = now[i];
                            tv[cntt] = nv[i];
                        }
                    }
                }
                now[i].clear();
                nv[i].clear();
            }
            cnt = 0;
            rise( i , 1 , cntt )
            {
                if( ( tmp[i].len > 1 || tmp[i].num[1] > 2 ) && tmp[i] > n )
                {
                    tmp[i].divid();
                    nv[++cnt] = tv[i] + one;
                    now[cnt] = tmp[i];
                }
                tmp[i].clear();
                tv[i].clear();
            }
            cntt = 0;
        }
        ans.out(1);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u014250021/article/details/38885977


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }