链接
https://arc100.contest.atcoder.jp/
C Linear Approximation
题解
把ai减去i后排序, 我们要的b就是排完序后的中位数
Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 ll read(){ 6 ll x=0,f=1;char c=getchar(); 7 while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();} 8 while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();} 9 return x*f; 10 } 11 12 int n; 13 int a[200200]; 14 map<int,int> m; 15 16 int main(){ 17 #ifdef LZT 18 freopen("in","r",stdin); 19 #endif 20 n=read(); 21 for(int i=1;i<=n;i++) a[i]=read()-i; 22 ll ans=0; 23 sort(a+1,a+n+1); 24 int mx=a[(n+1)/2]; 25 for(int i=1;i<=n;i++) ans+=abs(a[i]-mx); 26 printf("%lld ",ans); 27 return 0; 28 }
D Equal Cut
题解
如果只切一刀,那么很好确定位置
我们预处理出前i个和后i个切一刀的最佳位置
然后枚举中间的一刀的位置 然后前面后面两刀都处理出来了 算一下取最大值就好
Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 ll read(){ 6 ll x=0,f=1;char c=getchar(); 7 while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();} 8 while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();} 9 return x*f; 10 } 11 12 int n; 13 ll a[200200]; 14 ll fen1[200200],fen2[200200]; 15 pair<ll,ll> s1[200200],s2[200200]; 16 17 int main(){ 18 #ifdef LZT 19 freopen("in","r",stdin); 20 #endif 21 n=read(); 22 for(int i=1;i<=n;i++) a[i]=read(); 23 ll pos=1,sum=a[1],sum2=a[1]; 24 for(int i=2;i<=n-2;i++){ 25 sum2+=a[i]; 26 while(pos<i){ 27 ll nwsum=sum+a[pos+1]; 28 //cout<<sum2<<' '<<sum<<' '<<nwsum<<endl; 29 if(abs(sum2-sum-sum)>abs(sum2-nwsum-nwsum)){ 30 pos++; 31 sum=nwsum; 32 } 33 else break; 34 } 35 //cout<<pos<<endl; 36 if(pos==i) sum-=a[pos],pos--; 37 fen1[i]=pos; 38 s1[i].first=sum; 39 s1[i].second=sum2-sum; 40 //cout<<i<<' '<<sum<<' '<<sum2-sum<<endl; 41 } 42 pos=n,sum=a[n],sum2=a[n]; 43 for(int i=n-1;i>2;i--){ 44 sum2+=a[i]; 45 while(pos>i){ 46 ll nwsum=sum+a[pos-1]; 47 if(abs(sum2-sum-sum)>abs(sum2-nwsum-nwsum)){ 48 pos--; 49 sum=nwsum; 50 } 51 else break; 52 } 53 if(pos==i) sum-=a[pos],pos++; 54 fen2[i]=pos; 55 s2[i].first=sum; 56 s2[i].second=sum2-sum; 57 //cout<<i<<' '<<sum<<' '<<sum2-sum<<endl; 58 } 59 ll ans=1e18; 60 for(int i=2;i<=n-2;i++){ 61 ll S1=s1[i].first,S2=s1[i].second,S3=s2[i+1].first,S4=s2[i+1].second; 62 ans=min(ans,max(max(max(S1,S2),S3),S4)-min(min(min(S1,S2),S3),S4)); 63 } 64 printf("%lld ",ans); 65 return 0; 66 } 67 68 /* 69 5 70 3 2 4 1 2 71 */
E Or Plus Max
题解
我们要求max Ai+Aj s.t. i or j <=x
可以转化成max Ai+Aj s.t. i or j =x 然后求一个前缀max
转化成max Ai+Aj s.t. i or j ∈ x 然后求一个前缀max
转化成(max Ai s.t. i ∈ x )+ (second_max Ai s.t. i ∈ x)
所以我们需要维护pair<int,int> b[x]表示所有i∈x的最大值和第二大值
所有i∈x => 快速Zeta变换
然后就做完了
Code
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 ll read(){ 6 ll x=0,f=1;char c=getchar(); 7 while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();} 8 while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();} 9 return x*f; 10 } 11 12 int n; 13 int a[1000100]; 14 pair<int,int> b[1000100]; 15 16 void upd(int x,int y){ 17 int num1=b[x].first,num2=b[x].second,num3=b[y].first,num4=b[y].second; 18 b[x].first=max(num1,num3); 19 if(num1>num3) b[x].second=max(num2,num3); 20 else b[x].second=max(num1,num4); 21 } 22 23 int main(){ 24 #ifdef LZT 25 freopen("in","r",stdin); 26 #endif 27 n=read(); 28 for(int i=0;i<(1<<n);i++) 29 a[i]=read(); 30 for(int i=0;i<(1<<n);i++) 31 b[i].first=a[i],b[i].second=-1e9; 32 for(int k=0;k<n;k++){ 33 //cout<<k<<endl; 34 for(int i=0;i<(1<<n);i++){ 35 if((i&(1<<k))!=0) continue; 36 upd(i|(1<<k),i); 37 //cout<<(i|(1<<k))<<' '<<i<<endl; 38 } 39 }/* 40 for(int i=0;i+1<(1<<n);i++){ 41 upd(i+1,i); 42 }*/ 43 int lastans=0; 44 for(int i=1;i<(1<<n);i++){ 45 lastans=max(lastans,b[i].first+b[i].second); 46 printf("%d ",lastans); 47 } 48 return 0; 49 } 50 51 /* 52 2 53 1 2 3 1 54 */