【学习笔记】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 的情况，最少能构造出三个环

Decrementing

• 如果存在 $a_i=1$ ，那么判断 $\sum (a_i-1)$ 的奇偶性 。
• 定义 $\sum (a_i-1)$ 奇数时为胜态，偶数时为负态
• 如果当前正在操作的人为胜态，那么无论另一个人怎么操作，当前这个人必胜
• 因为考虑如果没有所有数都除以最大公约数这个操作的话，$\sum a_i$ 的奇偶性不会变化，那么 $\sum (a_i-1)$ 的奇偶性也不会变化，胜负态是固定的
• 现在相当于 $\sum a_i\to \frac{\sum a_i}{x}$ ，当且仅当 $x$ 是偶数且 $\frac{\sum a_i}{x}$ 为奇数时才行
• 记序列中奇数的个数为 cnt ，初始因为互质所以 cnt>=1 ，那么两个人轮流操作，后手的人永远无法让 cnt=0 （n>=3 时）
• 如果当前操作的人为败态，那就操作唯一的奇数，这样有可能逆转胜负 。
• 因此直接模拟 。最多不会超过 $\log a$ 次 。