题解 | 浙江机电职业技术大学第九届程序设计竞赛

题解

A.阿兔与拼好饭（贪心）

只要人数达到三人，我们就可以两两成对获得三份餐，另外一人只需发起拼单即可满足配送要求。

时间复杂度：

B.阿兔与转经筒（前缀和、二分）

根据题意，易得下面两个计算公式：

1. 当前数字小于等于转经的次数，则贡献为：
2. 当前数字大于转经的次数，则贡献为：

经过观察，排序并不改变功德值计算，因为每个数字都可以独立计算的。我们可以先对原始数组从小到大进行排序，然后根据当前的转经的次数二分找到数组的下标，使得下标左侧（包含）均为①式，下标右侧均为②式。

前者我们可以使用前缀和预处理①式即可 计算，后者我们需要推出下面公式。

预处理后缀和，我们即可 计算后者。

时间复杂度：

C.阿兔与璀璨宝石（贪心、排序）

根据题意，我们可以转化思路。若购买卡牌的其中一种颜色的宝石数量足够，则计数 ，若计数达到 ，则直接完成购买。

那么我们可以开三个数组和全局指针，分别对红宝石、绿宝石、蓝宝石的购买数量从小到大进行排序。当卡牌发生购买时，对于每一个数组，我们从上一次遍历的位置开始右移即可遍历，若宝石数量足够则计数 ，若计数达到 ，则可以直接购买。

时间复杂度：

D.阿兔与战局（根堆）

这题的题意是动态中位数维护，我们可以开小根堆和大根堆来维护中位数，中位数位于小根堆顶 ，并且分别记录小根堆和大根堆内数的个数为 、 ，数值的总和为 、 ，那么每次查询的结果为：

时间复杂度：​

E.阿兔与兔子洞（树上差分）

很明显，对于树上两点之间的简单路径，他们必然经过 。所以用树上差分维护经过次数即可，最后再暴力模拟修复使用寿命非1的过程，当使用寿命为 时，直接将剩余的经过次数加入答案中即可。

时间复杂度：​

F.阿兔与瑕疵回文串（哈希、二分）

可以明显看出，瑕疵回文串包含了普通回文串。

首先，我们可以预处理前缀哈希数组 和后缀哈希数组 ，然后结合二分法和前后缀字符串哈希，在 时间复杂度下求得每个下标作为中心时，最长回文串的区间 。

在求出回文串的基础上，我们进一步使用二分法来确定瑕疵字符的长度，使得在区间 处的哈希值与在区间 处的哈希值相等。

最终，答案可以表示为：

在二分过程中需要注意避免越界问题。

时间复杂度：

G.阿兔与兔崽子（贪心、排序）

如果阿兔开始攻击某一只兔崽子，那么阿兔肯定会一直攻击它直到它被制服。那么每只兔崽子的制服时间为：

接下来我们考虑比较相邻两只兔崽子 和 的交换贡献变化。交换对于 前面和 后面 的贡献都是一致，我们只考虑改变部分。

我们发现交换后贡献的变化为 ，那么我们在交换时使 即可降低贡献。所以排序规则为： 。我们排序后线性计算即可。

时间复杂度：

H.阿兔与兔儿子（线性DP）

我们考虑从前往后和从后往前进行线性DP，得到 为游玩前 个游乐设施，花费 元的最大快乐值； 为游玩后 个游乐设施，花费 元的最大快乐值。

那么对于兔儿子想要游玩的第 个游乐设施，当 时无解；反之我们可以枚举游玩前 个游乐设施的开销 进行计算答案：

时间复杂度：

I.阿兔与玫瑰树（换根DP）

换根DP板子题，用换根计算每个点到叶子节点的距离即可。

时间复杂度：

J.阿兔与种树（差分、前缀和）

若仅考虑区间 ，我们可以用差分记录，然后二次前缀和即可获得答案。

若有一段区间 ，经过观察我们可以发现 这一段每个位置的答案都多出 。我们考虑在第二次前缀和遍历到下标 时减去这个值即可。

时间复杂度：

K.阿兔与吉祥区间（倍增、双指针）

对于每一个右端点，我们可以使用毛毛虫算法批量处理一个最近的左端点，满足这一段正好为八个不同的数字，记录在 内。

对于一组查询 ，只要 即可对答案贡献 。若暴力枚举最坏复杂度为 ，用倍增优化即可。

时间复杂度：

L.阿兔与网页设计（贪心）

反向枚举字符串，当遇到 时 计数加一，反之 计数加一。

初始化答案为 ，当第二次及之后遇到 时，计算答案：

