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

[ABC261E] Many Operations(dp,位运算,打表)

[ABC261E] Many Operations - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Problem Statement

We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (Ti​,Ai​), and is the following operation:

  • if Ti​=1, it replaces the value of X with  and X and Ai​;
  • if Ti​=2, it replaces the value of X with  or X or Ai​;
  • if Ti​=3, it replaces the value of X with  xor X xor Ai​.

Initialize X with the value of C and execute the following procedures in order:

  • Perform Operation 1, and then print the resulting value of X.
  • Next, perform Operation 1,2 in this order, and then print the value of X.
  • Next, perform Operation 1,2,3 in this order, and then print the value of X.
  • Next, perform Operation 1,2,…,N in this order, and then print the value of X.

What are and,or,xorand,or,xor?

Constraints

  • 1≤N≤2×105
  • 1≤Ti​≤3
  • 0≤Ai​<230
  • 0≤C<230
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C
T1​ A1​
T2​ A2​
⋮
TN​ AN​

Output

Print N lines, as specified in the Problem Statement.

Sample 1

InputcopyOutputcopy
3 10
3 3
2 5
1 12
9
15
12

The initial value of X is 10.

  • Operation 1 changes X to 9.
  • Next, Operation 1 changes X to 10, and then Operation 2 changes it to 15.
  • Next, Operation 1 changes X to 12, and then Operation 2 changes it to 13, and then Operation 3 changes it to 12.

Sample 2

InputcopyOutputcopy
9 12
1 1
2 2
3 3
1 4
2 5
3 6
1 7
2 8
3 9
0
2
1
0
5
3
3
11
2

解析 :

用dp打表,将所有可能的状态都算出来,需要注意,这里如果不使用dp打表可能会超时(dp真的是最强的算法,可以解决的问题很多,效率还高)

集合划分:不重不漏,且需要将所有需要用到的状态体现出来

f[i][j][k] 表示:c的二进制的第 j 位是 i(0或1),且第 k 次操作所得的结果;

状态转移:

v = (a[k]>>j)&1;

当 t[k]==1 : f[i][j][k]=f[i][j][k-1] & v;

当 t[k]==2:f[i][j][k]=f[i][j][k-1] | v;

当 t[k]==3:f[i][j][k]=f[i][j][k-1] ^v;

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int n, c, t[N], a[N], f[2][35][N];int main() {cin >> n >> c;for (int i = 1; i <= n; i++) {scanf("%d%d", &t[i], &a[i]);}for (int i = 0; i < 2; i++) {for (int j = 0; j <= 30; j++) {f[i][j][0] = i;for (int k = 1; k <= n; k++) {int v = (a[k] >> j) & 1;if (t[k] == 1) {f[i][j][k] = f[i][j][k - 1] & v;}else if (t[k] == 2) {f[i][j][k] = f[i][j][k - 1] | v;}elsef[i][j][k] = f[i][j][k - 1] ^ v;}}}for (int i = 1; i <= n; i++) {int ans = 0;for (int j = 0,k=c; j <= 30; j++,k>>=1) {ans += f[k & 1][j][i] * (1 << j);}cout << ans << endl;c = ans;}return 0;
}

相关文章:

[ABC261E] Many Operations(dp,位运算,打表)

[ABC261E] Many Operations - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Problem Statement We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (Ti​,Ai​), and is the following operati…...

一、爬虫-爬取豆瓣电影案例

1、环境配置 你需要一个pycharm和requests第三方库&#xff0c;在安装完成之后即可继续浏览。 2、操作流程 &#xff08;1&#xff09;打开豆瓣电影网站&#xff0c;点击排行榜&#xff0c;点击喜剧&#xff0c;检查 &#xff08;2&#xff09;可以看到鼠标每次下移&#xff0…...

4G5G防爆执法记录仪、防爆智能安全帽赋能智慧燃气,可视化巡检巡线,安全生产管控

随着燃气使用的普及&#xff0c;燃气安全问题日益突出。传统应急安全问题处理方式暴露出以下问题&#xff1a; 应急预案不完善&#xff1a;目前一些燃气企业的应急预案存在实用性不高、流程不清晰等问题&#xff0c;导致在紧急情况下难以迅速启动和有效执行。 部门协同不流畅…...

武汉数字孪生赋能工业制造,加速推进制造业数字化转型

随着数字孪生技术的不断推进&#xff0c;互联网、物联网、智能传感技术开始应用到数控机床的远程服务&#xff0c;状态监控&#xff0c;故障诊断&#xff0c;维护管理等方面。武汉数字孪生是在虚拟空间中创建物理对象的高保真虚拟模型&#xff0c;以模拟其在现实世界中的行为提…...

安卓密码框、EditText

目录 1. 基础使用 2. 密码的展示与隐藏 (1) 使用setTransformationMethod方法 (2) 使用setInputType方法 3. imeOptions属性 4. 单行设置 在安卓中使用密码框普遍采用EditText设置inputType"textPassword"的方式。 1. 基础使用 <EditTextandroid:id"…...

ROS命令行工具

