2023CCPC网络赛(A E)
2023CCPC网络赛(A E)
The 2nd Universal Cup. Stage 3: Binjiang - Dashboard - Contest - Universal Cup Judging System
A. Almost Prefix Concatenation
思路:首先考虑如何求出每个位置允许失配一次的LCP长度 , 可以二分哈希求LCP , 即先二分一次求未失配的位置 , 向右扩展一位再次二分。
求出每个位置允许失配一次的LCP长度后考虑如何维护贡献 , 考虑最暴力的维护方式:
设计状态 dp[i][j] 为 i 位置及其后缀字符串分成 j 份 的方案数 , 这样显然很好转移。 但是时空双复杂度都是O(n^2) ,考虑优化 , 对于时间复杂度 , 我们不难发现 , 我们每次转移的位置都是一个区间 , 考虑后缀和优化 , O(1) 的进行转移。 对于空间复杂度 ,显然很难优化。转换思路 , 考虑直接维护平方贡献。
n o w 1 [ i ] 表示 i 所在后缀字符串划分的方案数 now1[i] ~表示 i所在后缀字符串划分的方案数 now1[i] 表示i所在后缀字符串划分的方案数
n o w 2 [ i ] 表示 i 所在后缀字符串划分的方案长度和 now2[i] ~表示i所在后缀字符串划分的方案长度和 now2[i] 表示i所在后缀字符串划分的方案长度和
n o w 3 [ i ] 表示 i 所在后缀字符串划分的方案长度平方和 now3[i] ~表示i所在后缀字符串划分的方案长度平方和 now3[i] 表示i所在后缀字符串划分的方案长度平方和
对于位置 i , 其转移区间显然是[i + 1 , i + lcp[i]] , 所以我们要对上面三个数组维护后缀和
s u f 1 [ i ] 为 n o w 1 [ i ] 的后缀和 suf1[i]~为now1[i]的后缀和 suf1[i] 为now1[i]的后缀和
s u f 2 [ i ] 为 n o w 2 [ i ] 的后缀和 suf2[i]~为now2[i]的后缀和 suf2[i] 为now2[i]的后缀和
s u f 3 [ i ] 为 n o w 3 [ i ] 的后缀和 suf3[i]~为now3[i]的后缀和 suf3[i] 为now3[i]的后缀和
对于转移:
不妨设 l = i + 1 , r = i + l c p [ i ] 不妨设 ~l=i+1,~r=i+lcp[i] 不妨设 l=i+1, r=i+lcp[i]
n o w 1 [ i ] = s u f 1 [ l ] − s u f 1 [ r + 1 ] (方案数直接转移) now1[i] = suf1[l] - suf1[r+1](方案数直接转移) now1[i]=suf1[l]−suf1[r+1](方案数直接转移)
n o w 2 [ i ] = s u f 2 [ l ] − s u f 2 [ r + 1 ] + n o w 1 [ i ] (每种方案长度都加 1 ) now2[i] = suf2[l] - suf2[r+1]+now1[i](每种方案长度都加1) now2[i]=suf2[l]−suf2[r+1]+now1[i](每种方案长度都加1)
n o w 3 [ i ] = ( s u f 3 [ l ] − s u f 3 [ r + 1 ] ) + 2 ∗ ( s u f 2 [ l ] − s u f 2 [ r + 1 ] ) + ( s u f 1 [ l ] − s u f 1 [ r + 1 ] ) [ 考虑 ( n + 1 ) 2 = n 2 + 2 ∗ n + 1 ] now3[i] = (suf3[l] - suf3[r+1])+2*(suf2[l]-suf2[r+1])+(suf1[l]-suf1[r+1])~~[考虑(n+1)^2=n^2+2*n+1] now3[i]=(suf3[l]−suf3[r+1])+2∗(suf2[l]−suf2[r+1])+(suf1[l]−suf1[r+1]) [考虑(n+1)2=n2+2∗n+1]
注意点:注意求LCP的时候双哈希即可 , 单哈希过不去。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e18;
const int N = 1e6 + 10;
const int mod = 998244353;
typedef pair<int,int>PII;
int n , m , lcp[N];
string s , t;const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int Base = 131;int base1[N] , ht1[N] , base2[N] , ht2[N] , hs1[N] , hs2[N];
int suf1[N] , suf2[N] , suf3[N];
int now1[N] , now2[N] , now3[N];inline void init_hash(int n){base1[0] = base2[0] = 1;for(int i = 1 ; i <= n ; i ++) base1[i] = base1[i - 1] * Base % mod1;for(int i = 1 ; i <= n ; i ++) base2[i] = base2[i - 1] * Base % mod2;
}int add(int x , int y) {x %= mod;y %= mod;return (x + y) % mod;
}
int reduce(int x , int y) {x %= mod;y %= mod;return ((x - y) % mod + mod) % mod;
}inline PII get_s(int l,int r){int x = ((hs1[r] - hs1[l] * base1[r - l]) % mod1 + mod1) % mod1;int y = ((hs2[r] - hs2[l] * base2[r - l]) % mod2 + mod2) % mod2;return {x , y};
}inline PII get_t(int l,int r){int x = ((ht1[r] - ht1[l] * base1[r - l]) % mod1 + mod1) % mod1;int y = ((ht2[r] - ht2[l] * base2[r - l]) % mod2 + mod2) % mod2;return {x , y};
}signed main(){cin >> s >> t;n = s.size();m = t.size();init_hash(max(n , m));hs1[0] = hs2[0] = 0;for(int i = 1 ; i <= n ; i ++) hs1[i] = (hs1[i - 1] * Base % mod1 + s[i - 1]) % mod1;for(int i = 1 ; i <= n ; i ++) hs2[i] = (hs2[i - 1] * Base % mod2 + s[i - 1]) % mod2;ht1[0] = ht2[0] = 0;for(int i = 1 ; i <= m ; i ++) ht1[i] = (ht1[i - 1] * Base % mod1 + t[i - 1]) % mod1;for(int i = 1 ; i <= m ; i ++) ht2[i] = (ht2[i - 1] * Base % mod2 + t[i - 1]) % mod2;for(int i = 0 ; i < n ; i ++) {int l = i , r = min(i + m - 1 , n - 1) , mid = 0;while(l <= r) {mid = (l + r) >> 1;if(get_s(l , mid + 1) != get_t(l - i , mid + 1 - i)) r = mid - 1;else l = mid + 1;}int ll = l , rr = min(i + m - 1 , n - 1) , midd = 0;if(ll > rr) { lcp[i] = ll - i; continue; }ll += 1;if(ll > rr) { lcp[i] = ll - i; continue; }while(ll <= rr) {midd = (ll + rr) >> 1;if(get_s(ll , midd + 1) != get_t(ll - i , midd + 1 - i)) rr = midd - 1;else ll = midd + 1;}lcp[i] = ll - i;}suf1[n] = 1;for(int i = n - 1 ; i >= 0 ; i -- ){int l = i + 1 , r = i + lcp[i];now1[i] = reduce(suf1[l] , suf1[r + 1]);now2[i] = add(reduce(suf2[l] , suf2[r + 1]) , now1[i]);now3[i] = add(add(reduce(suf3[l] , suf3[r + 1]) , 2 * reduce(suf2[l] , suf2[r + 1])) , reduce(suf1[l] , suf1[r + 1]));suf1[i] = add(suf1[i + 1] , now1[i]);suf2[i] = add(suf2[i + 1] , now2[i]);suf3[i] = add(suf3[i + 1] , now3[i]); }cout << now3[0] << "\n";return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);/*
g1[i] i 点所在后缀切割方案数
g2[i] i 点所在后缀切割方案长度和
g3[i] i 点所在后缀切割方案长度平方和suf1[i] :now1[i] 的后缀和
suf2[i] :now2[i] 的后缀和
suf3[i] :now3[i] 的后缀和
*/
E. Robot Experiment
对于每个位置显然会有三个状态:
状态 1 :未走过 状态1:未走过 状态1:未走过
状态 2 :不能走 状态2:不能走 状态2:不能走
状态 3 :必须走 状态3:必须走 状态3:必须走
枚举所有可能 , 状态一进行讨论 , 状态二三直接搜索即可。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF = 9e18;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int vis[110][110];
/*
0 可讨论
1 不能走
-1 必须走
*/int n ;
string s;
set<pair<int , int>>st;
void dfs(int x , int y , int pos) {if(pos == n) {st.insert({x , y});return ;}int xx = x , yy = y;if(s[pos] == 'L') xx -= 1;if(s[pos] == 'R') xx += 1;if(s[pos] == 'U') yy += 1;if(s[pos] == 'D') yy -= 1;if(vis[xx + 50][yy + 50] == 0) {vis[xx + 50][yy + 50] = 1;dfs(x , y , pos + 1);vis[xx + 50][yy + 50] = 0;vis[xx + 50][yy + 50] = -1;dfs(xx , yy , pos + 1);vis[xx + 50][yy + 50] = 0;}if(vis[xx + 50][yy + 50] == 1) {dfs(x , y , pos + 1);}if(vis[xx + 50][yy + 50] == -1) {dfs(xx , yy , pos + 1);}}signed main(){IOScin >> n >> s;vis[50][50] = -1;dfs(0 , 0 , 0);cout << st.size() << "\n";for(auto [x , y] : st) {cout << x << " " << y << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
相关文章:
2023CCPC网络赛(A E)
2023CCPC网络赛(A E) The 2nd Universal Cup. Stage 3: Binjiang - Dashboard - Contest - Universal Cup Judging System A. Almost Prefix Concatenation 思路:首先考虑如何求出每个位置允许失配一次的LCP长度 , 可以二分哈希求LCP , 即…...
使用 python 检测泛洪攻击的案例
使用 python 检测泛洪攻击的案例 本案例只使用python标准库通过执行命令来监控异常请求, 并封锁IP, 不涉及其他第三方库工具. import os import time from collections import Counter# 1、update 命令, 采集CPU的平均负载 def get_cpu_load():"""uptime 命令…...
SCROLLINFO scrollInfo; 2023/10/5 下午3:38:53
2023/10/5 下午3:38:53 SCROLLINFO scrollInfo;scrollInfo.cbSize = sizeof(SCROLLINFO);scrollInfo.fMask = SIF_ALL;//scrollInfo.nMin = 0; // 最小位置//scrollInfo.nMax = nRowCountToShow; // 最大位置//scrollInfo.nPage = nRowCountToShow; // 页面大小//scrollInf…...
Python--控制台获取输入与正则表达式
前言一、控制台获取输入1.1 字符串输入1.2 整数输入1.3 浮点数输入1.4 布尔值输入1.5 列表输入1.6 汇总 二、正则表达式2.1 匹配数字2.2 模式检查2.3 替换字符2.4 切分字符串2.5 搜索并提取匹配的部分2.6 使用捕获组提取匹配的部分2.7 非贪婪匹配2.8 忽略大小写匹配2.9 使用预定…...

网络基础知识面试题1
VC++常用功能开发汇总(专栏文章列表,欢迎订阅,持续更新...)https://blog.csdn.net/chenlycly/article/details/124272585C++软件异常排查从入门到精通系列教程(专栏文章列表,欢迎订阅,持续更新...)...

JavaScript系列从入门到精通系列第十五篇:JavaScript中函数的实参介绍返回值介绍以及函数的立即执行
文章目录 一:函数的参数 1:形参如何定义 2:形参的使用规则 二:函数的返回值 1:函数返回值如何定义 2:函数返回值种类 三:实参的任意性 1:方法可以作为实参 2:将匿…...

js中的原型链
编写思路: 简单介绍构造函数介绍原型对象原型对象、实例的关系,从而引出原型链的基本概念 原型链基本思想是利用原型让一个引用类型继承另一个引用类型的属性和方法。 1. 什么是构造函数 构造函数本身跟普通函数一样,也不存在定义构造函数…...

一文搞懂APT攻击
APT攻击 1. 基本概念2. APT的攻击阶段3. APT的典型案例参考 1. 基本概念 高级持续性威胁(APT,Advanced Persistent Threat),又叫高级长期威胁,是一种复杂的、持续的网络攻击,包含高级、长期、威胁三个要素…...
在pandas中通过一列数据映射出另一列的几种思路和方法
如果一句话中出现某个品牌的关键词,那么就将该品牌进行提取,开始我的做法是写了很多elif,如下: def brand_describe(x):if TRUM in x.upper():return "通快"elif BYSTRONIC in x.upper():return "百超"elif …...

数据分析视角中的商业分析学习笔记
数据分析一大堆,结果却是大家早就知道的结论?是工具和方法出问题了吗?真正原因可能是你的思维有误区。 为什么分析的这么辛苦,得出的结论大家早知道,谁谁都不满意?核心原因有3个: 分析之前&am…...

剑指offer——JZ26 树的子结构 解题思路与具体代码【C++】
一、题目描述与要求 树的子结构_牛客题霸_牛客网 (nowcoder.com) 题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构) 假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2}&…...