时间复杂度：

代码

A.阿兔与拼好饭（贪心）

void solve()
{
	int n;
	cin >> n;
    
	if (n < 3)
		cout << 0 << endl;
	else
		cout << (n / 2) * 3 << endl;
}

B.阿兔与转经筒（前缀和、二分）

const int maxn = 2e5 + 7;
int n, k, a[maxn], b[maxn], c[maxn], mod = 1e9 + 7;

int ksm(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b % 2)
			res = res * a % mod;
		b /= 2;
		a = a * a % mod;
	}
	return res;
}

void solve()
{
	int n, k;
	cin >> n >> k;

	int two = ksm(2, mod - 2);

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
	{
		b[i] = ((((a[i] + 1) * a[i] % mod) * two % mod) + b[i - 1]) % mod;
		c[i] = (a[i] + c[i - 1]) % mod;
	}

	for (int i = 1; i <= k; i++)
	{
		int x;
		cin >> x;
		int l = 0, r = n;
		while (l < r)
		{
			int mid = (l + r + 1) / 2;
			if (a[mid] <= x)
				l = mid;
			else
				r = mid - 1;
		}

		int tmp = ((((c[n] - c[l]) * 2 - (x - 1) * (n - l)) % mod) + mod) % mod;
		int ans = (b[l] + (tmp * x % mod) * two) % mod;
		cout << ans << endl;
	}
}

C.阿兔与璀璨宝石（贪心、排序）

const int N = 2e5 + 10, oo = 1e9 + 7;
int n, m, k;

struct card
{
	int id, r, g, b;
	char s;
	bool operator==(const card &o) const
	{
		return id == o.id;
	}
};

bool cmpr(card x, card y)
{
	return x.r < y.r;
}

bool cmpg(card x, card y)
{
	return x.g < y.g;
}

bool cmpb(card x, card y)
{
	return x.b < y.b;
}

card ra[N], ga[N], ba[N];
int r, g, b, ir, ig, ib;
int cnt[N];

void check()
{
	bool f = false;
	for (int i = ir; i <= n; i++)
	{
		int id = ra[i].id;
		char s = ra[i].s;
		if (ra[i].r <= r)
		{
			if (i == n)
				ir = n + 1;
			cnt[id]++;
		}
		else
		{
			ir = i;
			break;
		}
		if (cnt[id] == 3)
		{
			if (s == 'R')
				r++;
			else if (s == 'G')
				g++;
			else
				b++;
			f = true;
		}
	}
	// 已省略其余两个相同部分 //
	if (f)
		check();
}

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		card now;
		cin >> now.s >> now.r >> now.g >> now.b;
		now.id = i;
		ra[i] = now;
		ga[i] = now;
		ba[i] = now;
	}
    
	sort(ra + 1, ra + 1 + n, cmpr);
	sort(ga + 1, ga + 1 + n, cmpg);
	sort(ba + 1, ba + 1 + n, cmpb);
    
	r = g = b = 0;
	ir = ig = ib = 1;
    
	check();
    
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (cnt[i] == 3)
			ans++;
	cout << ans << endl;
}

D.阿兔与战局（根堆）

#define int long long
#define endl "\n"

const int maxn = 5e5 + 10;
int n, sum1, sum2, ans;
multiset<int> q1, q2;

void check()
{
	if (q1.size() > q2.size() + 1)
	{
		int val = *q1.begin();
		q1.erase(q1.begin()), sum1 += val;
		q2.insert(-val), sum2 -= val;
	}

	if (q1.size() < q2.size())
	{
		int val = *q2.begin();
		q2.erase(q2.begin()), sum2 -= val;
		q1.insert(-val), sum1 += val;
	}
}

void solve()
{
	cin >> n;
	sum1 = sum2 = ans = 0;
	while (n--)
	{
		string opt;
		int x;
		cin >> opt;
		if (opt[0] == 'a')
		{
			cin >> x;
			if (q1.empty() || x < -*q1.begin())
				q1.insert(-x), sum1 += x;
			else
				q2.insert(x), sum2 += x;
			check();
		}
		else if (opt[0] == 'r')
		{
			cin >> x;
			if (q1.find(-x) != q1.end())
				q1.erase(q1.find(-x)), sum1 -= x;
			else if (q2.find(x) != q2.end())
				q2.erase(q2.find(x)), sum2 -= x;
			check();
		}
		else
		{
             if (q1.empty()) cout << 0 << endl;
			else cout << (q1.size() * (-*q1.begin()) - sum1) + (sum2 - q2.size() * (-*q1.begin())) << endl;
		}
	}
}

