0%

简单构造题

qwq

1521A - Nastia and Nearly Good Numbers

给定$A,B$构造三个数$x,y,z$,使得其中两个数仅能被$A$整除,而第三个数能被$A\cdot B$整除,且$x+y=z$。

构造方法:构造$A+A\cdot B=A(B+1)$,那么除了$B=1$时都存在解。

1520C - Not Adjacent Matrix

构造一个$n\times n$矩阵,使得上下左右四个方向的任意两个数的绝对值差不等于$1$。

构造方法:注意到矩阵中任意两个相邻元素的横纵坐标之和的奇偶性不同,先依次填入和是偶数的,再依次填入和是奇数的位置即可。特判$n=2$无解。

798. 得分最高的最小轮调

把一个数组nums向左循环移位k步,称它为nums1。找到使得新的数组nums1nums1[i]<=i的数量最大的k

构造方法:已知一个元素x和它的下标i,可以求解令这个数产生贡献的k的区间范围,对这个区间差分+1。最后$O(n)$扫一下。