题目大意

给你一个字符串 $S$，有 $q$ 次询问。

每次询问给出四个数 $a$，$b$，$c$，$d$。

求 $\max_{a\le l\le r\le b}lcp(S[l\ldots r],S[c\ldots d])$。

后缀数组

解题思路

先二分答案，令长度为 $mid$ ，接下来就是要判断是否存在 $a\le pos\le b-mid+1$ 使 $S[pos\ldots pos+mid-1]=S[c\ldots c+mid-1]$。

也就是说 $lcp(S[pos\ldots n],S[c\ldots n])\ge mid$。

题目大意

给你一个字符串 $S$，每个位置都有一个权值 $a_i$。

定义 $p$ 和 $q$ 两个位置 $r$ 相似表示 $S[p\ldots p+r-1]=S[q\ldots q+r-1]$。

对于所有的 $r \in [0,n-1]$ 求：

• 有多少对 $(p,q)$ 是 $r$ 相似的。
• 最大的 $a_p \times a_q$ 满足 $(p,q)$ 是 $r$ 相似的。

解题思路

考虑倒着建 $SAM$，发现 $(p,q)$ 是 $r$ 相似的等价于存在一个 $endpos$ 等价类包含 $p$ 和 $q$，并且 $minlen\le r \le len$。

有了这个我们就可以计算每一个 $endpos$ 等价类对答案的贡献。

源码链接

Link

示例站点

Ftt2333's Blog

配置

貌似没啥好说的

title: Welcome to Ftt2333's Blog
menu: 
  - name: Archives 
    link: /archives/
  - name: Categories 
    link: /categories/
  - name: Tags
    link: /tags/
twikoo:
  enable: false
  envId:
valine:
  enable: false
  serverURL: 
  appID:
  appKey: 
waline:
  enable: false
  serverURL: 
cusdis:
  enable: false
  appId: 

功能介绍

输入一个 $6$ 位数，他会输出一个 $7$ 位数。

代码

/*
* @Author: ftt2333
* @Email: ftt2333@126.com
* @Last Modified time: 2022-10-11 16:54:18
*/

#include<bits/stdc++.h>
using namespace std;

#define qin cin
#define qout cout
#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define per(i, a, b) for(auto i = (a); i >= (b); i--)

char s[20];
int a[20], b[20];

int main() {
  scanf("%s", s + 1);
  rep(i, 1, 6) a[i] = s[i] - 48;
  rep(i, 1, 6) b[i * 2 - 1] = a[i], b[i * 2] = 10 - a[i];
  rep(i, 1, 4) qout << b[i];
  qout << (b[5] - b[6] + 10) % 10;
  qout << (b[7] + b[8] + b[9]) % 10;
  qout << (b[10] + b[11] + b[12] + 1) % 10;
}

彩蛋

输入114514有惊喜

献上代码！

Header

#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
void debug(...) {}
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define per(i, n) for (int i = (n) - 1; ~i; --i)
#define all(v) (v).begin(), (v).end()
using ll = long long;

int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
}

Debug

#ifndef MINE_DEBUG
#define MINE_DEBUG

#include <bits/stdc++.h>
using namespace std;

namespace debug_helper {

ostream& operator<<(ostream& os, __int128 x) {
  if (x >= 0) {
    if (x > 9) os << x / 10;
    os << char(x % 10 + 48);
  } else {
    os << '-';
    if (x < -9) os << -x / 10;
    os << char(48 - x % 10);
  }
  return os;
}
ostream& operator<<(ostream& os, unsigned __int128 x) {
  if (x > 9) os << x / 10;
  os << char(x % 10 + 48);
  return os;
}

template <class T1, class T2>
ostream& operator<<(ostream& os, pair<T1, T2> p) {
  return os << '{' << p.first << ", " << p.second << '}';
}

template <size_t P, enable_if_t<P == 1>*, class... Args>
void tuple_helper(ostream& os, tuple<Args...> tp);
template <size_t P, enable_if_t<P != 1>*, class... Args>
void tuple_helper(ostream& os, tuple<Args...> tp);
template <class... Args>
ostream& operator<<(ostream& os, tuple<Args...> x) {
  os << '{';
  tuple_helper<tuple_size<tuple<Args...>>::value,
                nullptr, Args...>(os, x);
  return os << '}';
}

template <class T> void list_helper(ostream& os, T v);
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
  list_helper(os, v); return os;
}
template <class T>
ostream& operator<<(ostream& os, list<T> v) {
  list_helper(os, v); return os;
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
  list_helper(os, v); return os;
}
template <class T>
ostream& operator<<(ostream& os, multiset<T> v) {
  list_helper(os, v); return os;
}
template <class T>
ostream& operator<<(ostream& os, unordered_set<T> v) {
  list_helper(os, v); return os;
}
template <class T>
ostream& operator<<(ostream& os, unordered_multiset<T> v) {
  list_helper(os, v); return os;
}

template <class T> void map_helper(ostream& os, T v);
template <class T1, class T2>
ostream& operator<<(ostream& os, map<T1, T2> v) {
  map_helper(os, v); return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, unordered_map<T1, T2> v) {
  map_helper(os, v); return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, multimap<T1, T2> v) {
  map_helper(os, v); return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, unordered_multimap<T1, T2> v) {
  map_helper(os, v); return os;
}

template <class T>
void list_helper(ostream& os, T v) {
  os << '{';
  bool flag = true;
  for (auto x : v) {
    if (flag) flag = false;
    else os << ", ";
    os << x;
  }
  os << '}';
}
template <class T>
void map_helper(ostream& os, T v) {
  os << '{';
  bool flag = true;
  for (auto x : v) {
    if (flag) flag = false;
    else os << ", ";
    os << x.first << ": " << x.second;
  }
  os << '}';
}
template <size_t P, enable_if_t<P == 1>*, class... Args>
void tuple_helper(ostream& os, tuple<Args...> tp) {
  os << get<0>(tp);
}
template <size_t P, enable_if_t<P != 1>*, class... Args>
void tuple_helper(ostream& os, tuple<Args...> tp) {
  tuple_helper<P - 1, nullptr, Args...>(os, tp);
  os << ", " << get<P - 1>(tp);
}

template <class T> void debug(T x) { cerr << x; }
template <class T, class... Args>
void debug(T x, Args... args) {
  cerr << x << ", ";
  debug(args...);
}

}

#define debug(...) \
cerr << #__VA_ARGS__ " = ", \
debug_helper::debug(__VA_ARGS__), \
cerr << '\n'

#endif