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

2024ICPC网络赛2记录:CK

这一次网络赛我们过8题,排名71,算是发挥的非常好的了。这一把我们三个人手感都很好,前六题都是一遍过,然后我又切掉了非签到的E和C,最后时间不是很多,K只想到大概字典树的思路,细节不是很懂就直接开冲,当然是没有冲出来。

C:
感觉思路挺容易的,但是我想了很久,如果我能秒掉这种题(当然我觉得实力不够秒掉这种题)有可能可以再把K开出来。

首先,我们肯定是要维护当前有哪些后缀能和前缀匹配的。
我们想了很多错误的思路以后才开始思考kmp,然后就想到了可以一直跳kmp,只需要把相同的合并起来,如果能匹配的就全部一起跳过,不匹配的就直接删掉,时间复杂度O(n)。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
#define ull unsigned long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=3e5+10;
int n;ll ans,a[N],b[N],c[N];
int f[N],g[N];
void solve(){qr(n);  ll tot=0;rep(i,1,n){qr(c[i]),qr(a[i]),qr(b[i]);c[i]=(c[i]+ans)%n;if(i==1)tot+=b[i];else{if(c[1]==c[i])tot+=b[i];int j=f[i-1];if(c[i]==c[j+1])g[i-1]=g[j];else g[i-1]=f[i-1];while(j){if(c[j+1]!=c[i]){tot-=b[i-j];j=f[j];}else break;}if(c[j+1]==c[i])f[i]=j+1;else f[i]=j;while(j){if(c[j+1]==c[i])j=g[j];else{tot-=b[i-j];j=f[j];}}}ans+=tot*a[i];qw(ans);puts("");}
}
int main(){int tt;tt=1;while(tt--)solve();return 0;
}

K
看上去要求某种匹配数的个数,有点吓人。
不过看到异或就知道这个异或肯定不是白给你的,大概就是用字典树,一开始我以为是把两个数组分开建字典树,后面发现要一起建,然后就想到用dp来维护。不过我的dp始终是4维的,优化不到三维,后面上网看了一下,发现全部都是四维,那我就直接交了。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
#define ull unsigned long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=210;
const int mod=998244353;
struct node{int f[N];node(){memset(f,0,sizeof(f));}void print(){rep(i,0,10)cout<<f[i]<<" ";cout<<endl;}
};
int n;ll k;
ll a[N],b[N],c[N];
int fc[N],ifc[N];
int power(int a,int b){int ret=1;while(b){if(b&1)ret=1ll*ret*a%mod;a=1ll*a*a%mod;b>>=1;}return ret;
}
int C(int x,int y){if(x<0||y<0||x<y)return 0;return 1ll*fc[x]*ifc[y]%mod*ifc[x-y]%mod;
}
int A(int x,int y){if(x<0||y<0||x<y)return 0;return 1ll*fc[x]*ifc[x-y]%mod;
}
node solve(int ki,int l,int r,int x,int y){if(l>r||x>y){node now;now.f[0]=1;return now;}if(ki==-1){node now;int t=min(r+1-l,y+1-x);rep(i,0,t)now.f[i]=1ll*C(r-l+1,i)*A(y-x+1,i)%mod;return now;}//sortint mid1=l-1,mid2=x-1;rep(i,l,r){if(a[i]>>ki&1)break;mid1=i;}rep(i,x,y){if(b[i]>>ki&1)break;mid2=i;}if(k>>ki&1){node ans1=solve(ki-1,l,mid1,mid2+1,y);node ans2=solve(ki-1,mid1+1,r,x,mid2);node ans;int siz1=min(mid1+1-l,y-mid2);int siz2=min(r-mid1,mid2+1-x);rep(i,0,siz1)rep(j,0,siz2)(ans.f[i+j]+=1ll*ans1.f[i]*ans2.f[j]%mod)%=mod;return ans;}else{node ans1=solve(ki-1,l,mid1,x,mid2);node ans2=solve(ki-1,mid1+1,r,mid2+1,y);node ans;int siz1=min(mid1+1-l,mid2+1-x);int siz2=min(r-mid1,y-mid2);rep(i,0,siz1){int x1=mid1+1-l-i,y1=mid2+1-x-i;rep(j,0,siz2){int x2=r-mid1-j,y2=y-mid2-j;int t1=min(x1,y2);int t2=min(x2,y1);rep(p1,0,t1){rep(p2,0,t2){(ans.f[i+j+p1+p2]+=1ll*ans1.f[i]*ans2.f[j]%mod*C(x1,p1)%mod*A(y2,p1)%mod*C(x2,p2)%mod*A(y1,p2)%mod)%=mod;}}}}return ans;}
}
void solve(){qr(n),qr(k);rep(i,1,n)qr(a[i]);rep(i,1,n)qr(b[i]);sort(a+1,a+n+1);sort(b+1,b+n+1);node ans=solve(61,1,n,1,n);rep(i,1,n)qw(ans.f[i]),puts("");
}
int main(){fc[0]=1;rep(i,1,200)fc[i]=1ll*fc[i-1]*i%mod;ifc[200]=power(fc[200],mod-2);dwn(i,199,0)ifc[i]=1ll*ifc[i+1]*(i+1)%mod;int tt;tt=1;while(tt--)solve();return 0;
}

