526互联

CF882 div2

发布时间 2023-07-07 02:02:36作者: 木易meow

碎碎念

时隔三个月我终于想起了我的博客密码（雾），好吧中间穿插着四级考试和期末周以及搬家balabala好多事情，回家摆了几天之后突然意识到自己已经足足一个月没有像样的写题了，觉得非常羞愧，于是决定洗心革面，重新做人。然后就是一次次的被题目AC哭哭/(ㄒoㄒ)/

开始正文

A

是一个求相邻两项绝对值之和最小的题目，虽然包装上了分成k段，但实际上就是纸老虎

The power of the group of villagers from l to r be defined as f(l,r)
where f(l,r)=|al−al+1|+|al+1−al+2|+…+|ar−1−ar|.
Here |x−y| is the absolute value of x−y. A group with only one villager has a power of 0.

Kars wants to break the villagers into exactly k contiguous subgroups so that the sum of their power is minimized. Formally, he must find k−1 positive integers 1≤r1<r2<…<rk−1<n such that f(1,r1)+f(r1+1,r2)+…+f(rk−1+1,n) is minimised. Help Kars in finding the minimum value of f(1,r1)+f(r1+1,r2)+…+f(rk−1+1,n).

策略就是：在差的绝对值较大的两个数中间分段
于是我选择用一个数组记录每个差的绝对值的值，用sort进行排序
代码如下

点击查看代码 
#include<iostream>
#include<algorithm>
using namespace std;
int a[105];//直接存差！！！
int abs(int x){
	if(x>=0)return x;
	else return 0-x;
} 
int cha(int x,int y){
	return y-x;
}
bool cmp(int x,int y){
	return x>y;
}
int main(){
	int T,n,k,x,y,dt,tot;
	cin>>T;
	while(T--){
		tot=0;
		cin>>n>>k;
		cin>>x;
		for(int i=1;i<n;i++){
			cin>>y;
			dt=cha(x,y);
			a[i]=abs(dt);
			tot+=a[i];
			x=y;
		}
		sort(a+1,a+n,cmp);
		for(int i=1;i<k;i++){
			tot-=a[i]; 
		}
		cout<<tot<<endl;
	}
	return 0;
}

B

让我坐牢的一个题目（骂骂咧咧），看到题目的下一刻我就选择去看C，然后就准备困告（啊位运算我害怕），后来想想来都来了那就做一下吧反正这个点又睡不着
分成多组使按位与值最小

There are n of them with strengths a1,a2,…,an.
Denote (l,r) as the group consisting of the vampires with indices from l to r. Jonathan realizes that the strength of any such group is in its weakest link, that is, the bitwise AND. More formally, the strength level of the group (l,r) is defined asf(l,r)=al&al+1&al+2&…&ar.
Here, & denotes the bitwise AND operation.

Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in exactly one group, and the sum of strengths of the groups is minimized. Among all ways to divide the vampires, he would like to find the way with the maximum number of groups.

Given the strengths of each of the n vampires, find the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.

策略：零与任何值按位与的结果均为零，看能出现多少次零

点击查看代码 
#include<iostream>
#include<cstdio>
using namespace std;
const int inf = 0x3f3f3f3f;
long long a[200005];
int main () {
    long long T,n,sum,ans;
	cin>>T;
    while (T--) {
        cin>>n;ans=0;
        cin>>a[1];
		sum=a[1];
        for(long long i=2;i<=n;i++){
			cin>>a[i];
			sum &= a[i];
		}
        if(sum!=0){
            cout<<1<<endl;
            continue;
        }
		else{
            sum=a[1];
            for(int i=2;i<=n;i++) {
                if(sum==0){
                	ans++;
					sum=a[i];
				}
                else sum&=a[i];
            }
            if(sum==0)ans++;
            printf("%lld\n", ans);
        }
    }
    return 0;
}