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

D. Eating【Codeforces Round 1005 (Div. 2)】

news 来源：原创 2025/6/30 17:37:22

D. Eating

题意

有 $n$ 个史莱姆排成一行，第 $i$ 个史莱姆的权重为 $w_i$ 。若史莱姆 $i$ 的权重满足 $w_i \geq w_j$ ，则它可以吃掉史莱姆 $j$ ；之后，史莱姆 $j$ 会消失，史莱姆 $i$ 的权重变为 $w_i \oplus w_j$ $^{\text{∗}}$ 。

史莱姆国王想用参数 $x$ 进行以下实验：

• 将一个权重为 $x$ 的新史莱姆添加到行的最右端（第 $n$ 个史莱姆之后）。

• 这个新史莱姆会尝试吃掉左侧的史莱姆（若满足条件），并移动到被吃者的位置。此过程会持续直到其左侧没有史莱姆，或者左侧史莱姆的权重大于它当前的值。（此过程中其他史莱姆不会被吃掉。）

• 实验的得分为被吃掉的史莱姆总数。

国王会询问 $q$ 次查询。每次查询给定整数 $x$ ，你需要计算该参数下实验的得分。注意这些查询是假设性的，不会实际改变史莱姆的状态（即查询之间相互独立）。

$^{\text{∗}}$ 此处 $\oplus$ 表示按位异或运算。

输入格式

第一行输入整数 $t$ ( $\le t \le 10^4$ )，表示测试用例数量。

每个测试用例的第一行包含整数 $n$ 和 $q$ ( $\le n, q \le 2 \cdot 10^5$ )，分别表示史莱姆数量和查询次数。

第二行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$ ( $\le w_i < 2^{30}$ )，表示史莱姆的权重。

接下来 $q$ 行每行输入一个整数 $x$ ( $\le x < 2^{30}$ )，表示实验参数。

所有测试用例的 $n$ 之和不超过 $\cdot 10^5$ ， $q$ 之和不超过 $\cdot 10^5$ 。

输出格式

对于每个查询，输出一个整数，表示对应实验的得分。

思路

区间异或和可以用前缀和来快速查询，并且若a的最高有效位大于b，那么a>b。

因此预处理每个位置的二进制信息，利用贪心跳跃加速查询：

预处理：对每个位置i，记录其二进制位数。维护数组j[i][k]，表示在i左侧，二进制位数不超过k的最远位置。这能快速定位可吞吃区间。
跳跃查询：从右向左处理，每次计算当前x的二进制位数g。利用j[t][g]找到最远可吞吃的位置l，此时区间[l, t]的史莱姆均满足条件。累加数量后，更新x为异或结果，并跳到l-1继续处理。
复杂度优化：通过预处理，每次查询只需 $O(log \max{W})$ 次跳跃，总复杂度 $O(q \log \max{W})$ ，避免暴力遍历。

