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;  
}