Codeforces Round 410(Div. 2)

Codeforces #410(Div. 2) - Click Here

  

Preface

  段考爆炸,《具体数学》看得我身心俱疲,所以还是来填填CF的坑吧~

  这场是构造题专场~

  

Problem A(CF798A)

Solutions

  扫一遍计算不满足的回文组数,然后判断是否为1即可。

  注意,如果回文组数为0且$n$为奇数,答案仍然为Yes。因为,可以通过修改中间字符来满足要求。

  

CODE

CODE - Click Here

  

Problem B(CF798B)

Solutions

  既然最后的目的是使得所有字符串都相同,那么只需要枚举第一个字符串的交换次数,就可以包含所有情况。

  所以暴力统计取最小值就好了~

  时间复杂度$O(N|S|^2)$

  

CODE

CODE - Click Here

  

Problem C(CF798C)

Solutions

  当初数论太差了,被这题卡死了QwQ。

  如果$gcd(a_1,a_2,…,a_n)>1$,显然不需要任何操作即满足要求。

  因此,现在只需要考虑$gcd(a_1,a_2,…,a_n)=1$的情况。

  

  首先设该序列的最大公约数为$d$。

  假设我们对序列中的$(a_i,a_{i+1})$进行操作,那么此时$d$应该满足,$d|(a_i-a_{i+1}) , \, d|(a_i+a_{i+1})$。根据整除的性质得$d|2a_i, \, d|2a_{i+1}$。

  又因为,$d$是序列的公约数,因此$d|gcd(a_1,a_2,…,2a_i,2a_{i+1},…,a_n)$。

  右式等价于$gcd(a_1,a_2,…,2gcd(a_i,a_{i+1}),…,a_n)$,因此$gcd(a_1,a_2,…,2a_i,2a_{i+1},…,a_n)|2$。

  即$d|2​$。

  换句话说,我们经过变换后,$d$只能够成为$2$。要满足$d=2$,需要将序列中所有奇数变为偶数

  

  考虑如何变换。

  如果$a_i$和$a_{i+1}$均为奇数,则只需要1次操作。(操作1)

  如果$a_i$和$a_{i+1}$仅含有一个奇数,则需要2次操作。(操作2)

  显然,要使得操作次数最少,最优策略是先执行操作1,后执行操作2。

  因此直接扫一遍计数即可。

  

  时间复杂度$O(Nlog \, a)$。

  

CODE

CODE - Click Here

  

Problem D(CF798D)

Solutions

  好套路的一题构造题,然而我并不会QwQ。

  题目要求选出一个集合$P$,使得$2\sum a_{p_k} > \sum a_i , \, 2\sum b_{p_k} > \sum b_i$。

  通过对式子的简单变形得到$\sum_{k \in P} a_k > \sum_{k \notin P} a_k , \, \sum_{k \in P} b_k > \sum_{k \notin P} b_k$。

  

  也就是说,我们选出的数字之和要大于未选出的数字之和

  同时注意到,选出的数字个数与未选出的数字个数的差为1或2。

  因此,我们可以对$A$序列和$B$序列适当的分组,每个组仅包含两个元素,这样从中选出较大的数字,则必定能够满足要求。

  但是$A$和$B$是互相制约的,$A$序列选取较大数字会导致$B$序列无法选取较大数字的情况。

  为了处理这种情况,可以对$A$排序,然后仅考虑$B$来选择。

  

  由此,我们得到最终的贪心策略:首先对$A$排序,然后必选最大的元素。接着,对剩下元素两两分组,选取$b$较大的元素。

  而这种做法的正确性亦是显然的:因为对$A$进行了排序,因此上次选取的元素必定大于等于这次未选取的元素;对于$B$,因为每次选取的都是最大的,因此每次选取的元素都大于等于未选取元素。又因为两者个数不同,又保证了不等式不可能取等号

  

CODE

CODE - Click Here

  

Problem E(CF798E)

Solutions

  又是构造题,不过这题比D要好做啊>_<。

  读入数据提供了一堆大小关系,因此根据差分约束的套路,可以由这些关系构造出一个有向图$G=(V,E)$,其中每条边$(u,v) \in E$都表示$p_u>p_v$。又因为$p_i$均不相同,所以这个图为有向无环图

  然后对这个图跑一遍拓扑排序,并根据拓扑序赋值,那么得到的答案必定是满足要求的。

  

  所以只要求出拓扑序,该题就解决了。所以我们考虑图中含有哪些边。

  

  令满足$a_i=-1$的值变为$a_i=n+1$。并定义$b_i=j$,其中$j$满足$a_j=i$,若不存在,则$b_i=n+1$。

  根据题意,显然可知对于每一个$i$,需要连的边有两种,一种为$(i,b_i)$,另一种为$(i,j)$,其中$1 \leq j < a_i$且$b_j>i$。

  第一种连边很好处理,但是另外一种连边就很难搞了,因为这种情况的边数最坏会达到$N^2$。要是使用Kahn算法,你必须要存储所有的边,或者是连续的加边并滋瓷用数据结构维护入度,而这两种方法都不能够实现。

  

  但是拓扑排序还能够dfs实现,我们考虑下基于dfs的拓扑排序能否解决问题。

  首先是第一种连边,显然可以实现。

  接着是第二种连边,需要找到连续区间内满足$b_j>i$的节点,这个节点可以利用线段树在$logN$的时间内找到,而且每个节点只会访问一次。因此寻找这种节点的总时间为$O(2NlogN)$。

  然后就解决问题啦~

  

  在这里提下为什么Kahn算法和基于dfs算法会在处理上出现时间上的差距。

  两种算法都是$O(V+E)$的,但不同之处在于Kahn算法需要利用到所有的边,而基于dfs的算法只需要找到与当前节点相连且未访问过的节点

  换句话说,基于dfs的算法不需要利用到所有的边。所以这种算法的时间是能够优化的~

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang