Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述

定义函数 f(t)f(t) 为：将字符串 tt 划分为若干部分的最大数量，满足每个部分都是 tt 的非空前缀。

There exist kk strings p1,p2,…,pkp_1,p_2,\ldots,p_k, which are prefixes of tt, such that t=p1+p2+…+pkt=p_1+p_2+\ldots+p_k. Here ++ denotes the string concatenation.

换句话说，f(t)f(t) 是满足以下条件的最大正整数 kk：存在 kk 个字符串 p1,p2,…,pkp_1, p_2, \dots, p_k，它们都是 tt 的前缀，且 t=p1+p2+⋯+pkt = p_1 + p_2 + \dots + p_k（++ 表示字符串拼接）。

给定一个长度为 nn 的小写英文字符串 ss。
你需要回答 qq 次询问，每次询问给出两个整数 lil_i 和 rir_i，要求计算并输出：
∑j=lirif(s[li…j])\sum_{j=l_i}^{r_i} f(s[l_i \dots j])
（其中 s[li…j]s[l_i \dots j] 表示 ss 从第 lil_i 个字符到第 jj 个字符组成的子串）。

image

这个其实是方便我们进行计算的。

输入格式

第一行包含一个整数 tt（1≤t≤1031 \le t \le 10^3），表示测试用例的数量。
每个测试用例的第一行包含两个整数 nn 和 qq（1≤n≤1061 \le n \le 10^6, 1≤q≤1001 \le q \le 100），分别表示字符串长度和询问次数。
第二行包含一个长度为 nn 的小写英文字符串 ss。
接下来 qq 行，每行包含两个整数 lil_i 和 rir_i（1≤li≤ri≤n1 \le l_i \le r_i \le n），表示一次询问。

保证所有测试用例中 nn 的总和不超过 10610^6。

输出格式

对于每次询问，输出一个整数表示表达式的求和结果。

样例数据

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
输入:
6
1 1
a
1 1
5 2
aaaaa
1 5
2 4
6 2
abcdef
1 6
3 5
6 3
abaaba
1 6
1 3
2 6
7 3
abcabca
1 7
2 7
4 7
8 3
aababaac
1 8
2 8
3 7

输出:
1
15
6
6
3
14
4
7
12
9
5
13
14
7

样例解释

在第一个测试用例中，f(a)=1f(\text{a}) = 1。

在第二个测试用例中：
对于第一次询问 1 5：f(a)+f(aa)+f(aaa)+f(aaaa)+f(aaaaa)=1+2+3+4+5=15f(\text{a}) + f(\text{aa}) + f(\text{aaa}) + f(\text{aaaa}) + f(\text{aaaaa}) = 1 + 2 + 3 + 4 + 5 = 15。
对于第二次询问 2 4（对应的子串是 aaa）：f(a)+f(aa)+f(aaa)=1+2+3=6f(\text{a}) + f(\text{aa}) + f(\text{aaa}) = 1 + 2 + 3 = 6。

在第三个测试用例中：
对于第一次询问 1 6：f(a)+f(ab)+f(abc)+f(abcd)+f(abcde)+f(abcdef)=1+1+1+1+1+1=6f(\text{a}) + f(\text{ab}) + f(\text{abc}) + f(\text{abcd}) + f(\text{abcde}) + f(\text{abcdef}) = 1 + 1 + 1 + 1 + 1 + 1 = 6。
对于第二次询问 3 5（对应的子串是 cde）：f(c)+f(cd)+f(cde)=1+1+1=3f(\text{c}) + f(\text{cd}) + f(\text{cde}) = 1 + 1 + 1 = 3。

思路讲解

P3375 【模板】KMP（前缀函数）（完全理解 kmp）

队友的这个思路，确实是非常好啊。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<ll> shortest_prefix(const vector<ll> &pi) {
    vector<ll> sp(SZ(pi));
    for (int i = 1; i < SZ(pi); ++i) {
        if (pi[i] == 0) {
            sp[i] = 0;
        } else if (sp[pi[i] - 1] > 0) {
            sp[i] = sp[pi[i] - 1];
        } else {
            sp[i] = pi[i];
        }
    }
    return sp;
}

这个方法的正确性还是比较容易看出来的，不言自明，只要前缀和后缀相同。其之所以有效，和 kmp 一样。

image

AC代码

AC
https://codeforces.com/contest/2209/submission/367859558

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题面总结

给定多组数据。每组给出三种幽火数量：红色 r、绿色 g、蓝色 b。

你需要构造一个只由 R、G、B 组成的字符串 s，表示按顺序摆放的幽火颜色，要求：

  • R、G、B 的使用次数分别不超过 r、g、b。

  • 对任意相邻位置，颜色不能相同，即 s_i != s_{i+1}。

  • 对任意间隔 2 个位置（下标差 3）的位置，颜色也不能相同，即 s_i != s_{i+3}。

  • 在满足以上条件下，|s| 要尽可能长。

如果有多个最长可行答案，输出任意一个即可。

输入输出要求

  • 输入第一行为测试组数 t。

  • 每组输入一行三个整数 r g b。

  • 对每组输出一行构造出的字符串 s。