1、roscore 在使用ROS之前&#xff0c;首先要启动roscore进程。当我们在终端中运行这个命令时&#xff0c;系统就会启动ROS Master、参数服务器和日志节点。在这之后&#xff0c;就可以运行任何其他的ROS程序&#xff0f;节点了。所以可以在一个终端窗口运行roscore指令&#…...

深入浅出 Golang 中的直接依赖和间接依赖管理

目录 引言 直接依赖 间接依赖 为什么需要间接依赖&#xff1f; 如何管理间接依赖&#xff1f; 小结 引言 Golang 中的依赖管理是使用 go mod 进行管理的。go mod 是 Golang 官方推出的依赖管理工具&#xff0c;可以帮助开发者管理项目的依赖关系&#xff0c;确保项目代码…...

深入Python元编程:了解声明与初始化定制元类

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com 简介 在Python中&#xff0c;元编程是指在运行时创建或定制类的编程。元类是Python中最强大的元编程工具之一&#xff0c;允许您控制类的创建过程。元类是类的类&#xff0c;它控制类的实例化&#xff0c;允许您…...

[传智杯初赛] 期末考试成绩

传智专修学院的 Java 程序设计课程的评价体系是这样的&#xff1a; 首先&#xff0c;所有学生会有一个卷面得分&#xff0c;这个得分一定是一个 [0,100][0,100] 之间的整数。 如果卷面得分在 9090 分及以上&#xff0c;那么他的 GPA&#xff08;加权平均成绩&#xff09; 就是…...

Linux 常用基本命令

文章目录 7.1 帮助命令7.1.1 man 获得帮助信息7.1.2 help 获得shell内置命令的帮助信息7.1.3 常用快捷键 7.2 文件目录类7.2.1 pwd 显示当前工作目录的绝对路径7.2.2 ls 列出目录的内容7.2.3 cd 切换目录7.2.4 mkdir 创建一个新的目录7.2.5 rmdir 删除一个空的目录7.2.6 touch …...

阿里云语雀频繁崩溃,有什么文档管理工具是比较稳定的?

10月23 日14:00左右&#xff0c;蚂蚁集团旗下的在线文档编辑与协同工具语雀发生服务器故障&#xff0c;在线文档和官网都无法打开。直到当天晚上22:24&#xff0c;语雀服务才全部恢复正常。从故障发生到完全恢复正常&#xff0c;语雀整个宕机时间将近 8 小时&#xff0c;如此长…...

二分查找(折半查找)探究学习

1.引入 当我们想要查找在一个数组中某一个特定的数它的下标是什么的时候&#xff0c;我们最先想的方法是遍历数组&#xff0c;如下&#xff1a; #include<stdio.h> #include<string.h> int main() { int arr[10]{1,2,3,4,5,6,7,8,9,10}; int key 8;//要找的数是8…...

Android : 异常记录

查询大数据时 报错 android.database.sqlite.SQLiteBlobTooBigException: Row too big to fit into CursorWindow requiredPos0, totalRows1解决办法&#xff1a;cursor DB.rawQuery("select * from " DBhelpUtil.TABLE_NAME" where id ?",new String[]…...

西南科技大学电路分析基础实验A1(元件伏安特性测试 )

目录 一、实验目的 二、实验设备 三、预习内容(如:基本原理、电路图、计算值等) 1、测定线性电阻的伏安特性 2、二极管伏安特性测试 3、测定实际电压源的伏安特性 四、实验数据及结果分析(预习写必要实验步骤和表格) 1、测定线性电阻的伏安特性 2、二极管伏安特性测…...

【Java】泛型的简单使用

文章目录 一、包装类1.基本数据类型和对应的包装类2.自动装箱和自动拆箱3.手动装箱和手动拆箱 二、什么是泛型三、泛型的使用四、裸类型&#xff08;Raw Type&#xff09;五、泛型是如何编译的六、泛型的上界七、泛型方法总结 一、包装类 在了解泛型之前我们先了解什么是包装类…...

注册Zoho Mail邮箱:优势与使用体验

如何注册Zoho Mail邮箱&#xff1f;要注册Zoho Mail邮箱&#xff0c;首先打开浏览器&#xff0c;访问Zoho Mail官网&#xff0c;点击页面右上角的“创建帐户”按钮。接下来&#xff0c;按照提示输入你的姓名、生日和性别&#xff0c;以及一个有效的手机号码或电子邮件地址。然后…...

第十四届蓝桥杯大赛国赛模拟题C++卷1

第十四届蓝桥杯大赛国赛模拟题C++卷1 一、选择题 1、在数组中,数组名表示( ) A.数组第1个元素的首地址 B.数组第2个元素的首地址 C.数组所有元素的首地址 D.数组最后1个元素的首地址答案:A.数组名是一个地址,指向第一个元素 2、下列叙述中正确的是( ) A.顺序存储结构的…...

基于UDP的TFTP文件传输

代码&#xff1a; #include <myhead.h>//实现下载功能 int download(int cfd,struct sockaddr_in sin) {char buf[516] ""; //定义资源包char fileName[128] ""; //定义文件名printf("请输入文件名:");scanf("%s",fileName…...

抵御代码重用攻击:指针认证(PAC)和分支目标识别(BTI)

