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

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

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

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

#include iostream 

#include algorithm 

#include cstdio 

using namespace std; 

struct node{

 int x;

 int i, j;

}a[320000];

int b[1000];

bool cmp(node a, node b){

 return a.x b.x;

int main(){

 int x, n;

 int c = 0;

 cin n;

 for(int k=2; k =2*n; ++k){

 for(int kk=1; kk ++kk){

 cin x;

 a[c].x = x;

 a[c].i = k;

 a[c++].j = kk;

 sort(a, a+c, cmp);

 int cnt = 0;

 for(int i=0; i ++i){

 if(!b[a[i].i] !b[a[i].j]){

 b[a[i].i] = a[i].j;

 b[a[i].j] = a[i].i;

 ++cnt;

 if(cnt == n) break;

 for(int i=1; i =2*n; ++i){

 if(i!=1) cout " ";

 cout b[i];

 cout endl;

 return 0;

}

解题思路：

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

(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)唉....想的这么明白，容易吗.....

#include iostream 

#include algorithm 

#include cstdio 

#include cmath 

using namespace std; 

int main(){

 int a, b;

 cin a b;

 if(b a) {

 cout -1 endl;

 } else {

 int k = a/b;

 if(k 1) ++k;

 printf("%.12lf\n", (a+b)*1.0/k);

 return 0;

}

解题思路：如果某个数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求得二进制长度！

#include iostream 

#include algorithm 

#include cstdio 

#include cmath 

#define N 200010

using namespace std; 

__int64 a[N];

__int64 pref[N];

__int64 suff[N];

int n, k, x;

int main(){

 scanf("%d%d%d", n, k, 

 long long maxN = 0;

 for(int i=1; i ++i)

 scanf("%I64d", a[i]);

 long long xk = (long long)(pow((double)x, (double)k) + 0.5);

 for(int i=1; i ++i){

 pref[i] = pref[i-1] | a[i];

 suff[n-i+1] = suff[n-i+2] | a[n-i+1];

 for(int i=1; i ++i){

 long long num = a[i]*xk | pref[i-1] | suff[i+1];

 if(maxN num)

 maxN = num;

 printf("%I64d\n", maxN);

 return 0;

}