E题：题意：给定一个数组，你有两个操作，第一个操作是对任意前缀减去一个数，第二个操作是对任意后缀减去一个数。现在希望你用这两个操作将这两个数都变成0，要求操作次数最少，无解情况需要判断。

Sol:考虑两种操作，一种前缀操作，一种后缀操作都是对一整个区间操作，我们应该想到区间加常用的差分！我们记d为差分数组

  • 操作1等价于d[1]−=k和d[i+1]+=kd[1]-=k和d[i+1]+=k

  • 操作2等价于d[n+1]+=k和d[n−i+1]−=kd[n+1]+=k和d[n-i+1]-=k

题目要求我们用最少操作次数完成原数组恰好全部置0，等价于差分数组变0.

问题转化到这逐渐清晰。

  • 考虑d[n+1]是不影响答案的，也就是操作二使用没有代价，对于差分数组中的所有正元素全部可以免费变0

  • 对于为0的不用管

  • 对于负元素，我们需要用操作1将其变0，考虑代价是次数加1以及d[1]减小，如果d[1]不够减，则原问题无解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>=1;i--)a[i]-=a[i-1];
	int sum=0;int cnt=0;
	for(int i=2;i<=n;i++){
		//cerr<<a[i]<<" ";
		if(a[i]<0){sum+=abs(a[i]);}
		if(a[i]!=0)cnt++;
	}
//	cerr<<endl;
	if(sum>a[1])cout<<-1<<endl;
	else if(sum==a[1])cout<<cnt<<endl;
	else cout<<cnt+1<<endl;
}

C题：有n个数每次取出最大的数x，算它的bitsum(x),然后x-=bitsum(x),这样反复k次，求第k次取出的数的bitsum.

Sol:由于k的范围最大到1e9,所以我们很难用优先队列去模拟这个过程，注意到初始的数值域只有1e6,我们考虑维护一个桶统计每个值出现的次数，从大到小遍历，次数累加到转移的数上面，直到k不够减。注意特判k过大的情况，直接输出0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int cal(int x){
	int res=0;
	string s=to_string(x);
	for(int i=0;i<s.size();i++)res+=s[i]-'0';
	return res;
}
//很好的维护手段
void solve(){
	//批量维护值域
	int k;cin>>n>>k;
	for(int i=1;i<=n;i++){int x;cin>>x;a[x]++;}
	for(int i=1e6;i>=0;i--){
		if(a[i]<k){
			k-=a[i];
			a[i-cal(i)]+=a[i];
			
		}
		else {
			cout<<cal(i)<<endl;
			return ;
		}
	}
	cout<<0<<endl;
}