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

【学习笔记】[AGC064C] Erase and Divide Game

有点难😅,看到比自己低一级的选手场切这道题就更绷不住了😇

考虑 从低到高位 建立 trie \text{trie} trie 树,但是因为是对反串建立的,所以编号连续的点在 trie \text{trie} trie 树上的位置是分散的😅

但是发现可以对 S G SG SG值相同的一段区间一起转移,具体就是自底向上合并(编号减去 2 j 2^j 2j),每一层合并完了过后的区间数目都不会超过 n n n(考虑端点的数目不会变)

让我想到了这道题 CF1864H Asterism Stream

大概也是分段转移

学了但是不会灵活运用,还是太菜了

复杂度 O ( n log ⁡ V ) O(n\log V) O(nlogV),非常优秀。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e4+5;
int T,n,m,cnt1,cnt2,cnt;
int to[3][3];
struct node{ll l,r;int v;
}a[N],b[N],c[N];
int get(int x,int y){return to[min(x,y)][max(x,y)];
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;to[0][0]=to[0][1]=to[0][2]=1,to[1][1]=0,to[1][2]=1,to[2][2]=2;while(T--){cin>>n;ll pre=0;cnt=0;for(int i=1;i<=n;i++){ll l,r;cin>>l>>r;if(pre<l)a[++cnt]={pre,l-1,2};a[++cnt]={l,r,1},pre=r+1;}if(pre<(1ll<<61))a[++cnt]={pre,(1ll<<61)-1,2};for(int i=60;i>=0;i--){cnt1=cnt2=0;for(int j=1;j<=cnt;j++){if(a[j].r<(1ll<<i)){b[++cnt1]=a[j];}else if(a[j].l>=(1ll<<i)){c[++cnt2]=a[j];}else{b[++cnt1]=a[j],b[cnt1].r=(1ll<<i)-1;c[++cnt2]=a[j],c[cnt2].l=1ll<<i;}}for(int j=1;j<=cnt2;j++)c[j].l-=1ll<<i,c[j].r-=1ll<<i;int p1=1,p2=1;cnt=0;while(p1<=cnt1&&p2<=cnt2){a[++cnt].l=b[p1].l,a[cnt].r=min(b[p1].r,c[p2].r),a[cnt].v=get(b[p1].v,c[p2].v);if(a[cnt].r==b[p1].r)p1++;else b[p1].l=a[cnt].r+1;if(a[cnt].r==c[p2].r)p2++;else c[p2].l=a[cnt].r+1;}}cout<<(a[1].v?"Takahashi":"Aoki")<<"\n";}
}

相关文章:

【学习笔记】[AGC064C] Erase and Divide Game

有点难&#x1f605;&#xff0c;看到比自己低一级的选手场切这道题就更绷不住了&#x1f607; 考虑 从低到高位 建立 trie \text{trie} trie 树&#xff0c;但是因为是对反串建立的&#xff0c;所以编号连续的点在 trie \text{trie} trie 树上的位置是分散的&#x1f605; …...

算法通关村-----数组中元素出现次数问题

数组中出现次数超过一半的数字 问题描述 数组中有一个数字出现的次数超过数组长度的一半&#xff0c;请找出这个数字。你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。详见剑指offer39 问题分析 最直接的方式就是使用hashMap,遍历给定数组&#xff0c…...

Qt-键盘消息的传递-键盘消息的获取-C++

文章目录 1.概述2.焦点3.强制获取键盘消息4.键盘常用组合方法5.总结 1.概述 QKeyEvent 类用来描述一个键盘事件。当键盘按键被按下或者被释放时&#xff0c;键盘事件便会被发送给拥有键盘输人焦点的部件。 QKeyEvent 的 key() 函数可以获取具体的按键&#xff0c;对于 Qt 中给…...

数据结构与算法(五)--链表概念以及向链表添加元素

一、前言 今天我们学习另一种非常重要的线性数据结构–链表&#xff0c;之前我们已经学习了三种线性数据结构&#xff0c;分别是动态数组&#xff0c;栈和队列。其中队列我们额外学习了队列的另一种实现方式–循环队列。其实我们自己实现过前三个数据结构就知道&#xff0c;它…...

计算机视觉与深度学习-图像分割-视觉识别任务02-目标检测-【北邮鲁鹏】

