当前位置: 首页 > 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…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...