CodeForce Round#275 Div.2

A. Counterexample

Your friend has recently learned about coprime numbers. A pair of numbers {a, b} is called coprime if the maximum number that divides both a and b is equal to one.

Your friend often comes up with different statements. He has recently supposed that if the pair (a, b) is coprime and the pair (b, c) is coprime, then the pair (a, c) is coprime.

You want to find a counterexample for your friend's statement. Therefore, your task is to find three distinct numbers (a, b, c), for which the statement is false, and the numbers meet the condition l ≤ a < b < c ≤ r.

More specifically, you need to find three numbers (a, b, c), such that l ≤ a < b < c ≤ r, pairs (a, b) and (b, c) are coprime, and pair(a, c) is not coprime.

Solution

r-l\leq50暴力怎么搞都能过


B. Friends and Presents

You have two friends. You want to present each of them several positive integers. You want to present cnt1 numbers to the first friend and cnt2 numbers to the second friend. Moreover, you want all presented numbers to be distinct, that also means that no number should be presented to both friends.

In addition, the first friend does not like the numbers that are divisible without remainder by prime number x. The second one does not like the numbers that are divisible without remainder by prime number y. Of course, you're not going to present your friends numbers they don't like.

Your task is to find such minimum number v, that you can form presents using numbers from a set 1, 2, ..., v. Of course you may choose not to present some numbers at all.

A positive integer number greater than 1 is called prime if it has no positive divisors other than 1 and itself.

Solution

个人感觉是比较好的一题

首先很容易发现答案满足单调性,想到二分一发答案

问题转化为,对于[1,n]能否取出cnt1,cnt2个数给小A,小B使得小A有的数均不能被x整除,小B有的数均不能被y整除

这就是经典套路题了

记集合A表示[1,n]能被x整除的数有多少个,集合B表示[1,n]能被y整除的数有多少个

集合A\cap B即表示[1,n]能被x,y整除的数有多少个

集合A\cup B表示[1,n]能被x,y中任意一个整除的数有多少个

首先有|A|=\frac{n}{x},|B|=\frac{n}{y},|A\cap B|=\frac{n}{lcm(x,y)}

由容斥原理,有A\cup B=|A|+|B|-|A\cap B|

现在,我们开始进行贪心的分配

很容易可以知道[1,n]只能被x整除的数有n-|B|-|A\cap B|

不能被y整除的数有n-|A|-|A\cap B|

那么先把只能被x整除的数丢给小B,只能被y整除的丢给小A

如果不够,考虑均不能被x,y整除的数的个数来补上,即N-|A\cup B|

如果还补不上,就只能GG咯,合法区间下调,不合法上调

注意一个坑点,答案可能会超过cnt1+cnt2,于是要开个long\;long

时间复杂度O(\log n)


C. Diverse Permutation

Permutation p is an ordered set of integers p1,   p2,   ...,   pn, consisting of n distinct positive integers not larger than n. We'll denote asn the length of permutation p1,   p2,   ...,   pn.

Your task is to find such permutation p of length n, that the group of numbers |p1 - p2|, |p2 - p3|, ..., |pn - 1 - pn| has exactly k distinct elements.

Solution

思博题,先按照差为k,k-1,k-2,....,1的方式构造出来

怎么构造呢?一种比较轻易的方法就是每次丢进当前最小,当前最大

这样下一次的差就是当前最大减去丢了当前最小以后的最小值,显然为k-1

然后就没了,时间复杂度O(n)


D. Interesting Array

We'll call an array of n non-negative integers a[1], a[2], ..., a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value should be equal to qi.

Your task is to find any interesting array of n elements or state that such array doesn't exist.

Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".

Solution

思博题,讲道理,这种涉及位运算就把数转为二进制处理的做法早就烂大街了吧

首先我们对问题进行离线处理

我们把q_{i}进行二进制拆分,对于有1的那一位,就把序列中[l,r]的那一位全都弄成1

最后查询答案是否存在只需要看如果q_{i}的二进制拆分情况为0的那一位所在的区间均为1就GG,否则直接用这种情况构造出来的解即可

那么暴力的时间复杂度为O(nm),TLE

考虑到最大的问题在于查询位数和i的区别,关于这个有2种优化

(1)建32棵线段树,每一次等价于插入区间,然后查询区间和,时间复杂度O(m\log^{2} n)

(2)线段树太烦,发现带修改的时候无查询操作,不妨转化为差分即可

对每次询问,把a[bit][s]++,a[bit][e+1]--,然后统计出即可

至于查询区间和可以考虑差分以后再前缀和,总的时间复杂度为O(m\log q_{i}+n)

考场上傻叉了wa在了很奇怪的地方,即如果长度为1的操作区间出现两次且q_{i}不同,就直接输出NO


E题概率DP,先skip了QQ图片20160623113147

发表评论