首页 > 其他分享 >Codeforces Round #890 Div.2

Codeforces Round #890 Div.2

时间:2023-08-07 11:58:07浏览次数:42  
标签:890 10 le 正整数 多测 sum Codeforces 序列 Div.2

link

题号:1856A~E2

A

题面:

给定一个正整数 \(n\) 和一个长度为 \(n\) 的序列 \(a\),重复执行以下操作直至 \(a\) 序列单调不减:

  • \(\forall 1 \le i \le n\),\(a_i = \max(a_i - 1, 0)\)。

求一共需要执行多少次操作。

多测,共 \(t\) 组数据。

对于所有数据,保证 \(1 \le t \le 500\),\(2 \le n \le 50\),\(1 \le a_i \le 10 ^ 9\)。

B

题面:

给定一个正整数 \(n\) 和一个长度为 \(n\) 的序列 \(a\),问是否存在正整数序列 \(b\) 满足以下条件:

  • \(\forall 1 \le i \le n\),\(a_i \ne b_i\)。

  • \(\sum \limits_{i = 1} ^ {n} a_i = \sum \limits_{i = 1} ^ {n} b_i\)。

若存在,输出 YES,否则输出 NO

多测,共 \(t\) 组数据。

对于所有数据,保证 \(1 \le t \le 10 ^ 4\),\(1 \le n, \sum n \le 10 ^ 5\),\(1 \le a_i \le 10 ^ 9\)。

C

给定两个正整数 \(n\) 和 \(k\),以及一个长度为 \(n\) 的序列 \(a\),你可以进行不超过 \(k\) 次如下操作(以下两个步骤合称一次操作):

  • 选择一个 \(i\) 满足 \(1 \le i < n\),且 \(a_i \le a_{i + 1}\)。

  • 将 \(a_i\) 增加 \(1\)。

求操作完成后,\(\max \limits_{i = 1} ^ {n} a_i\) 的最大可以是多少。

多测,共 \(t\) 组数据。

对于所有数据,保证 \(1 \le t \le 100\),\(1 \le n, \sum n \le 1000\),\(1 \le k, a_i \le 10 ^ 8\)。

D

本题交互。

有一个长为 \(n\) 的序列 \(a\),最初不知道 \(a\) 的任何一个值。

一次询问区间 \([l,r]\) 的逆序对个数,代价为 \((r-l)^2\)。

你需要进行若干次询问,求出 \(a\) 的最大值所在的位置,并使得询问总代价 \(w\le 5n^2\)。

多测,\(1\le t\le 100,1\le n\le 2000\)。所有数据中 \(n\) 的总和不超过 \(2000\)。

E2

这是问题的困难版本,两个版本之间的唯一区别是 \(n\) 的范围和时间限制的不同。

给定一棵以 \(1\) 为根的有根树,你需要给出一个 \(1\) 到 \(n\) 的排列 \(a\),最大化二元组 \((u,v)\) 的数量,满足 \(a_u < a_{\rm{lca(a_u,a_v)}} < a_v\),输出这个最大值。

\(2 \leq n \leq 10^6\)。

标签:890,10,le,正整数,多测,sum,Codeforces,序列,Div.2
From: https://www.cnblogs.com/oierpyt/p/17611034.html

相关文章

  • Codeforces Round 890 (Div. 2) A-E1
    A.TalesofaSort题意:给出一个长为n的数组a,每次操作可以使得所有的数-1,最小不会小于0,问至少需要多少次操作才能使得a变得有序。Solution把数组a排序,从大到小遍历,如果当前的\(a[i]\)不是原来的话,那么要想让它有序,必须进行当前的\(a[i]\)次操作,这样才能使得它有序voidsolve()......
  • Codeforces Round 890 (Div. 2) supported by Constructor Institute
    Preface现在开始严格按照双号上分法来打CF了,大致就是每次比赛都拿两个号中分较少的那个打,这样可以保证两个号的最高分不降然后昨天打完就后悔了,没有拿hl666那个号打导致没抓住难得的上分机会,本来可以打到橙名渡劫局的但分全加在Kusanagi_Misuzu那个号上了不过昨天这场其实可以......
  • 【题解】Codeforces Round 890(CF1856)
    赛时过了A-E1,rk195可惜是E2傻逼了不会背包优化了,直接连普及组水平都不到了。A.TalesofaSort题目描述:给定长度为\(n\)的序列\(a\),每次操作为对于所有\(i\)将\(a_i\)变为\(\max(a_i-1,0)\),询问最少多少次操作之后可以让序列\(a\)单调不降。题目分析:唯一能改变......
  • CodeForces 数学类题目 做题汇总
    写一下\(3\)月\(28\)日起开始做的题目感受:1.CF1793BFedyaandArray:普及-*1100Luogu链接CF链接一道比较正宗的组合清新小题,可以对本题进行数学上的加强。ACCode2.CF1774BColoring:普及/提高-*1500Luogu链接CF链接一道需要考虑全面的贪心小题目ACCode......
  • Codeforces Round 890 (Div. 2)
    TalesofaSort题解找到最大的能够产生逆序对的数即可暴力\(O(n^2)\)枚举即可constintN=2e5+10,M=4e5+10;intn;inta[N];voidsolve(){cin>>n;intans=0;for(inti=1;i<=n;++i){cin>>a[i];}fo......
  • Codeforces Round 690 (Div. 3)
    CodeforcesRound690(Div.3)https://codeforces.com/contest/1462A.FavoriteSequence按题意输出#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;inta[N],n;voidsolve(){cin>>n;for(inti=1;i<=n;i++)......
  • Codeforces Round 890 (Div. 2) supported by Constructor Institute ————C - T
    关于这场div2,只能说一言难尽C题可以二分的,赛时看到n<=1000,直接往\(O(n^2)\)考虑,想了一会贪心的话能写出来,但是,细节太多没调出来,G掉打分。\(O(n^2)\)做法:思路:每次让i为起点,往前贪心枚举,并且当前位置如果满足,也要枚举当前区间,细节就是要注意上下限,赛时,漏了一种上界小于下届的情......
  • Codeforces Round 890 (Div. 2) supported by Constructor Institute 题解
    A.TalesofaSort关键就是找逆序对记一组逆序对下标为\(l,r\),则求出最大的\(a_l\)即可B.GoodArrays记要构造的GoodArray为\(b\)前置:\(\forall1\lei\len,b_i=1\)然后\(O(n)\)扫一遍看一下有没有重复,有重复就\(b_i\leftarrowb_i+1\)扫完之后,记\(sum=\sum_......
  • Codeforces Round 882 (Div. 2) 题解
    A.TheManwhobecameaGod求出相邻两个元素的差值,去掉前\(m\)个大的差值以后的差值和即为答案B.HamonOdyssey由按位与的性质可以知道,前缀与和的值只会越来越小,只要和为\(0\)的时候我们就清空按位与前缀和,增加一下次数,如果最终次数不为\(0\),特判一下,次数加一即可C.......
  • CodeForces 1856E1 PermuTree (easy version)
    洛谷传送门CF传送门考虑局部贪心,假设我们现在在\(u\),我们希望\(u\)不同子树中的\((v,w),a_v<a_u<a_w\)的对数尽量多。我们实际上只关心子树内\(a_u\)的相对大小关系,不关心它们具体是什么。如果\(u\)只有两个儿子\(v,w\),我们可以让\(v\)子树内的\(a\)全部......