SRM389, SRM390, Qual1
Posted on 2008-02-09 14:48 oyjpart 閱讀(1747) 評論(0) 編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽 1
long long dp[500001];
2
bool p[500001];
3
4
void pre() {
5
memset(p, 0, sizeof(p));
6
p[0] = p[1] = 1;
7
int i, j;
8
for(i = 2; i < 500001; ++i) if(!p[i]) {
9
for(j = i+i; j < 500001; j+=i) {
10
p[j] = 1;
11
}
12
}
13
}
14
15
class PrimeSums
16
{
17
public:
18
long long getCount(vector <int> bag)
19
{
20
pre();
21
22
map<int, int> mm;
23
sort(bag.begin(), bag.end());
24
int i, j, k;
25
for(i = 0; i < sz(bag); ++i) {
26
if(mm.count(bag[i]))
27
mm[bag[i]]++;
28
else mm[bag[i]] = 1;
29
}
30
memset(dp, 0, sizeof(dp));
31
if(mm.begin()->first == 0) {
32
dp[0] = mm.begin()->second+1;
33
mm.erase(0);
34
}
35
else
36
dp[0] = 1;
37
for(map<int, int>::iterator it = mm.begin(); it != mm.end(); ++it) {
38
printf("%d %d\n", it->first, it->second);
39
int w = it->first;
40
for(j = 500000; j >= 0; --j) {
41
for(k = 1; k <= it->second; ++k) {
42
if(j-k*w >= 0) dp[j] += dp[j-k*w];
43
}
44
}
45
}
46
long long ans = 0;
47
for(i = 0; i < 500001; ++i) {
48
if(!p[i]) {
49
ans += dp[i];
50
if(dp[i]!=0) printf("dp[%d] = %d\n", i, dp[i]);
51
}
52
else if(dp[i]!=0) printf("dp[%d] = %d\n", i, dp[i]);
53
}
54
return ans;
55
}
56
};
57
long long dp[500001];2
bool p[500001];3

4
void pre() {5
memset(p, 0, sizeof(p));6
p[0] = p[1] = 1;7
int i, j;8
for(i = 2; i < 500001; ++i) if(!p[i]) {9
for(j = i+i; j < 500001; j+=i) {10
p[j] = 1;11
}12
}13
}14

15
class PrimeSums16
{ 17
public: 18
long long getCount(vector <int> bag) 19
{ 20
pre(); 21

22
map<int, int> mm;23
sort(bag.begin(), bag.end());24
int i, j, k;25
for(i = 0; i < sz(bag); ++i) {26
if(mm.count(bag[i]))27
mm[bag[i]]++;28
else mm[bag[i]] = 1;29
}30
memset(dp, 0, sizeof(dp));31
if(mm.begin()->first == 0) {32
dp[0] = mm.begin()->second+1;33
mm.erase(0);34
}35
else36
dp[0] = 1;37
for(map<int, int>::iterator it = mm.begin(); it != mm.end(); ++it) {38
printf("%d %d\n", it->first, it->second);39
int w = it->first;40
for(j = 500000; j >= 0; --j) {41
for(k = 1; k <= it->second; ++k) {42
if(j-k*w >= 0) dp[j] += dp[j-k*w];43
}44
}45
}46
long long ans = 0;47
for(i = 0; i < 500001; ++i) {48
if(!p[i]) {49
ans += dp[i];50
if(dp[i]!=0) printf("dp[%d] = %d\n", i, dp[i]);51
}52
else if(dp[i]!=0) printf("dp[%d] = %d\n", i, dp[i]);53
}54
return ans;55
} 56
};57

Rating 小漲,沒到黃。希望以后加油把Rating漲上去。