通过预处理二进制信息实现快速跳跃，将每次查询的时间从线性优化为对数级。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int maxn= 5e5+5,MAXN = maxn;
int a[200005];
int p[200005];
int j[200005][31];
int rj[31];
int qr(int l,int r){if(l==r)return a[l];return p[r]^p[l-1];
}
void solve() {int n,q;cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];p[i]=p[i-1]^a[i];int l= log2(a[i])+1;rj[l]=i;for(int k=1;k<=l;k++)rj[k]=i;for(int k=1;k<=30;k++){j[i][k]=rj[k];}}while(q--){int x,t=n,ans=0;cin>>x;while(x>=a[t] && t>0){int g=log2(x)+1;int l = min(t,j[t][g]+1);x=x^qr(l,t);ans+=t-l+1;t=l-1;}cout<<ans<<" ";}   cout<<endl;
}	signed main() {
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifcin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

D. Eating【Codeforces Round 1005 (Div. 2)】

D. Eating 题意有 n n n 个史莱姆排成一行，第 i i i 个史莱姆的权重为 w i w_i wi。若史莱姆 i i i 的权重满足 w i ≥ w j w_i \geq w_j wi≥wj，则它可以吃掉史莱姆 j j j；之后，史莱姆 j j j 会消失，…...

编程日记 2025/6/30 17:37:22

猫眼浏览器：简约安全，极速浏览

猫眼浏览器是一款以简约安全为目标的Chrome内核增强版浏览器，基于最新的Chromium开源内核进行二次优化开发。它不仅继承了Chrome浏览器的高速浏览体验，还通过增强的隐私保护设置，让用户远离被追踪和广告的烦恼。无论是日常浏览、信息查询还是…...

编程日记 2025/6/29 0:22:59

安全扫描之 Linux 杀毒软件 Clamav 安装

文章目录背景Clamav 简介安装使用1、安装epel-release2、Clamav安装3、成功安装4、更新病毒库5、执行扫描6、结果分析7、常见问题背景最近在做HVV准备工作，应要求需要在 Linux 服务器上安装杀毒软件，以此文记录下Clamav 安装过程。 Clamav 简介 Cl…...

编程日记 2025/6/30 17:32:27

排序算法详解

排序算法全面解析排序算法是计算机科学中最基础也最重要的算法之一。它将一组数据（例如数字列表、字符串集合）按照特定的顺序（升序或降序）重新排列。高效的排序算法对于优化其他算法（如搜索和合并算法）的…...

编程日记 2025/6/29 0:03:47

[特殊字符] GSG 插件 + 渲染 101：C4D 渲染效率革命！

一、GSG 插件：C4D 创作的「超级加速器」灰猩猩（GSG）插件是 C4D 设计师的刚需工具： Light Kit Pro：1 分钟生成专业灯光预设，告别手动布光烦恼GorillaCam：自动添加电影级相机运动，镜…...

编程日记 2025/6/28 22:55:22

centos中postfix的作用

/usr/libexec/postfix/master 是 Postfix 邮件服务器的主进程，qmgr 和 pickup 是 Postfix 的子进程。这些进程本身是正常的，但如果你怀疑服务器被用于钓鱼活动，需要进一步检查 Postfix 的配置和日志，确保它没有被滥用。 1. 检查 P…...

编程日记 2025/6/29 1:01:57

tocmat 启动怎么设置 jvm和gc

在生产环境中部署 Java Web 应用时，我们经常需要给 Tomcat 设置 JVM 参数和 GC 策略，以提高性能、稳定性和可观察性。以下是完整教程： 一、Tomcat 设置 JVM 启动参数的方式 1. 修改 startup 脚本（推荐） 以 Linux 系统…...

编程日记 2025/6/28 22:55:18

【工奥阀门科技有限公司】签约智橙PLM

近日，工奥阀门科技有限公司正式签约了智橙泵阀行业版PLM。忠于质量，臻于服务，精于研发工奥阀门科技有限公司（以下简称工奥阀门）坐落于浙江永嘉，是一家集设计、开发、生产、销售、安装、服务为一体的阀门…...

编程日记 2025/6/28 23:28:15

Axure设计之轮播图——案例“一图一轮播”

轮播图是一种常见且实用的组件，用于展示多张图片或内容，同时节省页面空间。在Axure中，通过动态面板和交互设置，我们可以轻松实现一个“一图一轮播”的效果，即每次只展示一张图片，并通过按钮或自动切换来浏览…...

编程日记 2025/6/30 17:00:07

可视化图解算法39：输出二叉树的右视图

1. 题目描述请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图数据范围： 0≤n≤10000 要求： 空间复杂度 O(n)，时间复杂度 O(n) 如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结…...

编程日记 2025/6/29 0:14:57

数据库基础复习笔记

数据库相关概念名称全称检查数据库存储数据的仓库，数据是有组织的进行存储DataBase（DB）数据库管理系统操作和管理数据库的大型软件DataBase Management System(DBMS)SQL操作关系型数据库的编程语言，定义了一套操作关系型数据库…...

编程日记 2025/6/29 1:10:56

鸿蒙OSUniApp 实现一个精致的日历组件#三方框架 #Uniapp

使用 UniApp 实现一个精致的日历组件前言最近在开发一个约会小程序时，需要实现一个既美观又实用的日历组件。市面上虽然有不少现成的组件库，但都不太符合我们的设计需求。于是，我决定从零开始，基于 UniApp 自己实现一个功能完…...

编程日记 2025/6/30 17:01:14

Kotlin 协程实战：实现异步值加载委托，对值进行异步懒初始化

在实际开发中，我们经常遇到这样的场景。需要立即初始化但计算成本高昂的值 val expensiveValue calculateExpensiveValue() 可能引发阻塞的初始化操作 val resource loadResourceFromNetwork()这些场景通常需要满足以下需求： 异步加载&#xff1a…...

编程日记 2025/6/28 23:24:57

MySQL增删查改进阶

文章目录一、数据库备份二、数据库约束2.1 NOT NULL2.2 UNIQUE：唯一约束2.3 DEFAULT：默认值约束一、数据库备份在MySQL当中，数据库是如何备份的呢？主要通过三种方式进行备份： 数据库最终都是存储在硬盘上&#xf…...

编程日记 2025/6/29 0:03:04

Tensorflow2保存和加载模型

1、model.save() and model.load() 此种方法可保存模型的结构、参数等内容。加载模型后无需设置即可使用！ 保存模型： model.save(my_model.h5) 加载模型： # 加载整个模型 loaded_model tf.keras.models.load_model(my_model.h5) 注意&…...

编程日记 2025/6/29 1:06:06

通过泛域名解析把二级域名批量绑定到wordpress的指定页面

通过泛域名解析将二级域名批量绑定到WordPress的指定页面，需要完成两个主要步骤：一是设置泛域名解析，二是配置服务器和WordPress以实现二级域名到指定页面的映射。以下是详细的操作方法： 1. 设置泛域名解析在域名注册商的管理后…...

编程日记 2025/6/29 1:29:46

一、实验拓扑二、IP规划骨干： 172.16.0.0/30 ---- R2-R3 172.16.0.4/30 ---- R3-R4 172.16.0.8/30 ---- R4-R7 172.16.0.12/30 ---- R6-R7 172.16.0.16/30 ---- R5-R6 172.16.0.20/30 ---- R2-R5 非骨干： 172.16.2.0/24 ---- R2的环回 2.2.2.2/32 17…...

编程日记 2025/6/29 0:10:45

3天云南旅游规划

云南的主要旅游城市和景点。昆明作为云南的省会，拥有丰富的自然景观和适合短途游玩的地方。第一天可以安排在昆明市内和周边，方便游玩。第二天，可以考虑去大理，这是云南的著名旅游城市，距离昆明大约2小时的车程。大理…...

编程日记 2025/6/30 17:06:17

SCDN能够运用在物联网加速当中吗？

在当今的科技化时代当中，物联网已经广泛渗透在各个领域行业当中，随着物联网规模的不断扩大，数据信息的传输速度和网络稳定性成为企业需要重视的两点因素，而SCDN也成为安全内容分发网络作为一种融合了内容加速和安全防护的技术&…...

编程日记 2025/6/28 23:43:38

Go语言八股之Mysql基础详解

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。非常期待和您一起在这个小…...

编程日记 2025/6/29 0:32:49

计算机视觉----基础概念、卷积

一、概述 1.计算机视觉的定义计算机视觉（Computer Vision）是一个跨学科的研究领域，主要涉及如何使计算机能够通过处理和理解数字图像或视频来自动进行有意义的分析和决策。其目标是使计算机能够从视觉数据中获取高层次的理解，类似于人类的视觉处理能力。具体来说，计算机…...

编程日记 2025/6/29 0:33:43

Problem E: List练习

1.题目描述运用List完成下面的要求: 1) 创建一个List，在List中增加三个工人，基本信息如下： 姓名年龄工资 Tom 18 3000 Peter 25 3500 Mark 22 3200 2) 插入一个工人，信息为：姓名：Robert&#xff0…...

