编程之美2015初赛第一场

Hihocoder 1156 彩色的树

题目链接: http://hihocoder.com/problemset/problem/1156

在每个更新操作的过程中,假设点P最初的颜色为color1,更新后的颜色为color2。
我们记与点P相邻,颜色为color1的点为num1, 颜色为color2的点为num2。
则 ans += num1 - 1, ans -= num2 - 1。

难点主要在于统计nun1, num2。直接暴力肯定是要TLE的,这里有个技巧。

既然是在树中,我们用map存点P的子节点各种颜色的点有多少个,将父节点单独考虑。
查询的过程中:

  • num1 = map[P][color1] + (color[ fa[P] ] == color1)
  • num2 = map[P][color2] + (color[ fa[p] ] == color2)

更新的时候只用将父节点的子节点的color1—, color2++。
在O(log)级的复杂度内就能完成更新查询操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <cstdlib>
#include <iostream>
using namespace std;
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,r) for(int i=0; i<(r); ++i)
#define DWN(i,r,l) for(int i=(r);i>=(l);--i)
#define pb push_back
const int N = 1e5 + 10;
vector<int>head[N];
int color[N], fa[N];
map<int, int>m[N];
void dfs(int cur) { //构建树形结构
for(int to: head[cur]) {
if(to == fa[cur]) continue;
fa[to] = cur;
m[cur][0] ++;
dfs(to);
}
}
void update(int cur, int tmp_color, int &ans) { //更新点的同时同时更新ans
int tmp = 0;
tmp += m[cur][ color[cur] ];
if(color[ fa[cur] ] == color[cur]) ++tmp;
ans += tmp - 1;
tmp = 0;
tmp += m[cur][tmp_color];
if(color[ fa[cur] ] == tmp_color) ++tmp;
ans -= tmp - 1;
--m[ fa[cur] ][ color[cur] ];
++m[ fa[cur] ][ tmp_color ];
color[cur] = tmp_color;
}
int main() {
int casnum, casid = 0, n, q, x, y, z;
cin >> casnum;
while(casnum--) {
memset(color, 0, sizeof(color));
FOR(i, 1, n) head[i].clear(), m[i].clear();
cin >> n;
REP(i, n-1) {
scanf("%d%d", &x, &y);
head[x].pb(y);
head[y].pb(x);
}
fa[1] = 0;
dfs(1);
printf("Case #%d:\n", ++ casid);
int ans = 1;
color[0] = -1;
cin >> q;
while(q--) {
scanf("%d", &x);
if(x == 1) printf("%d\n", ans);
else {
scanf("%d%d", &y, &z);
update(y, z, ans);
}
}
}
return 0;
}

Hihocoder 1157 建造金字塔

题目链接: http://hihocoder.com/problemset/problem/1157

DP。
输入的时候时候一个三角形用顶点坐标(x, y)来表示,我们转化成左右端顶点的横坐标来表示一个三角形(l,r) = (x-y,x+y)。然后按l进行排序。
我们用dp[i][j]表示第i个点,且前从前i个三角形选择的三角形中最右端为j的最大获益。
假设第i个点的左右端点为(l,r),利润为v1,成本为v2,分三种情况讨论:

  1. j <= l:dp[i][r] = max(dp[i][r], dp[i-1][j] + v1 - v2)
  2. j >= r:dp[i][j] = max(dp[i][j], dp[i-1][j] + v1)
  3. j > l && j < r:dp[i][r] = max(dp[i][r], dp[i-1][j] + v1 - v2 + v3)。v3为与之前的重叠面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,r) for(int i=0; i<(r); ++i)
