xy0v0's Blog

Back

题目#

There are NN cards, numbered 11 through NN. Initially, nothing is written on any of the cards.

You can write zero or more positive integers on each card.

The cost of writing a positive integer kk once is equal to the number of digits in the decimal representation of kk.

Determine whether it is possible to satisfy the following condition. If it is possible, output the minimum total cost required; if it is not possible, output −1-1.

  • For every pair of positive integers (x,y)(x,y) satisfying 1≤x<y≤K1 \leq x < y \leq K, there exists a card containing exactly one of xx and yy.

TT test cases are given; solve each of them.

做法#

将题目条件进行翻译,记记录了数字 ii 的卡片编号集合为 SiS_i ,要满足题意,即要求不存在 x,yx,y 使得 Sx=SyS_x=S_y ,即不存在两个相同的集合。对于大小为 kk 的集合,显然有 (Nk)\binom Nk 种。

再看题目要求的条件,即最小化:

∑ci⋅digit(i)\sum c_i \cdot digit(i)

其中 ci=∣Si∣c_i= | S_i | ,digit(i)digit(i) 是 ii 十进制的位数。

贪心地把 digitdigit 较大的数分配给较小的权重即可。

代码#