topcoder srm 687 div1

1、$A_{1}=2,A_{2}=3,A_{n}=A_{n-2}+A_{n-1}-1$。给出数字$n$，将其表示成若干个$A$中的不同元素的和。

思路：设$B_{n}=A_{n}-1$，那么有$B_{n}=B_{n-2}+B_{n-1},B_{1}=1,B_{2}=2$。那么$B$其实是斐波那契数列。设将$n$表示成$k$个$A$中的元素，那么就等同于将$n-k$表示成$k$个$B$中不同的元素。这个分两步进行：（1）将$n-k$表示成最少的$B$中元素的和，（2）如果这个个数大于$k$那么无解。若小于$k$，可以将某个数字$x=B_{t}$替换为$B_{t-2}+B_{t-1}$以增加一个数字。

#include <stdio.h>

#include <string.h>

#include <string>

#include <iostream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <stack>

using namespace std;

long long f[100];

int n;

void init(long long x)

{

    f[1]=1;

    f[2]=2;

    for(int i=3;i<100;++i)

    {

        f[i]=f[i-1]+f[i-2];

        if(f[i]>x)

        {

            n=i-1; break;

        }

    }

}

vector<int> ans;

int check(int k,long long x)

{

    if(x<=0) return 0;

    ans.clear();

    while(x>0)

    {

        for(int i=n;i>=1;--i) if(x>=f[i])

        {

            ans.push_back(i);

            x-=f[i];

            break;

        }

    }

    if((int)ans.size()>k) return 0;

    while((int)ans.size()<k)

    {

        sort(ans.begin(),ans.end());

        int ok=0;

        for(int i=0;i<(int)ans.size();++i)

        {

            if((i==0&&ans[0]>=3)||(i!=0&&ans[i]-ans[i-1]>=3))

            {

                ans.push_back(ans[i]-1);

                ans[i]-=2;

                ok=1;

                break;

            }

        }

        if(!ok) return 0;

    }

    return 1;

}

class AlmostFibonacciKnapsack

{

public:

	vector<int> getIndices(long long x)

	{

	    init(x);

	    for(int i=1;i<=n;++i) if(check(i,x-i)) return ans;

	    return vector<int>{-1};

	}

};

　2、给出一个二维整数数组$A[n][n]$。构造一个$n$个顶点的带权无向图$G$，使得对于$G$中任意两点$i,j$,它们之间的最小割等于$A[i][j]$。

思路：最小割的一个性质是：对于由一个割$C$将$G$分成的两个点集$P,Q$，对于$P,Q$内任意一点$p,q$，它们之间的最小割小于等于$|C|$。所以，初始化所有顶点是一个集合$S$。然后每一步重复下面操作：

（1）若$S$的大小小于2结束；否则找到最小的$t=A[i][j],i\in S,j\in S$

（2）初始化集合$S_{0},S_{1}$为空，将$S$中第一个元素$x_{0}$放入$S_{0}$.然后对于$S$中任意一个其他元素$x_{i}$，若$A[x_{0}][x_{i}]>t$则将$x_{i}$放入$S_{0}$,否则将其放入$S_{1}$

（3）对于$S_{0},S_{1}$中的元素$x,y$，若$A[x][y]!=t$，则无解。

（4）递归判断$S_{0},S_{1}$

#include <stdio.h>

#include <string.h>

#include <string>

#include <iostream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <stack>

using namespace std;

const int N=2005;

const int INF=1000000005;

class AllGraphCuts

{

    int n;

    int g[55][55];

    vector<int> ans;

    void add(int u,int v,int w)

    {

        ans.push_back(w*n*n+u*n+v);

    }

    int dfs(vector<int> S)

    {

        if(S.size()<=1) return 1;

        int tmp=INF;

        for(int i=0;i<(int)S.size();++i) for(int j=0;j<(int)S.size();++j)

        {

            if(i!=j&&g[S[i]][S[j]]<tmp) tmp=g[S[i]][S[j]];

        }

        vector<int> S0,S1;

        S0.push_back(S[0]);

        for(int i=1;i<(int)S.size();++i)

        {

            if(g[S[0]][S[i]]>tmp) S0.push_back(S[i]);

            else S1.push_back(S[i]);

        }

        if(S0.empty()||S1.empty()) return 0;

        for(int i=0;i<(int)S0.size();++i) for(int j=0;j<(int)S1.size();++j)

        {

            if(g[S0[i]][S1[j]]!=tmp) return 0;

        }

        add(S0[0],S1[0],tmp);

        return dfs(S0)&&dfs(S1);

    }

public:

	vector<int> findGraph(vector<int> x)

	{

	    n=1;

	    while(n*n!=(int)x.size()) ++n;

	    for(int i=0;i<n;++i) for(int j=0;j<n;++j) g[i][j]=x[i*n+j];

	    for(int i=0;i<n;++i) for(int j=0;j<n;++j)

        {

            if((i==j&&g[i][j]!=0)||(g[i][j]!=g[j][i])) return vector<int>{-1};

        }

	    vector<int> S;

	    for(int i=0;i<n;++i) S.push_back(i);

	    if(dfs(S)) return ans;

        return vector<int>{-1};

	}

};

巴特西

topcoder srm 687 div1

最新文章

热门文章