#define DWN(i,r,l) for(int i=(r);i>=(l);--i)
#define pb push_back
double dp[2][3010]; //滚动数组,第一维只要2就够了
struct Trangle {
int l, r;
double v1, v2;
bool operator <(const Trangle &other) const {
if(l != other.l) return l < other.l;
return r < other.r;
}
};
int main() {
int casnum, casid = 0, n, x, y, z;
cin >> casnum;
while(casnum--) {
double ans = 0;
cin >> n;
vector<Trangle>vec(n);
REP(i, n) {
scanf("%d%d%d", &x, &y, &z);
vec[i].l = x - y + 1000;//因为x-y有可能小于0,注意不要超出边界
vec[i].r = x + y + 1000;
vec[i].v1 = z;
vec[i].v2 = y * y;
}
sort(vec.begin(), vec.end()); //按l排序
int cur = 1, pre = 0;
REP(i, 2)
REP(j, 3001)
dp[i][j] = -1e18;
dp[cur][0] = 0;
for(auto t: vec) {
cur ^= 1, pre ^= 1;
REP(i, 3001)
dp[cur][i] = -1e18;
int l = t.l, r = t.r;
REP(i, 3001) {//分三种情况讨论
if(i >= r) dp[cur][i] = max(dp[cur][i], dp[pre][i] + t.v1);
else if(i <= l) dp[cur][r] = max(dp[cur][r], dp[pre][i] + t.v1 - t.v2);
else dp[cur][r] = max(dp[cur][r], dp[pre][i] + t.v1 - pow((t.r - t.l) / 2.0, 2.0) + pow((i - t.l) / 2.0, 2.0));
dp[cur][i] = max(dp[cur][i], dp[pre][i]);
ans = max(ans, dp[cur][i]);
}
}
printf("Case #%d: %.2lf\n", ++casid, ans);
}
return 0;
}

Hihocoder 1158 质数相关

题目链接:http://hihocoder.com/problemset/problem/1158

二分匹配求最大独立集。
可证:如果(a,b)质数相关,(b,c)质数相关,则(a,c)质数无关

因此没有奇数环,可划分为二分图。
求出二分匹配,最大独立集 = n - 最大匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <iostream>
using namespace std;
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,r) for(int i=0; i<(r); ++i)
#define DWN(i,r,l) for(int i=(r);i>=(l);--i)
#define pb push_back
const int N = 500010;
bool is_prime[510000], flag[510000];
void init() {
memset(is_prime, 1, sizeof(is_prime));
memset(flag, 0, sizeof(flag));
vector<int>prime;
FOR(i, 2, N) { //素数筛
if(!is_prime[i]) continue;
prime.pb(i);
for(int j = i + i; j <= N; j += i) is_prime[j] = 0;
}
FOR(i, 1, N) //给每个点染色,因为没有奇数环,所以必然染成或黑或白的一种
for(int x: prime) {
if(i > N / x) break;
flag[i * x] = flag[i] ^ 1;
}
}
struct Max_Match { //匈牙利匹配
vector<int>head[1100];
int match_x[1100], match_y[1100];
bool visit[1100];
void add(int x, int y) { head[x].pb(y); }
bool find_path(int cur) {
for(int to: head[cur])
if(!visit[to]) {
visit[to] = 1;
if(match_y[to] == -1 || find_path( match_y[to] )) {
match_x[cur] = to;
match_y[to] = cur;
return 1;
}
}
return 0;
}
int solve(int n, vector<int>&vec) {
memset(match_x, -1, sizeof(match_x));
memset(match_y, -1, sizeof(match_y));
int ret = 0;
REP(i, n) {
if(flag[ vec[i] ] != 0) continue;
memset(visit, 0, sizeof(visit));
ret += find_path(i);
}
return ret;
}
};
int main() {
init();
int casnum, casid = 0, n;
cin >> casnum;
while(casnum --) {
cin >> n;
vector<int>vec(n);
REP(i, n) scanf("%d", &vec[i]);
sort(vec.begin(), vec.end());
Max_Match match;
REP(i, n) //建立二分图
REP(j, i)
if(vec[i] % vec[j] == 0 && is_prime[ vec[i] / vec[j] ]) {
if(flag[ vec[i] ] < flag[ vec[j] ]) match.add(i, j);
else match.add(j, i);
}
printf("Case #%d: %d\n", ++casid, n - match.solve(n, vec));
}
return 0;
}