NEFU数字图像处理(1)绪论
一、简介 1.1什么是数字图像 图像是三维场景在二维平面上的影像。根据其存储方式和表现形式,可以将图像分为模拟图像和数字图像两大类 图像处理方法:光学方法、电子学方法 模拟图像:连续的图像数字图像:通过对时间上和数值上连续…...

数值分析学习笔记——绪论【华科B站教程版本】
绪论 数值分析概念 用计算机求解数学问题的数值方法和理论 三大科学研究方法 实验理论分析科学计算(用计算机去辅助研究):数值方法计算机 解析解和近似解 解析解:使用数学方法求出或推导出的结果,往往可以求解出…...

节日灯饰灯串灯出口欧洲CE认证办理
灯串(灯带),这个产品的形状就象一根带子一样,再加上产品的主要原件就是LED,因此叫做灯串或者灯带。2022年,我国灯具及相关配件产品出口总额超过460亿美元。其中北美是最大的出口市场。其次是欧洲市场&#…...

一线大厂Redis高并发缓存架构实战与性能优化
文章目录 一、redis主从架构锁失效问题分析二、从CAP角度剖析redis与zookeeper分布式锁区别三、redlock分布式锁原理与存在的问题分析四、大促场景如何将分布式锁性能提升100倍五、高并发redis架构代码实战 一、redis主从架构锁失效问题分析 我们都知道,一般的互联…...

