补题 | ARC224D

2026-07-13

题目

There are N cards, numbered 1 through N. 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 k once is equal to the number of digits in the decimal representation of k.

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.

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

T test cases are given; solve each of them.

做法

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

再看题目要求的条件，即最小化：

\sum c_i \cdot digit(i)

其中 c_i= | S_i | ，digit(i) 是 i 十进制的位数。

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

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int T;
    cin>>T;
    while(T--){
        int n,k;
        cin>>n>>k;
        ll cnt=1;
        for(int i=1;i<=n&&cnt<k;i++){
            cnt=min((ll)k,cnt*2);
        }
        if(cnt<k){
            cout<<-1<<"\n";
            continue;
        }
        vector<ll> digit(20);
        for(ll l=1,len=1;l<=k;l*=10,len++){
            ll r=min((ll)k,l*10-1);
            digit[len]=r-l+1;
        }
        vector<ll> C(n+1);
        C[0]=1;
        for(int i=0;i<n;i++){
            __int128 nxt=(__int128)C[i]*(n-i)/(i+1);
            C[i+1]=min<__int128>(nxt,k);
        }
        ll ans=0;
        int cur=8;
        while(cur>=0&&digit[cur]==0) cur--;
        for(int i=0;i<=n;i++){
            ll rem=C[i];
            while(rem>0&&cur>=1){
                ll use=min(rem,digit[cur]);
                ans+=i*cur*use;
                rem-=use;
                digit[cur]-=use;
                if(digit[cur]==0) cur--;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}