E. Sleep in Class
给定一个仅包含U与D的字符串，现在加上在第\(i\)个字符的位置上，遇到U则把该字符改成D并向右走，遇到D则把该字符改成U并向左走，重复此步骤，每步花费1秒，直到离开此字符串，问最终经过了多长时间。
手玩之后即可发现规律，规律很简单，不细说。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 5;
int cntd[maxn], cntu[maxn];
int rcntd[maxn], rcntu[maxn];
long long sumd[maxn], sumu[maxn];
char s[maxn];
int n;
int main()
{
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++)
{
sumd[i] = sumd[i - 1] + (s[i] == 'D' ? i : 0);
cntd[i] = cntd[i - 1] + (s[i] == 'D' ? 1 : 0);
sumu[i] = sumu[i - 1] + (s[i] == 'U' ? i : 0);
cntu[i] = cntu[i - 1] + (s[i] == 'U' ? 1 : 0);
}
for (int i = 1; i <= n; i++)
{
if (s[i] == 'D') rcntd[cntd[i]] = i;
else rcntu[cntu[i]] = i;
}
for (int i = 1; i <= n; i++)
{
if (i > 1) putchar(' ');
if (s[i] == 'D')
{
int cul = cntu[i];
int cdr = cntd[n] - cntd[i];
if (cul <= cdr) // fall from left
{
int findd = cntd[i] + cul;
int pos = rcntd[findd];
long long ans1 = sumd[pos] - sumd[i] - ((long long)i) * cul;
ans1 = ans1 * 2 - cul;
long long ans2 = ((long long)i) * cul - sumu[i];
ans2 = ans2 * 2 - cul;
printf("%lld", ans1 + ans2 + cul * 2 + i);
} else // fall from right
{
int findu = cntu[i] - cdr;
int pos = rcntu[findu];
long long ans1 = sumd[n] - sumd[i] - ((long long)i) * cdr;
ans1 = ans1 * 2 - cdr;
long long ans2 = ((long long)i) * (cdr + 1) - (sumu[i] - sumu[pos - 1]);
ans2 = ans2 * 2 - cdr - 1;
printf("%lld", ans1 + ans2 + (cdr + 1) * 2 + n - i);
}
} else
{
int cul = cntu[i - 1];
int cdr = cntd[n] - cntd[i];
if (cul < cdr) // fall from left
{
int findd = cntd[i] + cul + 1;
int pos = rcntd[findd];
long long ans1 = sumd[pos] - sumd[i] - ((long long)i) * (cul + 1);
ans1 = ans1 * 2 - (cul + 1);
long long ans2 = ((long long) i) * (cul + 1) - sumu[i];
ans2 = ans2 * 2 - (cul);
printf("%lld", ans1 + ans2 + (cul + 1) * 2 - 1 + i);
} else // fall from right
{
int findu = cntu[i] - cdr;
int pos = rcntu[findu];
long long ans1 = sumd[n] - sumd[i] - ((long long)i) * cdr;
ans1 = ans1 * 2 - cdr;
long long ans2 = ((long long)i) * cdr - (sumu[i - 1] - sumu[pos - 1]);
ans2 = ans2 * 2 - cdr;
printf("%lld", ans1 + ans2 + cdr * 2 + n - i + 1);
}
}
}
return 0;
}
F. Drivers Dissatisfation
给定一个带权无向图，可以花费\(c_i\)的代价，将边\(i\)的边权减少1，操作可进行多次，同时边权可以为负，现在要求花费不超过\(s\)的代价，求最小生成树。
首先可以有一个结论，即最佳答案可以最多修改一条边的边权。这个证明很简单，即考虑我们有两条边，它们的边权分别为\(c_1, c_2\)，则，如果修改这两条边的边权可以使答案减少，则当\(c_1 \le c_2\)时，\(ac_1 + bc_2 \ge (a+b)c_1\)，即如果只修改一条边，答案不比修改两条边更劣。
因而，我们可以先生成一棵不修改边权的最小生成树，然后枚举这条边。接下来的问题就是求树上的某条链的最大值问题，树链剖分即可。
#include <bits/stdc++.h>
using namespace std;
namespace ejq{
const int maxn = 200000 + 5;
struct edge{
int u, v, w, c, id;
}edg[maxn];
typedef pair<int, int> pii;
vector<int> e[maxn];
int dep[maxn];
int fa[maxn], link[maxn], son[maxn], top[maxn], id[maxn], rev[maxn], index;
pii val[maxn];
void dfs1(int u, int fa)
{
dep[u] = dep[fa] + 1;
ejq::fa[u] = fa;
for (int v : e[u])
{
if (v == fa) continue;
dfs1(v, u);
if (link[v] + 1 > link[u])
{
link[u] = link[v] + 1;
son[u] = v;
}
}
}
void dfs2(int u, int fa)
{
id[u] = ++index;
rev[index] = u;
if (son[u])
{
top[son[u]] = top[u];
dfs2(son[u], u);
}
for (int v : e[u])
{
if (v == fa || v == son[u]) continue;
top[v] = v;
dfs2(v, u);
}
}
pii segt[maxn * 4];
#define ls(x) ((x) * 2)
#define rs(x) (ls(x) + 1)
pii query(int x, int l, int r, int ql, int qr)
{
if (l == ql && r == qr) return segt[x];
int mid = (l + r) / 2;
if (qr <= mid) return query(ls(x), l, mid, ql, qr);
else if (ql > mid) return query(rs(x), mid + 1, r, ql, qr);
else return max(query(ls(x), l, mid, ql, mid), query(rs(x), mid + 1, r, mid + 1, qr));
}
void build_segt(int x, int l, int r)
{
if (l == r)
{
segt[x] = val[rev[l]];
return;
}
int mid = (l + r) / 2;
build_segt(ls(x), l, mid);
build_segt(rs(x), mid + 1, r);
segt[x] = max(segt[ls(x)], segt[rs(x)]);
}
pii query(int u, int v)
{
int fu = top[u], fv = top[v];
pii ans = pii(-1, -1);
while (fu != fv)
{
if (dep[fu] < dep[fv])
{
swap(fu, fv);
swap(u, v);
}
ans = max(ans, query(1, 1, index, id[fu], id[u]));
u = fa[fu];
fu = top[u];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v)
ans = max(ans, query(1, 1, index, id[u] + 1, id[v]));
return ans;
}
typedef pair<int, int> pii;
int st[maxn];
set<int> res;
pii curans;
long long ans, rans;
int n, m, s;
int dsu_find(int u)
{
return (st[u] == u) ? u : (st[u] = dsu_find(st[u]));
}
void dsu_union(int u, int v)
{
st[dsu_find(u)] = dsu_find(v);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) st[i] = i;
for (int i = 0; i < m; i++) edg[i].id = i;
for (int i = 0; i < m; i++)
scanf("%d", &edg[i].w);
for (int i = 0; i < m; i++)
scanf("%d", &edg[i].c);
for (int i = 0; i < m; i++)
scanf("%d%d", &edg[i].u, &edg[i].v);
scanf("%d", &s);
sort(&edg[0], &edg[m],
[](const edge &a, const edge &b) {
return a.w < b.w;
});
for (int i = 0; i < m; i++)
{
if (dsu_find(edg[i].u) != dsu_find(edg[i].v))
{
dsu_union(edg[i].u, edg[i].v);
ans += edg[i].w;
e[edg[i].u].push_back(edg[i].v);
e[edg[i].v].push_back(edg[i].u);
res.insert(i);
}
}
dfs1(1, -1);
dfs2(1, -1);
memset(val, -1, sizeof val);
for (int i : res)
{
int u = edg[i].u;
int v = edg[i].v;
if (dep[u] > dep[v])
val[u] = pii(edg[i].w, i);
else
val[v] = pii(edg[i].w, i);
}
build_segt(1, 1, index);
long long rans = ans;
for (int i = 0; i < m; i++)
{
pii tans = query(edg[i].u, edg[i].v);
long long newedg = edg[i].w - s / edg[i].c;
if (ans - tans.first + newedg < rans)
{
rans = ans - tans.first + newedg;
curans = pii(tans.second, i);
}
}
printf("%lld\n", rans);
for (int r : res)
{
// cerr << r << endl;
if (r == curans.first)
printf("%d %d\n", edg[curans.second].id + 1, edg[curans.second].w - s / edg[curans.second].c);
else
printf("%d %d\n", edg[r].id + 1, edg[r].w);
}
return 0;
}
}
int main()
{
return ejq::main();
}