nyoj 1078 汉诺塔（四）[二分图 || 规律 || 暴力 || 贪心]

秒速五厘米 2022-08-12 16:18 138阅读 0赞

题目：[nyoj 1078 汉诺塔（四）][nyoj 1078]

分析：做这个题目的时候是在图论的题目里面看到的，到时读了题目推了一下，发现好像有点规律，试了一下果然过了。

后来看了一下数据，才50，那么试了一下模拟，也过了。

好像zoj有一道题目卡模拟，模拟的时候必须贪心一下才能过

这道题出题人的意图在于考大家的：二分图最小路径覆盖。

把每一个球看做一个点，然后如果两个和为平方数的话就给这两个点之间连接一条边，然后用一个特殊的匹配算法，类似于匈牙利算法，但是每次找匹配的时候加入一条边上连接的有匹配的话就不能匹配，最后求一个最大匹配就好了。这个题目50个点，当然要预处理成离线的。

如果每次都建图跑的话时间复杂度是非常高的，所以我们可以用标记的方法，如果匹配过的就不用再匹配了。这样能降低很多时间，但是还是很长。

找规律代码：

#include <cstdio>
    int ans[55];
    void isit()
    {
        ans[1]=1,ans[2]=3;
        for(int i=3;i<51;i++)
            ans[i]=ans[i-1]+(i+1)/2 * 2;
    }
    int main()
    {
        int T,n;isit();
        scanf("%d",&T);
        for(;T--&&scanf("%d",&n);printf("%d\n",ans[n]));
    }

暴力代码：

#include <cstdio>
    #include <stack>
    #include <cmath>
    using namespace std;
    stack<int> st[60];
    int ans[60];
    void isit()
    {
        int tmp=1,i=1;
        while(i<55)
        {
            int ok=0;
            for(i=1;!st[i].empty();i++)
            {
                int zhi = st[i].top()+tmp;
                int sq=sqrt(zhi);
                if(sq * sq == zhi)
                {
                    st[i].push(tmp);
                    ok=1;
                    break;
                }
            }
            if(!ok){
                st[i].push(tmp);
                ans[i]=tmp-1;
            }
            tmp++;
        }
    }
    int main()
    {
        int T,n;isit();
        scanf("%d",&T);
        for(;T--&&scanf("%d",&n);printf("%d\n",ans[n+1])){}
    }

二分图匹配代码：

#include <cstdio>
    #include <stack>
    #include <cmath>
    #include <cstring>
    using namespace std;
    const int N = 60;
    const int M = 1500;
    int ans[N];
    bool  ok[M*2+10];
    bool mp[M][M];
    int mx[M],my[M]; //mx保存正向边 my保存反向边
    bool used[M]; //
    bool dfs(int v) {
         for (int u = 1; u < v; ++u) //优化
             if (mp[v][u] && !used[u]) {
                used[u] = true;
                 if (my[u] == -1 || dfs(my[u])) {  //一直向下找
                     my[u] = v;
                     mx[v] = u;
                     return true;
                 }
             }
         return false;
    }
    int Max_Pi(int ans,int n)  //最大匹配
    {
        for(int i=1;i<=n;i++)
        {
            if(mx[i]<0){
                memset(used,false,sizeof(used));
                if(dfs(i))
                    ans++;
            }
        }
        return ans;
    }
    void Min_Road()  //最小路径覆盖
    {
        memset(mx,-1,sizeof(mx)); //优化
        memset(my,-1,sizeof(my));
        for(int i=1;i*i<=2*M;i++)
            ok[i*i]=true;
        ans[1]=1;
        int tmp=0;
        for(int i=2;i<=M;i++)
        {
            for(int j=1;j<i;j++)
                if(ok[i+j])
                    mp[i][j]=true;
            tmp=Max_Pi(tmp,i);
            //printf("xx%d %d",i,tmp);
            ans[i-tmp]=i;
            if(i-tmp>55)
                break;
        }
    //    for(int i=1;i<=50;i++)
    //        printf("%d ",ans[i]);
    }
    int main()
    {
        int T,n;Min_Road();
        scanf("%d",&T);
        for(;T--&&scanf("%d",&n);printf("%d\n",ans[n])){}
    }

[nyoj 1078]: http://acm.nyist.net/JudgeOnline/problem.php?pid=1078http://