假设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 ;
}
标签：882,ch,int,Codeforces,read,maxn,ans,Div,getchar From： https://www.cnblogs.com/Vellichor/p/17536181.html