PHP 行事准则:allow_url_fopen 与 allow_url_include
文章目录 参考环境allow_url_fopenallow_url_fopen 配置项操作远程文件file 协议 allow_url_includeallow_url_include 配置项 allow_url_include 与 allow_url_fopen区别联系默认配置配置项关闭所导致异常运行时配置ini_set()限制 参考 项目描述搜索引擎Bing、GoogleAI 大模型…...

Replicate + ngrok云端大模型API实现教程
ChatGPT 的诞生预示着人工智能和机器学习领域的新时代。 日新月异,Hugging Face 不断推出突破性的语言模型,重新定义人机交互的界限。欢迎来到未来! 当然,有很多选项可以对它们进行推断。在本文中,我将告诉大家如何使…...
蓝桥等考Python组别十四级005
蓝桥等考Python组别十四级 第一部分:选择题 1、Python L14 (15分) 运行下面程序,输出的结果是( )。 d = {1 : one, 2 : two, 3 : three, 4 : four} print(d[2]) onetwothreefour正确答案:B...

Linux 本地 Docker Registry本地镜像仓库远程连接
Linux 本地 Docker Registry本地镜像仓库远程连接 Docker Registry 本地镜像仓库,简单几步结合cpolar内网穿透工具实现远程pull or push (拉取和推送)镜像,不受本地局域网限制! 1. 部署Docker Registry 使用官网安装方式,docker命令一键启动,该命令启动一个regis…...

二十九、高级IO与多路转接之epollreactor(收官!)
文章目录 一、Poll(一)定义(二)实现原理(三)优点(四)缺点 二、I/O多路转接之epoll(一)从网卡接收数据说起(二)如何知道接收了数据&…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...