比赛地址
先纪念一下ARC第100场！
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.
Idea
输入的时候先把$A_i$减去$i$，然后对新的数组排序，显然满足条件的$b$就是新数组的中位数。
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.
Idea
以下是官方题解：
中文：找到满足条件的前二大的$A_i$和$A_j$，使得$i \ or \ j ⊆ x$。必要条件是$x ⊆ i$和$x ⊆ j$。令$f_x$为满足条件的$i$和$j$，我们只要从小到大枚举$x$，对于每一个x的非零位j,我们可以用$f_x$的值去更新$f_{x|(1<<j)}$。同时维护$f_{x_0}$和$f_{x_1}$（前二大），最后$O(2^N)$更新答案。
时间复杂度$O(N 2^N)$。
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;
}
Summary
这场比赛没有打完就被电话拖住了。。。
幸好当时没有交题不然又是一题选手（