相关文章:

2024ICPC网络赛2记录:CK

这一次网络赛我们过8题&#xff0c;排名71&#xff0c;算是发挥的非常好的了。这一把我们三个人手感都很好&#xff0c;前六题都是一遍过&#xff0c;然后我又切掉了非签到的E和C&#xff0c;最后时间不是很多&#xff0c;K只想到大概字典树的思路&#xff0c;细节不是很懂就直…...

PerparedStatement概述

PreparedStatement 是 Java 中的一个接口&#xff0c;用于预编译 SQL 语句并执行数据库操作。 一、主要作用 提高性能&#xff1a; 数据库在首次执行预编译语句时会进行语法分析、优化等操作&#xff0c;并将其存储在缓存中。后续执行相同的预编译语句时&#xff0c;数据库可…...

联影医疗嵌入式面试题及参考答案(3万字长文)

假如你要做机器人控制,你会遵循怎样的开发流程? 首先,需求分析阶段。明确机器人的功能需求,例如是用于工业生产中的物料搬运、还是家庭服务中的清洁打扫等。了解工作环境的特点,包括空间大小、障碍物分布、温度湿度等因素。同时,确定机器人的性能指标,如运动速度、精度、…...

Rust的作用?

在Linux中&#xff0c;Rust可以开发命令行工具&#xff0c;如FD、SD、Ripgep、Bat、EXA、SKIM等。虽然Rust是面向系统编程&#xff0c;但也不妨碍使用Rust写命令行工具&#xff0c;因为Rust具备现代语言特性、无依赖、生成的目标文件小。 在云计算和区块链区域&#xff0c;Rus…...

无人机之可承受风速的影响因素

无人机可承受风速的影响因素是多方面的&#xff0c;这些因素共同决定了无人机在特定风速条件下的飞行稳定性和安全性。以下是一些主要的影响因素&#xff1a; 一、无人机设计与结构 无人机的大小、形状和重量都会直接影响其抗风能力。大型无人机由于具有更大的表面积和质量&am…...

HTML与JavaScript结合实现简易计算器

目录 背景&#xff1a; 过程&#xff1a; 代码: HTML部分解析&#xff1a; body部分解析&#xff1a; JavaScript部分解析&#xff1a; 效果图 &#xff1a; 总结: 背景&#xff1a; 计算器是一个典型的HTML和javaScript结合使用的例子&#xff0c;它展示了如何使用H…...

Docker网络原理

Docker 网络是 Docker 容器之间以及容器与外部世界之间通信的机制。Docker 提供了多种网络驱动&#xff0c;允许容器以不同的方式进行通信&#xff1a; Docker 网络工作原理&#xff1a; 网络命名空间&#xff1a;Docker 使用 Linux 的网络命名空间来隔离容器的网络堆栈。每个…...

PyTorch 目标检测教程

PyTorch 目标检测教程 本教程将介绍如何在 PyTorch 中使用几种常见的目标检测模型&#xff0c;包括 Faster R-CNN、SSD 以及 YOLO (You Only Look Once)。我们将涵盖预训练模型的使用、推理、微调&#xff0c;以及自定义数据集上的训练。 1. 目标检测概述 目标检测任务不仅要…...

校园美食导航:Spring Boot技术的美食发现之旅

