https://atcoder.jp/contests/abc173/tasks
E - Multiplication 4
题意：给定n个数，要选k个数，乘积最大。
很典型的贪心了。
只有在非负数没有选择空间时最终结果才可能是负数。在这种情况下直接选绝对值最小的负数即可。
其它情况下结果都是非负数。先选择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
84
85
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, k;
int cp, cn;
typedef pair<ll, int>pii;
vector<pii>vc, vv;
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
ll x;
scanf("%lld", &x);
if (x < 0)vc.push_back(pii(-x, 1)), cn++;
else vc.push_back(pii(x, 0)), cp++;
}
if (k == n && (k & 1) != (cp & 1) || cp == 0 && (k & 1)) {
ll ans = 1ll;
sort(vc.begin(), vc.end());
for (int i = 0; i < k; i++)ans = ans * vc[i].first % mod;
ans = (mod - ans) % mod;
printf("%lld\n", ans);
}
else {
ll ans = 1ll;
int cnt = 0;
sort(vc.begin(), vc.end(), greater<pii>());
for (int i = 0; i < k; i++) {
vv.push_back(vc[i]);
cnt += vc[i].second;
}
if (cnt & 1) {
ll tmp1 = vv.back().first, tmp2;
int p1 = -1, p2 = -1, q = -1;
int t = vv.back().second;
for (int i = (int)vv.size() - 2; i >= 0; i--) {
if (vv[i].second != t) {
tmp2 = vv[i].first;
q = i;
break;
}
}
if (q == -1) {
for (int i = k; i < (int)vc.size(); i++) {
if (vc[i].second != t) {
vv.pop_back();
vv.push_back(vc[i]);
break;
}
}
}
else {
for (int i = k; i < (int)vc.size() && (p1 == -1 || p2 == -1); i++) {
if (vc[i].second != t) {
if (p1 == -1) {
p1 = i;
tmp2 *= vc[i].first;
}
}
else {
if (p2 == -1) {
p2 = i;
tmp1 *= vc[i].first;
}
}
}
if (p2 == -1 || p1 != -1 && tmp1 < tmp2) {
vv.pop_back();
vv.push_back(vc[p1]);
}
else {
vv.erase(vv.begin() + q);
vv.push_back(vc[p2]);
}
}
}
for (pii p : vv)ans = ans * p.first%mod;
printf("%lld\n", ans);
}
return 0;
}
|
F - Intervals on Tree
题意：给定一棵树，f(L,R) 为由下标在区间 [L,R] 中的节点导出的子图的联通块个数，求所有区间的值之和。
dp
设 dp[i] 表示以 i 为右端点的所有区间的值之和。
每次加入一个节点，该结点连出的边可能减少联通块个数，所以要看在上一点的基础上增加了多少，减少了多少。
由于与 i-1 比较，所以限制连边只由大节点连向小节点。
设 u 连向的最大的节点为 v，则当区间左端点大于 v 时，u 都单独作为一个联通块，所以共增加了 u-v 个联通块。
u 连出的第一条边并不会使减少联通块个数，从第 2 条边起，连向点 vi，则必定减少了一个联通块，且对于所有包含 vi，即左端点小于等于 vi，右端点为 u 的区间来说，都少了一个联通块，所以共少了 vi 个联通块。
由于通过 u 连接的两个联通块之前必定不会联通（否则有环），所以这是正确的。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n;
vector<int>G[N];
ll dp[N], ans;
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[max(u, v)].push_back(min(u, v));
}
ans = dp[1] = 1ll;
for (int i = 2; i <= n; i++) {
sort(G[i].begin(), G[i].end(), greater<int>());
int mx = 0;
if (!G[i].empty())mx = G[i][0];
dp[i] = i - mx + dp[i - 1];
for (int j = 1; j < (int)G[i].size(); j++) {
int v = G[i][j];
dp[i] -= v;
}
ans += dp[i];
}
printf("%lld\n", ans);
return 0;
}
|
