Educational Codeforces Round 172 (Rated for Div. 2)（A~C）

Educational Codeforces Round 172 (Rated for Div. 2)

A. Greedy Monocarp

思路

考点：贪心+模拟

观察样例，它正好拿取k个金币就停止
那么我们先对数组进行降序排序，定义 $cnt$ 变量为小偷当前的金币数
正序遍历，如果小偷偷取当前的宝箱所获得的金币数小于等于 $k$ ，$cnt$加上这个宝箱的金币数
反之，结束循环

输出 $k-cnt$ 即是答案

code

const int N=1e6+5;
int a[N];
void solve(){
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;++i) cin >> a[i];
	sort(a+1,a+1+n,greater<int>());
	int cnt=0;
	for(int i=1;i<=n;++i){
		if(cnt+a[i]<=k) cnt+=a[i];
		else break;
	}
	cout << k-cnt << endl;
	return ;
}

B. Game with Colored Marbles

思路

考点：阅读理解？？？(cf上面的4，5个翻译软件翻译出的中文就是一坨，后面拿手机拍照翻译看懂了，bushi)

这题需要考虑2种情况：

• 对于只出现过一个颜色的小球，拿走它可以获得2分
• 对于其他颜色的小球，拿走它只能加一分（拿到相同颜色的小球，不在继续加分）

因此，对于Alice来说，先拿独一无二的小球是最优策略
对于其他小球，它至少也能拿到一个

对于Bob来说，它也是先拿独一无二的小球
由于Alice是先手，所以她可以向上取整

code

const int N=1e6+5;
int a[N];
void solve(){
	int n;cin >> n;
	for(int i=1;i<=n;++i) a[i]=0;
	for(int i=1;i<=n;++i){
		int x;cin >> x;
		a[x]++;
	} 
	int sum=0,cnt=0;
	for(int i=1;i<=n;++i){
		if(a[i]==1) sum++;
		else if(a[i]>=2) cnt++;
	}
	cout << (sum+1)/2*2+cnt << endl;
	return ;
}

C. Competitive Fishing

思路

非常有意思的一道思维题，赛时根本看不懂

首先我们明确一点，在一个地方放置挡板，它不会影响挡板左边的分数，只会影响挡板右边的分数
什么意思？先看例子

例如：00111
我们在00后面放置一个挡板，则变为00/111，分数为3
我们在将另一个挡板放在第一个1后面，则变为00/1/11，分数为5
那么这两次有什么联系呢，我们在第一次的基础上在放挡板，中间的1的价值还为1，但是后面2个1的价值变为2
对于中间的1的左边，它们的价值不变，但是对于中间1的右边，它的价值发生了变化，这个变化实际上就是这个数后面1，0个数的差值
1后面的差值为2，所以在原基础的分数上加2，即3+2=5
对于第一次隔板同理，0+3=3

因此，对于这题来说，我们只需要维护后缀数组就行了
当遍历的字符为1时，$a_i=1$,反之$a_i=-1$
由于我们需要的是最少挡板，所以将后缀数组进行排序，每次累加最大的数即可

注：第一个字符的左边不能放置挡板

code

void solve(){
	int n,k;
	cin >> n >> k;
	string s;cin >> s;
	s= " " + s;
	vector<int> v(n+1);
	v[n]=(s[n]=='1'?1:-1);
	for(int i=n-1;i>=2;--i){
		v[i]=(s[i]=='1'?1:-1);
		v[i]+=v[i+1];
	}
	sort(v.begin()+2,v.end(),greater<int>());
	int sum=0;
	for(int i=2;i<=n;++i){
		sum+=v[i];
		if(sum>=k){
			cout << i << endl;
			return ;
		}
	}
	cout << -1 << endl;
	return ;
}