24年CCPC郑州邀请赛VP

24年CCPC郑州邀请赛暨第六届CCPC河南省赛

A. Once In My Life

题意：一个数的数位包含 1~9 并且至少两个数位是 d 的十进制正整数都是幸运数。给出 d 和一个正整数 n，输出一个 k 使得 n*k 是幸运数。

题解：我们需要先构造出乘积。1234567890 满足包含 1~9 的条件，再加上 d 满足幸运数。为了不影响这个数幸运数的性质，我们可以在这个数后面添加几位使得这个数变成 n 的倍数。先在 123456789d 后面添加 n 位数个 0，加上 n-c%n 使这个数变成 n 的倍数，除以 n 即可得到 k。

void solve(){
    ll n,d;cin>>n>>d;
    ll len=to_string(n).size();//求n的位数
    ll c=1234567890ll+d;//构造幸运数
    c=c*pow(10,len);//后面添0
    c+=(n-c%n);//使这个数变成n的倍数
    ll ans=c/n;
    cout<<ans<<"\n";
}

C. 中二病也要打比赛

题意：给定一个序列 A，元素范围在 1~n 内。使用某个映射将序列 A 变为一个单调不降的序列。代价为 \(f(x)≠x\) 的数量。求最小代价。

题解：如果某两个数值相等，则这两数之间所有的数也全部相等。可以仅保留某个数的第一次出现和最后一次出现。问题就转化为每一段取一个数，求 LIS。将每一段中的数降序排列，求出最长严格上升子序列后即得。用数组总长度减去 LIS 长度就是答案。

K. 树上问题

题意：有一颗 n 个节点组成的无根树，每个节点有正整数点权。一个节点是美丽节点的充要条件为以这个节点做根所有节点的点权不小于其父亲节点的一半。有多少个美丽节点？

题解：先以任意结点做根，构成一棵树。对于相连的结点如 u 和 v，以 u 和 v 为根时，只有 u-v 这条边的方向发生变化。因此给 \(ans_u\) 减去 \(v→u\) 的贡献，加上 \(u→v\) 的贡献，就得到了 \(ans_v\)。采用换根 DP。

void dfs1(int u,int fa){
    int sum=0;
    for(int i=0;i<vt[u].size();i++){
        int v=vt[u][i];
        if(v==fa) continue;
        dfs1(v,u);
        sum+=cnt[v]+(a[v]*2<a[u]);
    }
    cnt[u]=sum;
}
void dfs2(int u,int fa){
    for(int i=0;i<vt[u].size();i++){
        int v=vt[u][i];
        if(v==fa) continue;
        ans[v]=ans[u]-(a[v]*2<a[u])+(a[u]*2<a[v]);
        dfs2(v,u);
    }
}

L. Toxel 与 PCPC II

题意：有 n 行代码和 m 行出现 bug，可以选择一个 i，从第一行执行到 i 行，需要 i 秒，并且修复这 i 行内的所有 bug，需要额外时间即 bug 数量的 4 次方。问最少时间修复所有 bug。

题解：简单 DP。状态：\(dp[i]\) 表示修复前 i 个 bug 所需的最少时间。转移方程：\(dp[i]=min_{1≤j≤i}(dp[j]+a_i+(i-j)^4)\)。

时间复杂度为 \(O(m^2)\)，会 TLE。优化：如果我们多运行一次代码，最大花费为 2e5，但是 \(38^4-37^4>2e5\)，这意味着选了 38 个 bug 不如先选一个 bug 再选 37 个 bug。所以只需向下枚举四五十行即可，时间复杂度 \(O(40m)\)。