Description

Input

Output

Sample Input

input 1：

6 3
1 1 1 0 0 0

input 2：

6 3
1 1 0 1 0 0

input 3:

6 3
11 8 2 1 3 9

Sample Output

output 1

1 1

output 2

1 0

output 3

11 1

Data Constraint

Solution

• 首先要仔細觀察題意和思考其內在本質，我們可以發現：

• ①：最大的或值一定是全選的（越多越好，反正不會變小），可以 O(N) 直接求出。

• ②：最大的與值一定是選 K 個（越少越好，多了又不會變大）。

• 那么如何求與值呢？枚舉區間的左端點，在 O(K) 計算？

• 不！這樣的話總時間復雜度可能達到 O(N?K) ，并不可取。

• 于是，我們就可以使用線段樹，維護整個區間的與值。

• 那么我們在枚舉區間的左端點時，就可以 O(logN) 查找區間的與值。

• 最終的時間復雜度就是 O(NlogN) ，可以通過本題。

Code

#include<cstdio> using namespace std; const int N=1e6+1,Mx=2147483647; int f[N<<2],a[N]; int ans1,ans2,num; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void make(int v,int l,int r) {if(l==r){f[v]=a[l];return;}int mid=(l+r)>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);f[v]=f[v<<1]&f[v<<1|1]; } inline void query(int v,int l,int r,int x,int y) {if(l==x && r==y){num&=f[v];return;}int mid=(l+r)>>1;if(y<=mid) query(v<<1,l,mid,x,y); elseif(x>mid) query(v<<1|1,mid+1,r,x,y); else{query(v<<1,l,mid,x,mid);query(v<<1|1,mid+1,r,mid+1,y);} } int main() {int n=read(),k=read();for(int i=1;i<=n;i++) ans1|=a[i]=read();if(n<=100 || k<=10)for(int i=1;i<=n-k+1;i++){int s=Mx;for(int j=i;j<i+k;j++) s&=a[j];if(s>ans2) ans2=s;}else{make(1,1,n);for(int i=1;i<=n-k+1;i++){num=Mx;query(1,1,n,i,i+k-1);if(num>ans2) ans2=num;}}printf("%d %d",ans1,ans2);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5185. 【NOIP2017提高组模拟6.30】tty's sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。