ARC149A - Repdigit Number
符合条件的数一共只有 \(9N\) 个,随便怎么做都行。AC Code
ARC149B - Two LIS Sum
这个操作相当于我们可以将 \(A\) 任意排列,然后对 \(B\) 进行对应的操作。
猜结论:最优方案一定是把 \(A\) 排成 \(1,2,\cdots,N\),然后求一下 \(B\) 的 \(\text{LIS}\)。
感性理解一下,在这种状态下,任意交换两个数都会使 \(A\) 的 \(\text{LIS}\) 至少减一,但是 \(B\) 的 \(\text{LIS}\) 至多增加 \(1\),因此这种情况就是最优的。当然这个证明非常不严谨,不过感觉上很对就是了((
ARC149C - Avoid Prime Sum
当 \(N\) 为偶数时,我们可以将这个正方形分成上下两半,上半部分填奇数,下面填偶数。
现在只需要找到 \(N\) 对和不为素数的奇偶数对,这个可以直接枚举奇数慢慢搜,搜到 \(N\) 对立刻退出。实测很快就搜出来了。然后把这 \(N\) 对数填到中间线的上下就行了。
当 \(N\) 为奇数时,会有一个位置匹配了两次:
11111
11111
11100
00000
00000
\(1\) 代表奇数,\(0\) 代表偶数,那么第三行第三列的奇数匹配了两次。
不过没有关系,我们可以乱搞:在这 \(N\) 个数对中暴力找 \(\frac{N(N-1)}{2}\) 对可能的多余匹配,如果找到了就把这一组放到中间的位置。然后就过了。AC Code
然而正经的做法是这样的:首先奇偶分类,然后在每一侧分别按模 \(3\) 意义下分类,都把 \(3\) 的倍数放在边界处。
这要求 \(\frac{N^2}{2}\ge 3N\) 即 \(N\ge 6\),因此只需要暴力跑一下 \(N=3,4,5\) 就行了。
ARC149D - Simultaneous Sugoroku
Difficulty 是 C 的两倍多。。。。
感觉官方题解说的很清楚啊
考虑直接维护 \([1,10^6]\) 这个区间内所有点的移动情况。注意到一个性质:
如果某一时刻出现了两个点 \(x,-x\),那么可以发现 \(-x\) 的所有移动都与 \(x\) 相对称,因此只需考虑二者之一。
这样一来,假如我们现在有个操作 \(-D\),然后区间变成了跨越零点的一条线段,那么我们发现只需要在较短的一边打上标记,然后只考虑较长的一边就行了。如图:
貌似有人赛时用平衡树过了啊,我暂且膜拜
ARC149E - Sliding Window Sort
不会啊,看了 1.5h 题解都没懂。。。
标签:AtCoder,AC,Code,奇数,text,149,Regular,LIS From: https://www.cnblogs.com/YunQianQwQ/p/16755835.html