第二章 系统分析 2.1 可行性分析 可行性分析的目的是确定一个系统是否有必要开发、确定系统是否能以最小的代价实现。其工作主要有三个方面&#xff0c;分别是技术、经济和社会三方面的可行性。我会从这三个方面对网上校园周边美食探索及分享平台进行详细的分析。 2.1.1技术可行…...

51单片机 - DS18B20实验1-读取温度

上来一张图&#xff0c;明确思路&#xff0c;程序整体裤架如下&#xff0c;通过单总线&#xff0c;单独封装一个.c文件用于单总线的操作&#xff0c;其实&#xff0c;我们可以把点c文件看成一个类操作&#xff0c;其属性就是我们面向对象的函数&#xff0c;也叫方法&#xff0c…...

go语言基础入门(一)

变量声明:批量声明变量:变量赋值: 声明变量同时为变量赋值可以在变量声明时为其赋值go中赋值时的编译器会自动根据等号右侧的数据类型自动推导变量的类型使用 : 进行赋值匿名变量 常量常量计数器iota1. 使用场景2. 基本用法3. 简化语法4. 自定义增量5. 复杂使用go的类似枚举 使…...

linux 基础(一)mkdir、ls、vi、ifconfig

1、linux简介 linux是一个操作系统&#xff08;os: operating system&#xff09; 中国有没有自己的操作系统&#xff08;华为鸿蒙HarmonyOS&#xff0c;阿里龙蜥(Anolis) OS 8、百度DuerOS都有&#xff09; 计算机组的组成&#xff1a;硬件软件 硬件&#xff1a;运算器&am…...

DAMODEL丹摩智算:LLama3.1部署与使用

文章目录 前言 一、LLaMA 3.1 的特点 二、LLaMA3.1的优势 三、LLaMA3.1部署流程 &#xff08;一&#xff09;创建实例 &#xff08;二&#xff09;通过JupyterLab登录实例 &#xff08;3&#xff09;部署LLaMA3.1 &#xff08;4&#xff09;使用教程 总结 前言 LLama3…...

Spring Boot 配置全流程 总结

1. 简介 Springboot可以简化SSM的配置&#xff0c;提高开发效率。 2. 代码 在pom.xml中添加&#xff1a; <parent><!-- 包含SSM常用依赖项 --><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</art…...

爬虫技术初步自学

目的 本篇文章实际上自学爬虫技术的学习一份学习笔记&#xff0c;希望可以对后学的小白起到帮助&#xff0c;也希望得到大佬的指点&#xff0c;若有错漏希望大佬指出。 初步认知 爬虫实际上是一个计算机程序。开发爬虫程序的常用语言是Python。&#xff08;Python我已经在五…...

【力扣 | SQL题 | 每日三题】力扣175, 176, 181

1. 力扣175&#xff1a;组合两个表 1.1 题目&#xff1a; 表: Person ---------------------- | 列名 | 类型 | ---------------------- | PersonId | int | | FirstName | varchar | | LastName | varchar | ---------------------- personId 是该…...

SpringBoot使用hutool操作FTP

项目场景&#xff1a; SpringBoot使用hutool操作FTP&#xff0c;可以实现从FTP服务器下载文件到本地&#xff0c;以及将本地文件上传到FTP服务器的功能。 实现步骤&#xff1a; 1、引入依赖 <dependency><groupId>commons-net</groupId><artifactId>…...

如何防止SQL注入攻击

SQL注入攻击是一种常见的网络安全威胁&#xff0c;攻击者通过在用户输入中插入恶意的SQL代码&#xff0c;从而可以执行未经授权的数据库操作。为了防止SQL注入攻击&#xff0c;我们可以采取一系列有效的措施来保护数据库和应用程序的安全性。以下是一些关键的防范策略&#xff…...

Java List类

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;Java 目录 &#x1f449;&#x1f3fb;List1. 接口与实现2. 特性3. 常用方法4. 示例代码5. 遍历6. 线程安全 &#x1f449;&#x1f3fb;List Java的 List …...

使用 Internet 共享 (ICS) 方式分配ip

设备A使用dhcp的情况下&#xff0c;通过设备B分配ip并共享网络的方法。 启用网络共享&#xff08;ICS&#xff09;并配置 NAT Windows 自带的 Internet Connection Sharing (ICS) 功能可以简化 NAT 设置&#xff0c;允许共享一个网络连接给其他设备。 打开网络设置&#xff1…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...