/ Vijos / 题库 / 超级汉诺塔 /

题解

38 条题解

  • 5
    @ 2016-11-17 13:05:34 
    /*
NOIP考前好题求++rp~
首先我们看到这道题目的时候   很容易想到n这么小是不是可以搜索来做
但是发现复杂度有点高~(枚举ans)
仔细想一下其实答案是具有单调性的
随着汉诺塔数量的增加  能放的圆盘数量一定是不减的
所以我们可以来二分ans以降低复杂度
(关于二分边界的话其实我们可以先写一个枚举打出n=15时的ans是600多改成二分即可)
这里我的二分范围是0-700了
那么我们考虑如果验证一个ans是否可行(check)
因为是要按顺序来的
所以我们考虑对于两个数x y
如果x+y是质数    我们连一条有向边x->y(注意一定要是有向边因为有顺序限制)
这样我们建立出了一个有向图
对于一条边的两个顶点  我们可以选择放在一个塔上
那么我们成功建模:
对于一个有向图,至少需要用多少条不相交路径才能将它盖住
那么我们有这样的定理
最小路径覆盖=顶点总数-最大匹配数
这样我们对于二分的ans
只需要跑一遍匈牙利算法(网络流)
求出最小路径覆盖判断是否小于或者等于ans即可
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;

const int MAXN=700;
int vis[MAXN+5],match[MAXN+5];
int g[MAXN+5][MAXN+5];
int n;

bool is_prime(int x)
{
    if(x==2)
        return 1;
    int k=sqrt(x);
    for(int i=2;i<=k;i++)
        if(x%i==0)
            return 0;
    return 1;
}

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=MAXN;i++)
        for(int j=i+1;j<=MAXN;j++)
            if(is_prime(i+j))
                g[i][j]=1;
}

bool dfs(int& u,int& x)
{
    for(int i=1;i<=x;i++)
        if(g[u][i]&&!vis[i])
        {
            
            vis[i]=1;
            if(!match[i]||dfs(match[i],x))
            {
                match[i]=u;
                return true;
            }
        }
    return false;
}

bool check(int x)
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=x;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i,x))
            ans++;
    }
    return (x-ans)<=n;
}

void work()
{
    int ans=0;
    int l=0,r=MAXN-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            ans=max(ans,mid);
            l=mid+1;
        }
        else
            r=mid-1;
    }
    printf("%d",ans);
}

int main()
{
    init();
    work();
}
  • 2
    @ 2016-12-01 13:15:38 
    #include <cstdio>
int ans[16] = {0,4,7,43,60,61,62,172,269,452,573,674,675,676,677,678};
int main() {
    int n;
    scanf("%d",&n);
    printf("%d",ans[n]);
    return 0;
}

    打表大法好！

  • 0
    @ 2016-11-09 18:48:33

    C++题解+代码
    http://www.cnblogs.com/937337156Zhang/p/6047825.html

  • 0
    @ 2016-05-22 16:43:35

    感慨一年前看着道题就懵逼了，现在一看直接匈牙利。。。

  • 0
    @ 2016-03-18 19:18:59

    测试数据 #0: Accepted, time = 0 ms, mem = 8416 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 8416 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 8416 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 8416 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 8416 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 8416 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 8416 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 8420 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 8420 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 8432 KiB, score = 10
    Accepted, time = 15 ms, mem = 8432 KiB, score = 100

  • 0
    @ 2015-08-28 09:19:22

    测试数据 #0: Accepted, time = 1 ms, mem = 2692 KiB, score = 10
    测试数据 #1: Accepted, time = 2 ms, mem = 2680 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 2688 KiB, score = 10
    测试数据 #3: Accepted, time = 2 ms, mem = 2684 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 2684 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 2688 KiB, score = 10
    测试数据 #6: Accepted, time = 35 ms, mem = 2684 KiB, score = 10
    测试数据 #7: Accepted, time = 1 ms, mem = 2684 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 2688 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 2684 KiB, score = 10
    Accepted, time = 86 ms, mem = 2692 KiB, score = 100
    var
    pan:array[0..1400] of boolean;
    n,i,j,sum,neck,neck1,minn,maxx,mid:longint;
    g:array[0..1400,0..1400] of boolean;
    used:array[0..700] of boolean;
    bl:array[0..700] of longint;
    function dfs(num:longint):boolean;
    var i:longint;
    begin
    for i:=num+1 to mid do
    if (g[num,i]=true) and (not used[i]) then
    begin
    used[i]:=true;
    if (bl[i]=0) or (dfs(bl[i])) then
    begin
    bl[i]:=num;
    exit(true);
    end;
    end;
    exit(false);
    end;
    begin
    readln(n);
    for i:=2 to 1400do
    pan[i]:=true;
    neck:=2;
    while neck<=1400 do
    begin
    neck1:=neck+neck;
    while neck1<=1400 do
    begin
    pan[neck1]:=false;
    neck1:=neck1+neck;
    end;
    neck:=neck+1;
    while (neck<=1400) and (pan[neck]=false) do
    neck:=neck+1;

    end;
    minn:=1;
    maxx:=700;
    for i:=1 to 700do
    for j:=i+1 to 700 do
    begin
    if pan[i+j] then g[i,j]:=true;
    end;
    while minn<=maxx do
    begin

    mid:=(maxx+minn) div 2;
    fillchar(used,sizeof(used),false);
    fillchar(bl,sizeof(bl),0);
    sum:=0;
    for i:=1 to mid do
    begin
    fillchar(used,sizeof(used),false);

    if dfs(i) then inc(sum);
    end;
    if mid-sum<=n then minn:=mid+1 else maxx:=mid-1;

    end;
    write(minn-1);

    end.

    来一发pascal题解

  • 0
    @ 2014-06-18 22:02:47

    #include <cstdio>
    #include <cstring>
    #include <cmath>

    #define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )
    #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
    #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

    #define maxn 1010
    #define maxm 1010000

    struct edge {
    edge *next ;
    int t ;
    } E[ maxm ] ;

    edge *pt = E , *head[ maxn ] ;

    inline void addedge( int s , int t ) {
    pt -> t = t , pt -> next = head[ s ] ; head[ s ] = pt ++ ;
    }

    inline bool check( int x ) {
    for ( int i = 2 , y = int( sqrt( x ) ) ; i <= y ; ++ i ) if ( ! ( x % i ) ) {
    return false ;
    }
    return true ;
    }

    int mat[ maxn ] , n ;
    bool used[ maxn ] ;

    bool dfs( int now ) {
    travel( now ) if ( ! used[ p -> t ] ) {
    used[ p -> t ] = true ;
    if ( ! mat[ p -> t ] || dfs( mat[ p -> t ] ) ) {
    mat[ p -> t ] = now ;
    return true ;
    }
    }
    return false ;
    }

    int main( ) {
    memset( head , 0 , sizeof( head ) ) , memset( mat , 0 , sizeof( mat ) ) ;
    scanf( "%d" , &n ) ;
    REP( i , 1 , ( maxn - 1 ) ) {
    rep( j , n ) addedge( i , j ) ;
    REP( j , 1 , ( i - 1 ) ) if ( check( i + j ) ) addedge( i , n + j ) ;
    rep( j , ( n + i ) ) used[ j ] = false ;
    if ( ! dfs( i ) ) {
    printf( "%d\n" , i - 1 ) ; return 0 ;
    }
    }
    return 0 ;
    }

    暴力匈牙利即可。

  • 0
    @ 2013-07-27 10:23:51

    最小路径覆盖。，。，无耻的打表

  • 0
    @ 2013-05-11 22:15:49

    魔术球问题= =

  • 0
    @ 2010-03-04 21:56:59

    二分还是稍微快点

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 9ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：9ms

  • 0
    @ 2010-03-04 18:17:13

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 25ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：25ms

    原来N=K时的匹配结果N=K+1时可以继续利用，但要加个条件限制确认此点没有匹配才能找增广路。

  • 0
    @ 2009-11-10 18:23:50

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 41ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：41ms

    O(n^0.5)的判素数，每次重新做最大匹配，从2开始穷举，邻接表，无任何优化。

    41ms，随便了。

  • 0
    @ 2009-11-02 20:54:39

    一年前看的这题。

    现在终于AC了。

    就像某些大牛说的那样。

    匈牙利这东西，每做一次都会有新的感悟。。

    Orz 楼下众神牛。

  • 0
    @ 2009-10-27 08:18:20

    用不着二分。。

    直接for上去就行了，并且每次可以接着上次的结果继续匹配下去，非常快。

    for (n = 2;;n++){

    AddVertex(n);

    memset(hash,0,sizeof(hash))

    cnt+=!dfs(n);

    if (cnt>=m) break;

    }

  • 0
    @ 2009-10-24 19:47:08

    solution...

    http://user.qzone.qq.com/740436286/infocenter?ptlang=2052

  • 0
    @ 2009-10-04 18:46:38

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    秒杀了 哈哈

  • 0
    @ 2009-10-01 15:09:41

    犯了和省选一样的错，我，我，我~~~~~~~~

  • 0
    @ 2009-09-28 17:40:03

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    唉 第一次还把二分图匹配写错了

    二分答案 + 二分图匹配 + 一点点剪枝 = 秒杀

  • 0
    @ 2009-09-25 14:58:24

    水题 秒扫

    二分+HopcroftKarp

  • 0
    @ 2009-09-11 22:43:48

    OTL 拜一个……每逢难题总是见到一堆神牛再楼下狂飙……

    美妙的匈牙利+2分……

超级汉诺塔

信息

ID
1526
难度
4
分类
图结构 | 二分图匹配 点击显示
标签
(无)
递交数
437
已通过
190
通过率
43%
被复制
5
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1