多校训练营10

D:Mi Re Do Si La? So Fa!

LyFive

标签

后缀数组(SA);计数;字符串周期;st表;lcp;lcs

题意

定义价值为字符串的所有可能的周期和。现给一个字符串，求其所有子串的价值和。

思路

对于循环节只有1的朴素方案可以直接统计为。 对于循环节大于等于2的串，首先我们先定周期，目标找到所有周期为的子串统计价值。不难发现，目标子串长度，定义指针进行扫描每次位移单位长度，一定能够扫描进入所有目标子串中。当扫入目标子串时，的位置一定在第一个循环节内，此时得到与的最长公共后缀和最长公共前缀便能划定区间得到目标子串(对于周期串一定有与的为，一定有与的为，将前后者连接即得到了目标串)。因此对跑一遍并使用表查询。同理对反向后再跑一遍，便能得到。 当得到目标串后，可能会出现两种形式。 1. 完整的周期串，类似 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
 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e6 + 10;
const int M = 20;
char s[N];
int n;
int Log[N];
int pow2[25];
struct SA
{
    int f[N][M]; // st表
    int h[N], sa[N], rk[N], x[2 * N], y[2 * N], c[N];
    int m;
    void init()
    {
        m = 30;
        for (int i = 0; i <= m; i++)c[i] = 0;
        for (int i = 1; i <= n; i++)c[x[i] = s[i] - 'a' + 1]++;
        for (int i = 1; i <= m; i++)c[i] += c[i - 1];
        for (int i = n; i >= 1; i--)sa[c[x[i]]--] = i;
        for (int k = 1; k <= n; k <<= 1)
        {
            int num = 0;
            for (int i = n; i >= n - k + 1; i--)y[++num] = i;
            for (int i = 1; i <= n; i++)
                if (sa[i] > k)y[++num] = sa[i] - k;
            for (int i = 0; i <= m; i++)c[i] = 0;
            for (int i = 1; i <= n; i++)c[x[i]]++;
            for (int i = 1; i <= m; i++)c[i] += c[i - 1];
            for (int i = n; i >= 1; i--)
                sa[c[x[y[i]]]--] = y[i], y[i] = 0;
            for (int i = 0; i <= 2 * n; i++)swap(x[i], y[i]);
            num = 0;
            x[sa[1]] = ++num;
            for (int i = 2; i <= n; i++)
                x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? num : ++num;
            if (num == n)break;
            m = num;
        }
    }
    void getHeight()
    {
        for (int i = 1; i <= n; i++)rk[sa[i]] = i;
        for (int i = 1, k = 0; i <= n; i++)
        {
            if (rk[i] == 1)continue;
            if (k)k--;
            int j = sa[rk[i] - 1];
            while (i + k <= n && j + k <= n && s[i + k] == s[j + k])k++;
            h[rk[i]] = k;
        }
    }
    void initST()
    {
        for (int i = 1; i <= n; i++)f[i][0] = h[i];
        for (int j = 1; j <= M; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                f[i][j] = min(f[i][j - 1], f[i + pow2[j - 1]][j - 1]);
    }
    int lcp(int x, int y)
    {
        int l = rk[x];
        int r = rk[y];
        if (l > r)swap(l, r);
        l++;
        int s = Log[r - l + 1];
        return min(f[l][s], f[r - pow2[s] + 1][s]);
    }
    void main()
    {
        init();
        getHeight();
        initST();
    }
} s1, s2;
void init()
{
    for (int i = 2; i < N; i++)Log[i] = Log[i / 2] + 1;
    pow2[0] = 1;
    for (int i = 1; i < 25; i++)pow2[i] = pow2[i - 1] * 2;
}
int lcp(int x, int y)
{
    return s1.lcp(x, y);
}
int lcs(int x, int y)
{
    return s2.lcp(n - y + 1, n - x + 1);
}
LL make(int len)
{
    LL res = 0;
    for (int i = 1; i + len <= n; i += len)
    {
        if (s[i] != s[i + len])continue;
        int ll = i - lcs(i, i + len) + 1;
        int rr = i + len + lcp(i, i + len) - 1;
        if (rr - ll + 1 < 2 * len)continue;
        int num = rr - ll + 1;
        int t = num / len; // 最大循环节数量
        int cnt = num % len + 1; // 拥有最大循环节的个数
        res += (LL)t * (t - 1) / 2 * cnt * len;
        res += (LL)(t-1)*(t-2)/2*(len - cnt)*len;
        i = rr - len + 1;
    }
    return res;
}
void solve()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    s1.main();
    reverse(s + 1, s + 1 + n);
    s2.main();
    reverse(s + 1, s + 1 + n);
    LL ans = 0;
    for (int i = 1; i <= n; i++)ans += (LL)i * (n - i + 1);
    for (int len = 1; len <= n / 2; len++)ans += make(len);
    printf("%lld\n", ans);
}
int main()
{
    init();
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)solve();
}

E:Reviewer Assignment

z3475

标签

匈牙利算法/上下界网络流

题意

有个审稿人篇论文，每个审稿人能审阅一篇论文，一篇论文必须有一个审稿人审阅，且能同时被多个审稿人审审阅。要使被大于等于1的审稿人审阅的论文数量最多，如果相等要使被大于等于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
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
#include <bits/stdc++.h>
#define N 1005
#define M 1005
using namespace std;
template <class T>
using vec = vector<T>;
bool FG[N][N];
multiset<int> ma[N];
int book[N], maxn = 0;
int n, m, e;
vec<int> v;
int dfs(int l, int p = 1000000) {
  book[l] = 1;
  int i = 0;
  bool f = true;
  int vs = 1000000, vvi;
  for (; i < v.size(); i++)
    if (FG[l][v[i]]) {
      int vi = v[i];
      if (exchange(f, false))
        vs = ma[vvi = vi].size();
      if (ma[vi].size() == 0) {
        ma[vi].insert(l);
        return vi;
      }
      for (auto j = ma[vi].begin(); j != ma[vi].end(); j++) {
        if ((!book[*j]) && dfs(*j, min(p, vs))) {
          ma[vi].erase(j);
          ma[vi].insert(l);
          return vi;
        }
      }
    }
  if ((!f) && vs < p) {
    ma[vvi].insert(l);
    return i;
  }
  return 0;
}
char gc() {
  char c;
  while ((c = cin.get()) && c != '0' && c != '1')
    ;
  return c;
}
int to[N];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++)
      if (gc() == '1') {
        FG[i][j] = 1;
      }
  }
  v.resize(m);
  iota(v.begin(), v.end(), 1);
  for (int i = 1; i <= n; i++) {
    sort(v.begin(), v.end(),
         [](auto&& a, auto&& b) { return ma[a].size() < ma[b].size(); });
    dfs(i);
    memset(book, 0, sizeof(book));
  }
  for (int i = 1; i <= m; i++) {
    for (auto j : ma[i]) {
      to[j] = i;
    }
  }
  for (int i = 1; i <= n; i++)
    if (to[i] == 0) {
      cout << -1 << endl;
      return 0;
    }
  for (int i = 1; i <= n; i++)
    cout << to[i] << " ";
  cout << endl;
}
build本页面最近更新：2022/8/28 20:23:20，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Ir1d
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论