目录标题 参考目标检测定义深度学习对目标检测的作用单目标检测多任务框架多任务损失预训练模型姿态估计 多目标检测问题滑动窗口&#xff08;Sliding Window&#xff09;滑动窗口缺点 AdaBoost&#xff08;Adaptive Boosting&#xff09;参考 区域建议 selective search 思想慢…...

Flink——Flink检查点(checkpoint)、保存点(savepoint)的区别与联系

Flink checkpoint Checkpoint是Flink实现容错机制最核心的功能&#xff0c;能够根据配置周期性地基于Stream中各个Operator的状态来生成Snapshot&#xff0c;从而将这些状态数据定期持久化存储下来&#xff0c;从而将这些状态数据定期持久化存储下来&#xff0c;当Flink程序一…...

[篇五章五]-如何禁用 Windows Defender-我的创作纪念日

################################################## 目录 禁用掉烦人的 Windows Defender 在本地组策略编辑器中禁用 Windows Defende 关闭 Microsoft Defender 防病毒 禁止 Defender 开机自动运行 重新激活 Windows Defender #######################################…...

什么情况下使用微服务?

单体架构图参考网络&#xff1a; 1. 什么是单体应用 单体应用就是将应用程序的所有功能都打包成一个独立的单元&#xff0c;最终以一个WAR包或JAR包存在&#xff0c;没有外部的任何依赖&#xff0c;里面包含DAO、Service、UI等所有的逻辑。 优点&#xff1a; &#xff11;&…...

【Linux】Ubuntu美化主题【教程】

【Linux】Ubuntu美化主题【教程】 文章目录 【Linux】Ubuntu美化主题【教程】1. 安装优化工具Tweak2.下载自己喜欢的主题3. 下载自己喜欢的iconReference 1. 安装优化工具Tweak 首先安装优化工具Tweak sudo apt-get install gnome-tweak-tool安装完毕后在菜单中打开Tweak 然后…...

spring-boot2.x,使用EnableWebMvc注解导致的自定义HttpMessageConverters不可用

在json对象转换方面&#xff0c;springboot默认使用的是MappingJackson2HttpMessageConverter。常规需求&#xff0c;在工程中使用阿里的FastJson作为json对象的转换器。 FastJson SerializerFeatures WriteNullListAsEmpty &#xff1a;List字段如果为null,输出为[],而非nu…...

2023-09-20 Android CheckBox 让文字显示在选择框的左边

一、CheckBox 让文字在选择框的左边 &#xff0c;在布局文件里面添加下面一行就可以。 android:layoutDirection"rtl" 即可实现 android:paddingStart"10dp" 设置框文间的间距 二、使用的是left to right <attr name"layoutDirection">&…...

目标检测YOLO实战应用案例100讲-基于改进YOLOv5的口罩人脸检测

目录 前言 国内外研究现状 目标检测研究发展 国内外口罩人脸检测研究现状...

CentOS7 yum安装报错:“Could not resolve host: mirrorlist.centos.org; Unknown error“

虚拟机通过yum安装东西的时候弹出这个错误&#xff1a; 1、查看安装在本机的网卡 网卡ens33处于disconnected的状态 nmcli d2、输入命令&#xff1a; nmtui3、选择网卡&#xff0c;然后点击edit 4、移动到Automatically connect按空格键选择&#xff0c;然后移动到OK键按空格…...

关于token续签

通常我们会对token设置一个有效期&#xff0c;于是&#xff0c;就有了token续签的问题。由于token并没有续时机制&#xff0c;如果不能及时的替换掉过期的token&#xff0c;可能会拦截用户正常的请求&#xff0c;用户只能重新登录&#xff0c;如果提交的信息量很大&#xff0c;…...

淘宝分布式文件存储系统( 二 ) -TFS

淘宝分布式文件存储系统( 二 ) ->>TFS 目录 : 大文件存储结构哈希链表的结构文件映射原理及对应的API文件映射头文件的定义 大文件存储结构 : 采用块(block)文件的形式对数据进行存储 , 分成索引块,主块 , 扩展块 。所有的小文件都是存放到主块中的 &#xff0c;扩展块…...

Java中synchronized:特性、使用、锁机制与策略简析

