CF1070

和 Eric 共同处理的一套题，这里处理奇数题号。

A

Description

给定两个数 $d(1\le d \le 500)$ 和 $s(1\le s\le 5000)$，找出最小数 $n$ 使得 $d\mid n$ 且$n$ 的各个位数之和为 $s$。

Solution

数字很小，直接设状态 $(x,y)$ 表示和为 $x$ 余数 $y$ 是否出现过，记录一下转移的前缀。我们使用 BFS 确保最小。

Code

# include <bits/stdc++.h>

using namespace std;

# define PII pair< int , int >
# define MP make_pair
# define fi first
# define se second

const int D = 500 + 5 , S = 5000 + 5;
int s , d , vis[S][D];
queue< PII > Q;
pair< PII , int > f[S][D];

void Prt(int x , int y)
{
    if(!x && !y) return ;
    Prt(f[x][y].fi.fi , f[x][y].fi.se);
    cout << f[x][y].se;
}

int main()
{
    cin >> d >> s;
    Q.push(MP(0 , 0));
    vis[0][0] = 1;
    while(!Q.empty())
    {
        int x = Q.front().fi , y = Q.front().se;
        Q.pop();
        for(int i = 0; i <= 9; i++)
        {
            int nx = x + i , ny = (y * 10 + i) % d;
            if(nx <= s && !vis[nx][ny])
            {
                vis[nx][ny] = 1;
                Q.push(MP(nx , ny));
                f[nx][ny] = MP(MP(x , y) , i);
            }
        }
    }
    if(!vis[s][0]) cout << -1;
    else Prt(s , 0);
    return 0;
}

一开始从低位到高位扩展，无法处理连续 $0$ 的数量，数位 DP 根本不熟啊。

C

Description

$\text{Buber}$ 是一家致力于浪费投资者的钱的 $\text{Berland}$ 技术公司。最近，$\text{Buber}$ 决定将他的设施转移到云端。公司决定连续$\ n\ $天云端租用$\text{CPU}$。$\text{Buber}$每天都要租用$\ k\ $个$\text{CPU}$。

云端供应商提供 $m$个租用计划，第$i$个计划有如下的特征：

$l_i,r_i$ 表示第 $i$ 个计划从第 $l_i$ 天开始，第$\ r_i\ $天结束。
$c_i$ 表示第$\ i\ $个计划中，每天最多租用$\text{CPU}$个数。
$p_i$ 表示第$\ i\ $个计划中，租用一个$\text{CPU}$一天的花费。

$\text{Buber}$ 可以同时使用多个计划，即他可以在第$\ x\ $天在每个进行中的计划（即$l_i≤x≤r_i$）中租用 $[0,c_i]$个$\text{CPU}$.

现在$\text{Buber}$告诉你正整数$\ k\ $，表示每天所需的$\text{CPU}$个数（如果某一天无论怎么租用都不能租到$\ k\ $个，他也希望租尽量多的$\text{CPU}$）。请你告诉他，他在这$\ n\ $天中最少需要花费多少钱来租用$\text{CPU}$？

JZTXT

CF1070

CF1070

A

Description

Solution

Code

C

Description