【csp-J 2023 T3】小木棍

cjrqwq · 2024-11-05 14:08:03 · 题解

考场思路：奇妙枚举法。最复杂的方法

题面信息：

那最简单的方法就是枚举所有数字个数，然后比较他们的字典序，预处理所有答案。但是太慢了，优化一下。

有一个数字集合 S，S 能够被 S_{1} 替换，当且仅当它们位数相同且字典序更小，或是位数更小的某些数字替换，并且还要 S,S_{1} 所用的小木棍数量相同，就说：

• 选七个 0 没有六个 8 优。
• 选两个 1 没有一个 4 优。
• 选四个 2 没有三个 0 和一个 1 优。
• 选一个 3 没有一个 2 优。
• 选两个 4 没有一个 2 和一个 6 优。
• 选一个 5 没有 2 优。
• 选两个 6 没有一个 6 和一个 0 优。
• 选两个 7 没有一个 6 优。
• 选 8 的数量没有限制。
• 选一个 9 没有 0 优。

如果选了前者，那么可以替换成后者且一定更优，即不可能选择这样的情况。我们证明了最多选择各个数字的个数，它们如下：

所以我们枚举一下，就好啦。

大概要循环 7\times2\times 4 \times 2 \times 2\times 2 \times 10^5 \div 7 = 6.4\times 10 ^ 6 次。带一个比较，常数比较大，但是可以通过。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct NUM{
    int a[7];
}a[100010];

bool operator > (const NUM &A, const NUM &B) {
    int sumA = A.a[0] + A.a[1] + A.a[2] + A.a[3] + A.a[4] + A.a[5] + A.a[6];
    int sumB = B.a[0] + B.a[1] + B.a[2] + B.a[3] + B.a[4] + B.a[5] + B.a[6];

    if(sumA == A.a[0]) return 1;
    if(sumB == B.a[0]) return 0;
    if(sumA != sumB) return sumA > sumB;

    int F0 = 1, F1 = 1;
    for(int i=6;i>0;i--) {
        if(A.a[i]) { F0=i;}
        if(B.a[i]) { F1=i;}
    }
    if(F0 != F1) return F0 > F1;

    sumA = 0, sumB = 0;
    for(int i=0;i<7;i++) {
        sumA += A.a[i], sumB += B.a[i];
        if(sumA != sumB) return sumA < sumB;
    }
    return 0;
}
int main() {
//  freopen("sticks.in","r",stdin);
//  freopen("sticks.out","w",stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin>>n;
    for(int _0=0;_0<=6;_0++) {
        for(int _1=0;_1<=1;_1++) {
            for(int _2=0;_2<=3;_2++) {
                for(int _4=0;_4<=1;_4++) {
                    for(int _6=0;_6<=1;_6++) {
                        for(int _7=0;_7<=1;_7++) {
                            for(int _8=0;_8<=1e5/7;_8++) {
                                int Q = _0*6+_1*2+_2*5+_4*4+_6*6+_7*3+_8*7;
                                if(Q > 1e5) continue;
                                NUM tmp = {_0,_1,_2,_4,_6,_7,_8};
                                if(a[Q] > tmp) a[Q] = tmp;
                            }
                        }
                    }
                }
            }
        }
    }
    while(n--) {
        int x; cin>>x; 
        int sum = 0;
        for(int i=0;i<7;i++) sum += a[x].a[i];
        if(sum == 0 || sum == a[x].a[0]) cout<<-1;
        else {
            int F0 = 1;
            for(int i=6;i>0;i--) {
                if(a[x].a[i]) { F0=i;}
            }
            a[x].a[F0]--;
            if(F0 == 0) cout<<0;
            if(F0 == 1) cout<<1;
            if(F0 == 2) cout<<2;
            if(F0 == 3) cout<<4;
            if(F0 == 4) cout<<6;
            if(F0 == 5) cout<<7;
            if(F0 == 6) cout<<8;
            for(int i=0;i<7;i++) {
                for(int j=1;j<=a[x].a[i];j++) {
                    if(i == 0) cout<<0;
                    if(i == 1) cout<<1;
                    if(i == 2) cout<<2;
                    if(i == 3) cout<<4;
                    if(i == 4) cout<<6;
                    if(i == 5) cout<<7;
                    if(i == 6) cout<<8;
                }
            }
            a[x].a[F0]++;
        }
        cout<<"\n";
    }
    return 0;
}