题目摘录

题目摘录

​ 记录一下感觉还不错的题目。

D. XOR-gun(Technocup 2021 - Elimination Round 2)

题意:给你一个长为 n(2n105)n(2\le n\le 10^5) 的不严格单增正整数序列(109\le 10^9),每次可以将两个相邻位置合并成一个位置,值为原来两个位置的异或,最小化合并次数使序列不(不严格)递增

思路

如果存在三个数,它们为 11 的最高位相等,那么把大的两个数异或起来一定比小的小,合并次数为 11

如果不存在,那么序列长度一定比 6161 小(最多只有 3030 种最高位),暴力即可

G. Swapping Places(2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20))

题意:给一个长 n(105)n(\le 10^5) 的字符串序列,保证不同的字符串数目不超过 200200 组,给定一些字符串关系 (u,v)(u,v)uuvv 在序列中相邻时可以交换,找到若干次交换后字典序最小的字符串序列。

思路

vp 时想了个真贪心但写不出来,转化成一个假贪心后狂 wa…

贪心是可以写的,但我比较啥比不会

介绍一个笨比方法。

考虑没有关系的 uuvv ,那么它们在序列中的前后关系一定不会发生变化。

于是我们对它们连边,然后跑字典序最小的拓扑排序

连边需要优化保证边数为 O(200n)O(200n)

K. Birdwatching(2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20))

题意:给一个有向图 GGG105|G|\le 10^5)和 其中一个点 TT,找到所有点 nn 满足存在边 E(n,T)E(n,T) 且此边在所有 nnTT 路径上都出现

为啥我这么笨比啊

思路

不知道有没有什么别的方法,反正我没想到,最开始的思路处理不了 nn 在至少一个 TT 不在的环上的情况,我想了老半天才明白原来这里出了问题。

大概问题可以转化成,对每个存在 E(n,T)E(n,T)nn ,是否存在至少一条到其他满足存在 E(n,T)E(n',T)nn' 的路径。

如果我们令点集 S={nE(n,T)G}S=\{n|E(n,T)\in G\} 中的点为特殊点,那么上述问题可以表达为 n0Sn_0\in S 的每个点 n0n_0S\{n0}S \backslash \{n_0\} 的可达性

注意到这是存在性问题,如果一个 n0n_0 能达到任意两个不同的特殊点,那么它一定是可达的(即不满足题意的点)

于是建出反图,从每个特殊点往外跑对点进行染色,且保证每个点最多染两次不同颜色,就保证了复杂度为 O(n)O(n)

Codeforces Round #698 1A2D

给一个数列,a1,a2,a3,,ana_1,a_2,a_3,\dots,a_n , 每一次操作定义为,从已有的数字中随意选一个数字作为 xx,再选一个数字作为 yy ,两个数字可以相同,然后向数列中加入 2×xy2\times x - y 这个数字,选中的数字仍然在数列中。

可以操作任意次,问是否能凑出kk

思路

注意到 2xy2x-y 的中 xxyy 的系数和为 11,那么新生成的系数和也只能为 11

于是我们猜想,我们能生成所有系数和为 11 的数,经过归纳法构造我们发现这是正确的

系数和为 11 的数可以分成一个单独的数和系数和为 00 的数构成的线性空间

可以取所有相邻对的差 aiai1|a_i-a_{i-1}| ,即构成系数为 00 的数构成的线性空间

由裴蜀定理,k1b1+k2b2++knbnk_1b_1+k_2b_2+\dots+k_nb_n 能构成的整数为 kgcd(b1,b2,,bn)k\gcd(b_1,b_2,\dots,b_n)

于是可以枚举系数 11,然后看 kk 与其的差能否被 gcd(a2a1,)\gcd(a_2-a_1,\dots) 整除

  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 Dew
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信