Atcoder Regular Contest 059 题解

ARC059C. Be Together

签到题。枚举要改成哪个，因为值域只有 \([-100,100]\)。然后对总代价取个 \(\min\) 即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 105;
LL n, A[MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(LL i = 1; i <= n; i ++) cin >> A[i];
	LL ans = 1e18;
	for(LL i = -100; i <= 100; i ++)
	{
		LL anss = 0;
		for(LL j = 1; j <= n; j ++)
			anss += (A[j] - i) * (A[j] - i);
		ans = min(ans, anss);
	}
	cout << ans << '\n';
	return 0;
}

ARC059D. Unbalanced

小清新结论题，考虑怎样构造这个串。其重要条件就是两个相同的字母的位置的绝对值相差为 \(1\) 或 \(2\)，然后判一下就做完了。思维难度主要在这个结论。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	for(int i = 1; i < (int)s.length(); i ++)
	{
		if(i >= 2) 
		{
			if(s[i] == s[i - 2])
			{
				cout << i - 1 << " " << i + 1 << '\n';
				return 0;
			}
		}
		if(s[i] == s[i - 1])
		{
			cout << i << " " << i + 1 << '\n';
			return 0;
		}
	}
	cout << -1 << " " << -1 << '\n';
	return 0;
}

ARC059E. Children and Candies

算贡献的题，又看起来是一个背包。所以我们考虑在背包的基础上做一做手脚。

定义 \(f_{i,j}\) 为考虑到第 \(i\) 个，选了 \(j\) 个糖果的价值总和。由于乘法具有分配率，所以

答案就是 \(f_{n,c}\)，这样是 \(O(n^3)\) 的。然后注意到那个和式可以 \(O(n^2)\) 与处理掉做前缀和优化，于是总体复杂度降为 \(O(n^2)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 405;
const LL MOD = 1e9 + 7;
LL n, c, A[MAXN], B[MAXN], Pw[MAXN][MAXN], SumPw[MAXN][MAXN], DP[MAXN][MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> c;
	for(LL i = 1; i <= n; i ++) cin >> A[i];
	for(LL i = 1; i <= n; i ++) cin >> B[i];
	for(LL i = 1; i < MAXN; i ++)
	{
		Pw[i][0] = 1ll;
		for(LL j = 1; j < MAXN; j ++)
			Pw[i][j] = (Pw[i][j - 1] * i) % MOD;
	}
	for(LL i = 1; i < MAXN; i ++)
		for(LL j = 0; j < MAXN; j ++)
			SumPw[i][j] = (SumPw[i - 1][j] + Pw[i][j]) % MOD;
	DP[0][0] = 1;
	for(LL i = 1; i <= n; i ++)
		for(LL j = 0; j <= c; j ++)
			for(LL k = 0; k <= j; k ++)
				DP[i][j] = (DP[i][j] + (DP[i - 1][j - k] * (SumPw[B[i]][k] - SumPw[A[i] - 1][k] + MOD)) % MOD) % MOD;
	cout << DP[n][c] << '\n';
	return 0;
}