http://codeforces.com/contest/1436
D. Bandit in a City
题意：给定一棵有根树，以1为根。每个点有一些人，这些人最终都走到叶子，要使得包含人最多的叶子上包含的人数最少。
这就是要求均分，且每个点只能向子孙分配。
树上的均分可以从下向上遍历，同时求均值，这样就能保证那些本来就很多，而又没法向其它点分配的点均值不会变小。
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout<<#x<<":\t"<<x
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n;
vector<int>G[N];
ll a[N],sum[N],cnt[N];
ll ans;
void dfs(int u){
sum[u]=a[u];
if(G[u].empty()){
cnt[u]=1;
}
for(int v:G[u]){
dfs(v);
sum[u]+=sum[v];
cnt[u]+=cnt[v];
}
ans=max(ans,(sum[u]+cnt[u]-1)/cnt[u]);
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
int p;
scanf("%d",&p);
G[p].push_back(i);
}
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
dfs(1);
printf("%lld\n",ans);
return 0;
}
|
E. Complicated Computations
题意：给定一个 n 个元素的数列A，1≤ai≤n，把所有非空连续子数组的MEX值放入一个集合，求这个集合的MEX值。
线段树
易知最终MEX只会在1到 n+2，所以从小到大枚举，第一个满足没有出现在集合里的数就是答案。
也就是要确定是否有非空连续子数组的MEX值为 x。
遍历 A 数组，ai 前一次出现的位置为 lasti，则 (lasti,i) 这一段中不含有 ai，则只要这一段中包含 [1,ai−1] 中的所有数，这段就以 ai 为MEX。
线段树维护每个数最后一次出现的位置，只要都大于 lasti，则都出现了。
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
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
int a[N], c1;
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int mn[N << 2];
void up(int rt) {
mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
}
int qry(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r)return mn[rt];
int ans = INF;
if (ql <= mid)ans = min(ans, qry(ql, qr, lson));
if (qr > mid)ans = min(ans, qry(ql, qr, rson));
return ans;
}
void upd(int q, int x, int l, int r, int rt) {
if (l == r) {
mn[rt] = x;
return;
}
if (q <= mid)upd(q, x, lson);
else upd(q, x, rson);
up(rt);
}
int gg[N];
int last[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]), c1 += (a[i] == 1);
if (c1 == n) {
puts("1");
return 0;
}
gg[1] = 1;
for (int i = 1; i <= n; i++) {
if (a[i] != 1) {
int x = qry(1, a[i] - 1, 1, n, 1);
if (x > last[a[i]]) {
gg[a[i]] = 1;
}
}
last[a[i]] = i;
upd(a[i], i, 1, n, 1);
}
for (int i = 2; i <= n + 1; i++) {
if (qry(1, i - 1, 1, n, 1) > last[i])gg[i] = 1;
}
for (int i = 1; i <= n + 2; i++)if (!gg[i]) {
printf("%d\n", i);
return 0;
}
return 0;
}
|
