假设sum为 omiga abs（a[i] - a[i -1]) 1 <= i <= n
只有设置断点的时候，假设设置在t和t-1之间 the value才会减少abs(a[t]-a[t-1])
所以把差距最大的几个地方分段就行了
#include<bits/stdc++.h> using namespace std ; #define maxn 400100 #define int long long int read(){ int ans = 0 , f = 1 ; char ch = getchar() ; while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; } while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ; return ans * f ; } int t = read() ; int a[maxn] , cha[maxn]; signed main(){ while(t--){ int n = read() , k = read() - 1 , sum = 0 ; for(int i = 1 ; i <= n ; i++){ a[i] = read() ; sum += cha[i] = abs(a[i] - a[i - 1] ); } cha[1] = 0 ; sum -= a[1] ; sort(cha + 1 , cha + 1 + n) ; for(int i = n ; i >= n - k + 1 ; i--) sum -= cha[i] ; printf("%lld\n" , sum) ; } return 0 ; }
贪心 在能and到0并且后面也能and成0的地方就断
#include<bits/stdc++.h> using namespace std ; #define maxn 400100 #define int long long int read(){ int ans = 0 , f = 1 ; char ch = getchar() ; while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; } while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ; return ans * f ; } int t = read() ; int a[maxn] , qian[maxn] , hou[maxn] ; signed main(){ while(t--){ int n = read() ; qian[1] = a[1] = read() ; hou[1] = 0 ; for(int i = 2 ; i <= n ;i++) a[i] = read() , qian[i] = qian[i - 1] & a[i] , hou[i] = 0 ; hou[n] = a[n] ; hou[n + 1] = 0 ; for(int i = n - 1; i >= 1 ; i--){ hou[i] = hou[i + 1] & a[i] ; } if(qian[n] != 0){ printf("1\n") ; continue ; } int cnt = 0 ; bool flag = 0 ; int sum = 0 ; for(int i = 1 ; i <= n ; i++){ if(!flag){ flag = 1 ; sum = a[i] ; } else { sum &= a[i] ; } if(sum == 0){ if(hou[i + 1] == 0){ cnt++ ; flag = 0 ; } } } printf("%lld\n" , cnt) ; } return 0 ; }
模拟之后可以发现其实本质上是找异或之后的最大子段
注意到a最大只有255 所以异或之后也不超过255 利用类似前缀和性质即可
#include<bits/stdc++.h> using namespace std ; #define maxn 400100 #define int long long int read(){ int ans = 0 , f = 1 ; char ch = getchar() ; while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; } while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ; return ans * f ; } int t = read() ; int cnt[500] ; signed main(){ while(t--){ int n = read() ; for(int i = 0 ; i < 256 ; i++) cnt[i] = 0 ; int sum = 0 , ans = 0 ; cnt[0] = 1 ; for(int i = 1 ; i <= n ; i++){ sum ^= read() ; cnt[sum]= 1 ; for(int i = 0 ; i < 256 ; i++) if(cnt[i]) ans = max(ans , sum ^ i) ; } printf("%lld\n" , ans) ; } return 0 ; }
以第二个样例为例模拟一遍
#include<bits/stdc++.h> using namespace std ; #define maxn 300100 #define int long long int read(){ int ans = 0 , f = 1 ; char ch = getchar() ; while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; } while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ; return ans * f ; } #define fi first #define se second int n , m , q ; pair<int,int> ques[maxn] , pi[maxn]; int val[maxn << 2] , a[maxn] , s[maxn] , sum , tag[maxn << 2]; char in[maxn] ; void pushdown(int o){ tag[o << 1]= tag[o << 1 | 1]= tag[o] ; val[o << 1 | 1] = val[o << 1] = tag[o] ; tag[o] = 0 ; return ; } #define lr o << 1 #define rr ((o << 1) | 1) #define mid ((l + r) >> 1) void modify(int o , int l , int r , int ql , int qr , int k){ if(l > qr || r < ql) return ; if(tag[o]) pushdown(o) ; if(l >= ql && r <= qr){ tag[o] = val[o] = k ; return ; } modify(lr , l , mid , ql , qr , k) ; modify(rr , mid + 1 , r , ql , qr , k ) ; return ; } int que(int o , int l , int r , int poss){ if(tag[o]) pushdown(o) ; if(l == r) return val[o] ; if(poss <= mid) return que(lr , l , mid , poss) ; else return que(rr , mid + 1 , r , poss) ; } int c[maxn] ; #define lowbit(x) (x & (-x)) void add(int pos , int x ){ while(pos <= n){ // printf("pos : %lld x : %lld \n" , pos , x) ; c[pos] += x ; pos += lowbit(pos) ; } return ; } int query(int pos){ int suum = 0 ; while(pos){ suum += c[pos] ; pos -= lowbit(pos) ; } return suum ; } vector<int> G[maxn] ; signed main(){ n = read() ; m = read() , q = read() ; scanf("%s" , in + 1) ; for(int i = 1 ; i <= n ; i++) sum += s[i] = in[i] - '0' ; for(int i = 1 ; i <= m ; i++) ques[i] = {read() , read()} ; for(int i = m ; i >= 1 ; i--){ modify(1 , 1 , n , ques[i].fi , ques[i].se , i) ; } for(int i = 1 ; i <= n ; i++){ a[i] = que(1 , 1 , n , i) ; // printf("a[%lld] : %lld \n" , i , a[i]) ; G[a[i]].push_back(i) ; } int num = 0 ; for(int i = 1 ; i <= m ; i++){ if(G[i].size()){ for(int j = 0 ; j < G[i].size() ; j++){ int v = G[i][j] ; a[v] = ++num ; // printf("a[%lld] : %lld \n" , v , a[v]) ; add(num , s[v]) ; } } } // printf("num : %lld \n" , num) ; while(q--){ int x = read() ; if(s[x] == 1){ s[x] = 0 ; sum-- ; if(a[x] != 0){ add(a[x] , -1) ; } } else { s[x] = 1 ; sum++ ; if(a[x] != 0) add(a[x] , 1) ;// printf("yes"); }// printf("%lld\n" , min(sum , num ) - query(min(sum , num)) ) ; } return 0 ; }