当前位置: 首页 > 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;如何知道接收了数据&…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

深入解析 ReentrantLock:原理、公平锁与非公平锁的较量

ReentrantLock 是 Java 中 java.util.concurrent.locks 包下的一个重要类,用于实现线程同步,支持可重入性,并且可以选择公平锁或非公平锁的实现方式。下面将详细介绍 ReentrantLock 的实现原理以及公平锁和非公平锁的区别。 ReentrantLock 实现原理 基本架构 ReentrantLo…...

C# WPF 左右布局实现学习笔记(1)

开发流程视频&#xff1a; https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码&#xff1a; GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用&#xff08;.NET Framework) 2.…...