当前位置: 首页 > news >正文

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+2n+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 思路&#xff1a;首先考虑如何求出每个位置允许失配一次的LCP长度 &#xff0c; 可以二分哈希求LCP &#xff0c; 即…...

使用 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中函数的实参介绍返回值介绍以及函数的立即执行

文章目录 一&#xff1a;函数的参数 1&#xff1a;形参如何定义 2&#xff1a;形参的使用规则 二&#xff1a;函数的返回值 1&#xff1a;函数返回值如何定义 2&#xff1a;函数返回值种类 三&#xff1a;实参的任意性 1&#xff1a;方法可以作为实参 2&#xff1a;将匿…...

js中的原型链

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

一文搞懂APT攻击

APT攻击 1. 基本概念2. APT的攻击阶段3. APT的典型案例参考 1. 基本概念 高级持续性威胁&#xff08;APT&#xff0c;Advanced Persistent Threat&#xff09;&#xff0c;又叫高级长期威胁&#xff0c;是一种复杂的、持续的网络攻击&#xff0c;包含高级、长期、威胁三个要素…...

在pandas中通过一列数据映射出另一列的几种思路和方法

如果一句话中出现某个品牌的关键词&#xff0c;那么就将该品牌进行提取&#xff0c;开始我的做法是写了很多elif&#xff0c;如下&#xff1a; def brand_describe(x):if TRUM in x.upper():return "通快"elif BYSTRONIC in x.upper():return "百超"elif …...

数据分析视角中的商业分析学习笔记

数据分析一大堆&#xff0c;结果却是大家早就知道的结论&#xff1f;是工具和方法出问题了吗&#xff1f;真正原因可能是你的思维有误区。 为什么分析的这么辛苦&#xff0c;得出的结论大家早知道&#xff0c;谁谁都不满意&#xff1f;核心原因有3个&#xff1a; 分析之前&am…...

剑指offer——JZ26 树的子结构 解题思路与具体代码【C++】

一、题目描述与要求 树的子结构_牛客题霸_牛客网 (nowcoder.com) 题目描述 输入两棵二叉树A&#xff0c;B&#xff0c;判断B是不是A的子结构。&#xff08;我们约定空树不是任意一个树的子结构&#xff09; 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}&#xff0c;B为{8,9,2}&…...

NEFU数字图像处理(1)绪论

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

数值分析学习笔记——绪论【华科B站教程版本】

绪论 数值分析概念 用计算机求解数学问题的数值方法和理论 三大科学研究方法 实验理论分析科学计算&#xff08;用计算机去辅助研究&#xff09;&#xff1a;数值方法计算机 解析解和近似解 解析解&#xff1a;使用数学方法求出或推导出的结果&#xff0c;往往可以求解出…...

节日灯饰灯串灯出口欧洲CE认证办理

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

一线大厂Redis高并发缓存架构实战与性能优化

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

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 的诞生预示着人工智能和机器学习领域的新时代。 日新月异&#xff0c;Hugging Face 不断推出突破性的语言模型&#xff0c;重新定义人机交互的界限。欢迎来到未来&#xff01; 当然&#xff0c;有很多选项可以对它们进行推断。在本文中&#xff0c;我将告诉大家如何使…...

蓝桥等考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 (拉取和推送)镜像,不受本地局域网限制&#xff01; 1. 部署Docker Registry 使用官网安装方式,docker命令一键启动,该命令启动一个regis…...

二十九、高级IO与多路转接之epollreactor(收官!)

文章目录 一、Poll&#xff08;一&#xff09;定义&#xff08;二&#xff09;实现原理&#xff08;三&#xff09;优点&#xff08;四&#xff09;缺点 二、I/O多路转接之epoll&#xff08;一&#xff09;从网卡接收数据说起&#xff08;二&#xff09;如何知道接收了数据&…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...