首页 > 其他分享 >CF R864 div2

CF R864 div2

时间:2023-04-12 20:13:13浏览次数:29  
标签:R864 CF div2 答案 集合 操作 我们 步数

A

 发现最劣的方案就是把其中一个围起来,答案为 \(4\),当 \(x=1/x=n/y=1/y=m\) 时答案有可能为 \(2/3\)
分类讨论即可

B

 要将原图形变为中心对称,若\((x,y)!=(n-x+1,n-y+1)\)我们必须操作,若步数有剩,剩余步数是偶数时对一个方块一直操作即可;剩余步数为奇数时,我们还需判断\(n\)的奇偶性,奇数时依旧合法(对中央的方块操作即可)

C

 这题策略本身不难,交互题。我们先询问 \((1,1)\),我们可以计算出国王的 \(x/y\)。
我们再询问 \((t+1,t+1)\),\(t\) 为交互所得答案。
分类讨论可以得出答案。

D

 我们分析旋转后哪些变量会改变,发现只要确定新的儿子,那么其他信息都可以快速完成。所以问题等价转化为找旋转后的儿子。
发现这是一个无序的有两个扼要属性的集合(子树大小及其编号),我们以这两个信息为关键字维护集合 \(S\),先把所有重儿子放在集合中,然后可以在\(O(logn)\)的时间内查询对应新儿子。
而在此基础上,我们可以更新 \(S\) 集合,从而维护旋转操作。
对于查询操作,直接输出信息。

标签:R864,CF,div2,答案,集合,操作,我们,步数
From: https://www.cnblogs.com/P32sx-qq1309267816-tel18081238250/p/17311075.html

相关文章

  • Docusaurus 配合 DocFX
    目标&背景最近公司刚刚搭好Docusaurus文档环境,刚好在即刻看到叫我三叔就行用户提到的DocFX自动生成C#API的工具,此工具最终会生成一组yaml文件,然后进行web的绘制,这个和Docusaurus刚好冲突现有的文档不兼容,着实有些遗憾,本篇文章会介绍如何兼容这两个工具DocFxMa......
  • CF698F Coprime Permutation 题解
    题意给定一个未填满的数组\(p\),求有多少种\(1\simn\)的排列\(p\)满足对于任意\(i<j\),都有\([\gcd(i,j)=1]=[\gcd(p_i,p_j)=1]\),答案对\(10^9+7\)取模。题解部分参考这篇题解(感觉这篇题解应该是目前为止最详细的吧)。记\(P\)为\([1,n]\)中所有素数与\(1\)构成......
  • CF1525F 题解
    题意有一个\(n\)个点的DAG,现在有\(k\)波进攻,第\(i\)波有\(i\)个人,它们每个人会选择一条DAG上的路径,并占领这个路径上的所有点,路径之间是不能相交的。第\(i\)波进攻前可以做一些准备,可以花\(1\)秒关闭某个点的所有入边,或关闭某个点的所有出边。第\(i\)波进攻有个......
  • cf-div2-856c
    题目链接:https://codeforces.com/contest/1816/problem/C我是傻逼,否了自己的第一直觉。。。思路:构造方法:以最后一个值的数值\(x\)为基准,把所有的的数字(除第一个)调整为\(x\)。以n的奇偶性分为两种情况。当n为奇数时:\(第一个数字y小于等于x,构造成功。否则就除了第一个数字外......
  • 练习记录-cf-div2-865(A-C)
    反转就是写的非常烂Awa10其他还行吧丢人A.IanVisitsMary如果这两个数的gcd是1可以直接过去如果是0那就绕一个1过去变成三角形不然就用(1,b-1)到(a,1)这样就是两次的1不会遇到#include<bits/stdc++.h>#defineclosestd::ios::sync_with_stdio(false),cin.ti......
  • CF486D 题解
    题目传送门题目分析不算很难的树形\(\text{dp}\)。令\(dp_i\)表示以\(i\)为根的子树中联通子图的个数。在更新的时候,考虑儿子的联通子图和自己的,则有:\[dp_u=dp_u\times(dp_v+1)\]选根的时候将\(a\)最大的作为根节点。还要注意另外一点,就是当\(a_{fa}=a_{v}\)......
  • CF1599A. Weights
    题意给出n个物品,第i个重量a[i](互不相同)每次任意选一个物品放到秤的左右两边,使得放完之后左>右或左<右给出a[i]和大小关系s[i],构造方案题解必定有解把a排序,假设当前选了LRLRLR,发现在最后加L可以瞬间反转,在最前加R可以保持不变即,当前选了一段连续的a[i],放的顺序为...LRL......
  • FastCFS:再谈 选主 与 过半写:续:2节点+vote节点 群集
    偶数的 2节点+vote节点群集健壮程度如何呢?先说结论:可以保证足够健壮。 虽然vote节点仅参与选主,不参与数据复制过程的过半写,but,对于FastCFS群集来说,先要完成“选主”才能正常进行数据复制层面的”过半写“!如果没有“选主”,根本就不会有后续“过半写”的问题。哈哈。 所......
  • 练习记录-cf-div2-856(A-C)
    vp的写出4道C感觉目前不是能力范围以后有机会留下来打比赛的话再说A-PrefixandSuffixArray给出字符串的前缀和后缀问是不是回文 我采用枚举长度为n-1和1的拼凑但是这并不奏效一直wa3后来改用拼两个n/2的就过了如果有大佬看到了希望能解答一下qwq#include<b......
  • 练习记录-cf-div2-864(A-D)
    状态不怎么好场上就写出3道还磨磨蹭蹭推错结论qwq 警钟长鸣A.LiHuaandMaze一开始以为要切割发现就把其中一个包起来就行了计算包某个块需要的最小块数#include<bits/stdc++.h>#defineclosestd::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)usingn......