首页 > 其他分享 >Codeforces Round 967 (Div. 2)

Codeforces Round 967 (Div. 2)

时间:2024-08-21 22:16:48浏览次数:14  
标签:le 题意 记录 sum Codeforces pop 967 Div 我们

题不难。

A. Make All Equal

题意: 一个圆,上面有 \(n\) 个数,每次可以删去相邻的两个不同数中任意一个,求至少几次使得剩下的数都一样。

显然下界是出现次数最多的数且一定能取到,时间复杂度 \(O(n)\)。

提交记录

B. Generate Permutation

题意: 要求构造一个排列,使得 \(x\) 所在位置大于 \(x+1\) 的与 \(x\) 所在位置小于 \(x+1\) 的个数相同。

考虑到关系总共 \(\frac{n-1}{2}\),显然 \(n\) 为偶数无解,\(n\) 为奇数时可以 \(n, n - 2, n - 4, \dots, 1, 2, 4, \dots, n - 1\) 构造。

提交记录

C. Guess The Tree

题意: 交互题,有一棵树,每次可以询问两个点的路径的中点(如果偶数就输出靠经第一个的点),要求在 \(15n\) 内构造这棵树。\(n \le 1000\)。

这个限制显然是大概 \(O(n \log n)\) 级别的。我们发现,如果对于 \(a,b\) 有 \(f(a,b) = a\) 则说明 \(a\) 到 \(b\) 右边。

我们选 1 号点为根,这样我们可以求出所有与 \(1\) 号点距离为 \(1\) 的点。

如果我们对于一个点对颠倒顺序询问两次就能得到这条路径是否为偶数,所以我们可以依次发现距离为 \(2,3,\dots\) 的点,每次只用不断查询中点即可。

这个题 \(O(n^2)\) 可过,用 bfs 优化一下应该就能做到 \(O(n \log n)\) 了。

提交记录

D. Longest Max Min Subsequence

题意: 选取一个序列的最长子序列,要求所有数互不相同,且将所有奇数位取反后的字典序最小。\(n,a_i \le 3 \times 10^5\)。

显然最长长度是确定的,我们按位确定。

我们记录 \(last_i\) 表示 \(i\) 这个数最后出现的位置,显然选取第一个数必须在 \([1, \min_i\{last_i\}]\) 之间。

则我们贪心地选取这些数中最大的那个,然后就是后面的事儿了。

整个过程可以用一个 set 维护所有的 \(last_i\),当一个数被选中时就将其 \(last_i\) 删去。

我们还要维护一个右边界 \(L\),表示上一个数位置是 \(L\),后面的数都要在这之后。同时对于前面的数维护两个 multiset,第一关键字是值,第二个是位置,但是其中一个的位置要取反。

每次我们选一个最大最小时,如果有多个就选最前面的。所以需要两个 multiset。

然后就没了,记得要把不合法地弹出。

提交记录

E1. Deterministic Heap (Easy Version)

题意: 对于一个满二叉树的大根堆,我们定义其可以唯一确定当且仅当进行一次 pop 操作时,不会出现两个儿子权值相同的情况。初始有一个高为 \(n\) 的满二叉树都是 \(0\),你可以恰好执行 \(m\) 次操作,每次将一个点到根路径上所有数加一,求最后有多少不同的可以唯一确定的大根堆。\(n,m \le 500\)

显然 dp 题。

我们观察到根的权值一定是 \(m\),所以我们可以 dp,设 \(g(i,j)\) 表示高为 \(i\),恰好执行了 \(j\) 次操作的方案数。

我们发现只需要枚举儿子谁更大即可,为了使得儿子方便枚举,我们要求上面的状态还要满足没有执行 \(i\) 自己加一的操作,同时定义
\(h(i,j)\) 表示高为 \(i\),恰好执行 \(j\) 次大根堆个数(其实也可以直接挡板法计算)。

