【学习笔记】AGC041

Domino Quality

• atcoder简洁题面好评
• 做构造题要有耐心
• 好阴间的构造题啊。。。
• 设$(A,Q)$表示每行每列数量为$Q$的$A\times A$大小的矩阵
• 如果我们知道$(A,Q)$以及$(B,Q)$的构造方法，我们就能构造出$(A+B,Q)$
• 具体做法是把两个矩阵分别放在左上角和右下角，其余为空
• 显然考虑$Q=3$的情况 并不显然
• 显然可以把$(4,3),(5,3),(6,3),(7,3)$全部暴搜出来
• 显然可以打表 反正这题考点也不在这
• 诶n=7怎么暴力跑不出来呀
• 诶加了玄学剪枝怎么就跑得飞快呀
• 代码一堆打表非常丑陋甚至输出也很丑陋

Unique Path

• 美妙的构造题 虽然我还是做不出来
• 显然删去所有边权为$1$的边，对于每个连通块内的点两两有唯一简单路径
• 先不忙对每个连通块缩点，首先我们从每个连通块中选取一个点，然后把它们连成一个环，这样对于不在同一个连通块内的点有至少两条简单路径
• 设连通块数目为$k$（上述构造恰连了$k$条边，构成一颗基环树），那么跨连通块边的数目不会超过$\frac{k(k-1)}{2}$，否则一个连通块不能保持其独立性
• 因此我们只要判断$m$的大小是否在范围内即可。
• 复杂度$O(n)$。
• 总结：考虑答案的上下界

Wide Swap

• 兔兔的题解
• 考虑一个好的问题转化
• 设$Q[i]$表示$i$在原序列中的位置
• 那么交换$Q[i]$和$Q[i+1]$的条件是$|Q[i]-Q[i+1]|\ge K$
• 如果$i<j$,$|Q[i]-Q[j]|<K$那么$Q[i]$和$Q[j]$的相对位置关系不会发生改变，换句话说$Q[i]$永远在$Q[j]$之前
• 那么我们让$Q[i]\to Q[j]$这样跑出来的拓扑序一定是满足限制的
• 同时我们要让$P$的字典序最小，转化成$1$在$Q$中最靠前，在$1$最靠前的前提下让$2$最靠前
• 这是一个经典问题 不要再经典了我都wa过一遍了 可以建反图跑最大拓扑序解决
• 可以按编号从小到大考虑$Q[i]$，我们发现只要找到$Q[i]$的前驱编号最大和后继编号最大连边即可。
• 复杂度$O(n\log n)$

Nondivisible Prefix Sums

• Hint1：所有元素之和不能被$P$整除 显然
• Hint2：众数出现次数不超过$\frac{n}{2}$的序列合法（可以倒着考虑
• Hint3：有一个巧妙的转化。设众数为$x$，将所有元素乘$x^{-1}$，那么前缀和也会乘$x^{-1}$
• Hint4：巧妙的观察注意到每跨过$P$都会消耗至少一个不为$1$的数字
• 那么不为$1$的数字至少有$\frac{{\sum }_{i=1}^n{y}_i}{P}$个
• 考虑构造方案，首先把所有数字$1$用完，然后对于剩下的只要我们让它不到达$P$
• 显然去掉众数后是有解的