算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
A题

分两部分求,因为题目数只有15,所以可以2^15枚举分组情况(分给L还是分给M)。

接下来求对于同一size的M种颜色的气球分配给N个题目的最小代价。
排序之后,从大到小贪心的分配就可以了。

 1 #include<iostream>
 2 #include<string>
 3 #include<vector>
 4 using namespace std;
 5 const int inf = ~0u>>2;
 6 int make(vector<int> &flag, vector<int> &num){
 7     int n = num.size(), m = flag.size(),len = min(n,m);
 8     int suma  = 0, sumb = 0;
 9     for(int i = 0; i < n; i++) suma += num[i];
10     for(int i = 0; i < m; i++) sumb += flag[i];
11     if(suma > sumb) return inf;
12     for(int i = 0; i < len; i++) suma -= min(num[i],flag[i]);
13     return suma;
14 }
15 bool cmp(int a,int b){return a>b;}
16 void op(vector<int> s){
17     for(int i = 0; i < s.size(); i++)cout<<s[i]<<" ";cout<<endl; 
18 }
19 class ICPCBalloons{
20     public :
21     int minRepaintings(vector <int> bC, string bS, vector <int> num){
22         int n= num.size();
23         vector<int> M ,L;
24         for(int i =0; i < bS.size(); i++if(bS[i] == 'L') L.push_back(bC[i]); else M.push_back(bC[i]);
25         sort(M.begin(),M.end(),cmp);
26         sort(L.begin(),L.end(),cmp);
27         sort(num.begin(),num.end(),cmp);
28         cout<<"M: "<<endl; op(M);
29         cout<<"L: "<<endl; op(L);
30         int ans = inf;
31         for(int i = 0; i < (1<<n); i++) {
32             vector<int> m,l;
33             for(int j = 0; j < n; j++if(1<<& i) m.push_back(num[j]); else l.push_back(num[j]);
34             int a = make(M,m);
35             int b = make(L,l);
36             //cout<<"m: "<<endl; op(m);
37             //cout<<"l: "<<endl; op(l);
38             ans = min(ans,a+b);
39         }
40         return ans == inf ? -1 : ans;
41     }
42 };

B题

博弈,给若干个有根树,节点数不超过50,两个人轮流给某个未染色的点染色,这个点一旦被染色,它以及它的所有祖先就都被染色了。
问先手胜还是后手胜。

树形DP求SG值,复杂度O(n^3)。非常裸...
更大规模的解法见 
http://www.2333333.tk/182.html


#include<string>
#include
<iostream>
#include
<vector>
#include
<cmath>
using namespace std;
const int N = 55;
int P[N] ,n, dp[N];
vector
<int> G[N];
inline 
void setc(int p,int c){P[c] = p;
    G[p].push_back(c);
}
bool ispar(int s,int p){
    
while(s!=-1){if(s==p)return 1; s=P[s];} return 0;
}
int dfs(int u) {
//    cout<<"u; "<<u<<endl;
    int &ans = dp[u];
    
if(ans != -1) {
        
//cout<<"back"<<endl;
        return ans;
    }
    
bool vis[101= {0};
    
for(int i = 0; i < n; i++if(ispar(i,u)) {
    
//    cout<<"i: "<<i<<endl;
        int v = i, last = -1 ,sg = 0;
        
while(v != P[u]) {
            
for(int j = 0; j < G[v].size(); j ++if(G[v][j] != last) sg ^= dfs(G[v][j]);
            last 
= v;
            v 
= P[v];
        }
        vis[sg] 
= 1;
    }
    
for(int i = 0; i < 101; i++if(!vis[i]) {ans = i; break;}
    
//cout<<"back"<<endl;
    return ans;
}
double dis(int x0,int y0,int x1,int y1){return sqrt(1.0*(x0-x1)*(x0-x1) + 1.0*(y0-y1)*(y0-y1));}
class CirclesGame{
    
public
    
string whoCanWin(vector <int> x, vector <int> y, vector <int> r){
        memset(P,
-1,sizeof(P));
        memset(dp,
-1,sizeof(dp));
        n 
= x.size();
        
for(int i  =0 ; i < n; i++) {
            
int s = -1;
            
for(int j= 0; j < n; j++if(j != i && 1.0*(r[j] - r[i]) > dis(x[i],y[i],x[j],y[j])){
                
//cout<<j<<" "<<i<<" "<<r[j]-r[i]<<" "<<dis(x[i],y[i],x[j],y[j])<<endl;
                if(s == -1 || r[j] < r[s]) s = j;
            }
            
if(s != -1){     
                setc(s,i);
            }
        }
        
//cout<<"endl"<<endl;
    
//    for(int i = 0; i < n; i++) cout<<P[i]<<" ";cout<<endl;
        int ans = 0;
        
for(int i = 0; i < n; i++if(-1 == P[i]) ans ^= dfs(i);
        
return ans ? "Alice" : "Bob";
    }
};
posted on 2012-11-21 16:02 西月弦 阅读(492) 评论(3)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: topcoder srm 561 div1[未登录]
2012-11-23 13:14 | kaka
不是很明白,能不能详细说一下第二题的思路?  回复  更多评论
  
# re: topcoder srm 561 div1
2012-11-24 14:30 | 西月弦
@kaka
这个... 就是对于每个局面计算SG值。  回复  更多评论
  
# re: topcoder srm 561 div1[未登录]
2012-11-24 20:57 | kaka
@西月弦
看完sg函数,终于明白代码的含义了....  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理