数据范围

  • 1 <= t <= 10^4

  • 0 <= r, g, b <= 10^6

  • r + g + b > 0

  • 所有测试组的 r + g + b 总和不超过 10^6

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
5
0 0 1
1 1 1
0 3 0
2 2 2
2 7 3

输出
B
RGB
G
GBRBRG
GRGRGBGBGBG

样例配合说明

  • 第 1 组：只有 1 个蓝色，输出 B，长度为 1 且合法。

  • 第 2 组：三种颜色各 1 个，RGB 使用了全部 3 个且满足限制。

  • 第 3 组：只有绿色 3 个，但相邻不能同色，所以最多只能放 1 个，输出 G。

  • 第 4 组：GBRBRG 长度为 6，刚好把 2,2,2 全部用完，并满足相邻与间隔 2 的限制。

  • 第 5 组：GRGRGBGBGBG 在给定数量下给出一个满足条件的最长构造。

思路讲解

image

不难发现，能够凑的话，肯定是凑出足够的这个 gb，gr，rb 最好。但是怎么样凑出最多的 gb，gr，rb？其实这个就是求解一个线性方程组（如上），我们可以得到 rb 的这个数量。

但你会发现，如果采用数学式方法，去求解这个二元组的数量，然后去做，肯定是能做出来的，但是坑非常多，首先，这个元组是有可能 rb 求出来是一个负数。

这道题目怎么做？如下。

image

当然，你说为什么就强制给他安一个前缀就对了？其实也没什么神秘的，其实到最后，就是一个奇偶性问题，奇偶性问题有的时候一个的改变，就足以改变正确性了。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// 强制枚举前缀
  for (int i = 0; i < pow3[3]; ++i) {
      ll opi = i;
      vector<Num_color> rgb = rgb_global;
      string ans;
      auto push_to_ans = [&](ll i) {
          ans.push_back(rgb[i].color);
          rgb[i].num--;
      };
      auto check_ans = [&]() {
          for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
              if (i - 1 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 1]) {
                  return false;
              }
          }
          for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
              if (i - 3 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 3]) {
                  return false;
              }
          }
          return true;
      };
      auto check_ans_all = [&]() {
          for (int i = SZ(ans) - 1; i >= 0; --i) {
              if (i - 1 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 1]) {
                  return false;
              }
          }
          for (int i = SZ(ans) - 1; i >= 0; --i) {
              if (i - 3 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 3]) {
                  return false;
              }
          }
          return true;
      };
      while (opi != 0) {
          push_to_ans(opi % 3);
          opi/=3;
      }
      if (!check_ans_all()) {
          continue;
      }
      sort(all(rgb), cmp);
      if (rgb[2].num < 0) {
          continue;
      }
      while (true) {
          sort(all(rgb), cmp);
          if (rgb[2].num > 0) {
              push_to_ans(0);
              push_to_ans(2);
              if (!check_ans()) {
                  swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
                  if (!check_ans()) {
                      break;
                  }
              }
              // 以后尽量不要这么写 continue，万一漏了很难 debug 出来
              continue;
          }
          if (rgb[1].num > 0) {
              push_to_ans(0);
              push_to_ans(1);
              if (!check_ans()) {
                  swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
                  if (!check_ans()) {
                      break;
                  }
              }
              continue;
          }
          if (rgb[0].num > 0) {
              push_to_ans(0);
              if (!check_ans()) {
                  ans.pop_back();
                  break;
              }
          }
          break;
      }
      // #ifdef LOCAL
      //         debug(ans);
      //         debug(ans_global);
      // #endif
      if (SZ(ans) > SZ(ans_global)) {
          swap(ans, ans_global);
      }
  }
  cout << ans_global << "\n";

AC代码

AC
https://codeforces.com/contest/2209/submission/367802322

心路历程（WA，TLE，MLE……）

写对拍器的时候，为了防止对拍写的有问题，最好写为不等于，这样子，对拍器生成的字符串过小也可以非常容易的看出来。

1
2
3
4
5
dfs(dfs, "");
if (SZ(brute) != SZ(ans)) {
    cout << "too small\n";
    cout << brute << "\n";
}

Posted on

题目大意

题目描述
给定两个长度均为 nn 的小写字母字符串 SS 和 TT。
你需要在 SS 中选取一个子串 S′S'，在 TT 中选取一个子串 T′T'（空串不算作子串），并将 T′T' 拼接在 S′S' 的后面组成一个新的字符串。
求共有多少种选取方式，使得拼接后的新字符串是一个回文串。
注：选取方式由子串在原串中的起始和终止位置决定；回文串指正读和反读都相同的字符串。

输入格式
第一行输入一个整数表示测试组数 TT（T≤10T \le 10）。
接下来每组数据输入两行，分别表示字符串 SS 和 TT。
数据保证两个字符串长度相等且 n≤2000n \le 2000。

输出格式
对于每组数据，输出一行整数，表示能组成回文串的子串选取方案数。

样例

样例输入

1
2
3
4
5
2
ab
ac
aba
bba

样例输出

1
2
2
15

