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

CF 1365 题解

时间:2024-11-08 11:02:01浏览次数:1  
标签:标号 一个 题解 元素 CF 二进制位 1365 集合

CF 1365 题解

A Matrix Game

注意到每次操作都相当于会损失一行和一列, 那么最多进行可用行列较少的那一个的轮数. 判断奇偶性即可,

B Trouble Sort

手玩发现, 不管一个属性的元素集合内部多么无序, 都可以借助一个其它属性的元素达到有序.

归纳证明特别简单.

因此, 一个序列可以被排序当且仅当它已经有序或者包含多种元素.

C Rotation Matching

由于两个序列都是排列, 只需要枚举值, 每一个值都有唯一的偏移量使得它对答案有贡献.

开个桶记录每个偏移量能获得多少答案, 找最大值即可.

D Solve The Maze

考虑贪心.

发现把每个坏人当场用墙围住一定比延后封闭更优.

因此把坏人周围建墙后判断好人到终点的可达性即可.

E Maximum Subsequence Value

首先, \(n\leq3\) 的情况特别平凡.

其次, 考虑选择大小不超过 \(3\) 的集合, 那么贡献是这三个元素按位或, 可得所选集合一定不小于 \(3\).

考虑选择大小不小于 \(3\) 的集合.

结论: 若选择一个集合 \(S\) , 且 \(|S|\geq 3\) , 那么总存在一个三元集 \(A\subseteq S\) , 使得 \(A\) 比 \(S\) 不劣.

证明:

记集合 \(Q\) 对答案贡献为 \(w(Q)\).

首先考虑任意选择一个元素 \(x\in S\), 那么对于每一个 \(w(S)\) 中有而 \(w(A)\) 没有的二进制位, 都满足它在 \(S\) 中只有 \(x\) 和另一个位置 \(y\) 处不存在. 这时再选择一个异于 \(x\) 的位置 \(k\) , 这时对于每一个 \(w(S)\) 中有而 \(w(A)\) 没有的二进制位, 都满足它在 \(S\) 中只有 \(x\) 和 \(k\) 处不存在.

这时再选择一个异于 \(x\) 和 \(k\) 的位置, 就有 \(w(A)\geq w(S)\).

因此这道题只要 \(O(n^3)\) 枚举三元集就可以了.

F Swaps Again

考虑两个关于中心点对称的元素, 发现交换后关于中心依然对称.

因此判断这个条件加上中心点不变就可以了.

G Secure Password

考虑把每个元素重标号为一个 \(13\) 位的二进制数, 并且其中恰有 \(6\) 个 \(1\).

考虑查询每个第 \(i\) 位是 \(1\) 的集合中的元素, 然后第 \(k\) 个元素的答案就是它的标号所有 \(0\) 的位对应答案的按位或.

原因在于我们约束每个元素标号所含 \(1\) 的个数一致, 因此标号不存在子集关系, 对于每一个 \(i\) 和 \(j\not=i\), 都存在一个二进制位 \(x\) 使得 \(i\) 中为 \(0\) , \(j\) 中为 \(1\).

标签:标号,一个,题解,元素,CF,二进制位,1365,集合
From: https://www.cnblogs.com/snowycat1234/p/18534664

相关文章

  • P5479 [BJOI2015] 隐身术 题解
    题目传送门前置知识后缀数组简介|字符串哈希|二分解法考虑分别计算出编辑距离恰好等于\(k_{0}\in[0,k]\)的答案。观察在编辑距离的存在下,长度差至多为\(k\)。考虑设\(f_{i,j}\)表示最大的\(x\)使得\(s_{1\simx}\)和\(t_{1\simx+j}\)可以在\(i\)次编......
  • P7984 [USACO21DEC] Tickets P 题解
    题目传送门前置知识线段树优化建图|最短路解法考虑对票建虚点,从\(c_{i}\)向\(i+n\)连一条权值为\(p_{i}\)的边,然后从\(i+n\)向\([a_{i},b_{i}]\)连一条权值为\(0\)的边。建出反图后\(1\toi\)和\(n\toi\)的路径集合会有重复统计的部分,不妨以\(dis_{1,i......
  • 快速上手Docker部署Flask项目 附常见问题解决
    一、准备Flask项目1.项目结构有一个app.py文件作为主应用程序入口,内容示例:fromflaskimportFlaskapp=Flask(__name__)@app.route('/')defhello_world():return'Hello,World!'if__name__=='__main__':app.run(host='0.0.0.0&#......
  • P9192 [USACO23OPEN] Pareidolia P 题解
    P9192[USACO23OPEN]PareidoliaP题解首先自然考虑不带修的情况。考虑问题的本质就是求序列中尽量短的bessie序列个数。对于尽量短的理解是对于bessiebessie序列,不考虑其由\(1,8\sim12\)构成的序列,只考虑\(1\sim6,7\sim12\)组成的序列。于是考虑dp:设\(dp_{i......
  • CF1956F Nene and the Passing Game 题解
    处理很妙的题,部分细节请教了未来姚班zyl和LYH_cpp,在此鸣谢。首先考虑把题目给的式子进行转化,设\(i<j\),那么\(i\)和\(j\)能传球当且仅当\(l_i+l_j\lej-i\ler_i+r_j\)。移项并拆开得到,\(i+l_i\lej-l_i\)且\(i+r_i\gej-r_j\),如果画到数轴上的话......
  • CF Round 982(Div 2)
    游记还是VP口胡了ABCD的做法,然后C假了打代码其实挺难的题解A反复观看样例可知,如果两个开关状态不一样灯泡开,否则灯泡关如果要灯泡开着的尽可能少,那么相同状态的配对尽可能多此时就是\(0\)和\(0\)配对,\(1\)和\(1\)配对,如果有落单的\(0\)必定有落单的\(1\),最多凑\(1\)对没......
  • CF Round 984 C. Anya and 1100(模拟)
    传送门https://codeforces.com/contest/2036/problem/C解题思路先扫一遍字符串,判断有几个1100子串。然后,对于每一次操作,可以算出对答案的影响,减去更改会减少的子串,再加上更改后会增加的子串。代码#include<bits/stdc++.h>usingnamespacestd;chars[200001];intq......
  • 题解:P11253 [GDKOI2023 普及组] 小学生数学题
    所求的式子带除法,模意义下除法计算复杂度带\(\log\)太慢了,先改写成乘法:\(\sum_{i=1}^ni!\timesi^{-k}\)。想求这个式子,最简单的思路就是对于每个整数\(i\in[1,n]\),分别预处理出\(i!\)和\(i^{-k}\)的值,最后乘起来再\(O(n)\)暴力加起来就好了!对于\(i!\),注意到:\[i!=\b......
  • 雷达目标检测cfar小白版本
     一编2024.11.7日 目前只是简单概念后续持续更**参考单元**和**保护单元**的概念###1.什么是保护单元?**保护单元**是指在检测过程中,紧邻目标检测单元的几个位置(也称距离单元)。这些单元的作用是**防止目标信号影响噪声估计**。例如,如果我们想在位置\(i\)检测......
  • P4621 [COCI2012-2013#6] BAKTERIJE 题解
    一道很好的数学题。首先不难想到每个细菌的移动路线是有循环节的,循环节外的时间最多就是每个格子的四个方向都走一遍,也就是\(4\timesN\timesM\)。可以预处理每个细菌分别通过四个方向第一次到达终点的时间\(b_{i,0/1/2/3}\)和再次回到当前状态的循环节长度\(md_{i,0/1/2/......