编程日记 2025/6/29 1:17:16

12-串口外设

一、串口外设的基本概述 1、基本定义串口通信，通过在通信双方之间以比特位（bit）的形式逐一发送或接收数据，实现了信息的有效传递。其通信方式不仅简单可靠，而且成本很低。 2、stm32的串口下面是两个MCU的数据交互&…...

编程日记 2025/6/29 8:50:23

C++（2）

二、面向对象基础 1. 类与对象 1.1 核心概念类（Class） 定义：抽象描述具有共同特征和行为的对象模板本质：代码复用的蓝图，定义数据（属性）与操作（行为&#xff0…...

编程日记 2025/6/30 17:15:05

GMT之Bash语言使用

GMT的操作有自己的逻辑和“命令”，但GMT是可以用Bash语言控制的，所以常常以.sh为后缀写GMT程序。 GMT程序运行步骤如下： 采用cd ，定位到指定文件夹；以sh ***.sh运行GMT，得到结果。另外，遇到…...

编程日记 2025/6/29 1:22:55

半成品的开源双系统VLA模型，OpenHelix-发表于2025.5.6

半成品的开源双系统VLA模型，OpenHelix https://openhelix-robot.github.io/ 0. 摘要随着OpenVLA的开源，VLA如何部署到真实的机器人上获得了越来越多的关注，各界人士也都开始尝试解决OpenVLA的效率问题，双系统方案是其中一个非…...

编程日记 2025/6/29 0:18:06

fiftyone-dataset使用基础

1.创建dataset 将dataset写入数据库时，对于已有的dataset name会报错： 解决方法：指定覆盖写添加参数overwriteTrue, 默认为False # 在写入数据集时，指定overwriteTrue，表示当dataset_name在数据库中已存在时&#…...

编程日记 2025/6/30 16:53:48

（1-4）Java Object类、Final、注解、设计模式、抽象类、接口、内部类

