前言

传送门 ;

A.

一个时间都可以同时移动,因此只需要考虑最大值即可,因为有四个角所以考虑四个角即可,即考虑四个角的曼哈顿距离

不注意

W

A

WA

WA了两发,是真的菜我

ll n,m,r,c;
void solve(){
	cin>>n>>m>>r>>c;
	ll ans = 0 ;
	
	ans = max(r-1+c-1,n-r+m-c);
	ans = max(ans,n-r+c-1);
	ans = max(ans,r-1+m-c);
	cout<<ans<<endl;
	
	// cout<<max(r-1+c-1,n-r+m-c)<<endl;
}

B.

因为值域很小,所以我们考虑在值域上进行枚举

对于每一次涂色我们总是拿最大的那个即可

int a[N],n;
int maxn,k;

void solve(){
	cin>>n>>k;
	
	for(int i=1;i<=n;i++) cin>>a[i],maxn = max(maxn,a[i]);	
	
	int ans = 0x3f3f3f3f ;
	
	//100 * 1e5
	// int cnt = 0 ;
	
	for(int i=1;i<=maxn;i ++ ){
		int cnt =  0;
		for(int j=1;j<=n;j++){
			if(a[j] == i) continue;
			j+=k-1;
			cnt++;
		}
		ans = min(ans,cnt);
	}

	cout<<ans<<endl;
	
}

C.

利用树状数组维护

f

[

i

]

f[i]

f[i]

然后利用离散化+二分进行加值

然后每一次更新之后我们将

f

f

f更新到树状数组中

const int N = 1e5+10;
int n,a[N],diff[N],len;

ll tr[N],res;
int lowbit(int x){return x&(-x);}

il void add(int x,ll c){
	for(int i=x;i<=len; i+= lowbit(i))
	tr[i] = max(tr[i],c);
}
il ll query(int x){
	ll res = 0 ;
	for(int i=x;i;i-=lowbit(i)) res = max(res,tr[i]);
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		diff[i-1] = a[i];
	}
	
	sort(diff,diff+n);
	len  = unique(diff,diff+n) - diff;
	//去重之后的长度 实际并没有去重只是加到了数组后面
	// for(int i=0;i<len;i++){
		// cout<<diff[i]<<" ";
// 		
	// }
	for(int i=1;i<=n;i++){
		a[i] = lower_bound(diff,diff+len,a[i]) - diff+1;
		ll f = diff[a[i] - 1] + query(a[i]-1);
		res = max(res,f);
		add(a[i],f);
	}
	cout<<res<<endl;
}