codeforces 168 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.有n个数字,选出一些数字,使得这些数字之间,两两不满足 y=x * k;选最多的数字

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
/*
分系列的思想,取一个最小的数字,x,然后x,kx,kkx,kkkx是一个系列的
(x,kx)是一个系列,kkkx,已经和之前的断开了,因为不连续
不同系列间不影响,只需要单调处理一个系列
用dp
对于一个系列,若不取当前这个数字,前面的数字可以取可以不取,看哪种更优;若取当前数字,则前一个数字一定不能取
*/
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define LL long long
#define LIM 1000000000LL
#define MAXN 100010
#define pb push_back
#define mp make_pair
#define pii pair<int,int>

map<int,int>mi;
vector<pii>number;
int a[MAXN],n,m;
bool vis[MAXN];
int dp[MAXN][2];

int work(int id) {
int length = 0;
dp[0][0] = 0;
dp[0][1] = number[id].second;
while (true) {
vis[id] = true;
LL temp = (LL)number[id].first * (LL)m;
if (temp > LIM || mi.find((int)temp) == mi.end()) break;
int pos = mi[(int)temp] - 1;
length++;
dp[length][0] = max(dp[length-1][0], dp[length-1][1]);
dp[length][1] = number[pos].second + dp[length-1][0];
id = pos;
}
return max(dp[length][0], dp[length][1]);
}

int solve() {
int ans = 0,numsize = number.size();
memset(vis,false,sizeof(vis));
for (int i = 0; i < numsize; i++) {
if (vis[i]) continue;
ans += work(i);
}
return ans;
}

void init() {
number.clear();
mi.clear();
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
sort(a,a+n);
int cnt = 1;
for (int i = 1; i < n; i++) {
if (a[i] == a[i-1]) cnt++;
else {
number.pb(mp(a[i-1],cnt));
cnt = 1;
}
}
number.pb(mp(a[n-1],cnt));
int numsize = number.size();
for (int i = 0; i < numsize; i++)
mi[number[i].first] = i+1;
}

int main() {
int x;
while (scanf("%d%d", &n, &m) != EOF) {
init();
if (m == 1) printf("%d\n",number.size());
else printf("%d\n",solve());
}
return 0;
}

B.一棵树,每个节点有个初始权值;每次选取一个子树(该子树必须包含1节点),将这个子树上的点全部+1,或全部-1,最终使得整个树每个节点的权值均为0,使得操作次数最少

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
/*
树dp:对于每个节点,看它所有分支里面,最多加了几次,最多减了几次,那么它就要加几次,减几次;
最后就是看1节点,加了几次,减了几次
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
#define INF 10000000000000000LL
#define MAXN 100010
#define pii pair<int,int>
#define LL long long
#define pb push_back
#define mp make_pair

int n;
vector<int>e[MAXN];
LL val[MAXN],add[MAXN],sub[MAXN];
bool vis[MAXN];

void dfs(int u) {
vis[u] = true;
int size = e[u].size();
for (int i = 0; i < size; i++) {
int v = e[u][i];
if (vis[v]) continue;
dfs(v);
add[u] = max(add[u], add[v]);
sub[u] = max(sub[u], sub[v]);
}
val[u] += add[u] - sub[u];
if (val[u] >= 0) sub[u] += val[u];
else add[u] += -val[u];
}

LL solve() {
memset(vis,false,sizeof(vis));
memset(add,0,sizeof(add));
memset(sub,0,sizeof(sub));
dfs(1);
return add[1]+sub[1];
}

int main() {
while (scanf("%d",&n) != EOF) {
for (int i = 0; i <= n; i++) e[i].clear();
for (int i = 1; i < n; i++) {
int u,v;
scanf("%d%d", &u, &v);
e[u].pb(v), e[v].pb(u);
}
for (int i = 1; i <= n; i++) cin >> val[i];
cout << solve() << endl;
}
return 0;
}