专栏文章

题解：P13867 [SWERC 2020] Unique Activities

EExscallop64_
P13867题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minlgg1g
此快照首次捕获于
2025/12/02 04:20
3 个月前
此快照最后确认于
2025/12/02 04:20
3 个月前
查看原文

题目简述

给定一个字符串 ss，求 ss 最短没有重复出现的子串，若有多个长度相同的子串，输出起始位置最小的那个。

思路

令 ∣s∣=n\vert s \vert = n。
首先注意到一个性质，如果存在合法的长度为 ll 的子串，那么也一定存在合法的长度为 l+1l+1 的子串。其实就是个小思维点，画图考虑将所有长度为 ll 的子串往后延伸一个就很显然了。
那么，我们就可以二分答案 ll。对于所有长度为 ll 的子串，看是否有只出现了一次的子串，可以用哈希 + map 判断。

时间复杂度

  • 时间复杂度：二分答案 O(log⁡n)O(\log n)，如果使用 unordered_map 并假设为 O(1)O(1) 不计复杂度，则判断部分为 O(n)O(n)，总复杂度 O(nlog⁡n)O(n \log n)。
  • 空间复杂度：O(n)O(n)。
CPP
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

const int MAXN = 3e5 + 5, BASE = 64007;
const ll MOD = 2999999929;

int n;
ll power[MAXN], h[MAXN];
string s;
unordered_map<ll, int> cnt;

int Query(int l, int r){
  return (h[r] - h[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
}

int Check(int len){
  cnt.clear();
  for(int i = 1; i <= n - len + 1; i++){
    cnt[Query(i, i + len - 1)]++;
  }
  for(int i = 1; i <= n - len + 1; i++){
    if(cnt[Query(i, i + len - 1)] == 1) return i;
  }
  return 0;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  n = s.size(), s = "#" + s;
  power[0] = 1;
  for(int i = 1; i <= n; i++){
    power[i] = power[i - 1] * BASE % MOD;
    h[i] = (h[i - 1] * BASE % MOD + s[i] - 'A') % MOD;
  }
  int l = 0, r = n;
  while(l < r){
    int mid = (l + r) >> 1;
    Check(mid) ? r = mid : l = mid + 1;
  }
  cout << s.substr(Check(l), l);
  return 0;
}

后记

给一些字符串哈希的小技巧吧，适合一些哈希新手。
虽然这题不卡哈希，但是不难想到 CF 特别喜欢拐卖 998244353998244353，109+710^9+7，1926081319260813 这些常用质数，考场上怎么避免被卡呢？
当然你可以使用双哈希，但是码量翻倍，当你懒的再找质数是个好办法。
也可以赛前积累一些怪异质数，比如 993244853993244853，11451400191145140019，最好好记且不广为人知。
不过我经常临场找，我们知道 1∼n1 \sim n 中质数的个数约为 O(nln⁡n)O(\frac{n}{\ln n})，那么大约每 ln⁡n\ln n 个数就会有一个质数！那么我们不妨随机从一个数 xx 往后找，一直找到质数为止，这样大概找 ln⁡x\ln x 次就可以找到，暴力判断质数即可，一两分钟就可以找到一个较好的质数，像这样：
CPP
#include<bits/stdc++.h>

using namespace std;

int n;

bool Check(int n){
  if(n <= 2) return n == 2;
  for(int i = 2; i * i <= n; i++){
    if(n % i == 0) return 0;
  }
  return 1;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  while(!Check(n)) n++;
  cout << n;
  return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...