不妨设 \(g'\) 是 \(g\) 对于 \(j\) 的前缀和,我们得到:

\[g(i,j) = 2\sum_{x > j - x}g'(i - 1, x)h'(i - 1, j - x)\\ h(i,j) = \sum_{x}h'(i-1,x)h'(i-1,j-x) \]

然后就可以在 \(O(nk^2)\) 内解决了。

提交记录

E2. Deterministic Heap (Hard Version)

题意: 现在定义唯一确定指执行两次 pop 都不会出现两个儿子权值相同的情况。求方案数。\(n \le 100, m \le 500\)。

其实不难。

我们发现由于需要两次 pop 所以我们需要记录儿子中的最大值。不妨设 \(f(i,j,k)\) 表示高为 \(i\),执行了 \(j\) 次(自己没有),儿子最大的为 \(k\) 的方案数。

相应的,我们设 \(g(i,j,k)\) 同上题,其中 \(k\) 记录儿子最大值,\(h(i,j)\) 不变。

我们讨论两种情况:

第一种,如果两次 pop 都去了同一颗子树,则:

\[f(i,j,k) = h'(i-1,j - k)\sum_{j - k < x \le k}f'(i-1,k,x) \]

第二种,如果两次 pop 去了不同子树,则:

\[f(i,j,k) = \sum_{x=0}^m g'(i-1,j-k,x)\sum_{x = 0}^{j-k-1}g(i-1,k,x) \]

前缀和优化一下就行了。注意每次 pop 会赋值为 -1,所以值域要加 1。

提交记录

标签:le,题意,记录,sum,Codeforces,pop,967,Div,我们
From: https://www.cnblogs.com/rlc202204/p/18372676

相关文章

  • CF 2001 E2 solution (967 Div.2)
    CF2001E2由于对称,所以设\(heap[u]\)为两次确定堆,且第一次弹出的是\(u\),\(heap[u,v]\)是第一次\(u\),第二次\(v\)则答案就是\(\sumheap[u]=2^{n-1}·heap[x]\)其中\(x\)任意。不妨我们考虑第一次都是从第一个叶子弹出,那么对于其他不同的第二个弹出的点,根据对称性......
  • 题解:Codeforces Round 967 (Div. 2) B [思维/构造]
    B.GeneratePermutationtimelimitpertest:1.5secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputThereisanintegersequence\(a\)oflength\(n\),whereeachelementisinitially\(-1\).Misukihastwoty......
  • Divisiblity of Difference
    题目传送门思路首先得知道个性质,即若$a\bmodb=c\bmodb$,那么$(a-c)\bmodb=0$,因为余数在$(a-c)$中被减掉了。于是我们可以把所有余数相同的$a_i$丢进一个vector里,之后再看余数相同的$a_i$的数量有没有$\gek$,有的话就输出前$k$个数,没有就输出No。代码#i......
  • Codeforces Round 966 (Div. 3)
    A.PrimaryTask#include<bits/stdc++.h>usingnamespacestd;usingvi=vector<int>;voidsolve(){strings;cin>>s;if(s.size()<=2){cout<<"NO\n";return;}if(s[0]!......
  • 题解:Codeforces Round 967 (Div. 2) [暴力/贪心]
    A.MakeAllEqualtimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenacyclicarray\(a_1,a_2,\ldots,a_n\).Youcanperformthefollowingoperationon\(a\)atmost\(n-......
  • Codeforces Round 967 (Div. 2) C题 类分治解法
    废话不多说,先上代码t=int(input())whilet>0:n=int(input())pre_d={1:[iforiinrange(2,n+1)]}pair_l=[]whilelen(pre_d)!=0:item=pre_d.items()now_d={}fork,vinitem:forii......
  • Codeforces Round 967 (Div. 2)
    A.MakeAllEqual题意:给定n个数每次可以选2个相邻的数,并且前面的数不能比后面的数大,并且删除其中的一个。这个数组是循环数组,最后一个数是第一个数的前一个数。问最少操作多少次,可以让剩下的数全都相等。思路:红黑树+一次遍历,记录出现次数最多的数,剩下的数全部删掉即可。总结:看......
  • CodeForces 360D Levko and Sets
    洛谷传送门CF传送门求出\(p\)的原根\(g\),对每个\(a_i\)求出一个\(x_i\)表示\(g^{x_i}\equiva_i\pmod{p}\)(这部分可以BSGS)。之后的表述中\(a_i\)指\(x_i\)。那么集合生成方式相当于初始\(c=0\),每次让\(c\gets(c+a_ib_j)\bmod(p-1)\)。根据裴蜀定......
  • 【LGR-196-Div.4】洛谷入门赛 #26 题A - H 详细题解--优化思路简洁代码(C++,Python语
    前言:    觉得这个比赛很有意思的,都是暴力题,涉及一些细节,难度比较适合刚学编程语言的,可以很好的锻炼基础还有手速,最后两题也是比较有意思,之后也准备更新atc的比赛题解和洛谷的一些高质量比赛题解(算法网瘾就是想参加各种比赛)   如果觉得有帮助,或者觉得我写的好,......
  • Educational Codeforces Round 168 (Rated for Div. 2) D题
    文章目录题目来源题意思路code题目来源D.MaximizetheRoot题意给定一棵n个点的数,根节点为1,每个点都有权值aia_i......