目录 synchronized的特性互斥性可见性可重入性 synchronized的使用方法synchronized的锁机制常见锁策略乐观锁与悲观锁重量级锁与轻量级锁公平锁与非公平锁可重入锁与不可重入锁自旋锁读写锁 synchronized的特性 互斥性 synchronized确保同一时间只有一个线程可以进入同步块或…...

记一次clickhouse手动更改分片数异常

背景&#xff1a;clickhouse中之前是1分片1副本&#xff0c;随着数据量增多&#xff0c;想将分片数增多&#xff0c;于是驻场人员手动添加了分片数的节点信息 <clickhouse><!-- 集群配置 --><clickhouse_remote_servers><feihuang_ck_cluster><sha…...

深度学习论文: ISTDU-Net:Infrared Small-Target Detection U-Net及其PyTorch实现

深度学习论文: ISTDU-Net&#xff1a;Infrared Small-Target Detection U-Net及其PyTorch实现 ISTDU-Net&#xff1a;Infrared Small-Target Detection U-Net PDF: https://doi.org/10.1109/LGRS.2022.3141584 PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTo…...

图像识别-YOLO V8安装部署-window-CPU-Pycharm

前言 安装过程中发现&#xff0c;YOLO V8一直在更新&#xff0c;现在是2023-9-20的版本&#xff0c;已经和1月份刚发布的不一样了。 eg: 目录已经变了&#xff0c;旧版预测:在ultralytics/yolo/v8/下detect 新版&#xff1a;ultralytics/models/yolo/detect/predict.py 1.安…...

js禁用F1至F12、禁止缩放、取消选中并且取消右键操作、打印、拖拽、鼠标点击弹出自定义信息、禁用开发者工具js

禁用js //禁止缩放 //luwenjie hualun window.addEventListener(mousewheel, function (event) {if (event.ctrlKey true || event.metaKey) {event.preventDefault();} }, {passive: false});//firefox window.addEventListener(DOMMouseScroll, function (event) {if (even…...

Zabbix5.0_介绍_组成架构_以及和prometheus的对比_大数据环境下的监控_网络_软件_设备监控_Zabbix工作笔记

z 这里Zabbix可以实现采集 存储 展示 报警 但是 zabbix自带的,展示 和报警 没那么好看,我们可以用 grafana进行展示,然后我们用一个叫睿象云的来做告警展示, 会更丰富一点. 可以看到 看一下zabbix的介绍. 对zabbix的介绍,这个zabbix比较适合对服务器进行监控 这个是zabbix的…...

百度SEO优化TDK介绍(分析下降原因并总结百度优化SEO策略)

TDK是SEO优化中很重要的部分&#xff0c;包括标题&#xff08;Title&#xff09;、描述&#xff08;Description&#xff09;和关键词&#xff08;Keyword&#xff09;&#xff0c;为百度提供网页内容信息。其中标题是最重要的&#xff0c;应尽量突出关键词&#xff0c;同时描述…...

搭建自动化 Web 页面性能检测系统 —— 设计篇

页面性能对于用户体验、用户留存有着重要影响&#xff0c;当页面加载时间过长时&#xff0c;往往会伴随着一部分用户的流失&#xff0c;也会带来一些用户差评。性能的优劣往往是同类产品中胜出的影响因素&#xff0c;也是一个网站口碑的重要评判标准。 一、名称解释 前端监控…...

记一次 mysql 数据库定时备份

环境&#xff1a;Centos 7.9 数据库&#xff1a;mysql 8.0.30 需求&#xff1a;生产环境 mysql 数据&#xff08;约670MB&#xff09;备份。其中存在大字段、longblob字段 参考博客&#xff1a;Linux环境下使用crontab实现mysql定时备份 - 知乎 一、数据库备份 1. 备份脚本。创…...

淘宝分布式文件存储系统(一) -TFS

淘宝分布式文件存储系统( 一 ) ->>TFS 目录 : 什么是文件系统文件存储的一些概念文件的结构系统读取文件的方式为什么采用大文件结构的原因 文件系统 : 将我们的数据整合成目录或者文件,提供对文件的存取接口,基于文件的权限进行访问,简单的说,文件系统就是对文件进行…...

LLM各层参数详细分析(以LLaMA为例)

