首页 > 代码库 > Codeforces Educational Round 23

Codeforces Educational Round 23

A

emmmmmmmmm

B

emmmmmmmmm

C(套路)

题意:

给定n和s(n,s<=1e18),计算n以内有多少个数x满足(x-x的各个位置数字之和)>=s

分析:

容易想到如果x相对于s很大很大,那么肯定是满足条件的

那些小于s的数,肯定是不行的

于是x就可以从s开始,往后枚举1e6个,去判定这1e6个有多少个是满足条件的,再往后的那些x肯定是满足的,直接算出多少个就行了

D(插板法)

题意:

给定一个长度为n(n<=1e6)的数列,对于这个数列的一个连续的子列,定义value=http://www.mamicode.com/该子列的最大值-最小值。求这个数列所有连续子列的value和

分析:

肯定要分开考虑,考虑一个数字a[i]作为最大值能贡献多少组子列,作为最小值能贡献多少组子列(作为最小值的时候是负贡献)

下面以求最大值为例,求最小值同理

问题就转变成了要求出每个数字a[i]往左往右至多扩展多长距离才遇见第一个比其大的数

可以先把所有数字排序,然后按照从大到小的顺序将数字插入到对应位置上,那么对于当前考察的a[i],离其最近的左边隔板和右边隔板就是它作为最大值的区间

这一过程可以用set来维护

时间复杂度O(nlogn)

E(Trie树处理异或比较问题)

题意:

在一个初始为空的集合中有1e5个操作:

  1)插入一个数字p

  2)删除一个数字p(保证合法)

  3)输入p和l,询问当前集合中有多少个数字x满足p xor x < l

分析:

经典的Trie树处理异或比较问题

这里有个删除操作

实际上在Trie树上就直接暴力删就行了,复杂度O(logA)的

具体的就是从root开始沿着p数字的二进制位走,如果发现当前某一分支的sum==1,就说明这个分支下面只管理着一个节点(这就是我们要删的),所以直接在这里把树枝断掉就行了

复杂度O(qlogA)

F(线段树)

题意:

在一个初始为空的集合中有1e5个操作:

  1)将[l,r]这些数加入到集合中(如果数字重复就只保留一个)

  2)将[l,r]这些数从集合中删除(如果集合中本来就没有某个数,那这个数就不操作)

  3)将[l,r]这些数在集合中的出现情况反转,也就是将原本在集合中存在的数删除,原本不在的数加入

l,r<=1e18

在每次操作之后,输出集合的mex,即最小的没有出现在集合中的正整数

分析:

每次的结果肯定会在所有的l、所有的r+1,以及数字1中产生

考虑先把所有数据读入,将这些数字离散,建立一个线段树

对于操作1和2,就是将线段树一段区间赋值,sum直接维护

对于操作3,就是将线段树一段区间异或(只有0和1),sum=len-sum

发现这个线段树是可以lazy的,并且可以合并

对于查询,就是寻找线段树上最左边的0的点,直接根据一个节点k的sum[lchild]与len[lchild]的大小关系即可判断是向左走还是向右走,查询也是O(logn)的

时间复杂度O(nlogn)

Codeforces Educational Round 23