首页 > 其他分享 >AtCoder Beginner Contest 306(ABC 306) E~F补题

AtCoder Beginner Contest 306(ABC 306) E~F补题

时间:2023-06-28 10:14:07浏览次数:51  
标签:AtCoder 数字 大根堆 306 leq 补题 集合 10

E

题目大意

给定数字$k$,规定数组 $A$ 的函数 $f(A)$ :$A$ 数组前 $k$ 大数字的和

  • 如 $A=[1,3,7,~4]$ ,$k=2$ ,则 $f(A)=7+4=11$

现在给定最大数组长度 $n$ ,有 $q$ 组操作,每次将第 $x$ 个数字修改为 $y$ ,输出每次操作后的 $f(A)$

其中 $0<k \leq n \leq 5\times 10^5,~q\leq 5\times 10^5, ~y\leq 10^9$

思路

考虑用一个小根堆 $X$ 和一个大根堆 $Y$,小根堆 $X$ 里放 $A$ 数组内前 $k$ 大的数字,大根堆 $Y$ 里放剩下的数字。每次修改后判断:

  • 若 $A[x]$ 没被修改过,则在 $Y$ 内插入 $y$ ,并记录 $A[x] = y$
  • 若 $A[x]$ 被修改过,则先在 $X$ 和 $Y$ 中删掉 $A[x]$ ,再在 $Y$ 中插入 $y$

然后执行平衡操作:判断大根堆 $Y$ 内最大的数字是否比小根堆 $X$ 内最小的数字大,如果是,交换两个数字

Code: https://atcoder.jp/contests/abc306/submissions/42763724

F

题目大意

对于两个有序集合 $A,B$ ,令有序集合 $C=A\cup B$ ,规定 $f(A,B)=\sum_{i=1}^{|A|} k_i$ ,其中 $k_i$ 是 $A[i]$ 在 $C$ 内的位置

现在给出 $n$ 个大小为 $m$ 的集合 $S_1,S_2,\cdots,S_n$ ,求 $ \sum_{1\leq i < j \leq n} f(S_i,S_j)$

其中 $n \leq 10^4,~m \leq 10^2, ~A_{i,j} \leq 10^9$ , 保证 $S_i \cap S_j = \emptyset$

思路

我的思路跟题解不太一样

现将所有数字一起排序,记为集合 $S$ 。并将每一个给定集合 $S_i$ 排序,然后考虑 $A_{i,j}$ 的贡献:

$A_{i,j}$ 的贡献是: $S$ 比它小的数字的数量 + 它在 $S_i$ 中的位置 $\times$ $S_i$ 作为 $A$ 而非 $B$ 的次数

也就是:$S$ 比它小的数字的数量 + 它在 $S_i$ 中的位置 $\times (n-i)$

为了避免重复计算,当考虑过 $A_{i,j}$ 后需要将它从集合 $S$ 中删掉。

为了在 $O(NlogN)$ 的复杂度内处理 $S$ ,考虑离散化 $A_{i,j}$ + 二叉索引树(Fenwick Tree)

Code: https://atcoder.jp/contests/abc306/submissions/42777281

标签:AtCoder,数字,大根堆,306,leq,补题,集合,10
From: https://www.cnblogs.com/tonyhgf/p/17496783.html

相关文章

  • AtCoder Beginner Contest 228 G Digits on Grid
    洛谷传送门AtCoder传送门?这啥啊,不会。考虑行和列分别作为左部点和右部点建二分图(实际上这个建图只是辅助理解,不需要显式建图),每个左部点和每个右部点,边权为格子中的数。容易想到一个dp,设\(f_{i,j}\)为走了\(i\)步,当前在点\(j\),走过的所有边权组成的不同整数的数量。但......
  • SummerResearch_Log_20230627
    WorkingContent:1.今天开始看VisionTransformer(ViT):看之前需要一些基础:(1)RNN(RecurrentNN,循环神经网络):一段连续的信息,前后信息之间是有关系地,必须将不同时刻的信息放在一起理解。如果是普通的神经网络,每个输入之间是相互独立的,如果是RNN,则可以接收上一个输入传递的信息。......
  • AtCoder Beginner Contest 072
    A-Sandglass2#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongint32_tmain(){inta,b;cin>>a>>b;cout<<max(a-b,0ll);return0;}B-OddString#include<bits/stdc++.h>......
  • AtCoder Beginner Contest 238 Ex Removing People
    洛谷传送门AtCoder传送门考虑期望转计数,方案数显然是\(n!\)(第\(i\)次操作有\(n-i+1\)个人可供选择),所以问题转化为求所有方案的代价之和。考虑倒着做,变成先放一个人,然后依次放\(n-1\)个人,每次放的这个人可以让左边的人的\(S\)变成R,代价是他与他左边的人的距离,......
  • SSO2.0 15-20230626
                     ......
  • AtCoder Beginner Contest 307 Ex Marquee
    洛谷传送门AtCoder传送门一开始看错题了,看了好久才发现就是个板子。。。这个东西本质上是循环移位,我们考虑在\(S\)前后各添加\(W-1\)个.,例如\(W=5,S=\texttt{ABC}\)时,添加后\(S=\texttt{....ABC....}\)。此时我们发现\(S\)的每个长度为\(W\)的子串一一对......
  • AtCoder Beginner Contest(abc) 307
    A-WeeklyRecords题目大意小莫每天跑步,输入n周每天的步数,输出每周跑的总步数;解题思路签到题不多嗦了;神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,m,k,idx;signedmain(){ cin>>n; intsum=0; for(inti......
  • AtCoder Beginner Contest 307 G Approximate Equalization
    洛谷传送门AtCoder传送门考虑我们如果确定了最终态\(B=(B_1,B_2,...,B_n)\),如何计算最少操作次数。显然从左往右依次使\(A_i=B_i\)。当操作到第\(i\)个位置时,此时\(A'_i=\sum\limits_{j=1}^iA_j-B_j\),所需操作次数为\(|A'_i|\)。令\(C_i=\sum\limits_{......
  • AtCoder Beginner Contest 245 Ex Product Modulo 2
    洛谷传送门AtCoder传送门很好的题。下文令\(k\)为原题面中的\(n\),\(n\)为原题面中的\(k\),\(m\)为原题面中的\(m\)。从一些简单的情况入手。1.\(m\)为质数\(k=0\)的情况是平凡的,只需要要求\(\existsi\in[1,n],a_i=0\)即可。总方案数减去不合法方案数,......
  • 20230626水题选做
    「数学基础」第6章期望问题单选错位题意单选把答案填在后面那道题了。假设所有题都正确,求答对题目的期望值。分析期望入门题。\(E(Ans)=\sumP[i]\)。那么显然有答对本题的期望为\(\dfrac{1}{\max\left(a\left[i+1\right],a\left[i\right]\right)}\)。代码#inc......