1863

CF1863E 参考这篇博客，本题解作为我的学习笔记。 思路 首先观察到提上说的依赖关系，容易联想到建出一张有向无环图。因为 \(a_i\) 要比 \(b_i\) 先完成，所以从 \(a_i\) 向 \(b_i\) 连一条边。而任务必须从入度为零的点开始依次往下做，因此想到拓扑排序（但题目给的就是拓 ......

B、Split Sort 跳转原题点击此：该题地址 1、题目大意 给定一个长度为n的排列（该排列的数字是包含\(1\sim n\)，每个数必须出现一次）。你可以执行以下操作： 选中一个数x，比x小的数按照原来的顺序放在x的左边，大于等于x的数按照原来的顺序放在x的右边。问你 将 原始排列组成\(a_ ......

C、MEX Repetition 跳转原题点击此：该题地址 1、题目大意 给定一个数组，要求每次依次从左到右将\(a_i\)替换为当前数组的最小非负整数（每次替换一个数后，最小非负整数也会发生改变）。问你，经过k次的操作后，最终数组是什么。 注意：该数组的数 和 最小非负整数，是从\(0,1,\cd ......

题意 给出具有依赖关系的 \(n\) 个任务，每个任务只能在某一天的第 \(h_i\) 小时做。只要满足了依赖关系，一个小时可以做很多任务。求最小的完成时间。 分析 结合题目条件，很快发现这是一个有多个联通块的 DAG。 拆分一下问题，先考虑怎么求单个联通块的所有开始时间和结束时间，然后再合并起来。 ......

本来开了某场远古 Div 1，然后学了一堆前置知识至今仍然不会 E。换一场写来得及吗？ A. Channel 模拟，略。 B. Split Sort Description 给你一个长度为 \(n\) 的排列。 每次操作你可以选择一个数 \(x\)，然后类似于快速排序地把小于 \(x\) 和大于等于 ......

CF1863 题解 A 条件很简单：如果总共的 '+' 号加上开始上线人数不到 \(n\) 人，就不可能。实时记录人数，如果某一时刻大于等于 \(n\) 人在线上，就一定是。剩余情况则可能。 #include<bits/stdc++.h> using namespace std; int main( ......

洛谷传送门 CF 传送门 看到 \(a_{a_i}\) 和 \(a_i \in [1, n]\)，果断连边 \(i \to a_i\)，得到内向基环森林。 那么每次相当于把 \(a_i\) 变成自环，连边 \(i \to a_{a_i}\)。 但是每次操作都改变图的形态很不好办，考虑打标记。 每次 ......

简洁的题面，深邃的思想。 首先，一个经典的套路是： 对于序列中涉及到对于 \(a_{a_i}\) 和 \(a_i\) 进行操作的问题，一般可以考虑建立 \((i,a_i)\) 的内向基环树或者 \((a_i,i)\) 的外向基环树转化为图论问题。 我们建立 \((i,a_i)\) 的内向基环树，\( ......

B. Split Sort 一开始想麻烦了，搞的没思路。 这道题只需要遍历一遍数组并查询当前查询的数小\(1\)的数是否查询过，如果没有查询过就代表该数在这个数的后面，\(Ans\)就需要加一，最后输出就行。 代码 #include <bits/stdc++.h> #define endl '\n' ......

C. MEX Repetition 通过观察样例，直接猜结论可知，例如第二个样例\([0, 1, 3]\)后面其实有一个隐藏数字（2），所以完整的排列为\([0, 1, 3, 2]\)。然后每一次操作都是把最后的一位数字移到整个排列的最前面，并把最后一位隐藏，所以直接取模就能求出最后的排列。 代码 ......

# CF1863B Split Sort 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863B) [Codeforces](https://codeforces.com/problemset/problem/1863/B) ## Desc ......

# CF1863C MEX Repetition 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863C) [Codeforces](https://codeforces.com/problemset/problem/1863/C) ## ......

# CF1863D Two-Colored Dominoes 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863D) [Codeforces](https://codeforces.com/problemset/problem/1863/ ......

[题面传送器](https://codeforces.com/contest/1863/problem/F "题面传送器") 首先有一个 $naive$ 的做法。 直接 $O(n^3)$ 暴力判断。 考虑寻找突破口。 假如给了你一个序列，异或值为 $S$ ，那么实际上假如中间有一个断点 $mid$ ......

## D.Two-Colored Dominoes ### 题目描述： 有一个$n\times m$棋盘，被分成若干小格。棋盘上还有一些多米诺骨牌。每张骨牌覆盖相邻的两个小格（即共用一条边的两个小格），没有两张骨牌重叠。 皮特认为这块棋盘太无聊了，需要涂上颜色。他要把多米诺骨牌的格子涂成黑色和白色。 ......

## 思路 ~~最开始没看懂题意，还想了会儿。~~ 容易发现，如果某个时刻存在总人数是满的，那么一定所有人都看到了，输出 ```YES```。 否则的话，如果不算减少的人数，总人数超过了 $n$，即认为每次新增的人都是之前没看过的人（虽然最终可能会超过 $n$，不符合情况），这样的话可能所有人都看到 ......

## 思路 对于每次操作，会把序列分成两个部分，两部分之间不会排序。 考虑仅每次排一个数字，理由如下： 假设已经排好了 $1,2,3\cdots i-1$ 的顺序，对于数字 $i$，如果 $i+1$ 在该数字的前面，那么 $k$ 应选择为 $i+1$，这样才能排好 $i$ 和 $i+1$。如果选择的 ......

## 思路 乍一看，感觉无从下手，于是就先列举了几个例子： ``` 02 10 21 02 013 201 320 132 013 12345 01234 50123 45012 34501 23450 12345 ``` 容易发现周期是 $n+1$，下面解释理由： 首先因为数量 $n$，且两两各不 ......

## 思路 首先考虑保证每行的黑白数量一样，横着的一定是贡献一黑一白，所以只用考虑竖着的，同理竖着的任何方案也不会影响横着的要求。 因为两个同行的竖着的颜色可以互换，所以在满足条件的情况下，谁黑谁白无所谓。 考虑从上往下满足，因为 ```D``` 的格子已经在上一行中确定了，所以可以在上一行时就先把 ......

看成内向基环森林，操作 $u\to v$ 相当于让 $u$ 连向 $v$ 所连的点，$v$ 变成自环。发现如果一个点 $v$ 变成了自环，那么操作任意一个 $u\to v$ 都没有用。 从简单的情形出发，对于一个内向树（或者说环大小为 $1$ 的内向基环树），每次操作 $x\to fa_x$ 时，相 ......