去長春之前的一場。。。 現在把題解補上
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
西月弦 閱讀(473)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告