企业官网建设流程全解析

P10512 序列合并

题目描述

给定一个长度为nnn的非负整数序列{an}\{a_n\}{an​}，你可以进行kkk次操作，每次操作你选择两个相邻的数，把它们合并成它们的按位或。

形式化地，一次操作中，你选择一个下标iii（1≤i<n1 \le i < n1≤i<n），然后把原序列变成{a1,a2,⋯ ,aior⁡ai+1,ai+2,⋯ ,an}\{a_1,a_2,\cdots,a_i \operatorname{or} a_{i+1},a_{i+2},\cdots,a_n\}{a1​,a2​,⋯,ai​orai+1​,ai+2​,⋯,an​}。

求kkk次操作后所有数按位与的最大值。

输入格式

第一行包含两个正整数n,kn,kn,k。

第二行包含nnn个非负整数，其中第iii个非负整数为aia_iai​。

输出格式

输出一行，包含一个正整数，代表答案。

输入输出样例 #1

输入 #1

5 2 2 1 2 3 1

输出 #1

2

说明/提示

【样例解释】

一种合法的方案：

• 第一次操作，选择第一个数和第二个数合并，序列变为{3,2,3,1}\{3,2,3,1\}{3,2,3,1}。
• 第二次操作，选择第三个数和第四个数合并，序列变为{3,2,3}\{3,2,3\}{3,2,3}。

最终所有数的按位与为222。可以证明不存在更优的方案。

【数据范围】

• 对于25%25\%25%的数据，n≤20n \le 20n≤20。
• 对于另外25%25\%25%的数据，k=n−2k=n-2k=n−2。

对于所有数据，保证1≤k<n≤2×1051 \le k<n \le 2 \times 10^51≤k<n≤2×105，0≤ai<2300 \le a_i < 2^{30}0≤ai​<230。

C++实现

#include<iostream>usingnamespacestd;intn,m,k,a[200010];intlg(intx){intcnt=0;while(x)x>>=1,cnt++;returncnt-1;}boolchk(intx){intsum=0,cnt=0;for(inti=1;i<=n;i++){sum|=a[i];if((sum&x)==x)sum=0,cnt++;}returncnt>=k;}intmain(){cin>>n>>k;k=n-k;for(inti=1;i<=n;i++){cin>>a[i];m=max(m,lg(a[i]));}intnow=0;for(inti=m;i>=0;i--){now+=(1<<i);if(!chk(now))now-=(1<<i);}cout<<now<<endl;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容