Codeforces Round 378 Div.2

Posted on By 二价氢

E. Sleep in Class

给定一个仅包含UD的字符串,现在加上在第个字符的位置上,遇到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

给定一个带权无向图,可以花费的代价,将边的边权减少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();
}