目录 一、代码重用攻击历史 二、小工具(Gadgets):它们是什么?为什么它们很危险? 三、ROP攻击...

业务逻辑漏洞

业务逻辑漏洞 扫描器扫不出来 漏洞包括 暴力破解任意用户/密码登陆短信/邮箱轰炸验证码绕过/爆破/重放/回传用户名/手机号枚举(用户名枚举&#xff1a;当用户登录时&#xff0c;显示用户名不存在&#xff0c;或密码不正确&#xff0c;两个其中一个不正确就称为用户名枚举)越…...

如何快速上手Scala Exercises:面向初学者的完整入门指南

如何快速上手Scala Exercises&#xff1a;面向初学者的完整入门指南 【免费下载链接】scala-exercises The easy way to learn Scala. 项目地址: https://gitcode.com/gh_mirrors/sc/scala-exercises Scala Exercises是一个基于Scala编程语言的开源交互式学习平台&#…...

电商人必备!AI净界RMBG-1.4批量处理商品图,效率提升10倍

电商人必备&#xff01;AI净界RMBG-1.4批量处理商品图&#xff0c;效率提升10倍 1. 电商人的痛点&#xff1a;每天被抠图折磨的日子 做电商的朋友&#xff0c;下面这个场景你一定不陌生&#xff1a; 早上9点&#xff0c;运营发来50张新款T恤的实拍图&#xff0c;要求今天下班…...

Qwen3.5-9B实战教程:app.py添加流式输出支持+前端loading状态优化

Qwen3.5-9B实战教程&#xff1a;app.py添加流式输出支持前端loading状态优化 1. 项目概述 Qwen3.5-9B是一款拥有90亿参数的开源大语言模型&#xff0c;具备强大的逻辑推理、代码生成和多轮对话能力。该模型支持多模态理解&#xff08;图文输入&#xff09;和长上下文处理&…...

OpenClaw多通道管理:Qwen3-32B同时接入飞书与钉钉机器人

OpenClaw多通道管理&#xff1a;Qwen3-32B同时接入飞书与钉钉机器人 1. 为什么需要多通道管理&#xff1f; 上周我遇到一个尴尬场景&#xff1a;团队部分成员用飞书沟通&#xff0c;另一些用钉钉。当我尝试用OpenClaw搭建自动化助手时&#xff0c;发现默认配置只能绑定单一通…...

如何解决Oracle JDBC驱动版本的兼容性问题_ojdbc8.jar与JDK版本的对应关系

不是。ojdbc8.jar 支持JDK 8及以上&#xff08;含11/17/21&#xff09;&#xff0c;关键看运行时JVM版本≥8&#xff1b;它实现JDBC 4.2规范&#xff0c;兼容Oracle 11g至21c&#xff0c;非仅限JDK 8。ojdbc8.jar 真的只支持 JDK 8 吗&#xff1f;不是。ojdbc8.jar 是 oracle 官…...

OpenClaw跨平台实战:Mac与Windows双端配置Qwen3-4B

OpenClaw跨平台实战&#xff1a;Mac与Windows双端配置Qwen3-4B 1. 为什么选择OpenClawQwen3-4B组合 去年我在整理个人知识库时&#xff0c;发现手动处理上千份PDF和网页存档效率极低。尝试过各种自动化工具后&#xff0c;最终被OpenClaw的"AI直接操控电脑"理念吸引…...

如何用Synonyms实现智能问答系统:面向初学者的完整指南

如何用Synonyms实现智能问答系统&#xff1a;面向初学者的完整指南 【免费下载链接】Synonyms :herb: 中文近义词&#xff1a;聊天机器人&#xff0c;智能问答工具包 项目地址: https://gitcode.com/gh_mirrors/sy/Synonyms Synonyms是一个强大的中文近义词工具包&#…...

macOS高效配置:OpenClaw与Qwen3.5-9B镜像深度集成指南

macOS高效配置&#xff1a;OpenClaw与Qwen3.5-9B镜像深度集成指南 1. 为什么选择OpenClaw与Qwen3.5-9B组合 去年冬天&#xff0c;当我第一次尝试用AI自动化处理日常工作报告时&#xff0c;发现大多数云端方案要么功能受限&#xff0c;要么隐私性存疑。直到遇见OpenClaw这个能…...

1985-2025年全国省/市/区县土地利用分类面积及占比统计数据

数据介绍 全国土地利用分类面积统计数据&#xff08;1985-2025&#xff09; 数据简介 本数据集基于1985-2025年30米分辨率土地利用分类数据&#xff0c;结合行政区划边界&#xff0c;提供全国省、市、县三级行政单元的土地利用分类面积及占比统计&#xff0c;为土地利用变化…...

数字示波器原理与高级测量技术详解

1. 示波器基础概念与核心功能 示波器作为电子工程师最常用的测试仪器之一&#xff0c;其核心功能是捕捉和显示电信号随时间变化的波形。现代数字示波器&#xff08;DSO&#xff09;通过模数转换器&#xff08;ADC&#xff09;将模拟信号转换为数字信号进行处理和显示&#xff0…...