A. Simple Palindrome

可以发现，两个相同的字母产生的回文子串与它们之间间隔的字母个数有关，因此考虑把 \(n\) 个字母分配给 \(aeiou\)，并且相同的元素相邻

code:

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
39
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        
        string s = "aeiou";
        int x = n / 5, y = n % 5;
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < x; j++) cout << s[i];
            if (y) 
            {
                cout << s[i];
                y--;
            }
        }
        cout << endl;
    }

    return 0;
    }

B1 & B2. The Strict Teacher

\(David\) 只会被他左右的老师抓住，因此考虑二分查找 \(David\) 左右两个老师的位置，可以发现，\(David\) 最多只能走到这两个老师的位置中间就会被抓住

code:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, m, q;
int b[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> q;
        for (int i = 0; i < m; i++) cin >> b[i];
        
        sort(b, b + m);
        
        for (int i = 0; i < q; i++)
        {
            int x;
            cin >> x;
            
            int l = 0, r = m - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (b[mid] > x) r = mid - 1;
                else l = mid;
            }
            
            bool flag = false;
            if (b[l] < x)
            {
                if (l == m - 1) cout << n - b[l] << ' ';
                else cout << (b[l + 1] - b[l] + 2) / 2 - 1 << ' ';
            }
            else cout << b[0] - 1 << ' ';
        }
        cout << endl;
    }

    return 0;
}

C. Lazy Narek

考虑 \(dp\), \(f[i]\) 为，\(narek\) 中，以第 \(i\) 个字母结尾的最大贡献

code:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int T;
int n, m;
string s[N];
int f[5];
string t = "narek";

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> s[i];
        
        f[4] = 0;
        for (int i = 0; i < 4; i++) f[i] = -1e9;
        for (int i = 0; i < n; i++)
        {
            int g[5];
            memcpy(g, f, sizeof g);
            for (int j = 0; j < 5; j++)
            {
                int id = j, cnt = f[j];
                for (int k = 0; k < m; k++)
                {
                    int x = t.find(s[i][k]);
                    if (x == t.npos) continue;
                    if ((id + 1) % 5 == x) 
                    {
                        cnt++;
                        id = (id + 1) % 5;
                    }
                    else cnt--;
                }
                g[id] = max(g[id], cnt);
            }
            memcpy(f, g, sizeof f);
        }
        
        int res = 0;
        for (int i = 0; i < 5; i++) res = max(res, f[i] - ((i + 1) % 5) * 2);
        
        cout << res << endl;
    }

    return 0;
}

D. Alter the GCD

\(tle\) 代码，\(st\) 表 + 二分

code:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;

const int N = 200010;

int T;
int n;
int f1[N][20], f2[N][20];

int gcd(int a, int b)
{
	return b? gcd(b, a % b) : a;
}

int ga(int l, int r)
{
	if (l > r) return 0;
	int x = log2(r - l + 1);
	return gcd(f1[l][x], f1[r - (1 << x) + 1][x]);
}

