去長(zhǎng)春之前的一場(chǎng)。。。 現(xiàn)在把題解補(bǔ)上
250pt
在二維坐標(biāo)軸上從0,a走到k,b，走一次在x軸上前進(jìn)一個(gè)單位長(zhǎng)度，在y軸上上升或者下降一個(gè)單位長(zhǎng)度。
現(xiàn)在已知中間的某段連續(xù)區(qū)域的走法（只由'U'和'D'構(gòu)成的不超過50的字符串）。問是否在保證最低點(diǎn)不低于0的情況下成功走到終點(diǎn)。
算法分析：
計(jì)算這段區(qū)域的最低點(diǎn)，如果低于0，那就全用'U'補(bǔ)上。然后判斷一下剩下的區(qū)間就可以了。
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
在一個(gè)圖中，支持一種操作。每次對(duì)一個(gè)無色點(diǎn)的所有后繼染色。但是不能對(duì)強(qiáng)聯(lián)通分支中的點(diǎn)操作。問最多染色幾次。
相當(dāng)于詢問一個(gè)有限偏序集的寬度。有定理
http://en.wikipedia.org/wiki/Dilworth%27s_theorem
求傳遞閉包的最小點(diǎn)路徑覆蓋。二分匹配中可以不去掉強(qiáng)聯(lián)通的邊，因?yàn)檫@樣的點(diǎn)在傳遞閉包中一定會(huì)占用一個(gè)最大匹配。
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
西月弦 閱讀(485)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告