天天看点

codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力,数学)

codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力,数学)

解题思路:就是求数 n 对应的二进制数中有多少个 1

codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力,数学)

解题思路:对(strength, i, j)按照strength进行递减排序,从左到右进行遍历,用b[N]表示i和j有关系! 

如果发现b[i]或者b[j]有关系了,则跳过这个strength, 否则b[i] =j, b[j] = i;

codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力,数学)

解题思路:

 

codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力,数学)

我们可以发现这样的一个规律:

(1)首先b一定要小于a,否则无论如何曲线也无法通过(a,b);

(2)设int k=a/b, 如果k为奇数,说明这个点在上图的绿色的线上, 没关系,我们让 k+=1;这样的话一定有(0,0), (a,b)这两点确定的直线的

斜率1/k介于(1/(k-1),  1/(k+1))之间,那么我们可以通过缩小(或者放大)X的值,使得第 k/2 个周期块 斜率为-1的那条边经过(a, b)。此时

的X值就是最小的!

(3)如果(a,b)在第 k/2 个周期块 斜率为-1的那条边上,那么这条边与X轴的交点就是(a+b, 0), 从(0, 0)到(a+b, 0)一共经过了 k/2个周期,

所以 X = (a+b)*1.0/(k/2 * 2)

(4)唉....想的这么明白,容易吗.....

codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力,数学)

解题思路:如果某个数a[i]乘以x, 必定会导致a[i]的二进制的长度增大。

首先求出或运算的前缀和后缀,然后对每个a[i]操作如下: a[i]*=x^k(x的k次方); 最后找到a[i]|pref[i-1]|suff[i+1]的最大值!

其实可以优化一处,就是a[i]|pref[i-1]|suff[i+1]的最大值一定对应二进制长度最大的a[i]; 可通过log(a[i])+1求得二进制长度!

继续阅读