首页 > 其他分享 >CF 1438 题解

CF 1438 题解

时间:2024-11-06 20:09:22浏览次数:1  
标签:两个 题解 CF 1438 异或 序列

CF 1438 题解

A Specific Tastes of Andre

考虑一种非常简单的构造 :\(a_i=1\). 不难发现满足条件.

B Valerii Against Everyone

结论: 符合条件当且仅当有两个一样的元素.

证明:

充分性显然, 下证必要性.

若不存在两个一样的元素, 则由于无法进位, 故没有办法得到两个区间和在相同二进制位上为 \(1\), 证毕.

C Engineer Artem

可以选择是否 \(+1\) 相当于可以控制奇偶性. 于是只要相邻格黑白染色后让黑格中是奇数, 白格中是偶数就一定不会有相邻格子中的数一样.

D Powerful Ksenia

一个重要的观察是, 在操作前后, 整个序列的异或和不会改变.

如果序列长度是奇数, 那么只需要如下构造:

\[(1,2,3),(3,4,5),\dots,(n-2,n-1,n) \]

就可以让最后一个数是原序列异或和, 前面的数每两个之间相等.

然后把每两个相等的位置和最后一个数操作一下, 就可以让每个数都是原序列异或和.

如果是偶数:

首先, 最后局面所有数异或和一定是 \(0\) , 那么原序列异或和必然为 \(0\) , 否则无解.

否则把前 \(n-1\) 个数跑一遍如上构造, 此时前 \(n-1\) 个数都一样, 由于整个数列异或和为 \(0\), 那么此时最后一个元素和前面也一样, 操作结束.

E Yurii Can Do Everything

\(O(n^2)\) 的暴力是容易的. 考虑优化:

我们首先钦定 \(a_l\) 必须小于 \(a_r\) , 然后反过来再跑一遍.

有什么好处呢? 这样 \(sum_{r-1}-sum_l=a_l\oplus a_r<2^k.\) 其中 \(k= \lceil \log_2 a_l\rceil\).

这样, 对于每一个 \(a_r\) 和 \(k\), 只会被枚举 \(3\) 次, 因为如果有更多次的话, 中间会超过 \(2^k\), 因此复杂度 \(O(n \log n)\).

F Olha and Igor

如果纯随机去操作, 有很大概率随机到根节点的两个子节点.

这意味着, 可以先操作一些次, 找到出现频次最大的两个答案, 然后枚举根节点的编号询问 \(n-2\) 次就可以了.

注意刷新输出流.

标签:两个,题解,CF,1438,异或,序列
From: https://www.cnblogs.com/snowycat1234/p/18530936

相关文章

  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • CF963-Div2-E. Xor-Grid Problem
    CF963-Div2-E.Xor-GridProblem题意给定一个\(n\timesm\)的矩阵\(a\),有两种操作:选择一行,把每个数变成所在列所有数的异或之和。选择一列,把每个数变成所在行所有数的异或之和。求进行任意次操作后整个矩阵最小的美丽值。思路第一个发现:同一数异或两次相当于没有异......
  • CF的背包DP (备用笔记)
    源自vjudge上找到题目,都是背包DP的变式------(推荐点点前两个字......
  • CF2001 题解
    A给定循环数组,每次操作时,设当前大小为m。选择$i\in[0,m)$,若满足$a_i\lea_{i+1\bmodm}$,则可删除$a_i,a_{i+1\bmodm}$中的任意一个。求最小的操作次数,使得数组中所有元素都相等。$n\le100$操作非常强,除了两个相邻位置相等的情况,可以删除任意元素。然而所有位置都......
  • 暂存的题解
    P4011孤岛营救问题感觉其实我能想出来,但是对难题产生了恐惧,直接看题解了,确实简单,很抱歉浪费了一道题。数据范围很小,搜索bfs,钥匙直接状态压缩,找到答案立即返回,否则就无解。我们要彻底的分析问题,为什么我想不到,以后我要怎么总结,首先看到题之后要先看数据范围,看到数据范围非常小......
  • E. Reverse the Rivers(二分)CF984
    题意:给定n个国家,k个地区,aij为第i个国家第j个地区,bij=a1j|a2j|---aij为第i个国家第j个地区的更新值,给出q个问题,每个问题包含m项要求,国家i必须满足m项要求:如果o=='<'必须满足bir<c否则bir>c,输出满足所有条件的最小序号的国家分析:如果o是小于号,用二分找到右区间,如果o是大于号,用二......
  • [USACO22JAN] Minimizing Haybales P 题解
    [USACO22JAN]MinimizingHaybalesP随机化?五分。显然对于任意\(a_i,a_j\),若\(|a_i-a_j|>K\),则这两堆草的先后顺序永远不会改变。所以易得暴力:对于所有这样的\(i,j\),不妨设\(i<j\),则连一条\(i\toj\)的边,答案就是这个图字典序最小的拓扑排序,优先队列即可。voidtoposort(......
  • [USACO21DEC] Tickets P 题解
    [USACO21DEC]TicketsP首先我们思考暴力的\(O(n^2)\)怎么做。显然比起每次以\(i\)为起点跑\(n\)遍最短路,建反图后分别以\(1\)和\(n\)为起点跑两遍最短路是更加经济的方式。然后你可能会以为\(\text{dis}(1,i)+\text{dis}(n,i)\)就是答案了,之后你就会发现连样例都过......
  • 【问题解决】java.lang.SecurityException: JCE cannot authenticate the provider BC
    问题复现历史项目升级JDK(由1.7升级到8),进行加密/解密时出现报错java.lang.SecurityException:JCEcannotauthenticatetheproviderBC。问题原因Wikipa上查到JCE的描述如下:JavaCryptographyExtension(JCE)isanofficiallyreleasedStandardExtensiontotheJavaPl......
  • 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间
    问题复现项目上历史项目为解决漏洞扫描从Tomcat6.0升级到了9.0版本,服务启动的日志显示如下警告,数据源是通过JNDI方式在server.xml中配置的,控制台上狂刷无法找到表空间的错误(没截图)报错:06-Nov-202410:32:03.701警告[main]java.util.ArrayList.forEachName=数据源Proper......