文章目录

洛谷 P3426 SZA-Template 做题笔记

发布于

题意

给定一个长度为 $n$ 的只包含小写字母的字符串 $S$。现在要在纸上印出字符串 $S$。
你可以刻一个印章,印章每使用一次,就会将印章上的所有字母印到纸上。同一个位置的相同字符可以印多次。但是,因为印上去的东西不能被抹掉,在同一位置上印不同字符是不允许的。

求印章的最小长度。

例如:用 $\texttt{aba}$ 这个印章不可以印出 $\texttt{abcba}$。

$1 \leq n \leq 5 \times 10^5$

题解

考虑 DP。设 $f\left(i\right)$ 表示只取 $S$ 的前 $i$ 个字符的答案。

容易发现,$f\left(i\right)$ 的值,只有两种可能:$i$ 或 $f\left(next\left(i\right)\right)$。

其中的 $next\left(i\right)$ 表示 $S$ 中前 $i$ 个字符的公共前后缀数量(即 KMP 中的 $\texttt{next}$ 数组)。

原因是,要覆盖前 $i$ 个,起码覆盖前 $next\left(i\right)$ 个。

考虑 $f\left(i\right)$ 什么时候取 $f\left(next\left(i\right)\right)$:因为前缀 $i$ 的后缀为 $next\left(i\right)$,所以我们最多在后面接上 $next\left(i\right)$ 这么长的字符串,也就是如果存在一个 $j$,使得 $f\left(j\right) = f\left(next\left(i\right)\right)$ 且 $i - next\left(i\right) \leq j$,那么 $f\left(i\right)$ 就取 $f\left(next\left(i\right)\right)$。

代码

// By rbtree (https://rbtr.ee) :\
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <valarray>
#include <vector>
#define ra _Read_Int()
#define rc _Read_Char()
#define rs _Read_String()
#define rr _READ_RAW_::_Rd()
#define iotop _Get_IO_Top()
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#define dputs(...)
#endif

using tp = long long;
tp _Read_Int();
char _Read_Char();
bool _Get_IO_Top();
std::string _Read_String();
namespace _READ_RAW_ {
char _Rd();
}  // namespace _READ_RAW_
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp _BUF_SIZE_ = 2179217;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

namespace __SOL__ {
void main([[maybe_unused]] size_t __CASE__) {  // :/
  constexpr tp Hat_N = 5e5 + 3;
  string s = ' ' + rs;
  tp n = s.size() - 1;
  array<tp, Hat_N> next, f, app;
  next[0] = -1;
  f[1] = 1;
  app.fill(0);
  app[1] = 1;
  for (tp i = 2, j = 0; i <= n; next[i++] = ++j) {
    for (; ~j && s[j + 1] != s[i]; j = next[j]) {
    }
  }
  for (tp i = 2; i <= n; ++i) {
    app[f[i] = app[f[next[i]]] >= i - next[i] ? f[next[i]] : i] = i;
  }
  printf("%lld\n", f[n]);
}  // :)
}  // namespace __SOL__

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

signed main() {
  tp __MTCS__ = ::__MTCS__ ? ra : 1;
  for (tp __i = 1; __i <= __MTCS__; ++__i) {
    __SOL__::main(__i);
  }
  return EXIT_SUCCESS;
}

namespace _READ_RAW_ {
std::array<char, _BUF_SIZE_> _BUF_;
std::array<char, _BUF_SIZE_>::iterator __Cur, __End = __Cur + 1;

char _Rd() {
  if (++__Cur == __End) {
    __Cur = _BUF_.begin();
    __End = __Cur + fread(_BUF_.begin(), 1, _BUF_SIZE_, stdin);
  }
  return *__Cur;
}
}  // namespace _READ_RAW_

bool _Get_IO_Top() {
  if (_READ_RAW_::__Cur + 1 == _READ_RAW_::__End) {
    _READ_RAW_::__Cur = _READ_RAW_::_BUF_.begin();
    _READ_RAW_::__End = _READ_RAW_::__Cur +
                        fread(_READ_RAW_::_BUF_.begin(), 1, _BUF_SIZE_, stdin);
    return _READ_RAW_::__Cur-- != _READ_RAW_::__End;
  }
  return 1;
}
tp _Read_Int() {
  bool __neg(0);
  char __c(_READ_RAW_::_Rd());
  tp __val;
  for (; __c < 48 || __c > 57; __c = _READ_RAW_::_Rd()) {
    __neg = __c == 45;
  }
  __val = __c & 15;
  for (__c = _READ_RAW_::_Rd(); __c > 47 && __c < 58; __c = _READ_RAW_::_Rd()) {
    __val = __val * 10 + (__c & 15);
  }
  return __neg ? ~__val + 1 : __val;
}
char _Read_Char() {
  char __c(_READ_RAW_::_Rd());
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  return __c;
}
std::string _Read_String() {
  char __c(_READ_RAW_::_Rd());
  std::string __val;
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  do {
    __val.push_back(__c);
    __c = _READ_RAW_::_Rd();
  } while (__c != 32 && __c != 10 && __c != 13);
  return __val;
}

/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/

暂无评论

发表评论