【洛谷P4144】大河的序列
题目大意：给定一个长度为 N 的序列，求序列中连续区间最大的（或和加与和）是多少。
题解：
引理：任意两个数 \(i, j\)，若 \(i>j\)，则在二进制表示下，i 对应的二进制串的字典序一定大于 j 对应的二进制串的字典序。
根据引理，若当前的最优解为 X，现考虑新加入一个元素 Y，有以下三种情况。
- 若 \(X>Y\)，则 Y 不应加入 X 对答案的贡献中，因为对于或来说新加入 Y 的贡献会比 Y & X 对答案的负贡献小。
- 若 \(X=Y\)，则无所谓。
- 若 \(X
另一种解法是 贪心+二分，枚举左端点，再根据二进制位从高到低进行贪心，用二分加速寻找最优的右端点。时间复杂度为 \(O(nlog^2n)\)。
代码如下
#include
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define cls(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair P;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
const double eps=1e-6;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;
}
inline ll sqr(ll x){return x*x;
}
inline ll fpow(ll a,ll b,ll c){ll ret=1%c;
for(;
b;
b>>=1,a=a*a%c)if(b&1)ret=ret*a%c;
return ret;
}
inline ll read(){
ll x=0,f=1;
char ch;
do{ch=getchar();
if(ch=='-')f=-1;
}while(!isdigit(ch));
do{x=x*10+ch-'0';
ch=getchar();
}while(isdigit(ch));
return f*x;
}
/*------------------------------------------------------------*/ll n,b,p,a[maxn],sum[32][maxn];
void read_and_parse(){
n=read(),b=read(),p=read();
for(int i=1;
i<=n;
i++)a[i]=read();
for(int i=0;
i<=25;
i++)
for(int j=1;
j<=n;
j++)
sum[i][j]=sum[i][j-1]+(a[j]>>i&1);
}
void solve(){
ll ans=0;
for(int i=1;
i<=n;
i++){
ll lb=i,rb=n,ret=0;
for(int bit=25;
~bit;
bit--){
if(a[i]>>bit&1){
ll l=lb-1,r=rb;
while(l>1;
if(sum[bit][mid]-sum[bit][i-1]==mid-i+1)l=mid;
else r=mid-1;
}
if(l==lb-1)ret+=(1<>1;
if(sum[bit][mid]-sum[bit][i-1]>0)r=mid;
else l=mid+1;
}
if(r==rb+1)continue;
else ret+=(1< 【【洛谷P4144】大河的序列】转载于:https://www.cnblogs.com/wzj-xhjbk/p/10679106.html
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长