1856
cf1856E2. PermuTree (hard version)(bitset+二进制优化背包+开不同大小bitset)
https://codeforces.com/contest/1856/problem/E2 结论是显然的,关键是有一些科技在里面 bitset+二进制优化 具体分析可以参考https://codeforces.com/blog/entry/98663 简而言之就是可以通过\(O(\frac{C\s ......
【树上背包】CF1856E1 PermuTree (easy version) 题解
CF1856E1 发现题目的要求只需要相对的大小关系,考虑一个子树时,不妨令子树内部编号连续。类似于一个 dp,这样也可以更好地将信息由儿子转移到父亲。 设 \(u\) 的孩子为 \(v_1,v_2,\dots,v_k\)。由于每棵子树内的编号是连续的,令以 \(v_i\) 为根的子树的编号为 \( ......
CF1856B Good Arrays
题意简述: 给定一个序列 \(a\),我们定义一个序列 \(b\) 是好的当且仅当对于 \(1\dots n\) 内的每一个 \(i\),\(a_i\neq b_i\) 且 \(\sum_{i=1}^na_i=\sum_{i=1}^nb_i\)(\(a_i\),\(b_i\) 均为正整数)。 现在有 ......
CF1856
# CF1856 ## A 将条件转化为 $\binom{n}{2}$ 个有序数对 $(i,j)$,**二元关系**,若 $a_i>a_j$,则至少需要 $a_i$ 的时间,对每个满足要求的 $a_i$ 取 $\min$ 即可。 ## B 关注正整数的条件,考虑转化,将 $a$ 同时减一,转化成 ......
【题解】Codeforces Round 890(CF1856)
赛时过了 A-E1,rk195 可惜是 E2 傻逼了不会背包优化了,直接连普及组水平都不到了。 ## A.Tales of a Sort ### 题目描述: 给定长度为 $n$ 的序列 $a$,每次操作为对于所有 $i$ 将 $a_i$ 变为 $\max(a_i-1,0)$,询问最少多少次操作之后可 ......
CF1856B
[原题](https://codeforces.com/problemset/problem/1856/B) [翻译](https://www.luogu.com.cn/problem/CF1855B) - 引理1:在$[l,r]$内一定存在一个数$x$使满足$(r-l+1)|x$ 证明:设$k=r ......
CodeForces 1856D More Wrong
[洛谷传送门](https://www.luogu.com.cn/problem/CF1856D "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1856/D "CF 传送门") 直接求最大值不好求。我们可以采用一个交互常见的套 ......
CodeForces 1856E1 PermuTree (easy version)
[洛谷传送门](https://www.luogu.com.cn/problem/CF1856E1 "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1856/E1 "CF 传送门") 考虑局部贪心,假设我们现在在 $u$,我们希 ......
CodeForces 1856E2 PermuTree (hard version)
[洛谷传送门](https://www.luogu.com.cn/problem/CF1856E2 "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1856/E2 "CF 传送门") 考虑局部贪心,假设我们现在在 $u$,我们希 ......
【题解】PermuTree (easy version) - Codeforces 1856E1
**链接:** https://codeforces.com/contest/1856/problem/E1 **题目大意:** 给定一棵以节点 $1$ 为根的树,树的大小不超过 $n(1\leq n\leq 5000)$ ,给树的节点赋各不相同的权值(可以简化为某个 $[1,n]$ 的排列),使得 ......