TopCoder SRM 661 (Div. 2) 总结

早上涨到蓝名下午就在模拟赛垫底了。。这人品守恒

唔。。这次div2打得还算可以吧,房间rank2(很不理解第二题dfs为什么没人写。。怕麻烦吗),950的题一直在推公式后来才发现可以暴力DP。。不过发现的时候已经到Challenge阶段了。

涨到蓝名,下次就得打div1了。。好虚啊,div1的题都不会做怎么办T T

250:

题目大意:给出一个方阵,o代表沙子,x代表障碍物,”.”代表空地。如果沙子下面是空地就会往下掉,障碍物不动。问最后是什么样子的。

模拟。。

class FallingSand {
    public:
    vector<string> simulate(vector<string> board) {
        int n=board.size(),len=board[0].length();
        for(int i=n-2;i>=0;--i) {
            for(int j=0;j<len;++j) if(board[i][j]=='o') {
                int i1=i;
                board[i1][j]='.';
                while(i1+1<n && board[i1+1][j]=='.') ++i1;
                board[i1][j]='o';
            }
        }
        return board;
    }
};

500:
题目大意:有两行点,初始每行第i个点和第i+1个点之间有双向边,带权值(最后一个点没有向后面的连边)。然后你需要添加k个垂直的双向边(即连接第一行的第i个点和第二行的第i个点),这些边权值都是0,使得所有点对中最短路最长的路径长度最小。返回这个值。

n,k<=11

嗯。。dfs枚举在哪加边,floyd更新答案

const int INF=~0U>>2;
const int MAXN=15;
int ar[MAXN];
vector<int> a,b;
int mat[MAXN<<1][MAXN<<1];
class BridgeBuildingDiv2 {
    int ans;
    int n,k;
    int calc() {
        memset(mat,-1,sizeof(mat));
        for(int i=0;i<n-1;++i)
            mat[i][i+1]=mat[i+1][i]=a[i];
        for(int i=0;i<n-1;++i)
            mat[i+n][i+n+1]=mat[i+n+1][i+n]=b[i];
        for(int i=0;i<2*n;++i)
            for(int j=0;j<2*n;++j) {
                if(mat[i][j]!=-1) continue;
                if(i==j) mat[i][j]=0;
                else mat[i][j]=INF;
            }
        for(int i=0;i<k;++i) mat[ar[i]][ar[i]+n]=mat[ar[i]+n][ar[i]]=0;
        int res=0;
        for(int k=0;k<n*2;++k)
            for(int i=0;i<n*2;++i)
                for(int j=0;j<n*2;++j)
                    mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
        for(int i=0;i<n*2;++i)
            for(int j=0;j<n*2;++j)
                res=max(res,mat[i][j]);
                //printf("%d\n",mat[i][j]);
        return res;
    }
    void dfs(int cur,int dep) {
        if(dep==k) {
            ans=min(ans,calc());
            return;
        }
        for(int i=cur;i<n;++i) {
            ar[dep]=i;
            dfs(i+1,dep+1);
        }
    }
    public:
    int minDiameter(vector<int> _a, vector<int> _b, int K) {
        a=_a;b=_b;
        n=a.size()+1;k=K;
        ans=INF;
        dfs(0,0);
        return ans;
    }
};

950:

有n个点,初始没有边。要用k种颜色染(不一定全部用到)。对于每个点i,可以选择一个j(j<i且i和j颜色不同),从i到j连一条有向边,也可以不选。问有多少种不同的图。

n<=100 k<=3

由于数据范围比较小,可以暴力dp。对于k=3的情况,dp[n][a][b]表示前n个点有a个颜色为1的点,b个颜色为2的点,n-a-b个颜色为3的点的方案数。k=2类似。定义状态之后转移就很好想了(详见代码)

然后敲完暴力dp交上去就可以A了。

但是!这题输入只有两个数,这启发我们寻找是否有规律。

经过打表发现确实是有规律的。。k=2的时候,答案=(n+1)!,k=3的时候,答案=1*3*5*7*…*(2*n+1)

然后这样写个程序交上去就跑的飞起了

由于懒。。没有写第二种解法的代码。。应该没有人不会写吧

const int MAXN=100+5;
const int MOD=1000000007;
typedef long long LL;
int n,k;
namespace work1 {
    int dp[MAXN][MAXN][MAXN];
    int src(int n,int a,int b) {
        int& ans=dp[n][a][b];
        if(ans!=-1) return ans;
        if(n==1) return ans=1;
        ans=0;
        if(a!=0) {
            LL t=src(n-1,a-1,b);
            (t*=n-a+1)%=MOD;
            (ans+=t)%=MOD;
        }
        if(b!=0) {
            LL t=src(n-1,a,b-1);
            (t*=n-b+1)%=MOD;
            (ans+=t)%=MOD;
        }
        if(n-a-b!=0) {
            LL t=src(n-1,a,b);
            (t*=a+b+1)%=MOD;
            (ans+=t)%=MOD;
        }
        return ans;
    }
    int work() {
        memset(dp,-1,sizeof dp);
        int ans=0;
        for(int i=0;i<=n;++i)
            for(int j=0;i+j<=n;++j)
                (ans+=src(n,i,j))%=MOD;
        return ans;
    }
};
namespace work2 {
    int dp[MAXN][MAXN];
    int src(int n,int a) {
        int& ans=dp[n][a];
        if(ans!=-1) return ans;
        if(n==1) return ans=1;
        ans=0;
        if(a>0) {
            LL t=src(n-1,a-1);
            (t*=n-a+1)%=MOD;
            (ans+=t)%=MOD;
        }
        if(n-a>0) {
            LL t=src(n-1,a);
            (t*=a+1)%=MOD;
            (ans+=t)%=MOD;
        }
        return ans;
    }
    int work() {
        memset(dp,-1,sizeof dp);
        int ans=0;
        for(int i=0;i<=n;++i) (ans+=src(n,i))%=MOD;
        return ans;
    }
};
class ColorfulLineGraphsDiv2 {
    public:
    int countWays(int N, int K) {
        n=N;k=K;
        if(k==1) return 1;
        if(k==2) return work2::work();
        return work1::work();
    }
};

 

发表评论

电子邮件地址不会被公开。