首页 > 其他分享 >#473. 编辑 & P5479 [BJOI2015] 隐身术

#473. 编辑 & P5479 [BJOI2015] 隐身术

时间:2024-11-08 08:50:23浏览次数:3  
标签:const int BJOI2015 mid st 473 maxN gets 隐身术

模拟赛出到加强版了,一点不会所以记录下。


枚举每个后缀。设 \(f_{i,j}\) 为操作 \(i\) 次,长度增加 \(j\),即插入的次数减删除的次数,所能匹配到的最大位置。也就是 \(A\) 的前 \(f_{i,j}\) 位匹配 \(B\) 的前 \(f_{i,j}+j\) 位。

考虑转移。假如已经操作完了,那显然有 \(f_{i,j} \gets f_{i,j}+\text{LCP}(A[f_{i,j}+1:|A|],B[f_{i,j}+j+1:|B|])\)。

进行操作的转移:

  • 替换:\(f_{i+1,j} \gets f_{i,j}+1\)
  • 删除:\(f_{i+1,j-1} \gets f_{i,j}+1\)
  • 添加:\(f_{i+1,j+1}\gets f_{i,j}\)

一些解释:添加操作的时候,\(A\) 多了一个虚拟的点,但最后一个匹配到的真正存在的点还是 \(f_{i,j}\)。删除操作的时候,那个被删的点也看做完成了匹配。

转移时注意多判边界。

LCP 可以直接用二分哈希,其实 SA 可以更快,但二分哈希完全够用。

最后统计答案记得找到最小操作次数后要跳出循环。

复杂度 \(O(nk^2\log n)\)。如果用 SA 的话是 \(O(nk^2)\)。

#include <bits/stdc++.h>

using namespace std;

using ubt = unsigned long long;

const int maxN = 1e5 + 7;

int k;
int n, m;
string s, t;

const ubt Base = 13331;
ubt H[maxN], S[maxN], T[maxN];
void inithash() {
  H[0] = 1, S[0] = T[0] = 0;
  for (int i = 1; i <= n || i <= m; i++) {
    if (i <= n) S[i] = S[i - 1] * Base + s[i];
    if (i <= m) T[i] = T[i - 1] * Base + t[i];
    H[i] = H[i - 1] * Base;
  }
}
ubt gets(int l, int r) {
  return S[r] - S[l - 1] * H[r - l + 1];
}
ubt gett(int l, int r) {
  return T[r] - T[l - 1] * H[r - l + 1];
}

int LCP(int ss, int st) {
  int l = 1, r = min(n - ss + 1, m - st + 1);
  int pos = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (gets(ss, ss + mid - 1) == gett(st, st + mid - 1))
      l = mid + 1, pos = mid;
    else r = mid - 1;
  }
  return pos;
}

const int inf = 1e9;
int ans[7];
int st;
int f[7][17];
void Main() {
  memset(f, ~0x3f, sizeof(f));
  f[0][k] = 0;
  for (int i = 0; i <= k; i++)
    for (int j = 0; j <= k * 2; j++) {
      if (f[i][j] <= -inf) continue;
      int p = j - k;
      if (f[i][j] + p < 0) continue;
      if (st - 1 + f[i][j] + p > m) continue;
      f[i][j] += LCP(f[i][j] + 1, st - 1 + f[i][j] + p + 1);
      if (i != k) {
        if (j)
          f[i + 1][j - 1] = max(f[i + 1][j - 1], min(f[i][j] + 1, n));
        if (f[i][j] != n)
          f[i + 1][j] = max(f[i + 1][j], min(f[i][j] + 1, n));
        if (j != k * 2)
          f[i + 1][j + 1] = max(f[i + 1][j + 1], f[i][j]);
      }
    }

  for (int i = 0; i <= k * 2; i++)
    for (int j = 0; j <= k; j++)
      if (f[j][i] == n)
      { ans[j]++; break; }
}

int main() {
  //ifstream cin("in.in");
  //ofstream cout("out.out");

  cin >> k >> s >> t;
  n = s.length(), m = t.length();
  s = '@' + s, t = '$' + t;

  inithash();

  for (st = 1; st <= m; st++)
    Main();

  int res = 0;
  for (int i = 0; i <= k; i++)
    res += ans[i];
  cout << res << '\n';
}

标签:const,int,BJOI2015,mid,st,473,maxN,gets,隐身术
From: https://www.cnblogs.com/ccxswl/p/18534359