int gb(int l, int r)
{
	if (l > r) return 0;
	int x = log2(r - l + 1);
	return gcd(f2[l][x], f2[r - (1 << x) + 1][x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> f1[i][0];
        for (int i = 1; i <= n; i++) cin >> f2[i][0];
        
        for (int j = 1; j <= 20; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
            {
                f1[i][j] = gcd(f1[i][j - 1], f1[i + (1 << j - 1)][j - 1]);
                f2[i][j] = gcd(f2[i][j - 1], f2[i + (1 << j - 1)][j - 1]);
            }
        
        ll res = 0, cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            int j = i;
            while (j <= n)
            {
                int d1 = ga(i, j), d2 = gb(i, j);
                int sd1 = ga(j + 1, n), sd2 = gb(j + 1, n);
                int l = j, r = n;
                while (l < r)
                {
                    int mid = l + r + 1 >> 1;
                    if (d1 != ga(i, mid) || d2 != gb(i, mid) || sd1 != ga(mid + 1, n) || sd2 != gb(mid + 1, n)) r = mid - 1;
                    else l = mid;
                }
                int r1 = gcd(ga(1, i - 1), gcd(d2, sd1));
                int r2 = gcd(gb(1, i - 1), gcd(d1, sd2));
                if (res <= r1 + r2)
                {
                    if (res < r1 + r2) cnt = 0;
                    res = r1 + r2;
                    cnt += r - j + 1;
                }
                j = r + 1;
            }
        }
        
        cout << res << ' ' << cnt << '\n';
    }

    return 0;
}

E1. Subtangle Game (Easy Version)

博弈题， 考虑 \(dp\)，设 \(f[i][j][k]\) 为第 \(i\) 步选择 \(s[k][j]\)，是否有必胜策略，\(i\) 为奇数代表先手，\(i\) 为偶数代表后手

当第 \(i + 1\) 步，在 \((j+1,k+1)\) 到 \((n,m)\) 的矩阵中选择有必胜策略时，\(f[i][j][k]\) 是必败的，为 \(0\)

当第 \(i + 1\) 步，在 \((j+1,k+1)\) 到 \((n,m)\) 的矩阵中选择没有必胜策略时，\(f[i][j][k]\) 是必胜的，为 \(1\)

可以用矩阵前缀和来维护子矩阵必胜策略

code:

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
39
40
41
42
43
#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int T;
int l, n, m;
int a[N], s[N][N];
int f[N][N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> l >> n >> m;
        for (int i = 1; i <= l; i++) cin >> a[i];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> s[i][j];
        
        for (int i = 1; i <= l + 1; i++)
            for (int j = 1; j <= n + 1; j++)
                for (int k = 1; k <= m + 1; k++)
                    f[i][j][k] = 0;
        
        for(int i = l; i >= 1; i--)
            for(int j = n; j >= 1; j--)
                for(int k = m; k >= 1; k--)
                {
                    if(s[j][k] == a[i] && !f[i + 1][j + 1][k + 1]) f[i][j][k] = 1;
                    f[i][j][k] += f[i][j + 1][k] + f[i][j][k + 1] - f[i][j + 1][k + 1];
                }
        
        if (f[1][1][1]) cout << 'T' << endl;
        else cout << 'N' << endl;
    }

    return 0;
}

E2. Subtangle Game (Hard Version)

设 \(f[1][i][j]\) 为先手在 \((i,j)\) 到 \((n,m)\) 中必胜的最小步数，\(f[0][i][j]\) 为后手在 \((i,j)\) 到 \((n,m)\) 中必胜的最小步数

记 \(last[x]\) 为 \(x\) 在 \(a\) 中最早出现的位置

若 第\(last[s[i][j]]\) 步选择 \(s[i][j]\)，并且另一个人不存在不超过 \(last[s[i][j]] + 1\) 步 在 \((i + 1,j + 1)\) 到 \((n,m)\) 中选择的必胜策略，则这一步是必胜的，值为 \(last[s[i][j]]\)

code:

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
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>

using namespace std;

const int N = 1510;

int T;
int l, n, m;
int a[N], s[N][N];
int f[2][N][N];
int last[N * N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> l >> n >> m;
        for (int i = 1; i <= l; i++) cin >> a[i];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> s[i][j];
        
        for (int i = l; i >= 1; i--) last[a[i]] = i;
        for (int i = 0; i < 2; i++)
            for (int j = 1; j <= n + 1; j++)
                for (int k = 1; k <= m + 1; k++)
                    f[i][j][k] = 1e9;
        
        for (int i = n; i >= 1; i--)
            for (int j = m; j >= 1; j--)
            {
                f[0][i][j] = min(f[0][i + 1][j], f[0][i][j + 1]);
                f[1][i][j] = min(f[1][i + 1][j], f[1][i][j + 1]);
                if (!last[s[i][j]]) continue;
                if (last[s[i][j]] % 2 == 0 && f[1][i + 1][j + 1] > last[s[i][j]] + 1) f[0][i][j] = min(f[0][i][j], last[s[i][j]]);
                if (last[s[i][j]] % 2 == 1 && f[0][i + 1][j + 1] > last[s[i][j]] + 1) f[1][i][j] = min(f[1][i][j], last[s[i][j]]);
            }
        
        if (f[1][1][1] == 1) cout << 'T' << '\n';
        else cout << 'N' << endl;	
        
        for (int i = 1; i <= l; i++) last[a[i]] = 0;
    }

    return 0;
}