PS:
1. 昨晚在公司里参加SRM416比赛,SF没想到竟然在我做第二题的时候临时给我任务,没办法只能中途搁下了. 以后再也不在公司里做了,免得被打扰了! 后来回去看的时候已经是Challenge阶段了,不小心扣了50points,吸取教训,以后没有把握绝不随便Challenge了.
2. 在TopCoder做了10场比赛了,还是处在灰色的底层阶级,感觉自己应该不至于是这个水平吧?! 从下一次开始要好好得玩了!
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
// 250 points
class MostCommonLetters
{
public:
string listMostCommon(vector <string> text)
{
stringresult ;
int n = text.size() ;
vector<int> res ;
for (int i = 0 ; i < 26 ; i ++)
res.push_back(0) ;
for (int i = 0 ; i < n ; i ++)
{
int m = text[i].size() ;
for (int j = 0 ; j < m ; j ++)
{
if (text[i][j] == ' ')
continue ;
else
res[text[i][j]-'a'] ++ ;
}
}
int max = res[0] ;
for (int i = 1 ; i < 26 ; i ++)
if (res[i] >= max)
max = res[i] ;
for (int i = 0 ; i < 26 ; i ++)
if (res[i] == max)
result += char(i+'a') ;
return result ;
}
};
// 500 point
class NextNumber
{
public:
int getNextNumber(int N)
{
int i , t ;
int result = 0 , TN = N ;
vector<int> res , temp ;
while (N > 0)
{
t = N % 2 ;
res.push_back(t) ;
N /= 2 ;
}
reverse(res.begin(),res.end()) ;
for (i = 0 ; i < res.size() ; i ++)
temp.push_back(res[i]) ;
next_permutation(temp.begin(),temp.end()) ;
for (i = 0 ; i < temp.size() ; i ++)
result = result*2 + temp[i] ;
if (result > TN)
return result ;
else
{
int cnt = 0 ;
for (i = res.size()-1 ; i >= 0 ; i --)
if(res[i] == 0) cnt ++ ;
else break ;
int tem = (int)pow((double)2,(double)(res.size())) ;
return (tem + ((2*TN-tem)>>(cnt+1))) ;
}
}
};
// 1000 points
// Method I –DFS Time Limited Exceeded
#define NUM 11
class DancingCouples
{
public:
int result ;
int KK , N , M ;
bool G[NUM] , B[NUM] ;
vector <string> CanDance ;
public:
long Solve(int i,int k)
{
if (k == KK)
{
result ++ ;
return ;
}
if (k == N)
{
return 0 ;
}
for ( ; i < N ; i ++)
{
if (B[i] == false)
{
for (int j = 0 ; j < M ; j ++)
{
if (G[j] == false)
{
if (CanDance[i][j] == 'Y')
{
k ++ ;
B[i] = true ;
G[j] = true ;
Solve(i+1,k) ;
G[j] = false ;
B[i] = false ;
k -- ;
}
}
}
}
}
}
int countPairs(vector <string> canDance, int K)
{
result = 0 ;
KK = K ;
N = canDance.size() ;
M = canDance[0].size() ;
CanDance = canDance ;
memset(G,false,sizeof(G)) ;
memset(B,false,sizeof(B)) ;
Solve(0,0) ;
return result ;
}
};
// Method II - DP
#define NUM 11
class DancingCouples
{
public:
int KK ;
vector <string> CanDance ;
int res[NUM][1<<NUM][NUM] ;
long long sovle(int b,int mask,int n)
{
if(n == KK) return 1 ;
if(b >= CanDance.size()) return 0 ;
if (res[b][mask][n] != -1) return res[b][mask][n] ;
int r = 0 ;
for (int i = 0 ; i < CanDance[b].size() ; i ++)
if ( CanDance[b][i] == 'Y' && !(mask&(1<<i)) )
r += sovle( b+1,mask|(1<<i),n+1 ) ;
r += sovle(b+1,mask,n) ;
return res[b][mask][n] = r ;
}
int countPairs(vector <string> canDance, int K)
{
KK = K ;
CanDance = canDance ;
memset(res,-1,sizeof(res)) ;
return sovle(0,0,0) ;
}
};