目录 1. Object类 1.1 equals 1.2 toString（） 2.final关键字 3.注解 4. 设计模式 4.1 单例模式 4.1.1 饿汉式 4.1.3 饿汉式 VS 懒汉式 5. 抽象类&抽象方法 6. 接口 1. Object类 1.1 equals 重写Object 的equals方法，两种实现方式…...

编程日记 2025/6/30 17:12:37

强力巨彩谷亚推出专业智慧显示屏，满足多元场景需求

LED显示屏作为信息传播与视觉展示的关键载体，其性能和品质的提升备受关注。为响应市场对高品质显示的迫切需求，强力巨彩旗下专业智慧显示高端品牌谷亚G-ART，携多款行业领先水平的LED显示屏产品亮相，为用户带来专业、高效且节能的显…...

编程日记 2025/6/30 17:23:41

基于Spring AI与Hugging Face TGI构建高效聊天应用：从配置到实践全解析

基于Spring AI与Hugging Face TGI构建高效聊天应用：从配置到实践全解析前言在人工智能技术蓬勃发展的当下，大语言模型（LLM）的应用场景日益丰富。如何快速将 Hugging Face 生态中的强大模型部署为可通过 API 访问的服务&#x…...

编程日记 2025/6/30 17:34:06

MySQL视图：虚拟表的强大功能与应用实践

在数据库管理系统中，视图(View)是一种极其重要却常被忽视的功能。作为MySQL数据库的核心特性之一，视图为开发者和数据库管理员提供了数据抽象、安全控制和查询简化的强大工具。本文将全面探讨MySQL视图的概念、工作原理、创建与管理方法，以及…...

编程日记 2025/6/30 17:19:06

matlab插值方法（简短）

在MATLAB中，可以使用interp1函数快速实现插值。以下代码展示了如何使用spline插值方法对给定数据进行插值： x1 [23,56]; y1 [23,56]; X 23:1:56*4; Y interp1(x1,y1,X,spline);% linear、 spline其中，x1和y1是已知数据点，X是…...

编程日记 2025/6/28 22:55:44

【拥抱AI】Deer-Flow字节跳动开源的多智能体深度研究框架

最近发现一款可以对标甚至可能超越GPT-Researcher的AI深度研究应用，Deer-Flow（Deep Exploration and Efficient Research Flow）作为字节跳动近期开源的重量级项目，正以其模块化、灵活性和人机协同能力引发广泛关注。该项目基于 La…...

编程日记 2025/6/30 17:17:53

基于开源AI大模型与S2B2C生态的个人品牌优势挖掘与标签重构研究

摘要：在数字文明时代，个人品牌塑造已从传统经验驱动转向数据智能驱动。本文以开源AI大模型、AI智能名片与S2B2C商城小程序源码为技术载体，提出"社会评价-数据验证-标签重构"的三维分析框架。通过实证研究发现，结合第三方…...

编程日记 2025/6/30 17:06:16

2025年PMP 学习十二第9章项目资源管理

2025年PMP 学习十二第9章项目资源管理序号过程过程组1规划资源管理规划2估算活动资源规划3获取资源执行4建设团队执行5管理团队执行6控制资源监控项目资源管理，包括实物资源和团队资源。文章目录 2025年PMP 学习十二第9章项目资源管理项目团队和项目管理团…...

编程日记 2025/6/28 23:30:12

AI生成功能测试文档｜测试文档

AI生成功能测试文档：链接直达计算机功能测试文档撰写教程链接直达：生成功能测试文档工具一、文档概述 （一）文档目的明确计算机功能测试的流程、方法和标准，确保测试的有效性和可靠性，为软件的质量评…...

编程日记 2025/6/29 1:00:07

Python 常用模块（八）：logging模块

目录一、引言：日志模块在项目开发中的重要性二、从 Django 日志配置看 Logging 模块的核心组成三、logging模块核心组件详解3.1 记录器Logger3.2 级别Level3.3 根记录器使用3.4 处理器Handler3.5 格式化器Formatter3.6 日志流3.7 日志示例四、日志模块总结一、引…...

编程日记 2025/6/28 23:32:43

入门OpenTelemetry——可观测性与链路追踪介绍

可观测性什么是可观测性可观察性（Observability）是从外部输出知识中推断所获得，可理解为衡量一个系统内部状态的方法。可观测性是一种能力，它能帮助你回答系统内部发生了什么——无需事先定义每种可能的故障或状态。系统的可观…...

编程日记 2025/6/28 22:55:25

c#队列及其操作

