【学习笔记】AGC010

多做 AGC 长脑子

不给样例，光靠脑子想

Rearranging

• 考虑如果两个数不互质，那么它们在最终序列相对位置不变
• 因此对两个不互质的数连边，同时对每条边定向构造 DAG
• 答案就是最大的拓扑序，因为考虑一个点没有入度的话可以和任何其他的点交换
• 贪心的构造 。从编号最小的点开始 dfs ，每次找节点编号最小的出边，可以理解成构造了一颗树 。
• 然后模拟就行了 （

Tiling

• 贪心的考虑如何最大限度将网格铺满
• 显然将网格剖分成若干个 2x2 的矩阵是最优的
• 边角料就铺对应的横砖或竖砖
• 这样一定能最大化铺砖的数量
• 手玩发现 n=3,m=3,A=2,B=2 的情况会有问题（这里找 hack 数据是难点
• 也就是说对于最后一个 2x2 的方格，还剩横砖和竖砖各一个，理论上能铺两块砖，但是由于形状原因只能铺一块

• 注意到右下角还空了一个位置，可以通过调整放下 。

• 直接分两种方案 check 即可 。
• 注意到网格问题 Nastia and a Beautiful Matrix ，从 最大化利用网格空间 入手，找到局部最优，进而构造出全局最优解 。

Three Circuits

• 每个点的度数都必须是偶数
• 题目给了这是一个连通图，所以一定存在欧拉回路
• 如果存在点的度数 >=6 ，那么必然有解（考虑从欧拉回路角度去证
• 记度数 = 4 的点个数为 cnt
• 如果 cnt=0 ，那么最多只能构造出一个环
• 如果 cnt=1 ，那么最多只能构造出两个环
• 如果 cnt=2 ，那么有两种情况（画图感知：可能构造出两个环或三个环
• 如果 cnt>=3 ，那么去掉一个简单环后归纳到 cnt=2 的情况，最少能构造出三个环