[YsOI2020]义已失吾亦死

· · 题解

似乎被一些不太正常的做法艹了，所以赛后加了组 HACK 数据

先讲不正经的部分分。

\rm{testdata}\ 1(4pts) a_i=0

答案全为 -1。

\rm{testdata}\ 8\sim9(8pts) p=2

因为 p=2，所以只能把 4 放最后，前面直接贪心。

\rm{testdata}\ 17\sim18(8pts) \sum a_i=n

然而出题人并不会这一档。

\rm{testdata}\ 19\sim20(8pts) a_i=n

发现非常容易搜出结果，直接爆搜。

算法一：

从高位到低位贪心搜索。

期望得分：32。

实际得分：？？（取决于出题人心情）

算法二：

容易发现上述搜索算法在无解时一定会 TLE。

于是限制每一组数据只能跑 200ms，超过则判 -1。

期望得分：44。

实际得分：？？（取决于出题人心情）

算法三：

容易发现，这是一道 dp 题。

下面介绍一种错误的状态设计：

设 dp_{b_1,b_4,b_5,l,q} 表示考虑了由高到低 l 位，剩余 b_1,b_4,b_5 个 a_1,a_4,a_5，当前模意义下为 q 的最大答案（一个高精度数）。

经过状态简化可以变为 dp_{b_1,b_4,b_5}，含义不变。

这么设计状态为什么错误？

因为前面尽可能大，后面不一定能有解。

就算从低位到高位考虑也是不对的，因为后面尽可能大前面不一定大。

期望得分：？？（取决于出题人心情）

实际得分：N/A（出题人是懒狗，没写）。

算法四：

把原本的最优化 dp 转变为可行性 dp。

设 dp_{b_1,b_4,b_5,l,q} 是否存在一个数，使得考虑了由低到高 l 位，剩余 b_1,b_4,b_5 个 a_1,a_4,a_5，当前模意义下为 q。

容易发现这样 dp 求解，过程是 O(n^4p)。

考虑如何获得答案，固定 l=n,q=0，枚举 b_1,b_4,b_5，贪心选取 5,4,1，获得答案。

计算答案是 O(n^3p)。

总复杂度 O(Tn^4p)

根据实现优劣可以拿到不同的分数。

期望得分：20\sim 28。

实际得分：N/A（出题人是懒狗，没写）。

算法五：

简化 dp 状态。

将状态仅仅保留为 dp_{b_1,b_4,b_5,q}。

因为你可以通过 b_1,b_4,b_5 直接求得当前位数 l。

总复杂度 O(Tn^3p)。

期望得分：56。

算法六：

继续简化 dp 状态。

发现 p 很小，可以直接使用 unsigned long long 进行压位。

总复杂度 O(Tn^3)。

期望得分：100。

以下为 std。

然而 std 的 dp 状态是 l,b_1,b_4。 然而 std 的 dp 状态是 l,b_1,b_4。 然而 std 的 dp 状态是 l,b_1,b_4

重要的事情说三遍。

最后求答案时可以进行剪枝，跑得飞快。 std 未剪枝。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
#define ULL unsigned long long
#define MX (234 + 1)
#define pow10 IEE

int n ,p;
int a1 ,a4 ,a5 ,pow10[MX];
ULL dp[MX][MX][MX];
ULL LOOP(ULL x ,int bit){ // 循环左移
    bit = (bit % p + p) % p; 
    return (x << bit) | (x >> (p - bit));
}

struct BIGINT{
    char k[MX];
    int len;
    BIGINT(){memset(k ,0 ,sizeof k); len = 0;}
    void push_back(char c){k[len++] = c;} 
    bool operator <(const BIGINT &B)const{
        if(len != B.len) return len < B.len;
        for(int i = 0 ; i < len ; ++i){
            if(k[i] != B.k[i]) return k[i] < B.k[i];
        }return false;
    }
    void output(){puts(k);}
}Ans ,tmp;

void solve(){
    memset(dp ,0 ,sizeof dp); 
    Ans = BIGINT(); 
    cin >> n >> p >> a1 >> a4 >> a5;
    pow10[0] = 1;
    for(int i = 1 ; i <= n ; ++i){
        pow10[i] = pow10[i - 1] * 10 % p;
    }
    dp[0][0][0] = 1;
    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j <= min(i ,a1) ; ++j){
            for(int s = 0 ; s <= a4 && s + j <= i ; ++s){
                int k = i - j - s; if(k > a5) continue;
                dp[i + 1][j + 1][s] |= LOOP(dp[i][j][s] ,pow10[i] * 1 % p);
                dp[i + 1][j][s + 1] |= LOOP(dp[i][j][s] ,pow10[i] * 4 % p);
                dp[i + 1][j][s] |= LOOP(dp[i][j][s] ,pow10[i] * 5 % p);
            }
        }
    }
    for(int j = 0 ; j <= a1 ; ++j){
        for(int s = 0 ; s <= a4 ; ++s){
            int A5 = n - j - s ,A1 = j ,A4 = s;
            if(A5 < 0 || A5 > a5 || (dp[n][j][s] & 1) == 0 ) continue;
            ULL st = 1;
            tmp = BIGINT();
            for(int t = n ; t ; --t){
                // priority: 5 > 4 > 1
                if(A5 && (LOOP(st ,-pow10[t - 1] * 5) & dp[t - 1][A1][A4])){
                    tmp.push_back('5');
                    st = LOOP(st ,-pow10[t - 1] * 5) & dp[t - 1][A1][A4] ,--A5;
                }else if(A4 && (LOOP(st ,-pow10[t - 1] * 4) & dp[t - 1][A1][A4 - 1])){
                    tmp.push_back('4');
                    st = LOOP(st ,-pow10[t - 1] * 4) & dp[t - 1][A1][--A4];
                }else{
                    tmp.push_back('1');
                    st = LOOP(st ,-pow10[t - 1] * 1) & dp[t - 1][--A1][A4];
                }
            }
            if(Ans < tmp) Ans = tmp;
        }
    }
    if(Ans.len == 0) puts("-1");
    else Ans.output();
}

int main(){
    int T; cin >> T;
    while(T--) solve();
    return 0;
}