topcoder srm 704 div1

1、对于一棵树上的一个节点$u$，定义$f(u)$表示树上距离$u$最远的节点到$u$的距离。给出每个节点的$f$值，构造出这棵树。

思路：找到树的主干，然后不在主干上的节点一定可以连接到主干的某个节点上。

#include <iostream>

#include <map>

#include <string>

#include <stdio.h>

#include <vector>

#include <set>

#include <algorithm>

#include <string.h>

#include <fstream>

#include <sstream>

using namespace std;

const int N=1000005;

const int mod=1000000007;

class TreeDistanceConstruction

{

    int a[111];

    int get(int t,vector<pair<int,int>> &p)

    {

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

        {

            if(p[i].first==t)

            {

                if(!a[p[i].second])

                {

                    a[p[i].second]=1;

                    return p[i].second;

                }

            }

        }

        return -1;

    }

public:

    vector<int> construct(vector<int> d)

    {

        const int n=(int)d.size();

        vector<pair<int,int>> p;

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

        {

            p.push_back(make_pair(d[i],i));

        }

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

        vector<int> ans;

        const int Max=p.back().first;

        const int Min=p[0].first;

        if(Min<(Max+1)/2) return ans;

        if(Min>(Max+1)/2) return ans;

        memset(a,0,sizeof(a));

        if(Max&1)

        {

            const int K=(Max+1)>>1;

            vector<int> ll,rr;

            for(int i=K;i<=Max;++i)

            {

                int t=get(i,p);

                if(t==-1) return ans;

                ll.push_back(t);

                t=get(i,p);

                if(t==-1) return ans;

                rr.push_back(t);

            }

            if(get(K,p)!=-1) return ans;

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

            {

                ans.push_back(ll[i]);

                ans.push_back(ll[i+1]);

            }

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

            {

                ans.push_back(rr[i]);

                ans.push_back(rr[i+1]);

            }

            ans.push_back(ll[0]);

            ans.push_back(rr[0]);

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

            {

                int id=p[i].second;

                if(!a[id])

                {

                    int len=p[i].first;

                    int nIndex=len-K-1;

                    ans.push_back(id);

                    ans.push_back(ll[nIndex]);

                }

            }

            return ans;

        }

        else

        {

            const int K=Max>>1;

            const int Kid=get(K,p);

            if(Kid==-1) return ans;

            if(get(K,p)!=-1) return ans;

            vector<int> ll,rr;

            for(int i=K+1;i<=Max;++i)

            {

                int t=get(i,p);

                if(t==-1) return ans;

                ll.push_back(t);

                t=get(i,p);

                if(t==-1) return ans;

                rr.push_back(t);

            }

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

            {

                ans.push_back(ll[i]);

                ans.push_back(ll[i+1]);

            }

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

            {

                ans.push_back(rr[i]);

                ans.push_back(rr[i+1]);

            }

            ans.push_back(ll[0]);

            ans.push_back(Kid);

            ans.push_back(rr[0]);

            ans.push_back(Kid);

            ll.insert(ll.begin(),Kid);

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

            {

                int id=p[i].second;

                if(!a[id])

                {

                    int len=p[i].first;

                    int nIndex=len-K-1;

                    ans.push_back(id);

                    ans.push_back(ll[nIndex]);

                }

            }

            return ans;

        }

    }

};

2、给定整数$n,K,v$，确定一个长度为$n$的序列$x$，满足$0\leq x_{i}< K$且$x_{1}x_{2}...x_{n}mod K=v$。问这样的序列有多少个。现在给出很多$v$，对每一个$v$计算一个答案。

思路：（1）首先，假设$x$的前$n-1$个数已经确定，令$r=Gcd(\prod_{i=1}^{n-1}x_{i},K)$。那么由$r,v$可以确定$x_{n}$的取值。由于$\left (r\cdot x_{n} \right )mod K=v$，那么$r\cdot x_{n}=tK+v$，所以$Gcd(r,K)$可以整除$v$。由于$r$可以整除$K$，所以$r=Gcd(r,K)$一定可以整除$v$。那么对于某个$r$，$x_{n}$有$K/r$种选择，分别是$\frac{tK+v}{r},0\leq t<r$。

（2）由于$K$的约数不会太多，所以可以进行动态规划，设$f[i][j]$表示已经确定了$i$个$x$，它们的乘积与$K$的最大公约数为$j$。那么每次可以由$f[i][j]$转移到$f[i+1][k]$，其中$j$可以整除$k$。令$p=\frac{k}{j}$，那么$q=Gcd(j\cdot tp,K)$一定是$k$的倍数。那么进行容斥原理即可确定$x_{i+1}$ 种类使得$j\cdot x_{i+1} mod K=k$。

#include <iostream>

#include <map>

#include <string>

#include <stdio.h>

#include <vector>

#include <set>

#include <algorithm>

#include <string.h>

using namespace std;

const int mod=1000000007;

int f[55][111111];

int d[111111];

vector<int> q[111111];

void add(int &x,int y)

{

    x+=y;

    if(x>=mod) x-=mod;

}

class ModEquation

{

public:

    vector<int> count(int n,int K,vector<int> query)

    {

        vector<int> p;

        for(int i=1;i*i<=K;++i) {

            if(K%i==0) {

                p.push_back(i);

                if(i*i!=K) p.push_back(K/i);

            }

        }

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

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

            q[i].clear();

            for(int j=i;j<(int)p.size();++j) {

                if(p[j]%p[i]==0) {

                    q[i].push_back(j);

                }

            }

        }

        f[0][0]=1;

        for(int i=1;i<=n-1;++i)

        {

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

            {

                for(int k=0;k<(int)q[j].size();++k) {

                    d[q[j][k]]=(long long)f[i-1][j]*(K/(p[q[j][k]]/p[j]))%mod;

                }

                for(int k=(int)q[j].size()-1;k>=0;--k) {

                    const int u=q[j][k];

                    for(int t=1;t<(int)q[u].size();++t) {

                        const int v=q[u][t];

                        add(d[u],mod-d[v]);

                    }

                }

                for(int k=0;k<(int)q[j].size();++k) {

                    const int u=q[j][k];

                    add(f[i][u],d[u]);

                    d[u]=0;

                }

            }

        }

        vector<int> ans;

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

            const int v=query[i];

            int tmp=0;

            for(int j=0;j<(int)p.size();++j) {

                if(v%p[j]==0) {

                    add(tmp,(long long)f[n-1][j]*p[j]%mod);

                }

            }

            ans.push_back(tmp);

        }

        return ans;

    }

};

3、构造一个有$n$个顶点的有向图，使得以0号节点开始，$n-1$号节点结束的哈密顿路径恰有$k$条。$2\leq n \leq 20$。

思路：如代码所示。路径上第二个节点是$n-2$时，有1条；否则若第二个节点是$n-3-i$，则有$2^{i}$条。

#include <iostream>

#include <map>

#include <string>

#include <stdio.h>

#include <vector>

#include <set>

#include <algorithm>

#include <string.h>

using namespace std;

class HamiltonianConstruction

{

public:

    vector<string> construct(int k)

    {

        const int n=20;

        vector<string> ans(n,string(n,'N'));

        for(int i=2;i<=n-2;++i) ans[i][i-1]='Y';

        for(int i=1;i<n;++i) {

            for(int j=i+1;j<n;++j) ans[i][j]='Y';

        }

        for(int i=n-3;i>=1;--i,k>>=1) {

            if(k&1) ans[0][i]='Y';

        }

        return ans;

    }

};

巴特西

topcoder srm 704 div1

最新文章

热门文章