首页 > 其他分享 >AtCoder Regular Contest 149

AtCoder Regular Contest 149

时间:2022-10-05 16:56:35浏览次数:90  
标签:AtCoder AC Code 奇数 text 149 Regular LIS

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\),因此这种情况就是最优的。当然这个证明非常不严谨,不过感觉上很对就是了((

AC Code

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\) 的倍数放在边界处。

图源 AtCoder Official Editorial

这要求 \(\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\),然后区间变成了跨越零点的一条线段,那么我们发现只需要在较短的一边打上标记,然后只考虑较长的一边就行了。如图:

AC Code

貌似有人赛时用平衡树过了啊,我暂且膜拜

ARC149E - Sliding Window Sort

不会啊,看了 1.5h 题解都没懂。。。

标签:AtCoder,AC,Code,奇数,text,149,Regular,LIS
From: https://www.cnblogs.com/YunQianQwQ/p/16755835.html

相关文章

  • 题解【CF1149C Tree Generator】
    CF1149CTreeGenerator™不一定更好的阅读体验。牛逼题&ZROIDay3数据结构选讲。来一波详细的题解。当时和\(\texttt{ys}\),\(\texttt{hy}\)还有小猴子讨论了半......
  • AtCoder Regular Contest 149(持续更新)
    Preface最近国庆在外面玩的有点high啊,欠了一篇AT和两篇CF没写,今天先浅浅写一下这场当时10.2号在外面玩得有点晚了,到寝室刚好比赛开始,晚饭都没吃就开干了主要是C写的太久......
  • AtCoder Regular Contest 149
    A发现所有数字都相同的数一共只有\(10^6\)种,考虑枚举每种情况,关键在于如何判断一个数\(\bmodm\)是否为\(0\)。考虑\(9\bmod8=1\),而\(99\bmod8=(9\times10+9)\b......
  • AtCoder Beginner Contest 271
    AtCoderBeginnerContest271D-FlipandAdjust一共有\(N\)张牌,每一面都写着一个整数。卡\(i(1\lei\leN)\)前面写着整数\(a_i\),后面写着整数\(b_i\)。你可......
  • AtCoder Regular Contest 137 D
    一道很好的题目,运用了很多不同的技巧。结论1:枚举变换次数\(k\),若\(A_{i}\)对答案有贡献,当且仅当\(C_{n-i+k-1}^{k-1}\equiv1\mod2\)。首先我们可以统计\(A_{p}\)对......
  • Atcoder 题目选做
    ABC257G直接考虑\(\rmKMP\)的过程。\(\rmKMP\)可以帮助我们求出\(S\)的\(border\),并找到\(T\)中每一个位置能匹配上的\(S\)的最长前缀。那么我们就可以很......
  • ARC149E Sliding Window Sort(组合)
    ARC149ESlidingWindowSort给定\(M,K\)和\(N\)排列\(B\)。问对\(i=0\toK-1\)依次执行对\(j=0\toM-1,A_{(i+j)\bmodN}\)这段循环区间排序,最......
  • 【合集】AtCoder 比赛题解
    PartAABCABC266(A-Ex)ABC267(A-G)ABC268(A-D)ABC269(A-F)ABC270(D-E)ABC271(C-F)PartBARCARC148(C)......
  • codeforces/AtCoder补题整理
    目录cf1738CEvenNumberAddicts(博弈/记忆化搜索)题意题解cf1739EResetKEdges(树,二分+贪心)题意题解cf1730DPrefixesandSuffixes(字符串,思维)题意题解cf1734DS......
  • ARC149D Simultaneous Sugoroku(并查集)
    ARC149DSimultaneousSugoroku有\(N\)个数\(X_i\)和\(M\)个数\(D_i\),对每个\(X_i\)询问依次对\(j=1\ton\)执行:如果\(X_i>0\)就\(-D_j\),如果\(X_i<......