Codeforces Round #621 (Div. 1 + Div. 2) 题解

Codeforces Round #621 (Div. 1 + Div. 2)

Cow and Haybales

贪心。

const int N = 107;
int n, d, a[N];

inline void solve() {
	rd(n), rd(d);
	for (int i = 1; i <= n; i++) rd(a[i]);
	for (int i = 2; i <= n; i++) {
		int now = min(d, a[i] * (i - 1));
		a[1] += now / (i - 1), d -= now;
	}
	print(a[1]);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Cow and Friend

贪心。

const int N = 1e5 + 7;
int n, d, a[N], x;

inline void solve() {
	rd(n), rd(d);
	for (int i = 1; i <= n; i++) rd(a[i]);
	sort(a + 1, a + n + 1);
	x = upper_bound(a + 1, a + n + 1, d) - a - 1;
	if (!x) print(2);
	else if (x == n) print((d - 1) / a[x] + 1);
	else print(min(2, (d - 1) / a[x] + 1));
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Cow and Message

前缀和，组合计数。

const int N = 1e5 + 7;
int n, c[26];
char s[N];
ll ans, f[26][26];

int main() {
	rds(s, n);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 26; j++)
			f[j][s[i]-'a'] += c[j];
		++c[s[i]-'a'];
	}
	ans = *max_element(c, c + 26);
	for (int j = 0; j < 26; j++)
		for (int k = 0; k < 26; k++)
			ans = max(ans, f[j][k]);
	print(ans);
	return 0;
}

Cow and Fields

求出每个点与 $1$ 到 $n$ 的最短路，一条新的路只可能从离 $n$ 更远的点连向离 $n$ 更近的点，贪心即可。

const int N = 2e5 + 7, inf = 1e9;
int n, m, k, a[N], ds[N], dt[N], v[N], ans;
vi e[N];

inline void dij(int s, int *d) {
	for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
	pq<pi> q;
	d[s] = 0, q.push(mp(0, s));
	while (q.size()) {
		int x = q.top().se;
		q.pop();
		if (v[x]) continue;
		v[x] = 1;
		for (int y : e[x])
			if (d[y] > d[x] + 1)
				d[y] = d[x] + 1, q.push(mp(-d[y], y));
	}
}

int main() {
	rd(n), rd(m), rd(k);
	for (int i = 1; i <= k; i++) rd(a[i]);
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	dij(1, ds), dij(n, dt);
	sort(a + 1, a + k + 1, [&](int i, int j) { return dt[i] < dt[j]; });
	for (int i = 1; i < k; i++)
		ans = max(ans, ds[a[i+1]] + 1 + dt[a[i]]);
	print(min(ans, ds[n]));
	return 0;
}

Cow and Treats

垃圾题。

Cow and Vacation

题目太神仙了，先咕咕咕着。

Cow and Exercise

题目太神仙了，先咕咕咕着。