首页 > 其他分享 >Codeforces Round 890 (Div. 2) supported by Constructor Institute 题解

Codeforces Round 890 (Div. 2) supported by Constructor Institute 题解

时间:2023-08-06 10:44:12浏览次数:40  
标签:890 le Institute 题解 sum mid 交互 DP 逆序

A. Tales of a Sort

关键就是找逆序对

记一组逆序对下标为 \(l,r\),则求出最大的 \(a_l\) 即可

B. Good Arrays

记要构造的 Good Array 为 \(b\)

前置:\(\forall 1\le i\le n,b_i=1\)

然后 \(O(n)\) 扫一遍看一下有没有重复,有重复就 \(b_i\leftarrow b_i+1\)

扫完之后,记 \(sum=\sum_{i=1}^n(a_i-b_i)\),如果 \(sum\ge 0\) 就有解;反之无解

C. To Become Max

假设 \(a_i\) 变成最大值 \(x\),那么后面一定是形如 \(x-1,x-2,\cdots\) 直到某个数不需要操作也能达到要求

这样一来,就是基于试错的方法计算答案,并且答案所在位置有单调性,很容易想到二分答案

然后就是枚举答案所在位置,模拟求解

复杂度 \(O(n\log m)\),其中 \(m=\max_{i=1}^n a_i+k\)

D. More Wrong

又是交互题

其实这道交互题和前面那些牛鬼蛇神比算比较简单的了

因为是求解整个序列的最大值位置,而交互一次 ? l r 返回的结果是 \([l,r]\) 的逆序对个数

这种问题显然可以分解,所以要么 DP 要么分治

如果考虑 DP,那就应该是区间 DP,但是 \(n\le 2000\),区间 DP 的复杂度基本上在 \(O(n^3)\),没法做(事实上也很难设状态和转移方程)

考虑分治,对于 \(l=r\) 的边界情况,显然就返回 \(l\)

否则,记 \(mid=\lfloor\frac{l+r}{2}\rfloor\),对于 \([l,mid]\) 和 \([mid+1,r]\) 分别求解,设 \(a\) 为 \([l,mid]\) 的解,\(b\) 为 \([mid+1,r]\) 的解,因为我们考虑分治,所以 \(a,b\) 其中一个是最大值,另一个是次大值

接下来就交互两次,一次是 \([a,b]\),另一次是 \([a,b-1]\)(\([a+1,b]\) 也行),然后判断逆序对数量是否相等即可

总交互次数就是 \(2n^2[1+\frac{1}{2}+(\frac{1}{2})^2+\cdots]<4n^2\),可以通过

E1. PermuTree (easy version) & E2. PermuTree (hard version)

(待补)

标签:890,le,Institute,题解,sum,mid,交互,DP,逆序
From: https://www.cnblogs.com/cantorsort2919/p/17609157.html

相关文章

  • Codeforces Round 882 (Div. 2) 题解
    A.TheManwhobecameaGod求出相邻两个元素的差值,去掉前\(m\)个大的差值以后的差值和即为答案B.HamonOdyssey由按位与的性质可以知道,前缀与和的值只会越来越小,只要和为\(0\)的时候我们就清空按位与前缀和,增加一下次数,如果最终次数不为\(0\),特判一下,次数加一即可C.......
  • abc313D 题解
    [abc313DOddorEven]。好有趣捏。我们考虑\(N=K+1\)。设\(s_i\)为\(\displaystyle\sum_{j\neqi}a_j\bmod2\)。因为\(K\)为奇数,我们可以得到\(\displaystyle\sum_{i=1}^{K+1}s_i\equiv\sum_{i=1}^{K+1}a_i\pmod2\)。所以\(a_i=\displaystyle\sum_{i=1}^{K+1}a_i\b......
  • Nule 题解
    1.题意简述:给定一个N行N列的非负整数方阵,从左上角(1,1)出发,只能向下或向右走,且不能到达值为0的方格,求出一条到达右下角的最佳路径,所谓最佳路径是指途径的数的乘积的末尾连续的0最少。2.样例解释:41300082256503015742这个样例有多重走法,这里给出两个:1.1->......
  • P4426 [HNOI/AHOI2018] 毒瘤 题解
    P4426[HNOI/AHOI2018]毒瘤题解非常好虚树题目,融合了容斥的内容。简化题意给定一张\(n\)个点、\(m\)条边的图,求图的独立集个数。其中\(n\leq10^5\),\(n-1\leqm\leqn+10\)。独立集:对于图\(G(U,E)\)的一个点集\(S\),\(\forall(u,v)\inE\),不存在\(u\inS\)且......
  • String Game 题解
    题目传送门一道二分题。\(|p|\le2\times10^6\),考虑\(O(n\logn)\)的算法,而又要输出最大值,不难想到二分答案。二分删除字母的数量,用一个数组将删掉的字母的下标存起来,然后判断删除字符后的\(t\)是否是\(p\)的子序列即可。Code#include<bits/stdc++.h>#definelllong......
  • Painting the Fence 题解
    题目传送门一道枚举题。我们可以直接枚举那\(2\)个去掉的粉刷匠。先统计一下每个栅栏会被多少个粉刷匠刷到,然后枚举第一个被去掉的粉刷匠,然后计算剩下的粉刷匠会将每个栅栏刷到多少次,我们只需要看只能被刷\(1\)次的栅栏就行了。接着处理一个前缀和数组,记录前\(i\)个栅栏......
  • Vanya and Brackets 题解
    题目传送门一道枚举题。枚举左括号和右括号的位置括号,为了答案最优,左括号只能在开头或者*的右边。右括号只能在末尾或者*的左边。每一次枚举都计算一下这个加了括号后表达式的值,最后取最大值即可。Code#include<bits/stdc++.h>#definelllonglong#defineINF1e9usi......
  • Permutations 题解
    题目传送门一道枚举题。数据范围非常小,考虑暴力枚举全排列。可以dfs两次,第一次求出能使\(f(p)\)取得的最大值。第二次求出第\(m\)个排列。注意一下,第二次dfs的时候需要按字典序枚举。Code#include<bits/stdc++.h>#definelllonglong#defineINF1e9usingname......
  • Prefixes and Suffixes 题解
    题目传送门一道字符串题。我们考虑还原字符串后再一个一个的判断。很显然,这个字符串是由一个长度为\(n-1\)的前缀和后缀组成的。因此我们可以找到这\(2\)个长度为\(n\)的字符串,然后枚举哪个是前缀,哪个是后缀。值得注意的是,当你判断一个字符串为前缀时,如果后面出现了同样......
  • Educational Codeforces Round 151 (Rated for Div. 2) 题解
    A.ForbiddenInteger显然,当\(x\not=1\)时,直接输出\(n\)个\(1\)即可否则,如果\(n\)为奇数,那就输出\(\lfloor\frac{n}{2}\rfloor-1\)个\(2\)和\(3\);如果\(n\)为偶数,那就输出\(\frac{n}{2}\)个\(2\)(要看一下\(k\)的大小)B.ComeTogether因为Bob和Carol都......