You are given a cyclic array A having N numbers. In an AND round, each element of the array A is replaced by the bitwise AND of itself, the previous element, and the next element in the array. All operations take place simultaneously. Can you calculate A after K such AND rounds ?
The first line contains the number of test cases T (T <= 50).
There follow 2T lines, 2 per test case. The first line contains two space seperated integers N (3 <= N <= 20000) and K (1 <= K <= 1000000000). The next line contains N space seperated integers Ai (0 <= Ai <= 1000000000), which are the initial values of the elements in array A.
Output T lines, one per test case. For each test case, output a space seperated list of N integers, specifying the contents of array A after K AND rounds.
Sample Input: 2 3 1 1 2 3 5 100 1 11 111 1111 11111 Sample Output: 0 0 0 1 1 1 1 1
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #include<bits/stdc++.h> 5 #include<algorithm> 6 #define MAX 400005 7 #define lc (id<<1) 8 #define rc ((id<<1)|1) 9 #define mid ((L+R)>>1) 10 using namespace std; 11 int res[(20000<<2)+30]; 12 int a[20010]; 13 void build(int id,int L,int R){ 14 if(L==R){ 15 res[id]=a[L]; 16 return; 17 } 18 build(lc,L,mid); 19 build(rc,mid+1,R); 20 res[id]=res[lc]&res[rc]; 21 } 22 int query(int id,int L,int R,int l,int r){ 23 if(R<=r&&L>=l){ 24 return res[id]; 25 } 26 if(r<=mid) return query(lc,L,mid,l,r); 27 else if(l>mid) return query(rc,mid+1,R,l,r); 28 else return (query(lc,L,mid,l,r)&query(rc,mid+1,R,l,r)); 29 } 30 int main() 31 { 32 int n,m,c,t,i,j,k; 33 cin>>t; 34 while(t--){ 35 cin>>n>>k; 36 cin>>a[1]; 37 int all=a[1]; 38 for(i=2;i<=n;++i) scanf("%d",a+i),all&=a[i]; 39 if(k*2+1>=n) { 40 for(i=1;i<=n;++i) 41 printf("%d%c",all,i==n?‘\n‘:‘ ‘); 42 continue; 43 } 44 build(1,1,n); 45 int l=n-k+1,r=2+k-1; 46 for(i=1;i<=n;++i){ 47 printf("%d%c",l<=r?query(1,1,n,l,r):(query(1,1,n,1,r)&query(1,1,n,l,n)),i==n?‘\n‘:‘ ‘); 48 r++; 49 if(r==n+1) r=1; 50 l++; 51 if(l==n+1) l=1; 52 } 53 } 54 return 0; 55 }
原文：https://www.cnblogs.com/zzqc/p/8835206.html