样例解释
对于第一组样例，S="ab"S = \text{"ab"}，T="ac"T = \text{"ac"}。合法的选取方式共 22 种：

  1. 选取 S[1…1]="a"S[1 \dots 1] = \text{"a"} 和 T[1…1]="a"T[1 \dots 1] = \text{"a"}，拼接得到 "aa"\text{"aa"}，是回文串。

  2. 选取 S[1…2]="ab"S[1 \dots 2] = \text{"ab"} 和 T[1…1]="a"T[1 \dots 1] = \text{"a"}，拼接得到 "aba"\text{"aba"}，是回文串。

对于第二组样例，S="aba"S = \text{"aba"}，T="bba"T = \text{"bba"}。合法的选取方式共 1515 种，列举其中几种情况：

  • 选取 S[1…1]="a"S[1 \dots 1] = \text{"a"} 和 T[3…3]="a"T[3 \dots 3] = \text{"a"}，拼接得到 "aa"\text{"aa"}。

  • 选取 S[2…2]="b"S[2 \dots 2] = \text{"b"} 和 T[1…1]="b"T[1 \dots 1] = \text{"b"}，拼接得到 "bb"\text{"bb"}。

  • 选取 S[2…2]="b"S[2 \dots 2] = \text{"b"} 和 T[2…2]="b"T[2 \dots 2] = \text{"b"}，拼接得到 "bb"\text{"bb"}。

  • 选取 S[1…2]="ab"S[1 \dots 2] = \text{"ab"} 和 T[2…3]="ba"T[2 \dots 3] = \text{"ba"}，拼接得到 "abba"\text{"abba"}。

  • 选取 S[1…3]="aba"S[1 \dots 3] = \text{"aba"} 和 T[2…3]="ba"T[2 \dots 3] = \text{"ba"}，拼接得到 "ababa"\text{"ababa"}。
    以此类推，满足条件的下标区间组合总共有 1515 种。

思路讲解

完全理解 manacher

image

image

image

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
void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    // 以 i 为起点的这个回文串数量
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
    }
    // 上面是在
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif
		// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            } else {
                lcsuf[i][j] = 0;
            }
            // 加一是因为还有空的情况，即 s 和 rev_t 都不提供 B
            ll add = lcsuf[i][j] * (cntS[i + 1] + cntT[j + 1] + 1);
            ans += add;
        }
    }
    cout << ans << "\n";
}

AC代码

TLE，这个代码是这个 O(n2)O(n^2) 的，但是还是这个哈希表还是有点慢，被卡了。

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1197&rid=19239

心路历程（WA，TLE，MLE……）

Posted on Edited on

manacher

马拉车算法其实和这个 kmp，z 函数还是有异曲同工之妙的。

我们维护一个最远的回文串边界，记为 r。

image

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

// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s){
    int n=SZ(s);
    s='$'+s+'^';
    vector<ll> p(n+2);
    ll l=0,r=1;     // (l,r) 是开区间，其内部是这个回文子串
    for(int i=1;i<=n;++i){
        // 保底半径
        p[i]=min(r-i,p[l+r-i]);
        // 暴力外扩
        while (s[i-p[i]]==s[i+p[i]]) { // 因为有哨兵，永不越界
            p[i]++;
        }
        if(i+p[i]>r){
            l=i-p[i],r=i+p[i];
        }
    }
    return vector<ll>(p.begin()+1,p.end()-1);
}
vector<ll> manacher(const string &s){
    string t;
    for(auto c:s){
        t+='#';     // 千万不要    t+='#'+'c'
        t+=c;
    }
    t+='#';
    auto res=manacher_odd(t);
    return vector<ll>(res.begin()+1,res.end()-1);
}
// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

可以这样子使用这个差分，得到以该点起点的的这个回文串的数量。

1
2
3
4
5
6
7
8
9
10
11
12
vector<ll> ps = manacher(s);
vector<ll> cntS(szs + 3);
for (int i = 0; i < SZ(ps); ++i) {
    ll r = ps[i] / 2;
    if (r == 0) {
        continue;
    }
    ll pos = i / 2;
    cntS[pos - r + 1]++;
    cntS[pos + 1]--;
}
partial_sum(all(cntS), cntS.begin());

Posted on

隔板法的思想就是，把 a 插入 d 个空格当中，换为给 a 加上 d-1 个隔板。

image

为什么是这个公式呢？不难发现，我们可以把 a 个球和 d-1 个隔板放在一起进行乱排，模拟可以为 0 的情况。

image

CN+K−1K−1=CN+K−1NC_{N+K-1}^{K-1}=C_{N+K-1}^{N} 我认为前面一个更容易理解。

要求这个题目要求 xi≥aix_{i}\geq a_{i}，也可以使用这个插板法。

image

The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-I. Tearing Paper

这道题目，隔板法是有效的，是因为隔板法其实是要求插入元素的这个顺序是不重要的，那么这道题目，细想之下，确实如此。

image

经过抽象以后，这道题目需要求解的内容如上。

不难发现，我们其实只关注这个 U R 之间的相对关系，说白了就是两个 U 之间隔了几个 R？只要这个不变，路径是不会改变的。

image