E.阿兔与兔子洞（树上差分）

const int maxn = 2e5 + 7, maxm = 21;
int n, k, a[maxn], b[maxn];
struct node
{
	int x, y;
};
vector<node> edge[maxn];
int f[maxn][maxm + 1], d[maxn];

void dfs(int x, int z)
{
	f[x][0] = z;
	for (node y : edge[x])
	{
		if (y.x == z)
			continue;
		a[y.x] = y.y;
		d[y.x] = d[x] + 1;
		dfs(y.x, x);
	}
}

int lca(int x, int y)
{
	if (d[x] < d[y])
		swap(x, y);

	for (int i = maxm; i >= 0; i--)
		if (d[x] - (1 << i) >= d[y])
			x = f[x][i];

	if (x == y)
		return x;

	for (int i = maxm; i >= 0; i--)
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];

	return f[x][0];
}

void dfs2(int x, int z)
{
	for (node y : edge[x])
	{
		if (y.x == z)
			continue;
		dfs2(y.x, x);
		b[x] += b[y.x];
	}
}

void solve()
{
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		edge[x].push_back({y, z});
		edge[y].push_back({x, z});
	}
	dfs(1, 0);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= maxm; j++)
			f[i][j] = f[f[i][j - 1]][j - 1];

	for (int i = 1; i <= k; i++)
	{
		int x, y;
		cin >> x >> y;
		int z = lca(x, y);
		b[x]++, b[y]++, b[z] -= 2;
	}
	dfs2(1, 0);

	int ans = 0;
	for (int i = 2; i <= n; i++)
		while (b[i] >= a[i])
		{
			if (a[i] == 1)
			{
				ans += b[i];
				break;
			}
			b[i] -= a[i];
			a[i] = (a[i] + 1) / 2;
			ans++;
		}
	cout << ans << endl;
}

F.阿兔与瑕疵回文串（哈希、二分）

const int maxn = 2e5 + 7, p = 131;
int n;
string s;

unsigned int hs[maxn], sh[maxn], qy[maxn];
unsigned int get1(int l, int r)
{
	return hs[r] - hs[l - 1] * qy[r - l + 1];
}

unsigned int get2(int l, int r)
{
	return sh[l] - sh[r + 1] * qy[r - l + 1];
}

bool check(int l1, int r1, int l2, int r2)
{
	if (l2 <= 0 || r1 > n)
		return false;

	return get1(l1, r1) == get2(l2, r2);
}

void solve()
{
	cin >> n >> s;

	qy[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		qy[i] = qy[i - 1] * p;
		hs[i] = hs[i - 1] * p + s[i - 1] - 'a';
	}
	for (int i = n; i >= 1; i--)
		sh[i] = sh[i + 1] * p + s[i - 1] - 'a';

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int l = 0, r = n;
		while (l < r)
		{
			int mid = (l + r + 1) / 2;
			if (check(i, i + mid, i - mid, i))
				l = mid;
			else
				r = mid - 1;
		}

		int tmp = l;
		if (i + (tmp + 1) <= n && i - (tmp + 1) > 0)
			tmp++;

		l = 0, r = n;
		while (l < r)
		{
			int mid = (l + r + 1) / 2;
			if (check(i + tmp + 1, i + tmp + mid, i - tmp - mid, i - tmp - 1))
				l = mid;
			else
				r = mid - 1;
		}

		ans = max(ans, 1 + (tmp + l) * 2);
	}

	for (int i = 1; i < n; i++)
	{
		int l = 0, r = n;
		while (l < r)
		{
			int mid = (l + r + 1) / 2;
			if (check(i + 1, i + mid, i + 1 - mid, i))
				l = mid;
			else
				r = mid - 1;
		}
		int tmp = l;
		if (i + (tmp + 1) <= n && i + 1 - (tmp + 1) > 0)
			tmp++;

		l = 0, r = n;
		while (l < r)
		{
			int mid = (l + r + 1) / 2;
			if (check(i + tmp + 1, i + tmp + mid, i + 1 - tmp - mid, i - tmp))
				l = mid;
			else
				r = mid - 1;
		}

		ans = max(ans, (tmp + l) * 2);
	}

	cout << ans << endl;
}

G.阿兔与兔崽子（贪心、排序）

const int maxn = 2e5 + 7, mod = 1e9 + 7;
int n, k, q;
struct node
{
	int h, a;
	bool operator<(const node &o) const
	{
		return h * o.a < o.h * a;
	}
} ha[maxn];

