茶-2025-03

Tea

20250303

Problem

Rock and Lever

输入 T(≤10) 表示 T 组数据。所有数据的 n 之和 ≤1e5。
每组数据输入 n(1≤n≤1e5) 和长为 n 的数组 a(1≤a[i]≤1e9)。

输出有多少对 (i, j)，满足 i < j 且 (a[i] & a[j]) >= (a[i] ^ a[j])。

Example

输入

1
2
3
4
5
6
7
8
9
10
11
5
5
1 4 3 7 10
3
1 1 1
4
6 2 5 3
2
2 4
1
1

输出

1
2
3
4
5
1
3
2
0
0

Solution

分析：如果a[i]和a[j]的最高位都为1,那么a[i]&a[j]严格大于a[i]^a[j]。若一个为0一个为1，此时a[i] ^ a[j]严格大于a[i]&a[j].

所以使用map维护数组a相同最高位的个数，使用组合加起来即位为答案。

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
int lowbits(int x){
	return x & -x;
}
int reverse(int x){
	x = ((x >> 1)  & 0x55555555) | ((x & 0x55555555) << 1);
	x = ((x >> 2)  & 0x33333333) | ((x & 0x33333333) << 2);
	x = ((x >> 4)  & 0x0f0f0f0f) | ((x & 0x0f0f0f0f) << 4);
	x = ((x >> 8)  & 0x00ff00ff) | ((x & 0x00ff00ff) << 8);
	x = ((x >> 16) & 0x0000ffff) | ((x & 0x0000ffff) << 16);
	return x;
}
int highbit(int x) {
    return reverse(lowbits(reverse(x)));
}
void solve()
{
    int n;
    cin >> n;
    vi a(n);
    map<int, int> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        m[highbit(a[i])]++;
    }
    int ans = 0;
    for (auto it : m) {
        if (it.second>=2) {
            ans += it.second * (it.second - 1) / 2;
        }
    }
    cout << ans << endl;
}

20250304

Problem

Palindrome pairs

输入长度 ≤2000 的字符串 s，只包含小写英文字母。

从 s 中选两个不重叠的非空回文子串，有多少种选法？
正式地，计算四元组 (i,j,p,q) 的个数，其中 1≤i≤j<p≤q≤n 且 s[i..j] 和 s[p..q] 都是回文串。

【灵茶の试炼】题目&题解
https://docs.qq.com/sheet/DWGFoRGVZRmxNaXFz

Example

输入 

1
aa

输出 

1
1

输入 

1
aaa

输出 

1
5

输入 

1
abacaba

输出 

1
36

Solution

  1. 找出所有回文子串
    使用中心扩展法，遍历每个可能的中心点（奇数和偶数长度），向两边扩展，记录所有回文子串的起始和结束位置。
  2. 统计起始位置
    对于每个回文子串，记录其起始位置的出现次数，保存在 cnt_start 数组中。
  3. 构建后缀和数组
    构建 suffix 数组，其中 suffix[i] 表示从位置 i 到字符串末尾的所有回文子串的起始位置总和。通过从右向左遍历累加实现。
  4. 计算合法对的数量
    遍历每个回文子串，利用 suffix 数组快速查询以当前子串结尾后的所有可能的合法后续回文子串数目，累加得到答案。
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
void expand(string &s, int left, int right, vector<pair<int, int>> &pals) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        pals.emplace_back(left, right);
        left--;
        right++;
    }
}
void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    vector<pii> pals;
    for (int i = 0; i < n; i++) {
        expand(s, i, i, pals);
        expand(s, i, i + 1, pals);
    }
    vi cnt_start(n, 0);
    for (auto& p:pals) {
        cnt_start[p.first]++;
    }
    vi suffix(n+1,0);
    for (int i = n - 1; i >= 0; --i) {
        suffix[i] = suffix[i+1]+cnt_start[i];
    }
    int total = 0;
    for (auto & p: pals) {
        int end = p.second;
        if (end + 1 < n) {
            total += suffix[end + 1];
        }
    }
    cout << total << endl;
}

20250305

Problem

Palindromes

输入长度 ≤500 的字符串 s，包含大小写英文字母。
输入 k(1≤k≤|s|)。

每次操作，你可以把一个 s[i] 改成任意字符。
把 s 分割为至多 k 个非空子串，要求每个子串都是回文串，最少要修改多少次？

第一行，输出最少修改次数。
第二行，输出修改后的字符串，并用 ‘+’ 表示分割位置，详见样例。
如果有多种分割方案，输出其中任意一种。

Example

输入

1
2
abacaba
1

输出

1
2
0
abacaba

输入

1
2
abdcaba
2

输出

1
2
1
abdcdba

输入

1
2
abdcaba
5

输出

1
2
0
a+b+d+c+aba

输入

1
2
abacababababbcbabcd
3

输出

1
2
1
abacaba+babab+bcbabcb