网上大多分析LLM参数的文章都比较粗粒度&#xff0c;对于LLM的精确部署不太友好&#xff0c;在这里记录一下分析LLM参数的过程。 首先看QKV。先上transformer原文 也就是说&#xff0c;当h&#xff08;heads&#xff09; 1时&#xff0c;在默认情况下&#xff0c; W i Q W_i…...

linux ansible(三)

ansible 配置详解 3.1 ansible 安装方式 ansible安装常用两种方式&#xff0c;yum安装和pip程序安装 3.1.1 使用 pip&#xff08;python的包管理模块&#xff09;安装 需要安装一个python-pip包&#xff0c;安装完成以后&#xff0c;则直接使用pip命令来安装我们的ansible包 …...

Anaconda和Pycharm详细安装 配置教程

Anaconda&#xff1a;是一个开源的Python发行版本&#xff0c;其中包含了conda、Python等180多个科学包及其依赖项。【Anaconda下载】 PyCharm&#xff1a;PyCharm是一种Python IDE&#xff0c;带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具。【PyCharm下载】…...

利用Linux虚拟化技术实现资源隔离和管理

在现代计算机系统中&#xff0c;资源隔离和管理是非常重要的&#xff0c;特别是在多租户环境下。通过利用Linux虚拟化技术&#xff0c;我们可以实现对计算资源&#xff08;如CPU、内存和存储&#xff09;的隔离和管理&#xff0c;以提供安全、高效、稳定的计算环境。下面将详细…...

12基于MATLAB的短时傅里叶变换( STFT),连续小波变换( CWT),程序已调通,可以直接运行。

基于MATLAB的短时傅里叶变换( STFT),连续小波变换( CWT),程序已调通&#xff0c;可以直接运行...

网站建设价格明细表/社会新闻最新消息

单反相机的长曝镜头拍出来的流水像极了牛奶丝&#xff0c;还有摄影师将光轨拍出模糊动感效果&#xff0c;画面很好看。忍不住被这样的画面吸引住&#xff0c;没有专业相机能否拍出这样的效果呢&#xff1f;手机能不能实现长曝呢&#xff1f;这一次的技巧就教你如何实现手机相机…...

附近计算机培训班咨询/seo关键词seo排名公司

2021~2021计算机基础知识练习题 20212021计算机基础知识练习题北京联合大学20212021计算机基础知识练习题一、选择题1.记录在存储介质上的一组相关信息的集合称为______。A)程序 B)磁盘 C)软件 D)文件2.当一个文件更名后&#xff0c;文件的内容会______。A)完全消失 B)完全不变…...

高端企业网站建站程序/线上培训机构

Thymeleaf是一个Java模板引擎开发库&#xff0c;可以处理和生成HTML、XML、JavaScript、CSS和文本&#xff0c;在Web和非Web环境下都可以正常工作。 Thymeleaf可以跟Spring boot很好的集成。 整合步骤 1.修改pom.xml 增加下面代码片段&#xff1a; <dependency><grou…...

贵阳学校网站建设/今日小说搜索风云榜

大家好&#xff0c;我是老赵Java 之父 James Gosling 近日发表推特称&#xff0c;开发者应尽快弃用 JDK 8&#xff0c;可以选择 JDK 17 LTS&#xff0c;因为后者在各个方面都带来了巨大的改进。不过醉翁之意不在酒&#xff0c;原来 Java 之父只是为了给东家 AWS 的 OpenJDK 发行…...

3d打印 东莞网站建设/线上推广的方式有哪些

前置知识&#xff1a;二叉排序树&#xff0c;堆。 应用场景&#xff1a;平衡树。 〇、导入 1. 二叉排序树 我们都知道&#xff0c;二叉排序树就是满足“\(lch<now<rch\)”&#xff08;左儿子小于根节点&#xff0c;右儿子大于根节点&#xff09;的二叉树&#xff0c;一…...

温州网站建设制作/长沙优化排名推广

转自&#xff1a;http://www.zgg.org.cn/jgwh/kpgy/kepu/201501/t20150114_494710.html“要是时间能停下来那就好了&#xff0c;哪怕只有一秒钟。”以往在动画中出现的桥段即将发生在现实中啦。1月12日&#xff0c;中科院国家授时中心预告&#xff0c; 2015年6月30日&#xff0…...