## 比赛地址

Tasks
– Linear Approximation
– Equal Cut
– Or Plus Max
– Colorful Sequences (too hard to deal with it)

### C – Linear Approximation

#### Statement

Snuke has an integer sequence $A$ of length $N$.
He will freely choose an integer $b$.
Here, he will get sad if $A_i$ and $b+i$ are far from each other.
More specifically, the sadness** of Snuke is calculated as follows:
$$abs(A_1 – (b+1)) + abs(A_2 – (b+2)) + … + abs(A_N – (b+N))$$
Here, $abs(x)$ is a function that returns the absolute value of $x$.
Find the minimum possible sadness of Snuke.

#### Code

    for(int i=1; i<=n; i++)
cin>>a[i], a[i]-=i;
sort(a+1,a+n+1);
long long t=a[(n+1)>>1];
for(int i=1; i<=n; i++)
ans+=abs(a[i]-t)
cout<<ans<<endl;


### D – Equal Cut

#### Statement

Snuke has an integer sequence $A$ of length $N$.
He will make three cuts in $A$ and divide it into four (non-empty) contiguous subsequences $B, C, D$ and $E$.
The positions of the cuts can be freely chosen.
Let $P,Q,R,S$ be the sums of the elements in $B,C,D,E$, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among $P,Q,R,S$ is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among $P,Q,R,S$.

#### Idea

$O(n)$枚举第二个分割点，对于每一个不同的位置，都有唯一确定的，分割它左边和右边部分的方案，使得结果对于这个位置最优。发现在第二个点向右移动的时候，第一个和第三个分割点也在不断向右移动。用两个指针处理即可。

#### Code

// Equal Cut.cpp: 定义控制台应用程序的入口点。
// XG_Zepto, 7/3/2018. All rights reserved.

#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 200101
using namespace std;
long long n,a[maxn],s[maxn],ans=0x7777777777777777;
long long gt(int l,int r){
return s[r]-s[l];
}
int l,r,m;
bool movl(){
if (l+1==m) return 0;
long long t1=abs(gt(0,l)-gt(l,m));
long long t2=abs(gt(0,l+1)-gt(l+1,m));
return t2<=t1;
}
bool movr(){
if (r+1==n) return 0;
long long t1=abs(gt(m,r)-gt(r,n));
long long t2=abs(gt(m,r+1)-gt(r+1,n));
return t2<=t1;
}
void update(){
long long t1=min(gt(0,l),min(gt(l,m),min(gt(m,r),gt(r,n))));
long long t2=max(gt(0,l),max(gt(l,m),max(gt(m,r),gt(r,n))));
ans=min(ans,t2-t1);
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
s[i]=s[i-1]+a[i];
l=1,r=3,m=2;update();
for (m=2;m<=n-2;m++){
while(movl()) l++;
while(movr()) r++;
update();
}
cout<<ans<<endl;
system("PAUSE");
return 0;
}


### E – Or Plus Max

#### Statement

There is an integer sequence of length $2^N$: $A_0, A_1, …, A_{2^N-1}$. (Note that the sequence is $0$-indexed.)
For every integer $K$ satisfying $1 \leq K \leq 2^N-1$, solve the following problem:

Let $i$ and $j$ be integers. Find the maximum value of $A_i + A_j$ where $0 \leq i < j \leq 2^N-1$ and $(i$ $or$ $j) \leq K$.
Here, $or$ denotes the bitwise OR.

#### Code

// Or Plus Max.cpp: 定义控制台应用程序的入口点。
// XG_Zepto, 7/4/2018. All rights reserved.

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 2000100
using namespace std;
int n,a[maxn],f[maxn][2],ans[maxn];
void work(int x,int y){
if (f[x][0]==y||f[x][1]==y) return;
if (a[f[x][1]]<a[y]){
f[x][1]=y;
if (a[f[x][0]]<a[f[x][1]]) swap(f[x][0],f[x][1]);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for (int i=0;i<(1<<n);i++){
cin>>a[i];f[i][0]=i;
}
for (int x=0;x<(1<<n);x++)
for (int j=0;j<n;j++){
if ((x>>j)&1) continue;
work(x|(1<<j),f[x][0]);
work(x|(1<<j),f[x][1]);
}
for (int i=1;i<(1<<n);i++){
ans[i]=max(ans[i-1],a[f[i][0]]+a[f[i][1]]);
cout<<ans[i]<<endl;
}
system("PAUSE");
return 0;
}