Solution

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
void solve()
{
    int k;
    string s;
    cin >> s >> k;
    int n = s.size();

    vector<vector<int>> mc(n, vi(n, 0));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            mc[i][j] = mc[i + 1][j - 1];
            if (s[i] != s[j]) {
                mc[i][j]++;
            }
        }
    }
    vector<vector<int>> fr(k, vector<int>(n, 0));
    vector<int> f(n);
    for (int j = 0; j < n; ++j) {
        f[j] = mc[0][j];
    }
    int minF = f[n - 1], minK = 0;
    for (int i = 1; i < k; ++i) {
        vector<int> new_f(n, 1e9);
        for (int r = n - 1; r >= i; --r) {
            for (int l = i; l <= r; ++l) {
                int val = f[l - 1] + mc[l][r];
                if (val < new_f[r]) {
                    new_f[r] = val;
                    fr[i][r] = l;
                }
            }
        }
        f = move(new_f);
        if (f[n - 1] < minF) {
            minF = f[n - 1];
            minK = i;
        }
    }
    vector<string> path;
    for (int i = minK, r = n - 1; i >= 0; --i) {
        int l = fr[i][r];
        string t = s.substr(l, r - l + 1);
        for (int j = 0, m = t.size(); j < m / 2; ++j) {
            if (t[j] != t[m - 1 - j]) {
                t[j] = t[m - 1 - j];
            }
        }
        path.push_back(t);
        r = l - 1;
    }
    reverse(path.begin(), path.end());
    
    cout << minF << "\n";
    for (size_t i = 0; i < path.size(); ++i) {
        if (i > 0) cout << "+";
        cout << path[i];
    }
    cout << endl;
}

20250306

Problem

Palindromic characteristics

输入长度 ≤5000 的字符串 s，只包含小写英文字母。

如果字符串 s 是回文串，我们称 s 为 1 阶回文串。
如果字符串 s 的左半部分等于 s 的右半部分，且左半部分和右半部分都是 k-1 阶回文串，我们称 s 为 k 阶回文串（k > 1）。
注：设 m = floor(len(s)/2)，「左半部分」指 s 的长为 m 的前缀，「右半部分」指 s 的长为 m 的后缀。

输出 n 个数，分别表示 s 的 1,2,3,…,n 阶非空回文子串的个数。

Example

输入 

1
abba

输出 

1
6 1 0 0

输入 

1
abacaba

输出 

1
12 4 1 0 0 0 0

Solution

由题意可得，一个k阶字符串一定是回文串，同时也一定是1~k-1阶字符串。

定义 isPal[l] [r] 表示 s[l] 到 s[r] 是否为回文串，这可以写个区间 DP（或者中心扩展法）预处理。
定义 f[l] [r]，表示 s[l] 到 s[r] 最大是 f[l] [r] 阶回文串。如果不是回文串则 f[l] [r]=0。

根据题目的定义，如果 s[l] 到 s[r] 是回文串，那么有
f[l] [r] = f[l] [(l+r-1)/2] + 1，即左半部分的阶数加一。
初始值 f[i] [i] = 1，其余为 0。

统计 f[l] [r] 的出现次数，记作 ans。
注意 ans[k] 统计的是最大为 k 阶的回文子串个数。
由于 k 阶回文串一定是 k-1 阶回文串，所以计算 ans 的后缀和，就是题目要算的东西了。

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
void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<bool>> isPal(n, vector<bool>(n, false));
    vector<vector<short>> order(n, vector<short>(n, 0));

    for (int len = 1; len <= n; ++len) {
        for (int l = 0; l + len - 1 < n; ++l) {
            int r = l + len - 1;
            if (len == 1) {
                isPal[l][r] = true;
            } else if (len == 2) {
                isPal[l][r] = (s[l] == s[r]);
            } else {
                isPal[l][r] = (s[l] == s[r] && isPal[l+1][r-1]);
            }
        }
    }

    for (int len = 1; len <= n; ++len) {
        for (int l = 0; l + len - 1 < n; ++l) {
            int r = l + len - 1;
            if (isPal[l][r]) {
                if (len == 1) {
                    order[l][r] = 1;
                } else {
                    int current_order = 1;
                    int left_l, left_r, right_l, right_r;
                    if (len % 2 == 0) {
                        int mid = len / 2;
                        left_l = l;
                        left_r = l + mid - 1;
                        right_l = l + mid;
                        right_r = r;
                    } else {
                        int mid = len / 2;
                        left_l = l;
                        left_r = l + mid - 1;
                        right_l = l + mid + 1;
                        right_r = r;
                    }
                    if (isPal[left_l][left_r] && isPal[right_l][right_r] &&
                        order[left_l][left_r] == order[right_l][right_r]) 
                    {
                        current_order = order[left_l][left_r] + 1;
                    }
                    order[l][r] = current_order;
                }
            }
        }
    }

    vector<int> ans(n + 2, 0);
    for (int l = 0; l < n; ++l) {
        for (int r = l; r < n; ++r) {
            if (isPal[l][r]) {
                int k = order[l][r];
                if (k <= n) ans[k]++;
            }
        }
    }

    for (int i = n; i >= 1; --i) {
        ans[i] += ans[i + 1];
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " \n"[i == n];
    }
}
codeforces
#acm
茶-2025-03
https://www.polarishaw.top/2025/03/03/Tea202503/
作者
Polaris
发布于
2025年3月3日
许可协议