cf-div 868 div cf
CF1423N BubbleSquare Tokens
CF1423N BubbleSquare Tokens 有一个很经典的思路。发现直接不好做,因为改边会影响一对点,所以考虑钦定操作顺序,按编号从小到大做,使得已经操作过的点的 token 不会改变。这样做最大的好处在于每次只用仅仅考虑当前操作点的 token 是否与相邻已操作的点的 token 一致 ......
【构造题】 CF1754B
题目大意 共有 $t$ 组测试数据,每组测试数据中有一个整数 $n$,请求出一个排列,由 $1 , 2 , 3 , 4 ,\cdots n$ 组成,使这个排列相邻的两元素的最小的差的绝对值最大。 即: 求一个 $1\sim n$ 的排列 $p$,使得 $$\min\limits_{i=1}^{n-1 ......
CF123E maze 题解
思考暴力:枚举起点和终点,再枚举每一种遍历序列得到答案。复杂度起飞。 根据期望的可加性,我们无需硬着头皮统计每一条序列的贡献,而是把序列的贡献拆成遍历序列包含的边的贡献。换句话说,假如 $Edge$ 为遍历时经过的边集,$e$ 为边,则: $$E[Edge] = \sum_{e\in Edge} E ......
Codeforces Round 857 (Div. 2) C-The Very Beautiful Blanket
题目地址 题意:构造一个二维数组,使得任意一个4*4的子矩阵满足: A11⊕A12⊕A21⊕A22=A33⊕A34⊕A43⊕A44 A13⊕A14⊕A23⊕A24=A31⊕A32⊕A41⊕A42 Solution(思路来源:知乎xioachou) 对于4个数来说,任意一个二进制位上的1和0都为偶数, ......
CF1739C Card Game
题目地址 题意:有n(n为偶数)张大小不同的卡牌,现在A和B玩一个游戏,规则是如果一个人出示了一张卡牌,另一个人无法出示更大的卡牌,他就赢了,如果反之该回合结束,并将这两张牌移除(移入墓地bushi),由另一个人先出示卡牌,如果牌全部出示完了,那么就算平局,现在问如果最开始由A出示,分别有多少种发牌 ......
CF 1738C Even Number Addicts
题目地址 题意:有一个数组,Alice和Bob每次拿走其中的一个数,Alice先拿,问最后Alice拿的数的和是否为偶数 Solution 博弈论,这里的数据量不大,dp+记忆化搜索 dp[cnt1][cnt2][c][s]表示剩余cnt1个奇数和cnt2个偶数时,当前的操作人为c,Alice拿的数 ......
Codeforces Round 855 (Div. 3) 题解集
CF1800题解集 包含
CF1800A CF1800B CF1800C1 CF1800C2 CF1800D CF1800E1 CF1800E2
七道题解(附详解及代码) ......
Educational Codeforces Round 143 (Rated for Div. 2) A-E
比赛链接 A 题意 有两座塔由红蓝方块组成,分别有 $n,m$ 个方块,一次操作可以把一座塔塔顶的方块移动到另一座塔的塔顶,问通过操作是否能使每座塔中没有颜色相同的相邻方块。 题解 知识点:贪心。 注意到,操作最多能拆掉一对相邻的方块,因此统计两座塔不合法的对数。 如果超过 $1$ 对,那么无解。 ......
Codeforces Round #851 (Div. 2) A-E
比赛链接 A 题意 给一串只包含 $1,2$ 的数,找到最小的 $k$ 使得 $\prod_{i=1}^k a_i = \prod_{i=k+1}^n a_i$ 。 题解 知识点:枚举。 因为只有 $1,2$ ,所以考虑左右两边 $2$ 的个数即可。 时间复杂度 $O(n)$ 空间复杂度 $O(n) ......
CF构造题1600-1800(1)
D. Same Count One(Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)) 题意 给定 $n$ 个长度为 $m$ 的 01 序列,每次操作可以选择两个序列a1, a2,并选择一个$pos$, std::swap(a1[pos] ......
Codeforces Round #844 (Div.1 + Div.2) CF 1782 A~F 题解
点我看题 A. Parallel Projection 我们其实是要在这个矩形的边界上找一个点(x,y),使得(a,b)到(x,y)的曼哈顿距离和(f,g)到(x,y)的曼哈顿距离之和最小,求出最小值之后加h就是答案了,因为我们不可能在竖着的墙面上来回走,只可能走一次。进一步发现我们在上底面和下底面 ......
Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) A-D
比赛链接 A 题意 设计一条线路要贴着6个墙面走,从 $(a,b)$ 到 $(f,g)$ ,线路长度最短。 题解 知识点:模拟。 分类取最短即可。 时间复杂度 $O(1)$ 空间复杂度 $O(1)$ 代码 #include <bits/stdc++.h> #define ll long long u ......
Codeforces Round #846 (Div. 2) A-E
比赛链接 A 题意 给 $n$ 个正整数,找到三个数,使得他们的和为奇数,输出他们的下标。 题解 知识点:贪心。 找到三个奇数或者一个奇数两个偶数即可,其他情况无解。 时间复杂度 $O(n)$ 空间复杂度 $O(n)$ 代码 #include <bits/stdc++.h> using namesp ......