首页 > 其他分享 >CFR-755-Div-2解题报告

CFR-755-Div-2解题报告

时间:2023-03-01 16:03:28浏览次数:64  
标签:info frac 755 no times Div CFR Problem 逆序

比赛传送门

赛时AC三道,补题做出一道。

A. Mathematical Addition

{% note info no-icon Problem %}
给你两个正整数 \(u,v\),求一对合法的 \(x,y\) 使得 \(\frac{x}{u}+\frac{y}{v}=\frac{x+y}{u+v}\)。

解方程。

\[\begin{array}{c} \frac{vx+uy}{uv}=\frac{x+y}{u+v} \\ (vx+uy)(u+v)=uv(x+y) \\ uvx+u^2y+v^2x+uvy=uvx+uvy \\ u^2y+v^2x=0 \end{array} \]

则显然一组合法解为 \(\begin{cases}x=-u^2\\y=v^2\end{cases}\)

B. Coloring Rectangles

{% note info no-icon Problem %}
有一个 \(n\times m\) 的矩阵,每个方格均为红色。你可以任意多次的横切或纵切(必须贯穿整块),不能出现 \(1\times 1\) 的矩阵,问切完后最少需要涂几个蓝色格子才能使得红色格子不相邻。

example: \(2\times 5\)

{% endnote %}

{% tabs Solution %}

容易发现,把格子割成 \(1\times 3\) 是最优的,于是考虑在不对后续操作产生影响的前提下,把它切成这样:

然后再切成这样:

最后特判剩下的。注意切的时候要时刻堤防剩下一行或剩下一列的情况,防止出现 \(1\times 1\)。

通过找规律,我们可以发现,答案为 \(\lceil\frac{n\times m}{3}\rceil\)。

{% endtabs %}

C. Two Arrays

{% note info no-icon Problem %}

给你两个数组 \(a,b\),问能否通过把 \(a\) 进行一次变换得到 \(b\)。

变换方式:在 \(a\) 数组中选出若干个数分别 \(+1\),然后随意排列顺序。

{% endnote %}

大水题。\(a,b\) 分别排序,看是否每个 \(a\) 数组的元素都等于 \(b\) 的对应元素或等于 \(b\) 的对应元素 \(+1\)。

D. Guess the Permutation

{% note info no-icon Problem %}

这是一道交互题。

有一个初始数组 \(a\),满足 \(a_i=i\),即 \({1,2,3...}\)。现在有 \(1<=i<j<=k<=n\),将 \([i,j-1],[j,k]\) 分别翻转。你需要通过不超过 \(40\) 次询问得到 \(i,j,k\) 的值。

每一次询问你可以给出 \(l,r\),得到 \([l,r]\) 中的逆序对个数。

\(n\le 10^9(\log_2(10^9)\approx 30)\)

{% endnote %}

  1. 用一次 \(\log\) 找到 \(k\):二分 \(mid\),询问 \([mid,r]\) 中逆序对个数,如果不为 \(0\),则 \(k\) 在 \([mid+1,r]\) 中,否则在 \([l,mid]\) 中。
  2. 用两次询问 \([1,k]\) 和 \([1,k-1]\) 来获得 \(j\) 的位置:一段降序区间 \([l,r]\) 的逆序对数减去 \([l,r-1]\) 的逆序对数等于 \(len-1\),于是 \([1,k]-[1,k-1]=len_{[j,k]}-1\)(\(j\) 前面的都被抵消了),用 \(k-(len-1)\) 即可求出 \(j\)。
  3. 同理用两次询问 \([1,j-1]\) 和 \([1,j-2]\) 来获得 \(i\) 的位置。

询问次数约为 \(\log(n)+4\)。

不开 long long 见祖宗(逆序对个数最多有 \(n^2\) 级别)。

标签:info,frac,755,no,times,Div,CFR,Problem,逆序
From: https://www.cnblogs.com/cxm1024/p/17168426.html

相关文章

  • CFR-844-Div-1-2解题报告
    比赛传送门A.ParallelProjection题意:有一个\(w\timesd\timesh\)的长方体,顶面和底面有两个点,只能走直线且不能穿过长方体,求最短距离。显然曼哈顿距离必须要走。......
  • CFR-745-Div-2解题报告
    没打比赛,赛后做出3道。这场比赛题目质量很高,非常巧妙。A.CQXYMCountPermutations\(Problem\)求有多少\(2n\)的排列满足存在超过\(n\)个\(i\)使得\(p_i<p_{i+......
  • CFR-746-Div-2解题报告
    VP做出来一道,补题又做出来3道。A.GamerHemose\(Problem\)你有\(n\)个武器,要打一个体力为\(H\)的敌人,第\(i\)个武器可以对敌人造成\(a_i\)的伤害,每把武器不能......
  • CFR-109解题报告
    A.Hometask题意:一个字符串,给定\(k\)个限制字符对\((a_i,b_i)\),要求从原串中删除尽可能少的字符,使得不存在一个相邻的限制字符对。保证\(a_i\neb_i\),且每个字符最多......
  • CFR-744-Div-3解题报告
    赛时AC2道题,掉大分(哭)A.Casimir'sStringSolitaire题目传送门\(Problem\)给你一个仅含A,B,C的字符串,每次可以删掉一个A和一个B,或一个B和一个C,位置、顺序不......
  • CFR-840-Div-2解题报告
    比赛传送门C.AnotherArrayProblem题意:给你一个数组\(a\),每次可以选两个位置\(i,j(i<j)\),将\([i,j]\)内的所有数替换为\(|a_i-a_j|\)。问最终数组的和最大为多少......
  • CFR-843-Div-2解题报告
    比赛传送门C.InterestingSequence题意:给你\(n,x\),求最小的\(m\gen\),使\(n\&(n+1)\&(n+2)\&\cdots\&m=x\),或判断无解。首先每一位独立,分别考虑。与运算每一位都......
  • CFR-850-Div-1解题报告
    比赛传送门A.Monsters(easyversion)题意:有\(n\)个怪物,每个有\(a_i\)滴血,每次可以选择一个怪物减一滴血,也可以“让所有怪物减一滴血,且如果杀死怪物则重复操作”。......
  • EDU-CFR-115-Div-2解题报告
    赛时AC3道,补题做出来一道A.ComputerGame\(Problem\)有一个\(2\timesn\)的01矩阵,1为障碍,你要从\((1,1)\)走到\((2,n)\),每一步只能向右、上、下、右上、右下走,问......
  • EDU-CFR-116-Div-2解题报告
    比赛传送门做出来五道题。A.ABBalance{%noteinfono-iconproblem%}给你一个只含有a和b的字符串,问怎样通过修改尽可能少的字符,使得ab的数量和ba的数量相......