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

一些做题记录(2025 2-3)

【MX-X9-T2】『GROI-R3』XOR

题目要求求区间异或和,先转化成前缀异或和。

\(0\)\(n\) 的异或和是有规律的。

\(F(n)=0\oplus1\oplus\cdots\oplus n\),则有:

\[F(n)=\begin{cases} n,&n\equiv 0\pmod4,\\ 1,&n\equiv 1\pmod4,\\ n+1,&n\equiv 2\pmod4,\\ 0,&n\equiv 3\pmod4. \end{cases} \]

题目要求 \(F(n)\oplus F(k-1)=x\),可转化为 \(F(n)=x\oplus F(k-1)\)。令 \(t=x\oplus F(k-1)\),也就是说我们要找到一个 \(n\in[l,r]\),使得 \(F(n)=t\)

下面我们分类讨论:

  • \(n\equiv 0\pmod4\) 时:\(F(n)=n \Rightarrow n=T(T\equiv 0\pmod4)\)
  • \(n\equiv 1\pmod4\) 时:\(F(n)=1 \Rightarrow T=1\)
  • \(n\equiv 2\pmod4\) 时:\(F(n)=n+1 \Rightarrow n=T-1(T\equiv 3\pmod4)\)
  • \(n\equiv 3\pmod4\) 时:\(F(n)=0 \Rightarrow T=0\)

因此:

  1. 如果 \(T=1\),则只要在区间内存在 \(n\equiv1\pmod4\) 的数即可。我们可以选区间内最小的 \(n\equiv1\pmod4\)
  2. 如果 \(T=0\),则必须选 \(n\equiv3\pmod4\),选区间内最小的 \(n\equiv3\pmod4\)
  3. 如果 \(T\not\in\{0,1\}\)
    • \(T\equiv0\pmod4\),则必须有 \(n=T\),检查 \(T\in[l,r]\)
    • \(T\equiv3\pmod4\),则必须有 \(n=T-1\),检查 \(T-1\in[l,r]\)
    • 其他情况无解。

参考代码

#include<iostream>
using namespace std;
int T,l,r,k,x;
int get(int x){if(x%4==0) return x;if(x%4==1) return 1;if(x%4==2) return x+1;if(x%4==3) return 0;
}
void solve(){cin>>l>>r>>k>>x;int a=get(k-1);int t=a^x;if(t==1){for(int i=l;i<=r;i++)if(i%4==1){cout<<i<<'\n';return;} cout<<-1<<'\n';return;}if(t==0){for(int i=l;i<=r;i++)if(i%4==3){cout<<i<<'\n';return;} cout<<-1<<'\n';return;}if(t%4==0&&t>=l&&t<=r){cout<<t<<'\n';return;}if(t%4==3&&t-1>=l&&t-1<=r){cout<<t-1<<'\n';return;}cout<<"-1\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>T;while(T--) solve();return 0;
}

AC 记录

http://www.hskmm.com/?act=detail&tid=25509

相关文章:

  • 智慧决策的透明化路径:“空白金兰契”架构下的“悟空备案制”研究
  • 笔记:寻找适合自己的简历工具(YAMLResume)
  • 实用指南:Linux 权限管理入门:从基础到实践
  • vue插槽
  • Magnet Axiom 9.6 新增功能概览 - 数字取证与分析
  • Windows 11 24H2 中文版、英文版 (x64、ARM64) 下载 (2025 年 9 月发布)
  • Windows 11 25H2 正式版发布,新增功能简介
  • 无法定时发送
  • 计算能力的重要性:从内存配置到进程迁移的未来展望
  • MongoDB财报超预期,文档数据库技术解析
  • 深入解析:【RabbitMQ】- Channel和Delivery Tag机制
  • 2020CSPS T1 儒略日题解
  • 调用百度AI接口实现网络图片中的文字识别
  • 英语_阅读_ChatGPT_待读
  • 实用指南:React 组件异常捕获机制详解
  • win11 为什么我的程序断网就转入导后台进程
  • 深入解析:AI与区块链:数据确权与模型共享的未来
  • 10.6阅读笔记
  • hetao 国庆
  • 详细介绍:运维 pgsql 安装完后某次启动不了
  • visual studio
  • [MCP] StreamableHTTPServer
  • 牛客 周赛109 20250924
  • 罗技G102螺丝型号
  • 详细介绍:深入剖析C#构造函数执行:基类调用、初始化顺序与访问控制
  • 英语_阅读_Let your baby go_待读
  • 第三章习题
  • 系统管理员的日常困境与幽默自嘲
  • AI数据标注平台获融资挑战行业巨头
  • 详细介绍:如何用 pnpm patch 给 element-plus 打补丁修复线上 bug(以 2.4.4 修复 PR#15197 为例)