1867
CF1867F Most Different Tree记录
题目链接:https://codeforces.com/contest/1867/problem/F 题意简述 记 \(P(T)\) 为一棵树 \(T\) 的所有子树的集合。给定一棵 \(n\) 个点的树 \(T\),找出点数相同的树 \(T'\),使 \(P(T')\) 的“与 \(P(T)\) ......
CF1867B XOR Palindromes
CF1867B XOR Palindromes 这里是一个关于 \(n\) 的奇偶性分类讨论的做法。 设最终的答案序列为 \(\{ans_{n+1}\}\),它由 \(0,1\) 组成。 首先计算出原序列中有序数对 \((i,n-i+1)\) 的个数,使得 \(s_i \not= s_{n-i+1} ......
CF1867C Salyg1n and the MEX Game
CF1867C Salyg1n and the MEX Game 简单博弈论题。 设给出序列的 \(\text{mex}\) 为 \(x\),那么 Alice 第一次操作时加入 \(x\) 一定是最优的。此时显然有 \(\text{mex(s)} \ge x\)。 因为如果加入的数 \(y<x\), ......
CF 1867 E1. Salyg1n and Array (simple version)
Link 简单版本的结论还是很容易猜到的。 首先很容易想到的第一步就是尽可能地不覆盖地取尽可能多地区间,最后剩下了一小块。 然后在接着原来的指针一个一个地往右问,直到不能问了为止。 为什么这样是正确的呢?首先,在这样一步一步地往右查询的过程中,我们会发现总是前$k-1个数加上后面的一个数。 然后题面 ......
CF1867D Cyclic Operations
事实上我们可以发现,如果\(b_i=x\)最后,那么我们可以连一条边,从\(i\)到\(x\) 这样我们就得到了一个有向图,在这张有向图呢,可以证明的是 如果\(k=1\),那么必须全部都是自环。 若不成立,则必须每个环的大小恰好为\(k\) 这样就可以解决了。 #include<cstdio> # ......
CF1867F 题解
一、题目描述: 给你一颗 $n$ 个点的有根树 $S$,你需要构造一颗 $n$ 个节点的有根树 $T$, 使得 $T$ 的 $n$ 颗子树中不与 $S$ 的任意一颗子树同构的数量最大。 注意,这里是有根树,旋转树之后的同构不算同构。输出 $T$ 的所有边。 数据范围:$1\le n\le 1\tim ......
CF1867F—构造最小同构树
有意思的问题。设原树为 \(G\)。 手玩一下,不难发现,若子树 \(T\) 与 \(G\) 中任何一颗子树都不同构,那么对于任意树 \(S\),其中 \(T\) 是 \(S\) 的子树,\(S\) 同样不与 \(G\) 中任何一颗子树同构。 进一步地,假设我们已经知道了一颗最小的 \(T\),我们 ......
CF1867D Cyclic Operations
前言 赛时没调出来,赛后调了一个上午,最后发现是有个地方没清零。 思路 首先对于位置 \(i\),我们必须要保证进行的操作中,最后一次出现 \(i\),\(i\) 的后面一定是 \(a_i\)。 那么我们考虑统计所有位置上的要求,用有向边链接,那么就会出现一个有环有向图(一定有环,因为点数等于边数) ......
CF1867A green_gold_dog, array and permutation
思路 很简单的一道题,洛谷大概都不会开放题解通道?(实际上貌似每场比赛的 A 都没开放?) 显然,对于原数组较小的数,我们尽量让大的数,取全排列的较小的数,这样可以保证差是逐渐变小的,也就让 \(c\) 数组差异变大。 所以直接拿个 struct 存,然后两边排序就好。 AC code #inclu ......
CF1867C Salyg1n and the MEX Game
思路 看着无从下手,实际上又是一道诈骗题。 假设原数列不存在 \(0\),那么我们可以直接加入 \(0\),然后游戏结束,假设答案是 \(k\)。那么,如果我们选择加入 \(k\),来试图让答案变大,那么 Bob 就会移除一个数,最优的话是 \(1\),这样的话,你无论加入 \(1\) 还是 \(0 ......
CF1867E1 Salyg1n and Array (simple version)
思路 首先考虑,\(n\) 是 \(k\) 的倍数的情况,直接枚举询问所有每一段就好,然后输出每一段的异或和的异或和。 如上图,每次询问都没有重叠部分,颠转互不干扰。 那么,\(n\) 不是 \(k\) 的倍数的情况呢? 可以看到,与第一种情况的区别就是末尾多了一小截,那么我们需要考虑如何计算这一小 ......
CF1867E2 Salyg1n and Array (hard version)
其实如果你在做 E1 的时候想到正解了,这道题都甚至不需要改 E1 的代码,直接交就好,这大概也是 E2 的分还没 E1 的高的原因。 因为一摸一样的思路,所以这里就不作介绍了,可以看看我的题解。 在这里呢,主要是稍微证明一下询问次数不会超,如下: 可以发现,有余数的情况,只会增加两次询问,而后面的 ......
CF1867B XOR Palindromes
思路 题目问的是改 \(i\) 位,能不能让原串变成回文串,其中 \(0\le i \le n\)。 首先,我们可以统计前后对称位置不一样的对数,记为 \(k\),那么至少也得改 \(k\) 次,假设剩下前后对称位置一样的有 \(m\) 对(如果 \(n\) 为奇数,则最中间的一位不计入 \(m\) ......