Codeforces Round 802
E(总体观察,数学),F(贪心)
E
https://codeforces.com/contest/1700/problem/E
给你一个矩阵,每个数字都不相同
然后让你依次取1,2,3,4,… 取完所有
取的块需要和之前取过的至少一个4临
直接可取输出0
需要还是交换两个位置(可以不相邻)后可取,输出1 方案数
还是都不行输出2
范围
矩阵大小4e5
2s
256MB
题解
我的思路
0很好判断,vis染色+bfs
其实就是1的时候怎么算个数
不妨设按找上述方法最开始失败的是x
意味着, 小于x的连在一起了,
那么有两种方案
- 交换x和小于x的外边界,这样小于等于x就连在一起了,
- 交换小于x的某一个和x的四临
但是这两种如果一个一个检验是时间复杂度会炸掉的
考虑可交换的,对于第一种没有什么思路
对于第二种,你可以考察每个依赖于它的是否仅依赖于它, 但也不一定
1 | 145 |
比如上面这样,7仅依赖于6,而6也可以移动
不知道怎么搞了
题解
不要看一步一步,看总览性质
如果一个位置，它的四个邻居有比他小的，那么它就能连到小于它的数。矩阵为可遍历当且仅当所有点（除了1）的四个邻居都有比他小的。
这归纳法可证明
所以判断可行,也不再需要vis+bfs, 而直接判断count(badpos)== 0
所以badpos 需要交换它或者它的邻居
两两不相同,显然badpos不相邻, 因为badpos需要小于4临, 说明4临都不是badpos
两两不同,说明交换以后的两个位置,一个比原来大,一个比原来小,
比原来大的位置4邻之前一定不是badpos,
比原来小的本身一定不是badpos
综上, badpos最多5个, 一个中心一个4临
5x5x4, 种
代码
无
F
题目
https://codeforces.com/contest/1700/problem/F
2 * n 的01矩阵,两个
每次交换第一个中相邻位置的01,求最小次数得到第二个矩阵
范围
n 2e5
1s
256mb
题解
我的思路
写了个假的
两个变量记录未匹配的,然后进入则+,退出则-
发生 一正一负则消耗1抵消
竟然官方数据弱还过了system test
然后有错误样例
1 | 0 1 0 |
我的匹配会
1 | 0 b 0 |
代价为4, 最小的是2
官方
直接可配消耗掉即可…….
代码
无
总结
E
这个总体观察没想到, 一直在想细节的步, 总体只想到vis+bfs 而不是这个充分性质
jiangly 也TLE了好像
F
贪心细节还是没想到啊