🌓
Ftt2333's Nest

Ftt2333's Nest

P4094

创建于2022-10-15

题目大意

给你一个字符串 SS,有 qq 次询问。

每次询问给出四个数 aabbccdd

maxalrblcp(S[lr],S[cd])\max_{a\le l\le r\le b}lcp(S[l\ldots r],S[c\ldots d])

后缀数组

解题思路

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

也就是说 lcp(S[posn],S[cn])midlcp(S[pos\ldots n],S[c\ldots n])\ge mid

P2178

创建于2022-10-15

题目大意

给你一个字符串 SS,每个位置都有一个权值 aia_i

定义 ppqq 两个位置 rr 相似表示 S[pp+r1]=S[qq+r1]S[p\ldots p+r-1]=S[q\ldots q+r-1]

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

  • 有多少对 (p,q)(p,q)rr 相似的。
  • 最大的 ap×aqa_p \times a_q 满足 (p,q)(p,q)rr 相似的。

解题思路

考虑倒着建 SAMSAM,发现 (p,q)(p,q)rr 相似的等价于存在一个 endposendpos 等价类包含 ppqq,并且 minlenrlenminlen\le r \le len

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

关于这个主题

创建于2022-10-14

源码链接

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: 

一个有意思的程序

创建于2022-10-11

功能介绍

输入一个 66 位数,他会输出一个 77 位数。

代码

/*
* @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有惊喜

我的缺省源

创建于2022-08-07

献上代码!

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

Powered by Hexo, theme by Facter