相关文章

  • 洛谷题单指南-字符串-P4735 最大异或和
    原题链接:https://www.luogu.com.cn/problem/P4735题意解读:已知长度为n的数组a[],要在l~r范围找到一个p,使得a[p]^a[p+1]^...^a[n]^x最大,求这个最大的异或值。解题思路:1、利用前缀和将问题转化设s[]是a[]的前缀异或数组,要计算a中一段范围l~r的异或,可以借助于s由于s[r]=a[0]^a[......
  • 2021年10月自考《数据库系统原理》04735试题
    目录一.选择题二.填空题三.简答题四.综合题五.设计题一.选择题1.以下不属于数据中存储数据的特点是(书中)P28页A.永久存储 B.集中管理 C.有组织D.可共享2.数据库(DB),数据库系统(DBS)和数据库管理系统(DBMS)三者之间的关系是(书中)P29页A.DBS包括DB和DBMSB.DBMS包括DB......
  • 基于SpringBoot及Vue的银行卡业务系统的设计与实现---附源码53473
    目 录摘 要1绪论1.1研究背景1.2研究意义1.3论文结构与章节安排2 银行卡业务系统系统分析2.1可行性分析2.2系统流程分析2.2.1数据增加流程2.2.2数据修改流程2.2.3数据删除流程2.3 系统功能分析2.3.1功能性分析2.3.2非功能性分析......
  • 基于SaaS的小区物业管理系统设计与实现--47357(免费领源码)可做计算机毕业设计JAVA、PHP
    摘 要本论文主要论述了如何使用SpringBoot开发一个基于SaaS的小区物业管理系统小程序,本系统将严格按照软件开发流程进行各个阶段的工作,面向对象编程思想进行项目开发。在引言中,作者将论述小区物业管理系统小程序的当前背景以及系统开发的目的,后续章节将严格按照软件开发流程......
  • P4734 [BalticOI 2015] Hacker
    题目大意详细题目传送门思路对于这种题目一般可以先断环成链。发现先手所得到的值是一个长度为\(\lceil\frac{n}{2}\rceil\)的区间,我们希望让它的元素之和能取到最大,但发现后手会让我们取不到最大。假设我们从第\(i\)台电脑开始,那么后手一定会让我们取到一个所有经过这......
  • C++竞赛初阶L1-14-第六单元-数组(31~33课)543: T456473 年龄与疾病
    题目内容某医院进行一项研究,想知道某项疾病是否与年龄有关。因此对以往的诊断记录进行整理,统计0-18、19-35、36-60、61及以上这四个年龄段的患者人数占总患者人数的比例。输入格式输入共 2 行。第一行包含一个整数 N(0<n≤100),表示总患者人数。第二行包含 N 个......
  • 全新Versal HBM 系列自适应 SoC:XCVH1542-1MSEVSVA3697、XCVH1542-2MLELSVA4737、XCVH1
    系列概述VersalHBM系列具有快速内存、安全连接和自适应计算的异构集成,可消除内存绑定的计算密集型工作负载(如机器学习、数据库加速、下一代防火墙和高级网络测试仪)的处理和内存瓶颈。它从底层开始构建,以适应不断发展的算法、协议和数据速率。与VersalPremium系列*相比,通过集......
  • 2024736DP专项练习赛
    前言比赛链接榜上那个冒着蓝光的就是我……提交记录跟答辩一样……\(\color{#F8BBD0}Heldivis%%%%%%%%%%%%%%%%%%%\)吐槽一下,虽然挂着DP专题赛的名字,但除了T1T3以外,全是记搜题(虽然好像只有四道题来着)。T1签到题,\(n\)范围很小,先用区间dp求出任意区间达到最终状态......
  • 【模板】树同构([BJOI2015]树的同构)
    一段合法的括号序和一棵有根树唯一对应,具体而言,考虑生成括号序的过程,从根节点出发,遇到左括号就向下走一步,遇到右括号就向上走一步由于树上的一个节点可能有多个子节点,因此在不规定访问顺序的情况下,同一棵树有多种不同的括号序列点击查看代码#include<bits/stdc++.h>using......
  • [题解]CF1473D Program
    思路因为此题目中对于数的更新只能为\(1\),所以,如果我们找到了\([1,l-1]\)与\([r+1,n]\)中能获得的两个极值即可。我们为\(S\)赋予权值,用一个数组\(a\)储存:如果\(S_i\)为+,则其权值为\(1\)。否则其权值为\(-1\)。那么,在第\(i\)次操作后,能产生的数是\(\s......