去长春之前的一场。。。 现在把题解补上
250pt
在二维坐标轴上从0,a走到k,b，走一次在x轴上前进一个单位长度，在y轴上上升或者下降一个单位长度。
现在已知中间的某段连续区域的走法（只由'U'和'D'构成的不超过50的字符串）。问是否在保证最低点不低于0的情况下成功走到终点。
算法分析：
计算这段区域的最低点，如果低于0，那就全用'U'补上。然后判断一下剩下的区间就可以了。
srm 557div1 250pt
1 #include<string>
2 #include<cstdlib>
3 #include<iostream>
4 using namespace std;
5 string judge(int x,int y,int len){
6 cout<<x<<" "<<y<<" "<<len<<endl;
7 if(len<0) return "NO";
8 if(abs(x - y) <= len && (len%2 == abs(x-y) %2)) return "YES";
9 return "NO";
10 }
11 class FoxAndMountainEasy{
12 public : string possible(int n, int h0, int hn, string ch){
13 int c= 0 , v = h0;
14 for(int i = 0; i < ch.size(); i++){
15 if( ch[i] == 'U') v++; else v--;
16 if(v < c) c = v;
17 }
18 int len = n - ch.size() + c;
19 h0 = v - c;
20 return judge(h0,hn,len);
21 }
22 };500pt
在一个图中，支持一种操作。每次对一个无色点的所有后继染色。但是不能对强联通分支中的点操作。问最多染色几次。
相当于询问一个有限偏序集的宽度。有定理
http://en.wikipedia.org/wiki/Dilworth%27s_theorem
求传递闭包的最小点路径覆盖。二分匹配中可以不去掉强联通的边，因为这样的点在传递闭包中一定会占用一个最大匹配。
srm 557div1 550pt
1 #include<vector>
2 #include<string>
3 #include<cstring>
4 using namespace std;
5 const int N = 55;
6 bool G[N][N], chk[N];
7 int yM[N],n;
8 int dfs(int u){
9 for(int v = 0; v < n; v++) if(G[u][v] && !chk[v]){
10 chk[v] = 1;
11 if(yM[v]==-1||dfs(yM[v])){
12 yM[v]=u;return 1;
13 }
14 }
15 return 0;
16 }
17 int maxmatch(){
18 int ans= 0;
19 memset(yM,-1,sizeof(yM));
20 for(int i = 0; i < n; i++){
21 memset(chk,0,sizeof(chk));
22 ans += dfs(i);
23 }
24 return ans;
25 }
26 class Incubator{
27 public : int maxMagicalGirls(vector <string> love){
28 n = love.size();
29 for(int i = 0; i < n; i++)
30 for(int j = 0; j < n; j++)
31 G[i][j] = love[i][j] == 'Y';
32 for(int k = 0; k < n; k ++)
33 for(int i = 0; i < n; i++)
34 for(int j = 0; j < n; j++)
35 if(G[i][k] & G[k][j]) G[i][j]=1;
36 return n - maxmatch();
37 }
38 };
posted on 2012-10-18 14:00
西月弦 阅读(448)
评论(0) 编辑 收藏 引用 所属分类:
解题报告