这里是关于Educational Codeforces Round 96的一些题解
A. Number of Apartments
题目大意
一共$t$组测试数据,对于每一组测试数据,给定$n$,求满足$3 \times x + 5 \times y + 7 \times z = n$的一组解,
数据范围
$1 \leq t \leq 10^3$,$1 \leq n \leq 10^3$
思路
数据范围小,直接暴力即可,当时直接没动脑子三个for循环枚举xyz,直接被hack;稍微多加几个判断条件可以
代码
1 | void solve(){ |
B. Barrels
题目大意
一共$t$组测试数据,对于每一组测试数据,给定$n,k$,表示一共有$n$个数,以及最多操作$k$次,对于每一次操作,我们可以选取任意一个数,将其与另一个数相加,然后将其归零,所得之和替换另一个数;求完成$k$次操作之后$n$个数里面最大值和最小值之差最大为多少。
数据范围
$1 \leq t \leq 10^3$,$1 \leq k \le n \leq 2 \times 10^5$
思路
看完题目直接贪心就行,排个序直接从大往小加起来就行;对于$k$进行$+1$处理可以稍微简化一点
代码
1 |
|
C. Numbers on Whiteboard
题目大意
一共$t$组测试数据,对于每一组测试数据,给定$n$,表示有$1,2,…,n-1,n$一共有$n$个数,,每次拿取两个数,进行相加除以二向上取整再放回,如此操作$n-1$次,最后剩下一个数,求该数最小值,并且给出操作步骤
数据范围
$1 \leq t \leq 10^3$,$2 \leq n \leq 2 \times 10^5$
思路
稍微纸笔思考一下可知是结论题,最小值一定是$2$,步骤一定是先将$n$与$n-2$相加,得到$n-1$,再将得到的$n-1$和原有的$n-1$合并为$n-1$,之后就发现可以一直重复最大数和最大数-2合并的操作,直到只剩下一个2;
特例$n==2$需要特殊考虑
代码
1 | void solve(){ |
D. String Deletion
题目大意
给你一个仅由”0”以及”1”组合而成的字符串,你对其进行如下操作,该操作包括先后两个步骤:
1.在该字符串中随意删除一个字符
2.随后将该字符串中由相同字符组成的前缀删除
求字符串被清空时最小操作次数,注意每次操作是包含上面两个步骤的
思路
首先可以想到,对于任意的由相同字符组成的前缀,都可以用于拆分成两个部分——第一个字符和后面的字符——用于完成一次操作的两个步骤,那么问题就被简化;对于每一个操作一,我们应该从连续相同字符组成的串长度大于1的串删除,而删除的顺序则是当前能进行如此操作的最左边的串
代码
1 | void solve(){ |