void solve()
{
	cin >> n >> k;
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> ha[i].h >> ha[i].a;
		ha[i].h = (ha[i].h + k - 1) / k;
		sum = (sum + ha[i].a) % mod;
	}

	sort(ha + 1, ha + 1 + n);

	int now = 0, ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans = (ans + ha[i].h * sum) % mod;
		sum = (sum - ha[i].a + mod) % mod;
	}
	cout << ans << endl;
}

H.阿兔与兔儿子（线性DP）

const int maxn = 2e3 + 7;
int n, k, q, h[maxn], c[maxn];
int f[maxn][maxn], d[maxn][maxn];

void solve()
{
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++)
		cin >> h[i] >> c[i];

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
			f[i][j] = f[i - 1][j];
		for (int j = c[i]; j <= k; j++)
			f[i][j] = max(f[i][j], f[i - 1][j - c[i]] + h[i]);
	}

	for (int i = n; i >= 1; i--)
	{
		for (int j = 0; j <= k; j++)
			d[i][j] = d[i + 1][j];
		for (int j = c[i]; j <= k; j++)
			d[i][j] = max(d[i][j], d[i + 1][j - c[i]] + h[i]);
	}

	while (q--)
	{
		int x;
		cin >> x;
		if (c[x] > k)
		{
			cout << -1 << endl;
			continue;
		}

		int ans = h[x];
		for (int i = 0; i <= k - c[x]; i++)
			ans = max(ans, h[x] + f[x - 1][i] + d[x + 1][k - c[x] - i]);
		cout << ans << endl;
	}
}

I.阿兔与玫瑰树（换根DP）

const int maxn = 2e5 + 7;
int n, k;
vector<int> edge[maxn];

int siz[maxn], sum[maxn];
void dfs(int x, int z)
{
	siz[x] = (edge[x].size() == 1);
	sum[x] = 0;
	for (int y : edge[x])
	{
		if (y == z)
			continue;
		dfs(y, x);
		siz[x] += siz[y];
		sum[x] += sum[y] + siz[y];
	}
}

int dis[maxn];
void dfs2(int x, int z)
{
	if (x != 1)
		dis[x] = dis[z] + (siz[1] - siz[x]) - siz[x];
	else
		dis[x] = sum[x];

	for (int y : edge[x])
	{
		if (y == z)
			continue;
		dfs2(y, x);
	}
}

void solve()
{
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	dfs(1, 0);
	dfs2(1, 0);

	for (int i = 1; i <= k; i++)
	{
		int x;
		cin >> x;
		cout << dis[x] << endl;
	}
}

J.阿兔与种树（差分、前缀和）

const int maxn = 2e5 + 7;
int n, m, a[maxn], b[maxn];

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		a[l]++, a[r + 1]--, b[r + 1] -= r - l + 1;
	}

	for (int i = 1; i <= n; i++)
		a[i] += a[i - 1];

	for (int i = 1; i <= n; i++)
	{
		a[i] += a[i - 1] + b[i];
		cout << a[i] << " ";
	}
	cout << endl;
}

K.阿兔与吉祥区间（倍增、双指针）

const int maxn = 2e5 + 7, maxm = 22;
int n, q, a[maxn], f[maxn][maxm + 1];

void solve()
{
	cin >> n >> q;
	for (int i = 2; i <= n + 1; i++)
		cin >> a[i];

	int j = n + 1;
	unordered_map<int, int> st;
	for (int i = n + 1; i >= 2; i--)
	{
		while (j > 1 && st.size() < 8)
			st[a[j--]]++;

		if (j == 1 && st.size() < 8)
			break;

		f[i][0] = j;

		st[a[i]]--;
		if (st[a[i]] == 0)
			st.erase(a[i]);
	}

	for (int j = 1; j <= maxm; j++)
		for (int i = 0; i <= n + 1; i++)
			f[i][j] = f[f[i][j - 1]][j - 1];

	for (int i = 1; i <= q; i++)
	{
		int l, r, ans = 0;
		cin >> l >> r;

		l += 1, r += 1;
		for (int j = maxm; j >= 0; j--)
			if (l - 1 <= f[r][j])
				r = f[r][j], ans += 1 << j;
		cout << ans << endl;
	}
}

L.阿兔与网页设计（贪心）

int n;
string str;

void solve()
{
	cin >> n >> str;

	int x = 0, y = 0, ans = 2147483647;
	for (int i = str.size() - 1; i >= 0; i--)
		if (str[i] == '1')
		{
			if (++x > 1)
				ans = min(ans, y / (x - 1));
		}
		else
			++y;

	cout << ans << endl;
}