可以用数组、链表实现队列，大致与栈相似，简要介绍下队列实现吧。值得注意的是循环队列判空判满操作，在用链表实现时需要额外思考下出入队列条件。设计头文件 #ifndef ARRAY_QUEUE_H #define ARRAY_QUEUE_H#include <stdbool.h> #incl…...

编程日记 2025/6/28 22:55:26

【Linux C/C++开发】轻量级关系型数据库SQLite开发（包含性能测试代码）

前言之前的文件分享过基于内存的STL缓存、环形缓冲区，以及基于文件的队列缓存mqueue、hash存储、向量库annoy存储，这两种属于比较原始且高效的方式。那么，有没有高级且高效的方式呢。有的，从数据角度上看，&#xff0…...

编程日记 2025/6/28 22:55:27

77. 组合【力扣(LeetCode) 】

文章目录零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码零、原题链接 77. 组合一、题目描述给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。二、测试用例示例 1： 输入&…...

编程日记 2025/6/28 22:55:28

GpuGeek全栈AI开发实战：从零构建企业级大模型生产管线（附完整案例）

目录背景一、算力困境：AI开发者的「三重诅咒」1.1 硬件成本黑洞‌1.2 资源调度失衡‌1.3 环境部署陷阱‌ 二、三大核心技术突破GpuGeek的破局方案2.1 ‌分时切片调度引擎（Time-Slicing Scheduler）‌2.2 ‌异构计算融合架构2.3 ‌AI资产自动化…...

编程日记 2025/6/29 0:20:14

LeetCode 热题 100_颜色分类（98_75_中等_C++）（技巧）(计数；双指针)

LeetCode 热题 100_颜色分类（98_75_中等_C） 题目描述：输入输出样例：题解：解题思路：思路一（计数）：思路二（双指针）： 代码实现代码实现&a…...

编程日记 2025/6/29 0:27:05

【前端】：单 HTML 去除 Word 批注

在现代办公中，.docx 文件常用于文档编辑，但其中的批注（注释）有时需要在分享或归档前被去除。本文将从原理出发，深入剖析如何在纯前端环境下实现对 .docx 文件注释的移除，并提供完整的实现源码。最后&#x…...

编程日记 2025/6/29 0:01:43

TTS-Web-Vue系列：Vue3实现内嵌iframe文档显示功能

🖼️ 本文是TTS-Web-Vue系列的新篇章，重点介绍如何在Vue3项目中优雅地实现内嵌iframe功能，用于加载外部文档内容。通过Vue3的响应式系统和组件化设计，我们实现了一个功能完善、用户体验友好的文档嵌入方案，包括加载状态…...

编程日记 2025/6/29 1:23:18

AWS CloudTrail日志跟踪启用

问题启用日志管理。步骤审计界面，如下图： 点击创建跟踪，AWS云就会记录AWS账号在云中的操作。...

编程日记 2025/6/28 23:53:31

PHP 编程：现代 Web 开发的基石与演进

引言 PHP（Hypertext Preprocessor）自1995年诞生以来，已成为全球最流行的服务器端脚本语言之一。尽管近年来Node.js、Python等语言在特定领域崭露头角，但PHP仍占据着超过78%的网站市场份额（W3Techs数据）。本…...

编程日记 2025/6/28 22:55:30

NAT/代理服务器/内网穿透

目录一 NAT技术二内网穿透/内网打洞三代理服务器一 NAT技术跨网络传输的时候，私网不能直接访问公网，就引入了NAT能讲私网转换为公网进行访问，主要解决IPv4(2^32)地址不足的问题。 1. NAT原理当某个内网想访问公网，就必…...

编程日记 2025/6/28 23:40:35

[已解决] VS Code / Cursor / Trae 的 PowerShell 终端 conda activate 进不去环境的常见问题

背景 PS C:\Users\Lenovo\WPSDrive\669715199_3\WPS云盘\课程\研一\ROAS5700 Robot Motion Planning and Control\Final\LaTex报告\final-v1> conda activate mpPS C:\Users\Lenovo\WPSDrive\669715199_3\WPS云盘\课程\研一\ROAS5700 Robot Motion Planning and Control\Fin…...

编程日记 2025/6/29 0:40:29

Kuka AI音乐AI音乐开发「人声伴奏分离」 —— 「Kuka Api系列|中文咬字清晰|AI音乐API」第6篇

导读今天我们来了解一下 Kuka API 的人声与伴奏分离功能。所谓“人声伴奏分离”，顾名思义，就是将一段完整的音频拆分为两个独立的轨道：一个是人声部分，另一个是伴奏（乐器）部分。这个功能在音乐创作和…...

编程日记 2025/6/29 0:34:42

题意

思路

代码

相关文章：