首页 > 其他分享 >CF1867E1 Salyg1n and Array (simple version)

CF1867E1 Salyg1n and Array (simple version)

时间:2023-09-12 12:24:51浏览次数:51  
标签:Salyg1n cout simple sum CF1867E1 颠转 异或 长度 余数

思路

首先考虑,\(n\) 是 \(k\) 的倍数的情况,直接枚举询问所有每一段就好,然后输出每一段的异或和的异或和。

如上图,每次询问都没有重叠部分,颠转互不干扰。

那么,\(n\) 不是 \(k\) 的倍数的情况呢?

可以看到,与第一种情况的区别就是末尾多了一小截,那么我们需要考虑如何计算这一小截的异或和。

很容易想到,提前在前面计算这个长度的异或和,后续就可以和第一种情况一样了。

可以发现,解题的关键就是查询后会颠转这个特殊性质,见下图:

因为异或的性质,自己异或自己会变成 \(0\),所以同一段的异或两次就会变成 \(0\)。使用这个性质可以发现,如果两个询问区间重叠,那么因为颠转,获得的异或和会转移到一起。

那么我们可以考虑先构造出前面一截是余数长度的区间的异或何,后续就是第一种情况了。

因为每次取得区间长度都是固定的,所以两段红色的区间长度也一定一样,因为两段长度和是余数,所以一段我们就取余数的一半。

因为 \(n\) 和 \(k\) 在题目中都给定了是正偶数,所以不用担心余数是奇数的情况。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,k,sum,a;
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>k,sum=0;
		if(n%k)
		{
			cout<<"? 1"<<endl;
			cin>>a,sum^=a;
			cout<<"? "<<1+(n%k)/2<<endl;
			cin>>a,sum^=a;
		}
		for(int i=(n%k)+1;i<=n;i+=k) cout<<"? "<<i<<endl,cin>>a,sum^=a;
		cout<<"! "<<sum<<endl;
	}
	return 0;
}

标签:Salyg1n,cout,simple,sum,CF1867E1,颠转,异或,长度,余数
From: https://www.cnblogs.com/One-JuRuo/p/17695828.html

相关文章

  • Vue简单浮动标签(simple floating labels)
    简介及使用教程Vue简单浮动标签(simplefloatinglabels)是一个基于Vue.js的简单浮动表单标签组件,支持自定义颜色、边框及错误信息。安装npmivue-simple-floating-labels使用引入组件importFloatingLabelfrom'vue-simple-floating-labels'exportdefault{......
  • F1. Omsk Metro (simple version)
    F1.OmskMetro(simpleversion)Thisisthesimpleversionoftheproblem.Theonlydifferencebetweenthesimpleandhardversionsisthatinthisversion$u=1$.Asisknown,OmskisthecapitalofBerland.Likeanycapital,Omskhasawell-developedm......
  • 云原生之部署Docker管理面板SimpleDocker
    (云原生之部署Docker管理面板SimpleDocker)一、SimpleDocker介绍1.SimpleDocker简介SimpleDocker是一个简单的Docker控制面板,致力于可以让开发者更方便,更无障碍的使用Docker,其界面简洁,操作便捷。2.SimpleDocker特点当前版本的特点镜像 详情、拉取、运行、导出、导......
  • Simple and Convenient Diagnostic Tools: A Comprehensive Review
    Intoday'stechnologicallyadvancedworld,theautomotiveindustryhaswitnessedsignificantadvancementsindiagnostictools.Thesetoolshavebecomeanintegralpartofeverymechanic'stoolbox,enablingthemtodiagnoseandresolveissueseff......
  • pip install numpy -i https://pypi.tuna.tsinghua.edu.cn/simple
    pipinstallnumpy-ihttps://pypi.tuna.tsinghua.edu.cn/simpleLookinginindexes:https://pypi.tuna.tsinghua.edu.cn/simpleCollectingnumpyDownloadinghttps://pypi.tuna.tsinghua.edu.cn/packages/8b/d9/22c304cd123e0a1b7d89213e50ed6ec4b22f07f1117d64d28f81c08......
  • 题解 ABC309Ex【Simple Path Counting Problem】
    好好玩的题。设普通生成函数\(F_i\),其中\([z^k]F_i\)表示从所有起点走到\((i,k)\)的方案数。特别地,\([z^k]F_1=\sum\limits_{a\inA}[a=k]\)。注意到\(F_i=(z^{-1}+1+z)F_{i-1}\)几乎成立,但是在\([z^1]F_i\)和\([z^M]F_i\)处不成立。尝试对\(F_i\)进行改造:\[[z^k......
  • Atcoder_[abc284E]Count Simple Paths题解
    题目链接这题就是很简单的图上深搜,我觉得放在E题太水了,代码里有详细注释。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvector<int>v[200010];//邻接表intans;//答案boolvis[200010];//vis[i]记录i号点有没有被访问过voiddfs(intx)......
  • SimpleDateFormat 线程安全问题修复方案
    问题介绍在日常的开发过程中,我们不可避免地会使用到JDK8之前的Date类,在格式化日期或解析日期时就需要用到SimpleDateFormat类,但由于该类并不是线程安全的,所以我们常发现对该类的不恰当使用会导致日期解析异常,从而影响线上服务可用率。以下是对SimpleDateFormat类不恰当......
  • 解决Cnblogs-Theme-SimpleMemory应用后博客加载缓慢问题
    在应用Cnblogs-Theme-SimpleMemory(https://github.com/BNDong/Cnblogs-Theme-SimpleMemory)美化博客之后,发现博客访问缓慢,甚至直接无法加载。为解决问题,仔细观察安装应用源码后,在其安装使用说明网站(点击访问)中找到以下代码行:该网址指向CloudFlare所提供的CDN加速服务,拉取了d......
  • SAP Commerce Cloud 中的 SimpleResponsiveBannerComponent
    SAPCommerceCloud(以下简称SAPCC)是一款综合性的电子商务解决方案,旨在帮助企业建立和管理现代化的电子商务平台。SimpleResponsiveBannerComponent是SAPCC中的一个核心组件,专门用于管理和展示响应式横幅广告。它允许商户轻松地在其电子商务平台上添加、配置和管理各种横幅......