找国外供应商去哪个网站_微信扫二维码网页历史记录_网站seo优化软件_哈尔滨seo优化

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 ;
}