早上涨到蓝名下午就在模拟赛垫底了。。这人品守恒
唔。。这次div2打得还算可以吧，房间rank2（很不理解第二题dfs为什么没人写。。怕麻烦吗），950的题一直在推公式后来才发现可以暴力DP。。不过发现的时候已经到Challenge阶段了。
涨到蓝名，下次就得打div1了。。好虚啊，div1的题都不会做怎么办T T
250：
题目大意：给出一个方阵，o代表沙子，x代表障碍物，”.”代表空地。如果沙子下面是空地就会往下掉，障碍物不动。问最后是什么样子的。
模拟。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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更新答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
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)
然后这样写个程序交上去就跑的飞起了
由于懒。。没有写第二种解法的代码。。应该没有人不会写吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
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(); } }; |