AtCoder Regular Contest 059

Educational DP Round（确信

C - Be Together

给定 \(n\) 个数 \(a_{1}\sim a_n\)，你至多可以对每个 \(a_i\) 操作一次，以 \((a_i-y)^2\) 的代价令 \(a_i\gets y\)，求 \(a\) 全相等的最小代价。

\(1\le n\le 100,-100 \le a_i\le 100\)

直接枚举 \(y\) 即可。

// Problem: C - Be Together
// Contest: AtCoder - AtCoder Regular Contest 059
// URL: https://atcoder.jp/contests/arc059/tasks/arc059_a
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 1e3 + 5;
int n,a[maxn];

int main() {
	int ans = 1e9,cnt = 0;
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i) {
		scanf("%d",&a[i]);
	}
	for(int k = -100;k <= 100;++ k) {
		cnt = 0;
		for(int i = 1;i <= n;++ i)
			cnt += (a[i] - k) * (a[i] - k);
		ans = std::min(ans , cnt);
	}
	printf("%d",ans);
	return 0;
}

D - Unbalanced

如果一个字符串 \(s\) 长度 \(\ge 2\) 且存在一个字符出现了「超过」一半次，那么称 \(s\) 是「不平衡」的。

给定一个字符串 \(s\)，询问其是否存在一个子串 \(t\) 使得 \(t\) 是「不平衡」的。

\(1\le |s|\le 10^5\)

显然，如果有相邻的两个相同字符，直接输出即可。

否则，如果任意两相同字符不相邻，唯一有可能的是 abababab 这样的形式，那么再判断一下长度为 3 的子串即可。

时间复杂度 \(\mathcal O(|s|)\)

Code

// Problem: D - Unbalanced
// Contest: AtCoder - AtCoder Regular Contest 059
// URL: https://atcoder.jp/contests/arc059/tasks/arc059_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;
char s[maxn];

int main() {
	scanf("%s",s + 1);
	int n = strlen(s + 1);
	for(int i = 1;i < n;++ i) {
		if(s[i] == s[i + 1]) {
			printf("%d %d\n",i,i + 1);
			return 0;
		}
	}
	for(int i = 1;i <= n - 2;++ i) {
		if(s[i] == s[i + 2]) {
			printf("%d %d\n",i,i + 2);
			return 0;
		}
	}
	puts("-1 -1");
	return 0;
}

E - Children and Candies

注：我对题面作了形式化处理，可能不太好理解，可以去看洛谷的原始翻译。

给定 \(n,m,a_{1\sim n},b_{1\sim n}\)。

定义序列 \(c_{1\sim n}\)，使得 \(\forall i\in [1,n],c_i\in [0,m]\) 且 \(\sum\limits_{i=1}^n c_i=m\)

定义函数 \(f(x_1,x_2,\dots,x_n)=\sum\limits_{c}\prod\limits_{i=1}^n x_i^{c_i}\)

求 \(\sum\limits_{x_1=a_1}^{b_1}\sum\limits_{x_2=a_2}^{b_2}\dots \sum\limits_{x_n=a_n}^{b_n}f(x_1,x_2,\dots,x_n)\)

\(1\le n,m\le 400,1\le a_i\le b_i\le 400\)

题面很吓人，但其实非常简单。

设 \(dp(i,j)\) 表示前 \(i\) 个数中 \(\sum_{k=1}^i c_k=j\) 的答案。

显然有 \(dp(i,j)=\sum\limits_{k=0}^j (dp(i-1,j-k)\times (\sum\limits_{x=a_i}^{b_i}x^k))\)

因为后面那串式子和 \(j\) 一点关系也没有，直接预处理出来即可。

时间复杂度 \(\mathcal O(n^3)\)

Code

// Problem: E - Children and Candies
// Contest: AtCoder - AtCoder Regular Contest 059
// URL: https://atcoder.jp/contests/arc059/tasks/arc059_c
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
typedef long long i64;

const i64 mod = 1e9 + 7;
const int maxn = 405;
int n,m,a[maxn],b[maxn];

i64 power(i64 x,i64 y) {
	i64 ans = 1;
	for(;y;y >>= 1) {
		if(y & 1)(ans *= x) %= mod;
		(x *= x) %= mod;
	}
	return ans;
}

i64 dp[maxn][maxn],sum[maxn][maxn];

int main() {
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&a[i]);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&b[i]);
	
	for(int k = 0;k <= m;++ k) {
		for(int i = 1;i <= n;++ i) {
			for(int j = a[i];j <= b[i];++ j)
				(sum[i][k] += power(j , k)) %= mod;
		}
	}
	
	dp[0][0] = 1;
	for(int i = 1;i <= n;++ i) {
		for(int j = 0;j <= m;++ j) {
			for(int k = 0;k <= j;++ k) {
				(dp[i][j] += dp[i - 1][j - k] * sum[i][k] % mod) %= mod;
			}
		}
	}
	
	printf("%lld\n",dp[n][m]);
	return 0;
}

F - Unhappy Hacking

小 z 得到了一个键盘，里面只有 1,0 和退格键

键 0 可以打出一个 0 的字符串，键 1 同理

退格键可以删除前面打出的那个字符

小 z 可以操作这个键盘 \(n\) 次 ，求操作完成后打出来的字符串恰好是 \(s\) 的方案数

注意：当前没有字符也可以使用退格键

\(1\le |s|\le n\le 5000\)

很明显，又是 DP。

设 \(dp(i,j)\) 表示操作第 \(i\) 次，目前已有 \(j\) 个字符匹配的方案数。

两种操作：

• 数字键：因为要匹配这一位字符，方案只有一种，即为 \(dp(i-1,j-1)\)

• 退格键：显然，退去的这一位是啥不重要，之前 \(dp(i-1,j+1)\) 中存储的是 \(j+1\) 这一位可以匹配上的方案数，但现在我们不用管它是什么了，所以方案数为 \(dp(i-1,j+1)\times 2\)

综上，\(dp(i,j)=dp(i-1,\max(j-1,0))+dp(i-1,j+1)\times 2\)

时间复杂度 \(\mathcal O(n^2)\)

Code

// Problem: AT_arc059_d [ARC059F] バイナリハック
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc059_d
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int mod = 1e9 + 7;
const int maxn = 5e3 + 5;

int n,dp[maxn][maxn];
char s[maxn];

int main() {
	scanf("%d %s",&n,s + 1);
	int m = strlen(s + 1);
	dp[0][0] = 1;
	for(int i = 1;i <= n;++ i) {
		for(int j = 0;j <= i;++ j) {
			dp[i][j] = (dp[i - 1][std::max(j - 1 , 0)] + 2 * dp[i - 1][j + 1] % mod) % mod;
		}
	}
	printf("%d",dp[n][m]);
	return 0;
}