AtCoder Regular Contest 059

C - Be Together

直接枚举最终结果是谁就行了,C 语言题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 107

int n, a[N];

inline int sqr(int x) {return x * x;}

inline int calc(int x) {
int ans = 0;
for (int i = 1; i <= n; ++i)
ans += sqr(a[i] - x);
return ans;
}

int main() {
n = rd();
for (int i = 1; i <= n; ++i) a[i] = rd();
int ans = 2e9;
for (int w = -100; w <= 100; ++w) ans = min(ans, calc(w));
printf("%d\n", ans);
return 0;
}

D - Unbalanced

给定一个字符串,找一个不平衡子串,子串中出现次数最多的字符次数超过长度的一半。

  • 长度为 \(2n\) 的不平衡串,该字符一定出现了至少 \(n+1\) 次,因此一定有连续两个字符相同;
  • 长度为 \(2n+1\) 的不平衡串,唯一特殊的情况是形如 abacada 这种,一定存在长度为 \(3\) 的不平衡子串;

综上,如果存在不平衡,那么最小的长度不会超过 \(3\) ,直接扫描即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 100007

char s[N];

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

E - Children and Candies

\[ \begin{array}{l} ans &= \displaystyle\sum_{x_1 = a_1}^{b_1}\sum_{x_2 = a_2}^{b_2}\cdots\sum_{x_n = a_n}^{b_n} \sum_{\substack{\sum c_i=C\\c_i\ge 0}}\prod_{i=1}^n x_i^{c_i}\\ &\displaystyle= \sum_{\substack{\sum c_i=C\\c_i\ge 0}} \sum_{x_1 = a_1}^{b_1} x_1^{c_1}\sum_{x_2 = a_2}^{b_2}x_2^{c_2}\cdots\sum_{x_n = a_n}^{b_n} x_n^{c_n}\\ &\displaystyle= \sum_{\substack{\sum c_i=C\\c_i\ge 0}}\prod_{i=1}^n\bigg(\sum_{x_i = a_i}^{b_i} x_i^{c_i}\bigg)\\ \end{array} \] 我们可以预处理出 \(pw_{i,k} =\sum_{x_i=a_i}^{b_i} x_i^k\) ,有

\[ ans = \sum_{\substack{\sum c_i=C\\c_i\ge 0}}\prod_{i=1}^n\bigg(\sum_{x_i = a_i}^{b_i} x_i^{c_i}\bigg) =\displaystyle\sum_{c_1=0}^C pw_{1,c_1}\sum_{\substack{c_2+\cdots + c_n=C-c_1\\c_i\ge 0}}\prod_{i=2}^n pw_{i,c_i} \] 按照这个思路继续拆分 \(c_2,\cdots, c_n\) ,本质上就是一个背包的动态规划。

\(f_{i,j}\) 表示考虑前 \(i\) 个变量,指数的和是 \(j\) ,对 \(ans\) 的贡献是多少。

枚举第 \(i\) 个指数占用了 \(k\ (k\le j)\) ,则转移方程: \[ f_{i,j}\leftarrow \sum_{k=0}^j f_{i-1,j-k}\times pw_{i,k} \] 时间复杂度 \(\mathcal{O}(n^3)\) ,空间复杂度 \(\mathcal{O}(n^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 407
#define mod 1000000007

int a[N], b[N], pw[N][N], f[N][N];

int main() {
int n = rd(), c = rd();
for (int i = 1; i <= n; ++i) a[i] = rd();
for (int i = 1; i <= n; ++i) b[i] = rd();
for (int i = 1; i <= n; ++i)
for (int j = a[i]; j <= b[i]; ++j)
for (int t = 0, nw = 1; t <= c; ++t, nw = 1ll * nw * j % mod)
pw[i][t] = (pw[i][t] + nw) % mod;
f[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= c; ++j)
for (int k = 0; k <= j; ++k)
f[i][j] = (f[i][j] + 1ll * f[i - 1][j - k] * pw[i][k]) % mod;
printf("%d\n", f[n][c]);
return 0;
}

F - Unhappy Hacking

\(n\) 次操作生成一个给定串 \(s\) 的方案数: 每次操作三选一:结尾加 \(0\) ,结尾加 \(1\) ,删除结尾一个字符(若空就什么都不做)

冷静一下这个计数和串是什么没关系,因为所有长度相同的串生成的概率相同。

\(f_{i,j}\) 表示 \(i\) 次操作生成长度为 \(j\) 的串的方案数,有: + 删除:\(f_{i,j} \leftarrow f_{i-1,j+1}+[j == 0]f_{i-1,j}\)
+ 添加:\([j>0] f_{i,j}\leftarrow f_{i-1,j-1}\times 2\)

答案就是 \(f_{n,|s|}\times 2^{-|s|}\) ,复杂度为 \(\mathcal{O}(n^2)\) ,感觉可能还能优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>  
using namespace std;
using ll = long long;

#define N 5007
#define mod 1000000007

inline int fpow(int x, int t) {
int res = 1;
for (; t; t >>= 1, x = 1ll * x * x % mod)
if (t & 1) res = 1ll * res * x % mod;
return res;
}

char s[N];

int f[N][N], pw[N] = {1};

inline void add(int &a, int b) {a = (a + b) % mod;}

int main() {
int n;
scanf("%d", &n);
scanf("%s", s + 1);
f[0][0] = 1;
for (int i = 1; i <= n; ++i) pw[i] = (pw[i - 1] << 1) % mod;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
add(f[i][j], f[i - 1][j + 1]);
if (!j) add(f[i][j], f[i - 1][j]);
else add(f[i][j], (f[i - 1][j - 1] << 1) % mod);
}
}
int m = strlen(s + 1);
int ans = 1ll * f[n][m] * fpow(pw[m], mod - 2) % mod;
printf("%d\n", ans);
return 0;
}