CF 643 div.2 ABDE
一个月没打cf了,难得打一次,结果D被fst了,又掉分cf太卡了不想进,因此以下代码仅供参考,不保证ac
A题 Sequence with Digits
就是给你一个数n,问你执行k-1次操作后变成多少。
操作:找到n中最大的数和最小的数,n加上这个数。
例如$487$,第一次操作:$487+(4\times8)=519$,第二次操作:$519+(1\times9)=528$
这题给的数据是$k<1e16$,一时间无从下手,我先写了BD才回过头来看A,先写了一个暴力模拟的代码,跑了一会发现,k大了之后n就不会变了,因为很快,n中就会出现0,当n中有0时,可以直接break输出
代码:略
B题 Young Explorers
题意:给出n个人的价值,每个人有价值ki,价值为k的人所在的队伍中至少有k个人,问你这些人最多能组成多少队伍。
其实仔细一想,要使队伍数量最大。价值为1的人必然自成一队,价值为2两人一队,以此类推。
然后第一次我用map记录一下每种价值的人数,然后除一下相加。wa了。
然后想到了1 2 2 2 3 3 这组数据,这样的答案应该是3:1
、22
、233
。
因此只要把前面余下的人加到后面即可。
代码:
1 | map<int, int> mp; |
D题 Game With Array
构造题
给出一个$N$和$S$,问你能不能给出一个$N$长度的序列,和为$S$,并且求出一个$K(0\le K\le M)$,使得序列中的某些元素和不为$K$
例如,$N=5$ $K=10$
那么可以给出序列$1$ $1$ $1$ $1$ $6$,$K=5$,这样在序列中找不到和为$5$的子序列。
但是如果$N=5$ $K=9$
不论如何构造序列,都可以找到和为$K(0\le K\le 9)$的子序列
有两种构造方式:
第一种,序列的前$N-1$项都为1,第$N$项只要$\ge N+1$即可,这样是找不到和为$N$的子序列的。构造条件:$S-(N-1)\ge (N-1)+2$
第二种,序列的前$N-1$项都为2,第$N$项只要$\ge 2$即可,这样是找不到和为$1$的子序列的。构造条件:$S-2\times (N-1)\ge 2$
可以发现,经过移项,两种构造方式的构造条件都是一样的
第一种构造方式代码
1 | int main() |
E题 Restorer Distance
给你$n$个用$ai$个相同的砖块垒成的柱子,可以选择三种操作:add
:给一个柱子加一块砖块,代价为aremove
:给一个柱子减一块砖块,代价为rmove
:将一个柱子的砖块移到另一个柱子上,代价为m
问你要使n个柱子高度相同,最少代价是多少
显然,move
操作是可以用a
+r
取代的。
三分高度mid。
关于三分,还是不太理解三分区间,有空再看看
1 | ll p[100010]; |