- Thinking
- 2020 南京 H. Harmonious Rectangle
- 2021 昆明 Parallel Sort
- 2019 哈尔滨 I. Interesting Permutation
- 2020 上海 D. Walker
-
Harmonious Rectangle
-
思路：意识到，当矩形长边大于 9 时，0，1，2 三个数字形成的 00，01，02，10，11，12，20，21，22 一定会出现重复出现，又因为 00，11，22 在前 7 列出现一个后，下一个一出现也会一定有重复。所以当矩形长边大于 7 时一定有解。
小数据暴力搜索后打表，大数据直接快速幂计算即可。
//思维题: 容斥原理！！！ #include
#define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) #define ll long long #define db double #define PII pair
-
Parallel Sort
-
思路：由于原数列是 1 ∼ n 1sim n 1∼n 的一个排列，所以没有重复数字，每个数值最终也会与位置编号一一对应。当 s z sz sz 个数字构成一个位置对应的环时，发现一种最多两步便可使所有数值归位的方法。例如：（其中第一步建成逆序排列）
位置编号 1 2 3 4 5 初始值 5 1 2 3 4 第一步后 5 4 3 2 1 第二步后 1 2 3 4 5 #include
#define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) #define ll long long #define db double #define VI vector #define PII pair
-
Interesting Permutation
-
思路： O ( n ) O(n) O(n)
∵ f i = max { a i , f i − 1 } , g i = min { a i , g i − 1 } ∴ h i = max { a i , f i − 1 } − min { a i , g i − 1 } 若 a i > f i , h i = a i − g i − 1 > h i − 1 若 g i − 1 < a i < f i , h i = f i − 1 − g i − 1 = h i − 1 若 a i < g i − 1 , h i = f i − 1 − a i > h i − 1 because f_i=max{a_i,f_{i-1}},g_i=min{a_i,g_{i-1}} qquadtherefore h_i=max{a_i,f_{i-1}}-min{a_i,g_{i-1}}\ begin{aligned}&若a_i>f_i,&h_i=a_i-g_{i-1}>h_{i-1}\ &若g_{i-1}h_{i-1}\ end{aligned} ∵fi=max{ai,fi−1},gi=min{ai,gi−1}∴hi=max{ai,fi−1}−min{ai,gi−1}若ai>fi,若gi−1-
因此 h 1 = 0 , h i ≥ h i − 1 h_1=0,h_ige h_{i-1} h1=0,hi≥hi−1 一定成立，于是无解情况需要充分讨论。
-
有解时
- 若 h i > h i − 1 h_i>h_{i-1} hi>hi−1，那么 a i a_i ai 可以为最大值或最小值两种情况，同时 g i − 1 ∼ f i − 1 g_{i-1}sim f_{i-1} gi−1∼fi−1 变为 g i ∼ f i g_isim f_i gi∼fi ，其中增加 h i − h i − 1 − 1 h_i-h_{i-1}-1 hi−hi−1−1 个空位。
- 若 h i = h i − 1 h_i=h_{i-1} hi=hi−1，那么 a i a_i ai 只能在 g i − 1 ∼ f i − 1 g_{i-1}sim f_{i-1} gi−1∼fi−1 中的空位中选择一个，并用掉一个空位。
#include
using namespace std; #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) #define ll long long #define db double #define VI vector #define PII pair -
-
Walker
-
思路：
-
首先 calc 这个函数绝妙，省去许多情况的讨论。
-
其次，分为三种情况：
- 一个人速度特别快，自己就走完全程即可。
- 两个人速度差距不大，但是速度慢的离自己临近端点较远，两个人只需要走到对面端点即可。
- 两个人分别负责自己的区间，争取同时完成(但不能强求)，两个区间交点便应该在 p1 和 p2 之间，二分查找最优答案即可。
我们一开始想到二分，但是写的复杂了许多，还没有用那个函数，越写越臃肿，思路就更乱了。
#include
using namespace std; #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) #define ll long long #define db double #define VI vector #define PII pair -
