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;
}