练习
A - Ambiguous Datas
题意
定义一年\(M\)个月,每个月\(Di\)天,现在日期有两种表达方式dd/mm/year 和 mm/dd/year, 这样会产生歧义,例如, 1/2/12就是歧义的,
而1/13/12不是歧义的。现在给 \(M\) 和 \(D_1, D_2, D_3...D_m\),问如何排列D, 可以使歧义天数最少。
分析
对于第i月,他产生歧义的天数范围是 1 - min(D_i, M), 对于这个区间,容易想到,要求出该区间内的大于i的个数,因为i与j歧义,首先满足\(1 \leq j \leq M 且 D_j \geq i\), 所以要尽可能的减少区间的贡献,考虑将序列升序排列,一定更优。
做法:sort + 找区间贡献(二分找大于i的最小的)
细节:注意要刨去\(D_i \geq i\)
const int N = 100010;
ll d[N], n, m;
ll ans;
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> d[i], m = max(m, d[i]);
sort(d + 1, d + n + 1);
for (int i = 1; i <= n; i++) {
int l = 0, r = min(n, d[i]) + 1;
while (l < r) {
int mid = (l + r) / 2;
if (d[mid] >= i) r = mid;
else l = mid + 1;
}
ans += (min(n, d[i]) - l + 1) - (d[i] >= i);
}
cout << ans << '\n';
}
B - Bacteria Experiment
题意
给一棵树,每过一个小时,u和v会连一条边,当存在点e,满足E(u, e), E(v, e)存在(即u-e, v-e直接相连,u,v没有边相连)。问这棵树经过几个小时,这个树会变成一个完全图。
分析
每次操作都是同时进行,所以我们只需要考虑最长的链,即找到树的直径,当这条直径完全两两相连时,树上的其他链均完成了这个过程。并且我们考虑一条长度为m的树链,可以发现,每过一个小时,路径长度变为原来的1/2,故,我们的答案为(\(2^{ans} >= dist\))最小的ans。
const int N = 500010;
int n, cnt;
VI e[N];
bool st[N];
PII bfs(int start) {
PII ans = {0, 0};
queue<PII> q;
q.push({0, start});
memset(st, 0, sizeof st);
while (!q.empty()) {
auto [d, u] = q.front(); q.pop();
if (st[u]) continue;
st[u] = 1;
for (auto v : e[u]) {
if (!st[v]) {
q.push({d + 1, v});
if (d + 1 > ans.fi) ans = {d + 1, v};
}
}
}
return ans;
}
void solve() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].pb(v);
e[v].pb(u);
}
auto a = bfs(1);
auto b = bfs(a.se);
int d = b.fi;
int ans = 0;
while ((1 << ans) < d) ans++;
cout << ans << '\n';
}
E - Inverted Signs
题意
给定一个整数序列a, 要求值 \(H = \sum_{i=2}^{N}(|a[i]-a[i-1]|)\),现在可以进行一次操作,选择一个区间[L, R],进行翻转,要求翻转后使H的值最小,问最小的H。
分析
[L, R]区间内部的差值不会变,变得只是a[L] - a[L-1]和a[R+1] - a[R],所以做法很简单,就是对于i,求出i翻转后的对答案的贡献,并且维护最小的和次小的贡献即可。
注意: 因为可以翻转整个序列,所以求出贡献要对0取min。
const int N = 1000010;
int a[N], n;
ll ans;
void solve() {
cin >> n;
PII mx = {1e9, 0}, mx2 = {0, 0};
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i > 1) {
int x = abs(a[i] - a[i - 1]);
int y = abs(-a[i] - a[i - 1]);
ans += x;
if (y - x < mx.fi) {
mx2 = mx;
mx = {y - x, i};
} else if (y - x < mx2.fi) {
mx2 = {y - x, i};
}
}
}
if (n == 1) ans = 0, mx = {0, 0};
cout << ans + min(0, mx.fi) + min(0, mx2.fi) << '\n';
}
标签:Salle,Pui,La,int,auto,st,ans,mx,歧义
From: https://www.cnblogs.com/rufu/p/17046762.html